Line data Source code
1 : //===- llvm/CodeGen/SelectionDAG.h - InstSelection DAG ----------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file declares the SelectionDAG class, and transitively defines the
11 : // SDNode class and subclasses.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #ifndef LLVM_CODEGEN_SELECTIONDAG_H
16 : #define LLVM_CODEGEN_SELECTIONDAG_H
17 :
18 : #include "llvm/ADT/APFloat.h"
19 : #include "llvm/ADT/APInt.h"
20 : #include "llvm/ADT/ArrayRef.h"
21 : #include "llvm/ADT/DenseMap.h"
22 : #include "llvm/ADT/DenseSet.h"
23 : #include "llvm/ADT/FoldingSet.h"
24 : #include "llvm/ADT/SetVector.h"
25 : #include "llvm/ADT/SmallVector.h"
26 : #include "llvm/ADT/StringMap.h"
27 : #include "llvm/ADT/ilist.h"
28 : #include "llvm/ADT/iterator.h"
29 : #include "llvm/ADT/iterator_range.h"
30 : #include "llvm/Analysis/AliasAnalysis.h"
31 : #include "llvm/Analysis/LegacyDivergenceAnalysis.h"
32 : #include "llvm/CodeGen/DAGCombine.h"
33 : #include "llvm/CodeGen/FunctionLoweringInfo.h"
34 : #include "llvm/CodeGen/ISDOpcodes.h"
35 : #include "llvm/CodeGen/MachineFunction.h"
36 : #include "llvm/CodeGen/MachineMemOperand.h"
37 : #include "llvm/CodeGen/SelectionDAGNodes.h"
38 : #include "llvm/CodeGen/ValueTypes.h"
39 : #include "llvm/IR/DebugLoc.h"
40 : #include "llvm/IR/Instructions.h"
41 : #include "llvm/IR/Metadata.h"
42 : #include "llvm/Support/Allocator.h"
43 : #include "llvm/Support/ArrayRecycler.h"
44 : #include "llvm/Support/AtomicOrdering.h"
45 : #include "llvm/Support/Casting.h"
46 : #include "llvm/Support/CodeGen.h"
47 : #include "llvm/Support/ErrorHandling.h"
48 : #include "llvm/Support/MachineValueType.h"
49 : #include "llvm/Support/RecyclingAllocator.h"
50 : #include <algorithm>
51 : #include <cassert>
52 : #include <cstdint>
53 : #include <functional>
54 : #include <map>
55 : #include <string>
56 : #include <tuple>
57 : #include <utility>
58 : #include <vector>
59 :
60 : namespace llvm {
61 :
62 : class BlockAddress;
63 : class Constant;
64 : class ConstantFP;
65 : class ConstantInt;
66 : class DataLayout;
67 : struct fltSemantics;
68 : class GlobalValue;
69 : struct KnownBits;
70 : class LLVMContext;
71 : class MachineBasicBlock;
72 : class MachineConstantPoolValue;
73 : class MCSymbol;
74 : class OptimizationRemarkEmitter;
75 : class SDDbgValue;
76 : class SDDbgLabel;
77 : class SelectionDAG;
78 : class SelectionDAGTargetInfo;
79 : class TargetLibraryInfo;
80 : class TargetLowering;
81 : class TargetMachine;
82 : class TargetSubtargetInfo;
83 : class Value;
84 :
85 : class SDVTListNode : public FoldingSetNode {
86 : friend struct FoldingSetTrait<SDVTListNode>;
87 :
88 : /// A reference to an Interned FoldingSetNodeID for this node.
89 : /// The Allocator in SelectionDAG holds the data.
90 : /// SDVTList contains all types which are frequently accessed in SelectionDAG.
91 : /// The size of this list is not expected to be big so it won't introduce
92 : /// a memory penalty.
93 : FoldingSetNodeIDRef FastID;
94 : const EVT *VTs;
95 : unsigned int NumVTs;
96 : /// The hash value for SDVTList is fixed, so cache it to avoid
97 : /// hash calculation.
98 : unsigned HashValue;
99 :
100 : public:
101 171614 : SDVTListNode(const FoldingSetNodeIDRef ID, const EVT *VT, unsigned int Num) :
102 171614 : FastID(ID), VTs(VT), NumVTs(Num) {
103 171614 : HashValue = ID.ComputeHash();
104 : }
105 :
106 0 : SDVTList getSDVTList() {
107 0 : SDVTList result = {VTs, NumVTs};
108 0 : return result;
109 : }
110 : };
111 :
112 : /// Specialize FoldingSetTrait for SDVTListNode
113 : /// to avoid computing temp FoldingSetNodeID and hash value.
114 : template<> struct FoldingSetTrait<SDVTListNode> : DefaultFoldingSetTrait<SDVTListNode> {
115 0 : static void Profile(const SDVTListNode &X, FoldingSetNodeID& ID) {
116 0 : ID = X.FastID;
117 0 : }
118 :
119 0 : static bool Equals(const SDVTListNode &X, const FoldingSetNodeID &ID,
120 : unsigned IDHash, FoldingSetNodeID &TempID) {
121 23002443 : if (X.HashValue != IDHash)
122 0 : return false;
123 21780221 : return ID == X.FastID;
124 : }
125 :
126 0 : static unsigned ComputeHash(const SDVTListNode &X, FoldingSetNodeID &TempID) {
127 0 : return X.HashValue;
128 : }
129 : };
130 :
131 : template <> struct ilist_alloc_traits<SDNode> {
132 0 : static void deleteNode(SDNode *) {
133 0 : llvm_unreachable("ilist_traits<SDNode> shouldn't see a deleteNode call!");
134 : }
135 : };
136 :
137 : /// Keeps track of dbg_value information through SDISel. We do
138 : /// not build SDNodes for these so as not to perturb the generated code;
139 : /// instead the info is kept off to the side in this structure. Each SDNode may
140 : /// have one or more associated dbg_value entries. This information is kept in
141 : /// DbgValMap.
142 : /// Byval parameters are handled separately because they don't use alloca's,
143 : /// which busts the normal mechanism. There is good reason for handling all
144 : /// parameters separately: they may not have code generated for them, they
145 : /// should always go at the beginning of the function regardless of other code
146 : /// motion, and debug info for them is potentially useful even if the parameter
147 : /// is unused. Right now only byval parameters are handled separately.
148 : class SDDbgInfo {
149 : BumpPtrAllocator Alloc;
150 : SmallVector<SDDbgValue*, 32> DbgValues;
151 : SmallVector<SDDbgValue*, 32> ByvalParmDbgValues;
152 : SmallVector<SDDbgLabel*, 4> DbgLabels;
153 : using DbgValMapType = DenseMap<const SDNode *, SmallVector<SDDbgValue *, 2>>;
154 : DbgValMapType DbgValMap;
155 :
156 : public:
157 58534 : SDDbgInfo() = default;
158 : SDDbgInfo(const SDDbgInfo &) = delete;
159 : SDDbgInfo &operator=(const SDDbgInfo &) = delete;
160 :
161 104979 : void add(SDDbgValue *V, const SDNode *Node, bool isParameter) {
162 104979 : if (isParameter) {
163 6 : ByvalParmDbgValues.push_back(V);
164 104973 : } else DbgValues.push_back(V);
165 104979 : if (Node)
166 68449 : DbgValMap[Node].push_back(V);
167 104979 : }
168 :
169 : void add(SDDbgLabel *L) {
170 1 : DbgLabels.push_back(L);
171 : }
172 :
173 : /// Invalidate all DbgValues attached to the node and remove
174 : /// it from the Node-to-DbgValues map.
175 : void erase(const SDNode *Node);
176 :
177 : void clear() {
178 1269050 : DbgValMap.clear();
179 : DbgValues.clear();
180 : ByvalParmDbgValues.clear();
181 : DbgLabels.clear();
182 1269050 : Alloc.Reset();
183 : }
184 :
185 104980 : BumpPtrAllocator &getAlloc() { return Alloc; }
186 :
187 : bool empty() const {
188 1269035 : return DbgValues.empty() && ByvalParmDbgValues.empty() && DbgLabels.empty();
189 : }
190 :
191 27333 : ArrayRef<SDDbgValue*> getSDDbgValues(const SDNode *Node) const {
192 27333 : auto I = DbgValMap.find(Node);
193 27333 : if (I != DbgValMap.end())
194 27333 : return I->second;
195 0 : return ArrayRef<SDDbgValue*>();
196 : }
197 :
198 : using DbgIterator = SmallVectorImpl<SDDbgValue*>::iterator;
199 : using DbgLabelIterator = SmallVectorImpl<SDDbgLabel*>::iterator;
200 :
201 : DbgIterator DbgBegin() { return DbgValues.begin(); }
202 : DbgIterator DbgEnd() { return DbgValues.end(); }
203 : DbgIterator ByvalParmDbgBegin() { return ByvalParmDbgValues.begin(); }
204 : DbgIterator ByvalParmDbgEnd() { return ByvalParmDbgValues.end(); }
205 : DbgLabelIterator DbgLabelBegin() { return DbgLabels.begin(); }
206 : DbgLabelIterator DbgLabelEnd() { return DbgLabels.end(); }
207 : };
208 :
209 : void checkForCycles(const SelectionDAG *DAG, bool force = false);
210 :
211 : /// This is used to represent a portion of an LLVM function in a low-level
212 : /// Data Dependence DAG representation suitable for instruction selection.
213 : /// This DAG is constructed as the first step of instruction selection in order
214 : /// to allow implementation of machine specific optimizations
215 : /// and code simplifications.
216 : ///
217 : /// The representation used by the SelectionDAG is a target-independent
218 : /// representation, which has some similarities to the GCC RTL representation,
219 : /// but is significantly more simple, powerful, and is a graph form instead of a
220 : /// linear form.
221 : ///
222 : class SelectionDAG {
223 : const TargetMachine &TM;
224 : const SelectionDAGTargetInfo *TSI = nullptr;
225 : const TargetLowering *TLI = nullptr;
226 : const TargetLibraryInfo *LibInfo = nullptr;
227 : MachineFunction *MF;
228 : Pass *SDAGISelPass = nullptr;
229 : LLVMContext *Context;
230 : CodeGenOpt::Level OptLevel;
231 :
232 : LegacyDivergenceAnalysis * DA = nullptr;
233 : FunctionLoweringInfo * FLI = nullptr;
234 :
235 : /// The function-level optimization remark emitter. Used to emit remarks
236 : /// whenever manipulating the DAG.
237 : OptimizationRemarkEmitter *ORE;
238 :
239 : /// The starting token.
240 : SDNode EntryNode;
241 :
242 : /// The root of the entire DAG.
243 : SDValue Root;
244 :
245 : /// A linked list of nodes in the current DAG.
246 : ilist<SDNode> AllNodes;
247 :
248 : /// The AllocatorType for allocating SDNodes. We use
249 : /// pool allocation with recycling.
250 : using NodeAllocatorType = RecyclingAllocator<BumpPtrAllocator, SDNode,
251 : sizeof(LargestSDNode),
252 : alignof(MostAlignedSDNode)>;
253 :
254 : /// Pool allocation for nodes.
255 : NodeAllocatorType NodeAllocator;
256 :
257 : /// This structure is used to memoize nodes, automatically performing
258 : /// CSE with existing nodes when a duplicate is requested.
259 : FoldingSet<SDNode> CSEMap;
260 :
261 : /// Pool allocation for machine-opcode SDNode operands.
262 : BumpPtrAllocator OperandAllocator;
263 : ArrayRecycler<SDUse> OperandRecycler;
264 :
265 : /// Pool allocation for misc. objects that are created once per SelectionDAG.
266 : BumpPtrAllocator Allocator;
267 :
268 : /// Tracks dbg_value and dbg_label information through SDISel.
269 : SDDbgInfo *DbgInfo;
270 :
271 : uint16_t NextPersistentId = 0;
272 :
273 : public:
274 : /// Clients of various APIs that cause global effects on
275 : /// the DAG can optionally implement this interface. This allows the clients
276 : /// to handle the various sorts of updates that happen.
277 : ///
278 : /// A DAGUpdateListener automatically registers itself with DAG when it is
279 : /// constructed, and removes itself when destroyed in RAII fashion.
280 : struct DAGUpdateListener {
281 : DAGUpdateListener *const Next;
282 : SelectionDAG &DAG;
283 :
284 : explicit DAGUpdateListener(SelectionDAG &D)
285 122316792 : : Next(D.UpdateListeners), DAG(D) {
286 110702940 : DAG.UpdateListeners = this;
287 : }
288 :
289 0 : virtual ~DAGUpdateListener() {
290 : assert(DAG.UpdateListeners == this &&
291 : "DAGUpdateListeners must be destroyed in LIFO order");
292 117828924 : DAG.UpdateListeners = Next;
293 0 : }
294 0 :
295 : /// The node N that was deleted and, if E is not null, an
296 : /// equivalent node E that replaced it.
297 0 : virtual void NodeDeleted(SDNode *N, SDNode *E);
298 0 :
299 0 : /// The node N that was updated.
300 : virtual void NodeUpdated(SDNode *N);
301 : };
302 0 :
303 0 : struct DAGNodeDeletedListener : public DAGUpdateListener {
304 : std::function<void(SDNode *, SDNode *)> Callback;
305 :
306 : DAGNodeDeletedListener(SelectionDAG &DAG,
307 : std::function<void(SDNode *, SDNode *)> Callback)
308 : : DAGUpdateListener(DAG), Callback(std::move(Callback)) {}
309 :
310 : void NodeDeleted(SDNode *N, SDNode *E) override { Callback(N, E); }
311 : };
312 :
313 14152073 : /// When true, additional steps are taken to
314 : /// ensure that getConstant() and similar functions return DAG nodes that
315 : /// have legal types. This is important after type legalization since
316 : /// any illegally typed nodes generated after this point will not experience
317 : /// type legalization.
318 12882968 : bool NewNodesMustHaveLegalTypes = false;
319 :
320 5739573 : private:
321 : /// DAGUpdateListener is a friend so it can manipulate the listener stack.
322 : friend struct DAGUpdateListener;
323 :
324 : /// Linked list of registered DAGUpdateListener instances.
325 : /// This stack is maintained by DAGUpdateListener RAII.
326 : DAGUpdateListener *UpdateListeners = nullptr;
327 :
328 : /// Implementation of setSubgraphColor.
329 : /// Return whether we had to truncate the search.
330 : bool setSubgraphColorHelper(SDNode *N, const char *Color,
331 : DenseSet<SDNode *> &visited,
332 : int level, bool &printed);
333 :
334 : template <typename SDNodeT, typename... ArgTypes>
335 642 : SDNodeT *newSDNode(ArgTypes &&... Args) {
336 : return new (NodeAllocator.template Allocate<SDNodeT>())
337 642 : SDNodeT(std::forward<ArgTypes>(Args)...);
338 : }
339 355 :
340 : /// Build a synthetic SDNodeT with the given args and extract its subclass
341 355 : /// data as an integer (e.g. for use in a folding set).
342 : ///
343 124 : /// The args to this function are the same as the args to SDNodeT's
344 : /// constructor, except the second arg (assumed to be a const DebugLoc&) is
345 29655357 : /// omitted.
346 23001761 : template <typename SDNodeT, typename... ArgTypes>
347 58687619 : static uint16_t getSyntheticNodeSubclassData(unsigned IROrder,
348 : ArgTypes &&... Args) {
349 31 : // The compiler can reduce this expression to a constant iff we pass an
350 0 : // empty DebugLoc. Thankfully, the debug location doesn't have any bearing
351 31 : // on the subclass data.
352 : return SDNodeT(IROrder, DebugLoc(), std::forward<ArgTypes>(Args)...)
353 31 : .getRawSubclassData();
354 0 : }
355 64 :
356 : template <typename SDNodeTy>
357 64 : static uint16_t getSyntheticNodeSubclassData(unsigned Opc, unsigned Order,
358 0 : SDVTList VTs, EVT MemoryVT,
359 37 : MachineMemOperand *MMO) {
360 : return SDNodeTy(Opc, Order, DebugLoc(), VTs, MemoryVT, MMO)
361 37 : .getRawSubclassData();
362 0 : }
363 0 :
364 : void createOperands(SDNode *Node, ArrayRef<SDValue> Vals);
365 0 :
366 0 : void removeOperands(SDNode *Node) {
367 0 : if (!Node->OperandList)
368 : return;
369 0 : OperandRecycler.deallocate(
370 0 : ArrayRecycler<SDUse>::Capacity::get(Node->NumOperands),
371 642 : Node->OperandList);
372 : Node->NumOperands = 0;
373 0 : Node->OperandList = nullptr;
374 0 : }
375 0 : void CreateTopologicalOrder(std::vector<SDNode*>& Order);
376 : public:
377 1284 : explicit SelectionDAG(const TargetMachine &TM, CodeGenOpt::Level);
378 0 : SelectionDAG(const SelectionDAG &) = delete;
379 355 : SelectionDAG &operator=(const SelectionDAG &) = delete;
380 : ~SelectionDAG();
381 0 :
382 0 : /// Prepare this SelectionDAG to process code in the given MachineFunction.
383 0 : void init(MachineFunction &NewMF, OptimizationRemarkEmitter &NewORE,
384 : Pass *PassPtr, const TargetLibraryInfo *LibraryInfo,
385 710 : LegacyDivergenceAnalysis * Divergence);
386 0 :
387 124 : void setFunctionLoweringInfo(FunctionLoweringInfo * FuncInfo) {
388 : FLI = FuncInfo;
389 0 : }
390 0 :
391 0 : /// Clear state and free memory necessary to make this
392 : /// SelectionDAG ready to process a new block.
393 248 : void clear();
394 0 :
395 31 : MachineFunction &getMachineFunction() const { return *MF; }
396 0 : const Pass *getPass() const { return SDAGISelPass; }
397 0 :
398 44321606 : const DataLayout &getDataLayout() const { return MF->getDataLayout(); }
399 0 : const TargetMachine &getTarget() const { return TM; }
400 43484 : const TargetSubtargetInfo &getSubtarget() const { return MF->getSubtarget(); }
401 62 : const TargetLowering &getTargetLoweringInfo() const { return *TLI; }
402 0 : const TargetLibraryInfo &getLibInfo() const { return *LibInfo; }
403 31 : const SelectionDAGTargetInfo &getSelectionDAGInfo() const { return *TSI; }
404 0 : LLVMContext *getContext() const {return Context; }
405 0 : OptimizationRemarkEmitter &getORE() const { return *ORE; }
406 0 :
407 0 : /// Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
408 98636541 : void viewGraph(const std::string &Title);
409 62 : void viewGraph();
410 11065 :
411 64 : #ifndef NDEBUG
412 0 : std::map<const SDNode *, std::string> NodeGraphAttrs;
413 0 : #endif
414 0 :
415 0 : /// Clear all previously defined node graph attributes.
416 : /// Intended to be used from a debugging tool (eg. gdb).
417 128 : void clearGraphAttrs();
418 0 :
419 37 : /// Set graph attributes for a node. (eg. "color=red".)
420 : void setGraphAttrs(const SDNode *N, const char *Attrs);
421 168 :
422 : /// Get graph attributes for a node. (eg. "color=red".)
423 168 : /// Used from getNodeAttributes.
424 : const std::string getGraphAttrs(const SDNode *N) const;
425 537 :
426 : /// Convenience for setting node color attribute.
427 463 : void setGraphColor(const SDNode *N, const char *Color);
428 :
429 374 : /// Convenience for setting subgraph color attribute.
430 : void setSubgraphColor(SDNode *N, const char *Color);
431 374 :
432 : using allnodes_const_iterator = ilist<SDNode>::const_iterator;
433 612 :
434 : allnodes_const_iterator allnodes_begin() const { return AllNodes.begin(); }
435 612 : allnodes_const_iterator allnodes_end() const { return AllNodes.end(); }
436 :
437 310 : using allnodes_iterator = ilist<SDNode>::iterator;
438 :
439 310 : allnodes_iterator allnodes_begin() { return AllNodes.begin(); }
440 : allnodes_iterator allnodes_end() { return AllNodes.end(); }
441 3493052 :
442 : ilist<SDNode>::size_type allnodes_size() const {
443 3493052 : return AllNodes.size();
444 : }
445 3158493 :
446 : iterator_range<allnodes_iterator> allnodes() {
447 3158493 : return make_range(allnodes_begin(), allnodes_end());
448 : }
449 0 : iterator_range<allnodes_const_iterator> allnodes() const {
450 0 : return make_range(allnodes_begin(), allnodes_end());
451 0 : }
452 :
453 0 : /// Return the root tag of the SelectionDAG.
454 215873 : const SDValue &getRoot() const { return Root; }
455 0 :
456 : /// Return the token chain corresponding to the entry of the function.
457 22057289 : SDValue getEntryNode() const {
458 24265327 : return SDValue(const_cast<SDNode *>(&EntryNode), 0);
459 50125749 : }
460 :
461 944472 : /// Set the current root tag of the SelectionDAG.
462 944472 : ///
463 10147336 : const SDValue &setRoot(SDValue N) {
464 5325304 : assert((!N.getNode() || N.getValueType() == MVT::Other) &&
465 0 : "DAG root value is not a chain!");
466 8238969 : if (N.getNode())
467 8238969 : checkForCycles(N.getNode(), this);
468 10422248 : Root = N;
469 8238969 : if (N.getNode())
470 10232959 : checkForCycles(this);
471 8238969 : return Root;
472 6 : }
473 7849137 :
474 0 : #ifndef NDEBUG
475 0 : void VerifyDAGDiverence();
476 7849137 : #endif
477 6560936 :
478 7849137 : /// This iterates over the nodes in the SelectionDAG, folding
479 7849137 : /// certain types of nodes together, or eliminating superfluous nodes. The
480 6560936 : /// Level argument controls whether Combine is allowed to produce nodes and
481 7849137 : /// types that are illegal on the target.
482 0 : void Combine(CombineLevel Level, AliasAnalysis *AA,
483 0 : CodeGenOpt::Level OptLevel);
484 :
485 : /// This transforms the SelectionDAG into a SelectionDAG that
486 : /// only uses types natively supported by the target.
487 : /// Returns "true" if it made any changes.
488 : ///
489 : /// Note that this is an involved process that may invalidate pointers into
490 : /// the graph.
491 : bool LegalizeTypes();
492 :
493 6820903 : /// This transforms the SelectionDAG into a SelectionDAG that is
494 : /// compatible with the target instruction selector, as indicated by the
495 : /// TargetLowering object.
496 : ///
497 : /// Note that this is an involved process that may invalidate pointers into
498 : /// the graph.
499 13641806 : void Legalize();
500 :
501 168 : /// Transforms a SelectionDAG node and any operands to it into a node
502 : /// that is compatible with the target instruction selector, as indicated by
503 : /// the TargetLowering object.
504 : ///
505 : /// \returns true if \c N is a valid, legal node after calling this.
506 : ///
507 336 : /// This essentially runs a single recursive walk of the \c Legalize process
508 : /// over the given node (and its operands). This can be used to incrementally
509 473 : /// legalize the DAG. All of the nodes which are directly replaced,
510 : /// potentially including N, are added to the output parameter \c
511 : /// UpdatedNodes so that the delta to the DAG can be understood by the
512 : /// caller.
513 : ///
514 : /// When this returns false, N has been legalized in a way that make the
515 946 : /// pointer passed in no longer valid. It may have even been deleted from the
516 : /// DAG, and so it shouldn't be used further. When this returns true, the
517 374 : /// N passed in is a legal node, and can be immediately processed as such.
518 : /// This may still have done some work on the DAG, and will still populate
519 : /// UpdatedNodes with any new nodes replacing those originally in the DAG.
520 : bool LegalizeOp(SDNode *N, SmallSetVector<SDNode *, 16> &UpdatedNodes);
521 :
522 : /// This transforms the SelectionDAG into a SelectionDAG
523 748 : /// that only uses vector math operations supported by the target. This is
524 : /// necessary as a separate step from Legalize because unrolling a vector
525 612 : /// operation can introduce illegal types, which requires running
526 : /// LegalizeTypes again.
527 : ///
528 : /// This returns true if it made any changes; in that case, LegalizeTypes
529 : /// is called again before Legalize.
530 16985 : ///
531 1224 : /// Note that this is an involved process that may invalidate pointers into
532 : /// the graph.
533 3502420 : bool LegalizeVectors();
534 :
535 : /// This method deletes all unreachable nodes in the SelectionDAG.
536 : void RemoveDeadNodes();
537 :
538 : /// Remove the specified node from the system. This node must
539 7004840 : /// have no referrers.
540 : void DeleteNode(SDNode *N);
541 3316856 :
542 : /// Return an SDVTList that represents the list of values specified.
543 : SDVTList getVTList(EVT VT);
544 : SDVTList getVTList(EVT VT1, EVT VT2);
545 : SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3);
546 : SDVTList getVTList(EVT VT1, EVT VT2, EVT VT3, EVT VT4);
547 6633712 : SDVTList getVTList(ArrayRef<EVT> VTs);
548 :
549 : //===--------------------------------------------------------------------===//
550 : // Node creation methods.
551 16718 :
552 : /// Create a ConstantSDNode wrapping a constant value.
553 : /// If VT is a vector type, the constant is splatted into a BUILD_VECTOR.
554 : ///
555 16718 : /// If only legal types can be produced, this does the necessary
556 : /// transformations (e.g., if the vector element type is illegal).
557 : /// @{
558 : SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT,
559 : bool isTarget = false, bool isOpaque = false);
560 0 : SDValue getConstant(const APInt &Val, const SDLoc &DL, EVT VT,
561 0 : bool isTarget = false, bool isOpaque = false);
562 0 :
563 17 : SDValue getAllOnesConstant(const SDLoc &DL, EVT VT, bool IsTarget = false,
564 0 : bool IsOpaque = false) {
565 17 : return getConstant(APInt::getAllOnesValue(VT.getScalarSizeInBits()), DL,
566 34 : VT, IsTarget, IsOpaque);
567 0 : }
568 :
569 : SDValue getConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT,
570 : bool isTarget = false, bool isOpaque = false);
571 : SDValue getIntPtrConstant(uint64_t Val, const SDLoc &DL,
572 : bool isTarget = false);
573 7454 : SDValue getTargetConstant(uint64_t Val, const SDLoc &DL, EVT VT,
574 : bool isOpaque = false) {
575 11199054 : return getConstant(Val, DL, VT, true, isOpaque);
576 14908 : }
577 : SDValue getTargetConstant(const APInt &Val, const SDLoc &DL, EVT VT,
578 : bool isOpaque = false) {
579 210448 : return getConstant(Val, DL, VT, true, isOpaque);
580 : }
581 : SDValue getTargetConstant(const ConstantInt &Val, const SDLoc &DL, EVT VT,
582 : bool isOpaque = false) {
583 433 : return getConstant(Val, DL, VT, true, isOpaque);
584 : }
585 2604151 :
586 : /// Create a true or false constant of type \p VT using the target's
587 : /// BooleanContent for type \p OpVT.
588 : SDValue getBoolConstant(bool V, const SDLoc &DL, EVT VT, EVT OpVT);
589 0 : /// @}
590 :
591 : /// Create a ConstantFPSDNode wrapping a constant value.
592 15592668 : /// If VT is a vector type, the constant is splatted into a BUILD_VECTOR.
593 673306 : ///
594 405299 : /// If only legal types can be produced, this does the necessary
595 0 : /// transformations (e.g., if the vector element type is illegal).
596 : /// The forms that take a double should only be used for simple constants
597 : /// that can be exactly represented in VT. No checks are made.
598 0 : /// @{
599 : SDValue getConstantFP(double Val, const SDLoc &DL, EVT VT,
600 : bool isTarget = false);
601 : SDValue getConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT,
602 : bool isTarget = false);
603 : SDValue getConstantFP(const ConstantFP &V, const SDLoc &DL, EVT VT,
604 : bool isTarget = false);
605 : SDValue getTargetConstantFP(double Val, const SDLoc &DL, EVT VT) {
606 : return getConstantFP(Val, DL, VT, true);
607 : }
608 : SDValue getTargetConstantFP(const APFloat &Val, const SDLoc &DL, EVT VT) {
609 10 : return getConstantFP(Val, DL, VT, true);
610 : }
611 : SDValue getTargetConstantFP(const ConstantFP &Val, const SDLoc &DL, EVT VT) {
612 : return getConstantFP(Val, DL, VT, true);
613 : }
614 : /// @}
615 :
616 : SDValue getGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT,
617 : int64_t offset = 0, bool isTargetGA = false,
618 : unsigned char TargetFlags = 0);
619 : SDValue getTargetGlobalAddress(const GlobalValue *GV, const SDLoc &DL, EVT VT,
620 : int64_t offset = 0,
621 : unsigned char TargetFlags = 0) {
622 693469 : return getGlobalAddress(GV, DL, VT, offset, true, TargetFlags);
623 : }
624 : SDValue getFrameIndex(int FI, EVT VT, bool isTarget = false);
625 : SDValue getTargetFrameIndex(int FI, EVT VT) {
626 4020200 : return getFrameIndex(FI, VT, true);
627 : }
628 : SDValue getJumpTable(int JTI, EVT VT, bool isTarget = false,
629 : unsigned char TargetFlags = 0);
630 : SDValue getTargetJumpTable(int JTI, EVT VT, unsigned char TargetFlags = 0) {
631 3261 : return getJumpTable(JTI, VT, true, TargetFlags);
632 : }
633 : SDValue getConstantPool(const Constant *C, EVT VT,
634 : unsigned Align = 0, int Offs = 0, bool isT=false,
635 10230 : unsigned char TargetFlags = 0);
636 : SDValue getTargetConstantPool(const Constant *C, EVT VT,
637 10230 : unsigned Align = 0, int Offset = 0,
638 20460 : unsigned char TargetFlags = 0) {
639 33314 : return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
640 : }
641 : SDValue getConstantPool(MachineConstantPoolValue *C, EVT VT,
642 : unsigned Align = 0, int Offs = 0, bool isT=false,
643 : unsigned char TargetFlags = 0);
644 : SDValue getTargetConstantPool(MachineConstantPoolValue *C,
645 : EVT VT, unsigned Align = 0,
646 : int Offset = 0, unsigned char TargetFlags=0) {
647 107751 : return getConstantPool(C, VT, Align, Offset, true, TargetFlags);
648 6279867 : }
649 : SDValue getTargetIndex(int Index, EVT VT, int64_t Offset = 0,
650 : unsigned char TargetFlags = 0);
651 : // When generating a branch to a BB, we don't in general know enough
652 155 : // to provide debug info for the BB at that time, so keep this one around.
653 : SDValue getBasicBlock(MachineBasicBlock *MBB);
654 : SDValue getBasicBlock(MachineBasicBlock *MBB, SDLoc dl);
655 : SDValue getExternalSymbol(const char *Sym, EVT VT);
656 : SDValue getExternalSymbol(const char *Sym, const SDLoc &dl, EVT VT);
657 5689938 : SDValue getTargetExternalSymbol(const char *Sym, EVT VT,
658 : unsigned char TargetFlags = 0);
659 : SDValue getMCSymbol(MCSymbol *Sym, EVT VT);
660 5689938 :
661 5689938 : SDValue getValueType(EVT);
662 5689938 : SDValue getRegister(unsigned Reg, EVT VT);
663 5689938 : SDValue getRegisterMask(const uint32_t *RegMask);
664 5689938 : SDValue getEHLabel(const SDLoc &dl, SDValue Root, MCSymbol *Label);
665 5689938 : SDValue getLabelNode(unsigned Opcode, const SDLoc &dl, SDValue Root,
666 : MCSymbol *Label);
667 : SDValue getBlockAddress(const BlockAddress *BA, EVT VT,
668 : int64_t Offset = 0, bool isTarget = false,
669 : unsigned char TargetFlags = 0);
670 : SDValue getTargetBlockAddress(const BlockAddress *BA, EVT VT,
671 : int64_t Offset = 0,
672 : unsigned char TargetFlags = 0) {
673 157 : return getBlockAddress(BA, VT, Offset, true, TargetFlags);
674 : }
675 :
676 1176437 : SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg,
677 : SDValue N) {
678 : return getNode(ISD::CopyToReg, dl, MVT::Other, Chain,
679 2352874 : getRegister(Reg, N.getValueType()), N);
680 : }
681 :
682 : // This version of the getCopyToReg method takes an extra operand, which
683 : // indicates that there is potentially an incoming glue value (if Glue is not
684 : // null) and that there should be a glue result.
685 218041 : SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg, SDValue N,
686 7175 : SDValue Glue) {
687 218041 : SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
688 436082 : SDValue Ops[] = { Chain, getRegister(Reg, N.getValueType()), N, Glue };
689 14350 : return getNode(ISD::CopyToReg, dl, VTs,
690 396379 : makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
691 : }
692 :
693 : // Similar to last getCopyToReg() except parameter Reg is a SDValue
694 1568778 : SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, SDValue Reg, SDValue N,
695 127110 : SDValue Glue) {
696 2492 : SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
697 129602 : SDValue Ops[] = { Chain, Reg, N, Glue };
698 254220 : return getNode(ISD::CopyToReg, dl, VTs,
699 4832 : makeArrayRef(Ops, Glue.getNode() ? 4 : 3));
700 254124 : }
701 :
702 1454174 : SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT) {
703 1457259 : SDVTList VTs = getVTList(VT, MVT::Other);
704 1454174 : SDValue Ops[] = { Chain, getRegister(Reg, VT) };
705 1454174 : return getNode(ISD::CopyFromReg, dl, VTs, Ops);
706 : }
707 :
708 : // This version of the getCopyFromReg method takes an extra operand, which
709 : // indicates that there is potentially an incoming glue value (if Glue is not
710 : // null) and that there should be a glue result.
711 62232 : SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, unsigned Reg, EVT VT,
712 133477 : SDValue Glue) {
713 164759 : SDVTList VTs = getVTList(VT, MVT::Other, MVT::Glue);
714 164759 : SDValue Ops[] = { Chain, getRegister(Reg, VT), Glue };
715 133477 : return getNode(ISD::CopyFromReg, dl, VTs,
716 31282 : makeArrayRef(Ops, Glue.getNode() ? 3 : 2));
717 : }
718 :
719 : SDValue getCondCode(ISD::CondCode Cond);
720 :
721 : /// Return an ISD::VECTOR_SHUFFLE node. The number of elements in VT,
722 : /// which must be a vector type, must match the number of mask elements
723 : /// NumElts. An integer mask element equal to -1 is treated as undefined.
724 : SDValue getVectorShuffle(EVT VT, const SDLoc &dl, SDValue N1, SDValue N2,
725 : ArrayRef<int> Mask);
726 :
727 : /// Return an ISD::BUILD_VECTOR node. The number of elements in VT,
728 : /// which must be a vector type, must match the number of operands in Ops.
729 : /// The operands must have the same type as (or, for integers, a type wider
730 : /// than) VT's element type.
731 116290 : SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDValue> Ops) {
732 : // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
733 116290 : return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
734 : }
735 :
736 : /// Return an ISD::BUILD_VECTOR node. The number of elements in VT,
737 : /// which must be a vector type, must match the number of operands in Ops.
738 : /// The operands must have the same type as (or, for integers, a type wider
739 : /// than) VT's element type.
740 : SDValue getBuildVector(EVT VT, const SDLoc &DL, ArrayRef<SDUse> Ops) {
741 245839 : // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
742 : return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
743 245839 : }
744 :
745 107 : /// Return a splat ISD::BUILD_VECTOR node, consisting of Op splatted to all
746 : /// elements. VT must be a vector type. Op's type must be the same as (or,
747 : /// for integers, a type wider than) VT's element type.
748 405791 : SDValue getSplatBuildVector(EVT VT, const SDLoc &DL, SDValue Op) {
749 : // VerifySDNode (via InsertNode) checks BUILD_VECTOR later.
750 810478 : if (Op.getOpcode() == ISD::UNDEF) {
751 1104 : assert((VT.getVectorElementType() == Op.getValueType() ||
752 1754 : (VT.isInteger() &&
753 : VT.getVectorElementType().bitsLE(Op.getValueType()))) &&
754 : "A splatted value must have a width equal or (for integers) "
755 : "greater than the vector element type!");
756 0 : return getNode(ISD::UNDEF, SDLoc(), VT);
757 2131425 : }
758 :
759 2536664 : SmallVector<SDValue, 16> Ops(VT.getVectorNumElements(), Op);
760 4668089 : return getNode(ISD::BUILD_VECTOR, DL, VT, Ops);
761 : }
762 3173443 :
763 : /// Returns an ISD::VECTOR_SHUFFLE node semantically equivalent to
764 : /// the shuffle node in input but with swapped operands.
765 : ///
766 : /// Example: shuffle A, B, <0,5,2,7> -> shuffle B, A, <4,1,6,3>
767 : SDValue getCommutedVectorShuffle(const ShuffleVectorSDNode &SV);
768 :
769 44086 : /// Convert Op, which must be of float type, to the
770 : /// float type VT, by either extending or rounding (by truncation).
771 : SDValue getFPExtendOrRound(SDValue Op, const SDLoc &DL, EVT VT);
772 :
773 : /// Convert Op, which must be of integer type, to the
774 226574 : /// integer type VT, by either any-extending or truncating it.
775 226574 : SDValue getAnyExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
776 226574 :
777 226574 : /// Convert Op, which must be of integer type, to the
778 : /// integer type VT, by either sign-extending or truncating it.
779 : SDValue getSExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
780 :
781 : /// Convert Op, which must be of integer type, to the
782 : /// integer type VT, by either zero-extending or truncating it.
783 396792 : SDValue getZExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT);
784 :
785 396792 : /// Return the expression required to zero extend the Op
786 396792 : /// value assuming it was the smaller SrcTy value.
787 : SDValue getZeroExtendInReg(SDValue Op, const SDLoc &DL, EVT VT);
788 396792 :
789 : /// Return an operation which will any-extend the low lanes of the operand
790 : /// into the specified vector type. For example,
791 : /// this can convert a v16i8 into a v4i32 by any-extending the low four
792 : /// lanes of the operand from i8 to i32.
793 : SDValue getAnyExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT);
794 :
795 : /// Return an operation which will sign extend the low lanes of the operand
796 : /// into the specified vector type. For example,
797 : /// this can convert a v16i8 into a v4i32 by sign extending the low four
798 : /// lanes of the operand from i8 to i32.
799 : SDValue getSignExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT);
800 :
801 : /// Return an operation which will zero extend the low lanes of the operand
802 : /// into the specified vector type. For example,
803 8030 : /// this can convert a v16i8 into a v4i32 by zero extending the low four
804 : /// lanes of the operand from i8 to i32.
805 8030 : SDValue getZeroExtendVectorInReg(SDValue Op, const SDLoc &DL, EVT VT);
806 :
807 : /// Convert Op, which must be of integer type, to the integer type VT,
808 : /// by using an extension appropriate for the target's
809 : /// BooleanContent for type OpVT or truncating it.
810 : SDValue getBoolExtOrTrunc(SDValue Op, const SDLoc &SL, EVT VT, EVT OpVT);
811 :
812 : /// Create a bitwise NOT operation as (XOR Val, -1).
813 : SDValue getNOT(const SDLoc &DL, SDValue Val, EVT VT);
814 2426 :
815 : /// Create a logical NOT operation as (XOR Val, BooleanOne).
816 : SDValue getLogicalNOT(const SDLoc &DL, SDValue Val, EVT VT);
817 :
818 : /// Create an add instruction with appropriate flags when used for
819 : /// addressing some offset of an object. i.e. if a load is split into multiple
820 : /// components, create an add nuw from the base pointer to the offset.
821 203296 : SDValue getObjectPtrOffset(const SDLoc &SL, SDValue Op, int64_t Offset) {
822 203296 : EVT VT = Op.getValueType();
823 203296 : return getObjectPtrOffset(SL, Op, getConstant(Offset, SL, VT));
824 : }
825 :
826 203384 : SDValue getObjectPtrOffset(const SDLoc &SL, SDValue Op, SDValue Offset) {
827 406768 : EVT VT = Op.getValueType();
828 :
829 : // The object itself can't wrap around the address space, so it shouldn't be
830 : // possible for the adds of the offsets to the split parts to overflow.
831 : SDNodeFlags Flags;
832 : Flags.setNoUnsignedWrap(true);
833 203384 : return getNode(ISD::ADD, SL, VT, Op, Offset, Flags);
834 : }
835 :
836 : /// Return a new CALLSEQ_START node, that starts new call frame, in which
837 : /// InSize bytes are set up inside CALLSEQ_START..CALLSEQ_END sequence and
838 : /// OutSize specifies part of the frame set up prior to the sequence.
839 16085 : SDValue getCALLSEQ_START(SDValue Chain, uint64_t InSize, uint64_t OutSize,
840 : const SDLoc &DL) {
841 16085 : SDVTList VTs = getVTList(MVT::Other, MVT::Glue);
842 : SDValue Ops[] = { Chain,
843 16085 : getIntPtrConstant(InSize, DL, true),
844 16085 : getIntPtrConstant(OutSize, DL, true) };
845 16085 : return getNode(ISD::CALLSEQ_START, DL, VTs, Ops);
846 : }
847 :
848 : /// Return a new CALLSEQ_END node, which always must have a
849 158 : /// glue result (to ensure it's not CSE'd).
850 : /// CALLSEQ_END does not have a useful SDLoc.
851 999537 : SDValue getCALLSEQ_END(SDValue Chain, SDValue Op1, SDValue Op2,
852 : SDValue InGlue, const SDLoc &DL) {
853 999537 : SDVTList NodeTys = getVTList(MVT::Other, MVT::Glue);
854 158 : SmallVector<SDValue, 4> Ops;
855 999537 : Ops.push_back(Chain);
856 999379 : Ops.push_back(Op1);
857 999379 : Ops.push_back(Op2);
858 999379 : if (InGlue.getNode())
859 999344 : Ops.push_back(InGlue);
860 999379 : return getNode(ISD::CALLSEQ_END, DL, NodeTys, Ops);
861 158 : }
862 :
863 158 : /// Return true if the result of this operation is always undefined.
864 : bool isUndef(unsigned Opcode, ArrayRef<SDValue> Ops);
865 158 :
866 158 : /// Return an UNDEF node. UNDEF does not have a useful SDLoc.
867 48259 : SDValue getUNDEF(EVT VT) {
868 48259 : return getNode(ISD::UNDEF, SDLoc(), VT);
869 0 : }
870 158 :
871 : /// Return a GLOBAL_OFFSET_TABLE node. This does not have a useful SDLoc.
872 28 : SDValue getGLOBAL_OFFSET_TABLE(EVT VT) {
873 28 : return getNode(ISD::GLOBAL_OFFSET_TABLE, SDLoc(), VT);
874 : }
875 :
876 : /// Gets or creates the specified node.
877 318756 : ///
878 318756 : SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
879 : ArrayRef<SDUse> Ops);
880 : SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT,
881 : ArrayRef<SDValue> Ops, const SDNodeFlags Flags = SDNodeFlags());
882 : SDValue getNode(unsigned Opcode, const SDLoc &DL, ArrayRef<EVT> ResultTys,
883 : ArrayRef<SDValue> Ops);
884 : SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList,
885 : ArrayRef<SDValue> Ops);
886 :
887 : // Specialize based on number of operands.
888 : SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT);
889 : SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue Operand,
890 : const SDNodeFlags Flags = SDNodeFlags());
891 : SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
892 : SDValue N2, const SDNodeFlags Flags = SDNodeFlags());
893 : SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
894 : SDValue N2, SDValue N3,
895 : const SDNodeFlags Flags = SDNodeFlags());
896 : SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
897 : SDValue N2, SDValue N3, SDValue N4);
898 : SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, SDValue N1,
899 : SDValue N2, SDValue N3, SDValue N4, SDValue N5);
900 :
901 : // Specialize again based on number of operands for nodes with a VTList
902 : // rather than a single VT.
903 : SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList);
904 : SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N);
905 : SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
906 : SDValue N2);
907 : SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
908 : SDValue N2, SDValue N3);
909 : SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
910 : SDValue N2, SDValue N3, SDValue N4);
911 983678 : SDValue getNode(unsigned Opcode, const SDLoc &DL, SDVTList VTList, SDValue N1,
912 : SDValue N2, SDValue N3, SDValue N4, SDValue N5);
913 983678 :
914 : /// Compute a TokenFactor to force all the incoming stack arguments to be
915 983678 : /// loaded from the stack. This is used in tail call lowering to protect
916 983678 : /// stack arguments from being clobbered.
917 983678 : SDValue getStackArgumentTokenFactor(SDValue Chain);
918 :
919 : SDValue getMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
920 : SDValue Size, unsigned Align, bool isVol, bool AlwaysInline,
921 : bool isTailCall, MachinePointerInfo DstPtrInfo,
922 : MachinePointerInfo SrcPtrInfo);
923 330 :
924 : SDValue getMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
925 330 : SDValue Size, unsigned Align, bool isVol, bool isTailCall,
926 : MachinePointerInfo DstPtrInfo,
927 330 : MachinePointerInfo SrcPtrInfo);
928 330 :
929 330 : SDValue getMemset(SDValue Chain, const SDLoc &dl, SDValue Dst, SDValue Src,
930 330 : SDValue Size, unsigned Align, bool isVol, bool isTailCall,
931 0 : MachinePointerInfo DstPtrInfo);
932 330 :
933 : SDValue getAtomicMemcpy(SDValue Chain, const SDLoc &dl, SDValue Dst,
934 : unsigned DstAlign, SDValue Src, unsigned SrcAlign,
935 : SDValue Size, Type *SizeTy, unsigned ElemSz,
936 : bool isTailCall, MachinePointerInfo DstPtrInfo,
937 : MachinePointerInfo SrcPtrInfo);
938 :
939 120145 : SDValue getAtomicMemmove(SDValue Chain, const SDLoc &dl, SDValue Dst,
940 120145 : unsigned DstAlign, SDValue Src, unsigned SrcAlign,
941 : SDValue Size, Type *SizeTy, unsigned ElemSz,
942 0 : bool isTailCall, MachinePointerInfo DstPtrInfo,
943 : MachinePointerInfo SrcPtrInfo);
944 0 :
945 : SDValue getAtomicMemset(SDValue Chain, const SDLoc &dl, SDValue Dst,
946 : unsigned DstAlign, SDValue Value, SDValue Size,
947 : Type *SizeTy, unsigned ElemSz, bool isTailCall,
948 : MachinePointerInfo DstPtrInfo);
949 :
950 0 : /// Helper function to make it easier to build SetCC's if you just
951 : /// have an ISD::CondCode instead of an SDValue.
952 : ///
953 112888 : SDValue getSetCC(const SDLoc &DL, EVT VT, SDValue LHS, SDValue RHS,
954 0 : ISD::CondCode Cond) {
955 : assert(LHS.getValueType().isVector() == RHS.getValueType().isVector() &&
956 : "Cannot compare scalars to vectors");
957 : assert(LHS.getValueType().isVector() == VT.isVector() &&
958 : "Cannot compare scalars to vectors");
959 : assert(Cond != ISD::SETCC_INVALID &&
960 : "Cannot create a setCC of an invalid node.");
961 112888 : return getNode(ISD::SETCC, DL, VT, LHS, RHS, getCondCode(Cond));
962 : }
963 117078 :
964 : /// Helper function to make it easier to build Select's if you just
965 : /// have operands and don't want to check for vector.
966 4705 : SDValue getSelect(const SDLoc &DL, EVT VT, SDValue Cond, SDValue LHS,
967 : SDValue RHS) {
968 : assert(LHS.getValueType() == RHS.getValueType() &&
969 : "Cannot use select on differing types");
970 : assert(VT.isVector() == LHS.getValueType().isVector() &&
971 117078 : "Cannot mix vectors and scalars");
972 9410 : return getNode(Cond.getValueType().isVector() ? ISD::VSELECT : ISD::SELECT, DL, VT,
973 9181 : Cond, LHS, RHS);
974 : }
975 :
976 12438 : /// Helper function to make it easier to build SelectCC's if you
977 : /// just have an ISD::CondCode instead of an SDValue.
978 : ///
979 1932 : SDValue getSelectCC(const SDLoc &DL, SDValue LHS, SDValue RHS, SDValue True,
980 : SDValue False, ISD::CondCode Cond) {
981 : return getNode(ISD::SELECT_CC, DL, True.getValueType(),
982 26808 : LHS, RHS, True, False, getCondCode(Cond));
983 23741 : }
984 :
985 : /// VAArg produces a result and token chain, and takes a pointer
986 : /// and a source value as input.
987 : SDValue getVAArg(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
988 : SDValue SV, unsigned Align);
989 1929 :
990 : /// Gets a node for an atomic cmpxchg op. There are two
991 : /// valid Opcodes. ISD::ATOMIC_CMO_SWAP produces the value loaded and a
992 1929 : /// chain result. ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS produces the value loaded,
993 : /// a success flag (initially i1), and a chain.
994 : SDValue getAtomicCmpSwap(unsigned Opcode, const SDLoc &dl, EVT MemVT,
995 : SDVTList VTs, SDValue Chain, SDValue Ptr,
996 : SDValue Cmp, SDValue Swp, MachinePointerInfo PtrInfo,
997 : unsigned Alignment, AtomicOrdering SuccessOrdering,
998 : AtomicOrdering FailureOrdering,
999 : SyncScope::ID SSID);
1000 : SDValue getAtomicCmpSwap(unsigned Opcode, const SDLoc &dl, EVT MemVT,
1001 : SDVTList VTs, SDValue Chain, SDValue Ptr,
1002 : SDValue Cmp, SDValue Swp, MachineMemOperand *MMO);
1003 :
1004 : /// Gets a node for an atomic op, produces result (if relevant)
1005 : /// and chain and takes 2 operands.
1006 : SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, SDValue Chain,
1007 : SDValue Ptr, SDValue Val, const Value *PtrVal,
1008 : unsigned Alignment, AtomicOrdering Ordering,
1009 : SyncScope::ID SSID);
1010 : SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, SDValue Chain,
1011 : SDValue Ptr, SDValue Val, MachineMemOperand *MMO);
1012 :
1013 : /// Gets a node for an atomic op, produces result and chain and
1014 : /// takes 1 operand.
1015 : SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT, EVT VT,
1016 : SDValue Chain, SDValue Ptr, MachineMemOperand *MMO);
1017 :
1018 : /// Gets a node for an atomic op, produces result and chain and takes N
1019 : /// operands.
1020 : SDValue getAtomic(unsigned Opcode, const SDLoc &dl, EVT MemVT,
1021 : SDVTList VTList, ArrayRef<SDValue> Ops,
1022 : MachineMemOperand *MMO);
1023 :
1024 : /// Creates a MemIntrinsicNode that may produce a
1025 4352 : /// result and takes a list of operands. Opcode may be INTRINSIC_VOID,
1026 : /// INTRINSIC_W_CHAIN, or a target-specific opcode with a value not
1027 : /// less than FIRST_TARGET_MEMORY_OPCODE.
1028 : SDValue getMemIntrinsicNode(
1029 : unsigned Opcode, const SDLoc &dl, SDVTList VTList,
1030 : ArrayRef<SDValue> Ops, EVT MemVT,
1031 : MachinePointerInfo PtrInfo,
1032 : unsigned Align = 0,
1033 4352 : MachineMemOperand::Flags Flags
1034 : = MachineMemOperand::MOLoad | MachineMemOperand::MOStore,
1035 : unsigned Size = 0);
1036 :
1037 : SDValue getMemIntrinsicNode(unsigned Opcode, const SDLoc &dl, SDVTList VTList,
1038 2869 : ArrayRef<SDValue> Ops, EVT MemVT,
1039 : MachineMemOperand *MMO);
1040 :
1041 : /// Create a MERGE_VALUES node from the given operands.
1042 : SDValue getMergeValues(ArrayRef<SDValue> Ops, const SDLoc &dl);
1043 :
1044 5738 : /// Loads are not normal binary operators: their result type is not
1045 2899 : /// determined by their operands, and they produce a value AND a token chain.
1046 : ///
1047 : /// This function will set the MOLoad flag on MMOFlags, but you can set it if
1048 : /// you want. The MOStore flag must not be set.
1049 : SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
1050 : MachinePointerInfo PtrInfo, unsigned Alignment = 0,
1051 45 : MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1052 : const AAMDNodes &AAInfo = AAMDNodes(),
1053 : const MDNode *Ranges = nullptr);
1054 45 : SDValue getLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
1055 : MachineMemOperand *MMO);
1056 : SDValue
1057 : getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT, SDValue Chain,
1058 : SDValue Ptr, MachinePointerInfo PtrInfo, EVT MemVT,
1059 : unsigned Alignment = 0,
1060 : MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1061 6796354 : const AAMDNodes &AAInfo = AAMDNodes());
1062 6796354 : SDValue getExtLoad(ISD::LoadExtType ExtType, const SDLoc &dl, EVT VT,
1063 : SDValue Chain, SDValue Ptr, EVT MemVT,
1064 : MachineMemOperand *MMO);
1065 : SDValue getIndexedLoad(SDValue OrigLoad, const SDLoc &dl, SDValue Base,
1066 : SDValue Offset, ISD::MemIndexedMode AM);
1067 : SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
1068 : const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
1069 : MachinePointerInfo PtrInfo, EVT MemVT, unsigned Alignment = 0,
1070 : MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1071 : const AAMDNodes &AAInfo = AAMDNodes(),
1072 : const MDNode *Ranges = nullptr);
1073 : SDValue getLoad(ISD::MemIndexedMode AM, ISD::LoadExtType ExtType, EVT VT,
1074 : const SDLoc &dl, SDValue Chain, SDValue Ptr, SDValue Offset,
1075 : EVT MemVT, MachineMemOperand *MMO);
1076 :
1077 : /// Helper function to build ISD::STORE nodes.
1078 : ///
1079 : /// This function will set the MOStore flag on MMOFlags, but you can set it if
1080 : /// you want. The MOLoad and MOInvariant flags must not be set.
1081 : SDValue
1082 : getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1083 : MachinePointerInfo PtrInfo, unsigned Alignment = 0,
1084 : MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1085 : const AAMDNodes &AAInfo = AAMDNodes());
1086 : SDValue getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1087 : MachineMemOperand *MMO);
1088 : SDValue
1089 : getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr,
1090 : MachinePointerInfo PtrInfo, EVT SVT, unsigned Alignment = 0,
1091 : MachineMemOperand::Flags MMOFlags = MachineMemOperand::MONone,
1092 : const AAMDNodes &AAInfo = AAMDNodes());
1093 : SDValue getTruncStore(SDValue Chain, const SDLoc &dl, SDValue Val,
1094 : SDValue Ptr, EVT SVT, MachineMemOperand *MMO);
1095 : SDValue getIndexedStore(SDValue OrigStore, const SDLoc &dl, SDValue Base,
1096 : SDValue Offset, ISD::MemIndexedMode AM);
1097 :
1098 : /// Returns sum of the base pointer and offset.
1099 : SDValue getMemBasePlusOffset(SDValue Base, unsigned Offset, const SDLoc &DL);
1100 :
1101 : SDValue getMaskedLoad(EVT VT, const SDLoc &dl, SDValue Chain, SDValue Ptr,
1102 : SDValue Mask, SDValue Src0, EVT MemVT,
1103 : MachineMemOperand *MMO, ISD::LoadExtType,
1104 : bool IsExpanding = false);
1105 : SDValue getMaskedStore(SDValue Chain, const SDLoc &dl, SDValue Val,
1106 : SDValue Ptr, SDValue Mask, EVT MemVT,
1107 : MachineMemOperand *MMO, bool IsTruncating = false,
1108 : bool IsCompressing = false);
1109 : SDValue getMaskedGather(SDVTList VTs, EVT VT, const SDLoc &dl,
1110 : ArrayRef<SDValue> Ops, MachineMemOperand *MMO);
1111 : SDValue getMaskedScatter(SDVTList VTs, EVT VT, const SDLoc &dl,
1112 : ArrayRef<SDValue> Ops, MachineMemOperand *MMO);
1113 :
1114 : /// Return (create a new or find existing) a target-specific node.
1115 : /// TargetMemSDNode should be derived class from MemSDNode.
1116 : template <class TargetMemSDNode>
1117 : SDValue getTargetMemSDNode(SDVTList VTs, ArrayRef<SDValue> Ops,
1118 : const SDLoc &dl, EVT MemVT,
1119 : MachineMemOperand *MMO);
1120 :
1121 : /// Construct a node to track a Value* through the backend.
1122 : SDValue getSrcValue(const Value *v);
1123 :
1124 : /// Return an MDNodeSDNode which holds an MDNode.
1125 : SDValue getMDNode(const MDNode *MD);
1126 :
1127 : /// Return a bitcast using the SDLoc of the value operand, and casting to the
1128 : /// provided type. Use getNode to set a custom SDLoc.
1129 : SDValue getBitcast(EVT VT, SDValue V);
1130 :
1131 : /// Return an AddrSpaceCastSDNode.
1132 : SDValue getAddrSpaceCast(const SDLoc &dl, EVT VT, SDValue Ptr, unsigned SrcAS,
1133 : unsigned DestAS);
1134 :
1135 : /// Return the specified value casted to
1136 : /// the target's desired shift amount type.
1137 : SDValue getShiftAmountOperand(EVT LHSTy, SDValue Op);
1138 :
1139 : /// Expand the specified \c ISD::VAARG node as the Legalize pass would.
1140 : SDValue expandVAArg(SDNode *Node);
1141 :
1142 : /// Expand the specified \c ISD::VACOPY node as the Legalize pass would.
1143 : SDValue expandVACopy(SDNode *Node);
1144 :
1145 : /// *Mutate* the specified node in-place to have the
1146 : /// specified operands. If the resultant node already exists in the DAG,
1147 218 : /// this does not modify the specified node, instead it returns the node that
1148 : /// already exists. If the resultant node does not exist in the DAG, the
1149 : /// input node is returned. As a degenerate case, if you specify the same
1150 : /// input operands as the node already has, the input node is returned.
1151 : SDNode *UpdateNodeOperands(SDNode *N, SDValue Op);
1152 : SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2);
1153 : SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1154 : SDValue Op3);
1155 218 : SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1156 : SDValue Op3, SDValue Op4);
1157 : SDNode *UpdateNodeOperands(SDNode *N, SDValue Op1, SDValue Op2,
1158 : SDValue Op3, SDValue Op4, SDValue Op5);
1159 : SDNode *UpdateNodeOperands(SDNode *N, ArrayRef<SDValue> Ops);
1160 :
1161 : /// *Mutate* the specified machine node's memory references to the provided
1162 : /// list.
1163 : void setNodeMemRefs(MachineSDNode *N,
1164 : ArrayRef<MachineMemOperand *> NewMemRefs);
1165 :
1166 : // Propagates the change in divergence to users
1167 : void updateDivergence(SDNode * N);
1168 :
1169 : /// These are used for target selectors to *mutate* the
1170 : /// specified node to have the specified return type, Target opcode, and
1171 : /// operands. Note that target opcodes are stored as
1172 : /// ~TargetOpcode in the node opcode field. The resultant node is returned.
1173 : SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT);
1174 : SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT, SDValue Op1);
1175 : SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT,
1176 : SDValue Op1, SDValue Op2);
1177 : SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT,
1178 : SDValue Op1, SDValue Op2, SDValue Op3);
1179 : SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT,
1180 : ArrayRef<SDValue> Ops);
1181 : SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1, EVT VT2);
1182 : SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
1183 : EVT VT2, ArrayRef<SDValue> Ops);
1184 : SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
1185 : EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
1186 : SDNode *SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT1,
1187 : EVT VT2, SDValue Op1);
1188 : SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT1,
1189 : EVT VT2, SDValue Op1, SDValue Op2);
1190 : SDNode *SelectNodeTo(SDNode *N, unsigned MachineOpc, SDVTList VTs,
1191 : ArrayRef<SDValue> Ops);
1192 :
1193 : /// This *mutates* the specified node to have the specified
1194 : /// return type, opcode, and operands.
1195 : SDNode *MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs,
1196 : ArrayRef<SDValue> Ops);
1197 :
1198 : /// Mutate the specified strict FP node to its non-strict equivalent,
1199 : /// unlinking the node from its chain and dropping the metadata arguments.
1200 : /// The node must be a strict FP node.
1201 : SDNode *mutateStrictFPToFP(SDNode *Node);
1202 :
1203 : /// These are used for target selectors to create a new node
1204 : /// with specified return type(s), MachineInstr opcode, and operands.
1205 : ///
1206 : /// Note that getMachineNode returns the resultant node. If there is already
1207 : /// a node of the specified opcode and operands, it returns that node instead
1208 : /// of the current one.
1209 : MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT);
1210 : MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1211 : SDValue Op1);
1212 : MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1213 : SDValue Op1, SDValue Op2);
1214 : MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1215 : SDValue Op1, SDValue Op2, SDValue Op3);
1216 : MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT,
1217 : ArrayRef<SDValue> Ops);
1218 : MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1219 : EVT VT2, SDValue Op1, SDValue Op2);
1220 : MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1221 : EVT VT2, SDValue Op1, SDValue Op2, SDValue Op3);
1222 : MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1223 : EVT VT2, ArrayRef<SDValue> Ops);
1224 : MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1225 : EVT VT2, EVT VT3, SDValue Op1, SDValue Op2);
1226 : MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1227 : EVT VT2, EVT VT3, SDValue Op1, SDValue Op2,
1228 : SDValue Op3);
1229 : MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT1,
1230 : EVT VT2, EVT VT3, ArrayRef<SDValue> Ops);
1231 : MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl,
1232 : ArrayRef<EVT> ResultTys, ArrayRef<SDValue> Ops);
1233 : MachineSDNode *getMachineNode(unsigned Opcode, const SDLoc &dl, SDVTList VTs,
1234 : ArrayRef<SDValue> Ops);
1235 :
1236 : /// A convenience function for creating TargetInstrInfo::EXTRACT_SUBREG nodes.
1237 : SDValue getTargetExtractSubreg(int SRIdx, const SDLoc &DL, EVT VT,
1238 : SDValue Operand);
1239 :
1240 : /// A convenience function for creating TargetInstrInfo::INSERT_SUBREG nodes.
1241 : SDValue getTargetInsertSubreg(int SRIdx, const SDLoc &DL, EVT VT,
1242 : SDValue Operand, SDValue Subreg);
1243 :
1244 : /// Get the specified node if it's already available, or else return NULL.
1245 : SDNode *getNodeIfExists(unsigned Opcode, SDVTList VTList, ArrayRef<SDValue> Ops,
1246 : const SDNodeFlags Flags = SDNodeFlags());
1247 :
1248 : /// Creates a SDDbgValue node.
1249 : SDDbgValue *getDbgValue(DIVariable *Var, DIExpression *Expr, SDNode *N,
1250 : unsigned R, bool IsIndirect, const DebugLoc &DL,
1251 : unsigned O);
1252 :
1253 : /// Creates a constant SDDbgValue node.
1254 : SDDbgValue *getConstantDbgValue(DIVariable *Var, DIExpression *Expr,
1255 : const Value *C, const DebugLoc &DL,
1256 : unsigned O);
1257 :
1258 : /// Creates a FrameIndex SDDbgValue node.
1259 : SDDbgValue *getFrameIndexDbgValue(DIVariable *Var, DIExpression *Expr,
1260 : unsigned FI, bool IsIndirect,
1261 : const DebugLoc &DL, unsigned O);
1262 :
1263 : /// Creates a VReg SDDbgValue node.
1264 : SDDbgValue *getVRegDbgValue(DIVariable *Var, DIExpression *Expr,
1265 : unsigned VReg, bool IsIndirect,
1266 : const DebugLoc &DL, unsigned O);
1267 :
1268 : /// Creates a SDDbgLabel node.
1269 : SDDbgLabel *getDbgLabel(DILabel *Label, const DebugLoc &DL, unsigned O);
1270 :
1271 : /// Transfer debug values from one node to another, while optionally
1272 : /// generating fragment expressions for split-up values. If \p InvalidateDbg
1273 : /// is set, debug values are invalidated after they are transferred.
1274 : void transferDbgValues(SDValue From, SDValue To, unsigned OffsetInBits = 0,
1275 : unsigned SizeInBits = 0, bool InvalidateDbg = true);
1276 :
1277 : /// Remove the specified node from the system. If any of its
1278 : /// operands then becomes dead, remove them as well. Inform UpdateListener
1279 : /// for each node deleted.
1280 : void RemoveDeadNode(SDNode *N);
1281 :
1282 : /// This method deletes the unreachable nodes in the
1283 : /// given list, and any nodes that become unreachable as a result.
1284 : void RemoveDeadNodes(SmallVectorImpl<SDNode *> &DeadNodes);
1285 :
1286 : /// Modify anything using 'From' to use 'To' instead.
1287 : /// This can cause recursive merging of nodes in the DAG. Use the first
1288 : /// version if 'From' is known to have a single result, use the second
1289 : /// if you have two nodes with identical results (or if 'To' has a superset
1290 : /// of the results of 'From'), use the third otherwise.
1291 : ///
1292 : /// These methods all take an optional UpdateListener, which (if not null) is
1293 : /// informed about nodes that are deleted and modified due to recursive
1294 : /// changes in the dag.
1295 : ///
1296 : /// These functions only replace all existing uses. It's possible that as
1297 : /// these replacements are being performed, CSE may cause the From node
1298 : /// to be given new uses. These new uses of From are left in place, and
1299 : /// not automatically transferred to To.
1300 : ///
1301 : void ReplaceAllUsesWith(SDValue From, SDValue To);
1302 : void ReplaceAllUsesWith(SDNode *From, SDNode *To);
1303 : void ReplaceAllUsesWith(SDNode *From, const SDValue *To);
1304 :
1305 : /// Replace any uses of From with To, leaving
1306 : /// uses of other values produced by From.getNode() alone.
1307 : void ReplaceAllUsesOfValueWith(SDValue From, SDValue To);
1308 :
1309 : /// Like ReplaceAllUsesOfValueWith, but for multiple values at once.
1310 : /// This correctly handles the case where
1311 : /// there is an overlap between the From values and the To values.
1312 : void ReplaceAllUsesOfValuesWith(const SDValue *From, const SDValue *To,
1313 : unsigned Num);
1314 :
1315 : /// If an existing load has uses of its chain, create a token factor node with
1316 : /// that chain and the new memory node's chain and update users of the old
1317 : /// chain to the token factor. This ensures that the new memory node will have
1318 : /// the same relative memory dependency position as the old load. Returns the
1319 : /// new merged load chain.
1320 : SDValue makeEquivalentMemoryOrdering(LoadSDNode *Old, SDValue New);
1321 :
1322 : /// Topological-sort the AllNodes list and a
1323 : /// assign a unique node id for each node in the DAG based on their
1324 : /// topological order. Returns the number of nodes.
1325 : unsigned AssignTopologicalOrder();
1326 :
1327 : /// Move node N in the AllNodes list to be immediately
1328 : /// before the given iterator Position. This may be used to update the
1329 : /// topological ordering when the list of nodes is modified.
1330 0 : void RepositionNode(allnodes_iterator Position, SDNode *N) {
1331 : AllNodes.insert(Position, AllNodes.remove(N));
1332 0 : }
1333 :
1334 : /// Returns an APFloat semantics tag appropriate for the given type. If VT is
1335 : /// a vector type, the element semantics are returned.
1336 65 : static const fltSemantics &EVTToAPFloatSemantics(EVT VT) {
1337 65 : switch (VT.getScalarType().getSimpleVT().SimpleTy) {
1338 0 : default: llvm_unreachable("Unknown FP format");
1339 12 : case MVT::f16: return APFloat::IEEEhalf();
1340 32 : case MVT::f32: return APFloat::IEEEsingle();
1341 19 : case MVT::f64: return APFloat::IEEEdouble();
1342 0 : case MVT::f80: return APFloat::x87DoubleExtended();
1343 2 : case MVT::f128: return APFloat::IEEEquad();
1344 0 : case MVT::ppcf128: return APFloat::PPCDoubleDouble();
1345 : }
1346 11760 : }
1347 11760 :
1348 0 : /// Add a dbg_value SDNode. If SD is non-null that means the
1349 199 : /// value is produced by SD.
1350 6961 : void AddDbgValue(SDDbgValue *DB, SDNode *SD, bool isParameter);
1351 4424 :
1352 146 : /// Add a dbg_label SDNode.
1353 28 : void AddDbgLabel(SDDbgLabel *DB);
1354 2 :
1355 : /// Get the debug values which reference the given SDNode.
1356 0 : ArrayRef<SDDbgValue*> GetDbgValues(const SDNode* SD) const {
1357 16011 : return DbgInfo->getSDDbgValues(SD);
1358 : }
1359 :
1360 : public:
1361 : /// Return true if there are any SDDbgValue nodes associated
1362 : /// with this SelectionDAG.
1363 1269035 : bool hasDebugValues() const { return !DbgInfo->empty(); }
1364 :
1365 0 : SDDbgInfo::DbgIterator DbgBegin() { return DbgInfo->DbgBegin(); }
1366 0 : SDDbgInfo::DbgIterator DbgEnd() { return DbgInfo->DbgEnd(); }
1367 :
1368 0 : SDDbgInfo::DbgIterator ByvalParmDbgBegin() {
1369 0 : return DbgInfo->ByvalParmDbgBegin();
1370 : }
1371 :
1372 0 : SDDbgInfo::DbgIterator ByvalParmDbgEnd() {
1373 0 : return DbgInfo->ByvalParmDbgEnd();
1374 : }
1375 :
1376 0 : SDDbgInfo::DbgLabelIterator DbgLabelBegin() {
1377 0 : return DbgInfo->DbgLabelBegin();
1378 : }
1379 0 : SDDbgInfo::DbgLabelIterator DbgLabelEnd() {
1380 0 : return DbgInfo->DbgLabelEnd();
1381 : }
1382 :
1383 : /// To be invoked on an SDNode that is slated to be erased. This
1384 : /// function mirrors \c llvm::salvageDebugInfo.
1385 : void salvageDebugInfo(SDNode &N);
1386 :
1387 : void dump() const;
1388 :
1389 : /// Create a stack temporary, suitable for holding the specified value type.
1390 : /// If minAlign is specified, the slot size will have at least that alignment.
1391 : SDValue CreateStackTemporary(EVT VT, unsigned minAlign = 1);
1392 :
1393 : /// Create a stack temporary suitable for holding either of the specified
1394 : /// value types.
1395 : SDValue CreateStackTemporary(EVT VT1, EVT VT2);
1396 :
1397 : SDValue FoldSymbolOffset(unsigned Opcode, EVT VT,
1398 : const GlobalAddressSDNode *GA,
1399 : const SDNode *N2);
1400 :
1401 : SDValue FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
1402 : SDNode *Cst1, SDNode *Cst2);
1403 :
1404 : SDValue FoldConstantArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
1405 : const ConstantSDNode *Cst1,
1406 : const ConstantSDNode *Cst2);
1407 :
1408 : SDValue FoldConstantVectorArithmetic(unsigned Opcode, const SDLoc &DL, EVT VT,
1409 : ArrayRef<SDValue> Ops,
1410 : const SDNodeFlags Flags = SDNodeFlags());
1411 :
1412 : /// Constant fold a setcc to true or false.
1413 : SDValue FoldSetCC(EVT VT, SDValue N1, SDValue N2, ISD::CondCode Cond,
1414 : const SDLoc &dl);
1415 :
1416 : /// See if the specified operand can be simplified with the knowledge that only
1417 : /// the bits specified by Mask are used. If so, return the simpler operand,
1418 : /// otherwise return a null SDValue.
1419 : ///
1420 : /// (This exists alongside SimplifyDemandedBits because GetDemandedBits can
1421 : /// simplify nodes with multiple uses more aggressively.)
1422 : SDValue GetDemandedBits(SDValue V, const APInt &Mask);
1423 :
1424 : /// Return true if the sign bit of Op is known to be zero.
1425 : /// We use this predicate to simplify operations downstream.
1426 : bool SignBitIsZero(SDValue Op, unsigned Depth = 0) const;
1427 :
1428 : /// Return true if 'Op & Mask' is known to be zero. We
1429 : /// use this predicate to simplify operations downstream. Op and Mask are
1430 : /// known to be the same type.
1431 : bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth = 0)
1432 : const;
1433 :
1434 : /// Determine which bits of Op are known to be either zero or one and return
1435 : /// them in Known. For vectors, the known bits are those that are shared by
1436 : /// every vector element.
1437 : /// Targets can implement the computeKnownBitsForTargetNode method in the
1438 : /// TargetLowering class to allow target nodes to be understood.
1439 : KnownBits computeKnownBits(SDValue Op, unsigned Depth = 0) const;
1440 :
1441 : /// Determine which bits of Op are known to be either zero or one and return
1442 : /// them in Known. The DemandedElts argument allows us to only collect the
1443 : /// known bits that are shared by the requested vector elements.
1444 : /// Targets can implement the computeKnownBitsForTargetNode method in the
1445 : /// TargetLowering class to allow target nodes to be understood.
1446 : KnownBits computeKnownBits(SDValue Op, const APInt &DemandedElts,
1447 : unsigned Depth = 0) const;
1448 :
1449 : /// \copydoc SelectionDAG::computeKnownBits(SDValue,unsigned)
1450 21874 : void computeKnownBits(SDValue Op, KnownBits &Known,
1451 : unsigned Depth = 0) const {
1452 21874 : Known = computeKnownBits(Op, Depth);
1453 21874 : }
1454 :
1455 : /// \copydoc SelectionDAG::computeKnownBits(SDValue,const APInt&,unsigned)
1456 4539 : void computeKnownBits(SDValue Op, KnownBits &Known, const APInt &DemandedElts,
1457 : unsigned Depth = 0) const {
1458 4539 : Known = computeKnownBits(Op, DemandedElts, Depth);
1459 4539 : }
1460 9674898 :
1461 : /// Used to represent the possible overflow behavior of an operation.
1462 9674898 : /// Never: the operation cannot overflow.
1463 9674898 : /// Always: the operation will always overflow.
1464 : /// Sometime: the operation may or may not overflow.
1465 : enum OverflowKind {
1466 : OFK_Never,
1467 : OFK_Sometime,
1468 : OFK_Always,
1469 : };
1470 :
1471 : /// Determine if the result of the addition of 2 node can overflow.
1472 : OverflowKind computeOverflowKind(SDValue N0, SDValue N1) const;
1473 :
1474 : /// Test if the given value is known to have exactly one bit set. This differs
1475 : /// from computeKnownBits in that it doesn't necessarily determine which bit
1476 : /// is set.
1477 : bool isKnownToBeAPowerOfTwo(SDValue Val) const;
1478 :
1479 : /// Return the number of times the sign bit of the register is replicated into
1480 : /// the other bits. We know that at least 1 bit is always equal to the sign
1481 : /// bit (itself), but other cases can give us information. For example,
1482 : /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal
1483 : /// to each other, so we return 3. Targets can implement the
1484 : /// ComputeNumSignBitsForTarget method in the TargetLowering class to allow
1485 : /// target nodes to be understood.
1486 : unsigned ComputeNumSignBits(SDValue Op, unsigned Depth = 0) const;
1487 :
1488 : /// Return the number of times the sign bit of the register is replicated into
1489 : /// the other bits. We know that at least 1 bit is always equal to the sign
1490 : /// bit (itself), but other cases can give us information. For example,
1491 : /// immediately after an "SRA X, 2", we know that the top 3 bits are all equal
1492 : /// to each other, so we return 3. The DemandedElts argument allows
1493 : /// us to only collect the minimum sign bits of the requested vector elements.
1494 : /// Targets can implement the ComputeNumSignBitsForTarget method in the
1495 : /// TargetLowering class to allow target nodes to be understood.
1496 : unsigned ComputeNumSignBits(SDValue Op, const APInt &DemandedElts,
1497 : unsigned Depth = 0) const;
1498 :
1499 : /// Return true if the specified operand is an ISD::ADD with a ConstantSDNode
1500 : /// on the right-hand side, or if it is an ISD::OR with a ConstantSDNode that
1501 : /// is guaranteed to have the same semantics as an ADD. This handles the
1502 : /// equivalence:
1503 : /// X|Cst == X+Cst iff X&Cst = 0.
1504 : bool isBaseWithConstantOffset(SDValue Op) const;
1505 :
1506 : /// Test whether the given SDValue is known to never be NaN. If \p SNaN is
1507 : /// true, returns if \p Op is known to never be a signaling NaN (it may still
1508 : /// be a qNaN).
1509 : bool isKnownNeverNaN(SDValue Op, bool SNaN = false, unsigned Depth = 0) const;
1510 :
1511 : /// \returns true if \p Op is known to never be a signaling NaN.
1512 : bool isKnownNeverSNaN(SDValue Op, unsigned Depth = 0) const {
1513 463 : return isKnownNeverNaN(Op, true, Depth);
1514 : }
1515 :
1516 : /// Test whether the given floating point SDValue is known to never be
1517 : /// positive or negative zero.
1518 : bool isKnownNeverZeroFloat(SDValue Op) const;
1519 :
1520 : /// Test whether the given SDValue is known to contain non-zero value(s).
1521 : bool isKnownNeverZero(SDValue Op) const;
1522 788 :
1523 : /// Test whether two SDValues are known to compare equal. This
1524 788 : /// is true if they are the same value, or if one is negative zero and the
1525 788 : /// other positive zero.
1526 : bool isEqualTo(SDValue A, SDValue B) const;
1527 :
1528 253551 : /// Return true if A and B have no common bits set. As an example, this can
1529 : /// allow an 'add' to be transformed into an 'or'.
1530 253551 : bool haveNoCommonBitsSet(SDValue A, SDValue B) const;
1531 253551 :
1532 0 : /// Match a binop + shuffle pyramid that represents a horizontal reduction
1533 0 : /// over the elements of a vector starting from the EXTRACT_VECTOR_ELT node /p
1534 0 : /// Extract. The reduction must use one of the opcodes listed in /p
1535 0 : /// CandidateBinOps and on success /p BinOp will contain the matching opcode.
1536 0 : /// Returns the vector that is being reduced on, or SDValue() if a reduction
1537 0 : /// was not matched.
1538 0 : SDValue matchBinOpReduction(SDNode *Extract, ISD::NodeType &BinOp,
1539 : ArrayRef<ISD::NodeType> CandidateBinOps);
1540 :
1541 : /// Utility function used by legalize and lowering to
1542 : /// "unroll" a vector operation by splitting out the scalars and operating
1543 : /// on each element individually. If the ResNE is 0, fully unroll the vector
1544 : /// op. If ResNE is less than the width of the vector op, unroll up to ResNE.
1545 : /// If the ResNE is greater than the width of the vector op, unroll the
1546 : /// vector op and fill the end of the resulting vector with UNDEFS.
1547 : SDValue UnrollVectorOp(SDNode *N, unsigned ResNE = 0);
1548 :
1549 : /// Return true if loads are next to each other and can be
1550 0 : /// merged. Check that both are nonvolatile and if LD is loading
1551 11322 : /// 'Bytes' bytes from a location that is 'Dist' units away from the
1552 : /// location that the 'Base' load is loading from.
1553 : bool areNonVolatileConsecutiveLoads(LoadSDNode *LD, LoadSDNode *Base,
1554 : unsigned Bytes, int Dist) const;
1555 :
1556 : /// Infer alignment of a load / store address. Return 0 if
1557 : /// it cannot be inferred.
1558 : unsigned InferPtrAlignment(SDValue Ptr) const;
1559 :
1560 : /// Compute the VTs needed for the low/hi parts of a type
1561 : /// which is split (or expanded) into two not necessarily identical pieces.
1562 : std::pair<EVT, EVT> GetSplitDestVTs(const EVT &VT) const;
1563 :
1564 : /// Split the vector with EXTRACT_SUBVECTOR using the provides
1565 : /// VTs and return the low/high part.
1566 : std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL,
1567 : const EVT &LoVT, const EVT &HiVT);
1568 :
1569 : /// Split the vector with EXTRACT_SUBVECTOR and return the low/high part.
1570 6073 : std::pair<SDValue, SDValue> SplitVector(const SDValue &N, const SDLoc &DL) {
1571 6073 : EVT LoVT, HiVT;
1572 12146 : std::tie(LoVT, HiVT) = GetSplitDestVTs(N.getValueType());
1573 6073 : return SplitVector(N, DL, LoVT, HiVT);
1574 : }
1575 :
1576 : /// Split the node's operand with EXTRACT_SUBVECTOR and
1577 : /// return the low/high part.
1578 5259 : std::pair<SDValue, SDValue> SplitVectorOperand(const SDNode *N, unsigned OpNo)
1579 : {
1580 10802 : return SplitVector(N->getOperand(OpNo), SDLoc(N));
1581 284 : }
1582 568 :
1583 284 : /// Append the extracted elements from Start to Count out of the vector Op
1584 : /// in Args. If Count is 0, all of the elements will be extracted.
1585 : void ExtractVectorElements(SDValue Op, SmallVectorImpl<SDValue> &Args,
1586 : unsigned Start = 0, unsigned Count = 0);
1587 :
1588 38 : /// Compute the default alignment value for the given type.
1589 : unsigned getEVTAlignment(EVT MemoryVT) const;
1590 76 :
1591 : /// Test whether the given value is a constant int or similar node.
1592 : SDNode *isConstantIntBuildVectorOrConstantInt(SDValue N);
1593 :
1594 : /// Test whether the given value is a constant FP or similar node.
1595 : SDNode *isConstantFPBuildVectorOrConstantFP(SDValue N);
1596 :
1597 : /// \returns true if \p N is any kind of constant or build_vector of
1598 : /// constants, int or float. If a vector, it may not necessarily be a splat.
1599 8100 : inline bool isConstantValueOfAnyType(SDValue N) {
1600 14262 : return isConstantIntBuildVectorOrConstantInt(N) ||
1601 6162 : isConstantFPBuildVectorOrConstantFP(N);
1602 : }
1603 :
1604 : private:
1605 : void InsertNode(SDNode *N);
1606 : bool RemoveNodeFromCSEMaps(SDNode *N);
1607 : void AddModifiedNodeToCSEMaps(SDNode *N);
1608 : SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op, void *&InsertPos);
1609 : SDNode *FindModifiedNodeSlot(SDNode *N, SDValue Op1, SDValue Op2,
1610 : void *&InsertPos);
1611 : SDNode *FindModifiedNodeSlot(SDNode *N, ArrayRef<SDValue> Ops,
1612 : void *&InsertPos);
1613 : SDNode *UpdateSDLocOnMergeSDNode(SDNode *N, const SDLoc &loc);
1614 :
1615 : void DeleteNodeNotInCSEMaps(SDNode *N);
1616 : void DeallocateNode(SDNode *N);
1617 :
1618 : void allnodes_clear();
1619 :
1620 : /// Look up the node specified by ID in CSEMap. If it exists, return it. If
1621 : /// not, return the insertion token that will make insertion faster. This
1622 : /// overload is for nodes other than Constant or ConstantFP, use the other one
1623 : /// for those.
1624 : SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos);
1625 :
1626 : /// Look up the node specified by ID in CSEMap. If it exists, return it. If
1627 : /// not, return the insertion token that will make insertion faster. Performs
1628 : /// additional processing for constant nodes.
1629 : SDNode *FindNodeOrInsertPos(const FoldingSetNodeID &ID, const SDLoc &DL,
1630 : void *&InsertPos);
1631 :
1632 : /// List of non-single value types.
1633 : FoldingSet<SDVTListNode> VTListMap;
1634 :
1635 : /// Maps to auto-CSE operations.
1636 : std::vector<CondCodeSDNode*> CondCodeNodes;
1637 :
1638 : std::vector<SDNode*> ValueTypeNodes;
1639 : std::map<EVT, SDNode*, EVT::compareRawBits> ExtendedValueTypeNodes;
1640 : StringMap<SDNode*> ExternalSymbols;
1641 :
1642 126 : std::map<std::pair<std::string, unsigned char>,SDNode*> TargetExternalSymbols;
1643 126 : DenseMap<MCSymbol *, SDNode *> MCSymbols;
1644 257286 : };
1645 126 :
1646 257034 : template <> struct GraphTraits<SelectionDAG*> : public GraphTraits<SDNode*> {
1647 257034 : using nodes_iterator = pointer_iterator<SelectionDAG::allnodes_iterator>;
1648 :
1649 : static nodes_iterator nodes_begin(SelectionDAG *G) {
1650 64 : return nodes_iterator(G->allnodes_begin());
1651 : }
1652 128 :
1653 : static nodes_iterator nodes_end(SelectionDAG *G) {
1654 : return nodes_iterator(G->allnodes_end());
1655 : }
1656 : };
1657 :
1658 : template <class TargetMemSDNode>
1659 : SDValue SelectionDAG::getTargetMemSDNode(SDVTList VTs,
1660 : ArrayRef<SDValue> Ops,
1661 : const SDLoc &dl, EVT MemVT,
1662 : MachineMemOperand *MMO) {
1663 : /// Compose node ID and try to find an existing node.
1664 : FoldingSetNodeID ID;
1665 : unsigned Opcode =
1666 : TargetMemSDNode(dl.getIROrder(), DebugLoc(), VTs, MemVT, MMO).getOpcode();
1667 : ID.AddInteger(Opcode);
1668 : ID.AddPointer(VTs.VTs);
1669 : for (auto& Op : Ops) {
1670 : ID.AddPointer(Op.getNode());
1671 : ID.AddInteger(Op.getResNo());
1672 : }
1673 : ID.AddInteger(MemVT.getRawBits());
1674 : ID.AddInteger(MMO->getPointerInfo().getAddrSpace());
1675 : ID.AddInteger(getSyntheticNodeSubclassData<TargetMemSDNode>(
1676 : dl.getIROrder(), VTs, MemVT, MMO));
1677 :
1678 : void *IP = nullptr;
1679 : if (SDNode *E = FindNodeOrInsertPos(ID, dl, IP)) {
1680 : cast<TargetMemSDNode>(E)->refineAlignment(MMO);
1681 : return SDValue(E, 0);
1682 : }
1683 :
1684 : /// Existing node was not found. Create a new one.
1685 : auto *N = newSDNode<TargetMemSDNode>(dl.getIROrder(), dl.getDebugLoc(), VTs,
1686 : MemVT, MMO);
1687 : createOperands(N, Ops);
1688 : CSEMap.InsertNode(N, IP);
1689 : InsertNode(N);
1690 : return SDValue(N, 0);
1691 : }
1692 :
1693 : } // end namespace llvm
1694 :
1695 : #endif // LLVM_CODEGEN_SELECTIONDAG_H
|
