93a577a978d3801a70c7e877b87ee6a8388f32f4
[lldb.git] / llvm / lib / CodeGen / SelectionDAG / SelectionDAGBuilder.h
1 //===-- SelectionDAGBuilder.h - Selection-DAG building --------*- 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 implements routines for translating from LLVM IR into SelectionDAG IR.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #ifndef LLVM_LIB_CODEGEN_SELECTIONDAG_SELECTIONDAGBUILDER_H
15 #define LLVM_LIB_CODEGEN_SELECTIONDAG_SELECTIONDAGBUILDER_H
16
17 #include "StatepointLowering.h"
18 #include "llvm/ADT/APInt.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/Analysis/AliasAnalysis.h"
21 #include "llvm/CodeGen/SelectionDAG.h"
22 #include "llvm/CodeGen/SelectionDAGNodes.h"
23 #include "llvm/IR/CallSite.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/Statepoint.h"
26 #include "llvm/Support/ErrorHandling.h"
27 #include "llvm/Target/TargetLowering.h"
28 #include <utility>
29 #include <vector>
30
31 namespace llvm {
32
33 class AddrSpaceCastInst;
34 class AllocaInst;
35 class BasicBlock;
36 class BitCastInst;
37 class BranchInst;
38 class CallInst;
39 class DbgValueInst;
40 class ExtractElementInst;
41 class ExtractValueInst;
42 class FCmpInst;
43 class FPExtInst;
44 class FPToSIInst;
45 class FPToUIInst;
46 class FPTruncInst;
47 class Function;
48 class FunctionLoweringInfo;
49 class GetElementPtrInst;
50 class GCFunctionInfo;
51 class ICmpInst;
52 class IntToPtrInst;
53 class IndirectBrInst;
54 class InvokeInst;
55 class InsertElementInst;
56 class InsertValueInst;
57 class Instruction;
58 class LoadInst;
59 class MachineBasicBlock;
60 class MachineInstr;
61 class MachineRegisterInfo;
62 class MDNode;
63 class MVT;
64 class PHINode;
65 class PtrToIntInst;
66 class ReturnInst;
67 class SDDbgValue;
68 class SExtInst;
69 class SelectInst;
70 class ShuffleVectorInst;
71 class SIToFPInst;
72 class StoreInst;
73 class SwitchInst;
74 class DataLayout;
75 class TargetLibraryInfo;
76 class TargetLowering;
77 class TruncInst;
78 class UIToFPInst;
79 class UnreachableInst;
80 class VAArgInst;
81 class ZExtInst;
82
83 //===----------------------------------------------------------------------===//
84 /// SelectionDAGBuilder - This is the common target-independent lowering
85 /// implementation that is parameterized by a TargetLowering object.
86 ///
87 class SelectionDAGBuilder {
88   /// CurInst - The current instruction being visited
89   const Instruction *CurInst;
90
91   DenseMap<const Value*, SDValue> NodeMap;
92
93   /// UnusedArgNodeMap - Maps argument value for unused arguments. This is used
94   /// to preserve debug information for incoming arguments.
95   DenseMap<const Value*, SDValue> UnusedArgNodeMap;
96
97   /// DanglingDebugInfo - Helper type for DanglingDebugInfoMap.
98   class DanglingDebugInfo {
99     const DbgValueInst* DI;
100     DebugLoc dl;
101     unsigned SDNodeOrder;
102   public:
103     DanglingDebugInfo() : DI(nullptr), dl(DebugLoc()), SDNodeOrder(0) { }
104     DanglingDebugInfo(const DbgValueInst *di, DebugLoc DL, unsigned SDNO)
105         : DI(di), dl(std::move(DL)), SDNodeOrder(SDNO) {}
106     const DbgValueInst* getDI() { return DI; }
107     DebugLoc getdl() { return dl; }
108     unsigned getSDNodeOrder() { return SDNodeOrder; }
109   };
110
111   /// DanglingDebugInfoMap - Keeps track of dbg_values for which we have not
112   /// yet seen the referent.  We defer handling these until we do see it.
113   DenseMap<const Value*, DanglingDebugInfo> DanglingDebugInfoMap;
114
115 public:
116   /// PendingLoads - Loads are not emitted to the program immediately.  We bunch
117   /// them up and then emit token factor nodes when possible.  This allows us to
118   /// get simple disambiguation between loads without worrying about alias
119   /// analysis.
120   SmallVector<SDValue, 8> PendingLoads;
121
122   /// State used while lowering a statepoint sequence (gc_statepoint,
123   /// gc_relocate, and gc_result).  See StatepointLowering.hpp/cpp for details.
124   StatepointLoweringState StatepointLowering;
125 private:
126
127   /// PendingExports - CopyToReg nodes that copy values to virtual registers
128   /// for export to other blocks need to be emitted before any terminator
129   /// instruction, but they have no other ordering requirements. We bunch them
130   /// up and the emit a single tokenfactor for them just before terminator
131   /// instructions.
132   SmallVector<SDValue, 8> PendingExports;
133
134   /// SDNodeOrder - A unique monotonically increasing number used to order the
135   /// SDNodes we create.
136   unsigned SDNodeOrder;
137
138   enum CaseClusterKind {
139     /// A cluster of adjacent case labels with the same destination, or just one
140     /// case.
141     CC_Range,
142     /// A cluster of cases suitable for jump table lowering.
143     CC_JumpTable,
144     /// A cluster of cases suitable for bit test lowering.
145     CC_BitTests
146   };
147
148   /// A cluster of case labels.
149   struct CaseCluster {
150     CaseClusterKind Kind;
151     const ConstantInt *Low, *High;
152     union {
153       MachineBasicBlock *MBB;
154       unsigned JTCasesIndex;
155       unsigned BTCasesIndex;
156     };
157     BranchProbability Prob;
158
159     static CaseCluster range(const ConstantInt *Low, const ConstantInt *High,
160                              MachineBasicBlock *MBB, BranchProbability Prob) {
161       CaseCluster C;
162       C.Kind = CC_Range;
163       C.Low = Low;
164       C.High = High;
165       C.MBB = MBB;
166       C.Prob = Prob;
167       return C;
168     }
169
170     static CaseCluster jumpTable(const ConstantInt *Low,
171                                  const ConstantInt *High, unsigned JTCasesIndex,
172                                  BranchProbability Prob) {
173       CaseCluster C;
174       C.Kind = CC_JumpTable;
175       C.Low = Low;
176       C.High = High;
177       C.JTCasesIndex = JTCasesIndex;
178       C.Prob = Prob;
179       return C;
180     }
181
182     static CaseCluster bitTests(const ConstantInt *Low, const ConstantInt *High,
183                                 unsigned BTCasesIndex, BranchProbability Prob) {
184       CaseCluster C;
185       C.Kind = CC_BitTests;
186       C.Low = Low;
187       C.High = High;
188       C.BTCasesIndex = BTCasesIndex;
189       C.Prob = Prob;
190       return C;
191     }
192   };
193
194   typedef std::vector<CaseCluster> CaseClusterVector;
195   typedef CaseClusterVector::iterator CaseClusterIt;
196
197   struct CaseBits {
198     uint64_t Mask;
199     MachineBasicBlock* BB;
200     unsigned Bits;
201     BranchProbability ExtraProb;
202
203     CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits,
204              BranchProbability Prob):
205       Mask(mask), BB(bb), Bits(bits), ExtraProb(Prob) { }
206
207     CaseBits() : Mask(0), BB(nullptr), Bits(0) {}
208   };
209
210   typedef std::vector<CaseBits> CaseBitsVector;
211
212   /// Sort Clusters and merge adjacent cases.
213   void sortAndRangeify(CaseClusterVector &Clusters);
214
215   /// CaseBlock - This structure is used to communicate between
216   /// SelectionDAGBuilder and SDISel for the code generation of additional basic
217   /// blocks needed by multi-case switch statements.
218   struct CaseBlock {
219     CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs,
220               const Value *cmpmiddle, MachineBasicBlock *truebb,
221               MachineBasicBlock *falsebb, MachineBasicBlock *me,
222               BranchProbability trueprob = BranchProbability::getUnknown(),
223               BranchProbability falseprob = BranchProbability::getUnknown())
224         : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs),
225           TrueBB(truebb), FalseBB(falsebb), ThisBB(me), TrueProb(trueprob),
226           FalseProb(falseprob) {}
227
228     // CC - the condition code to use for the case block's setcc node
229     ISD::CondCode CC;
230
231     // CmpLHS/CmpRHS/CmpMHS - The LHS/MHS/RHS of the comparison to emit.
232     // Emit by default LHS op RHS. MHS is used for range comparisons:
233     // If MHS is not null: (LHS <= MHS) and (MHS <= RHS).
234     const Value *CmpLHS, *CmpMHS, *CmpRHS;
235
236     // TrueBB/FalseBB - the block to branch to if the setcc is true/false.
237     MachineBasicBlock *TrueBB, *FalseBB;
238
239     // ThisBB - the block into which to emit the code for the setcc and branches
240     MachineBasicBlock *ThisBB;
241
242     // TrueProb/FalseProb - branch weights.
243     BranchProbability TrueProb, FalseProb;
244   };
245
246   struct JumpTable {
247     JumpTable(unsigned R, unsigned J, MachineBasicBlock *M,
248               MachineBasicBlock *D): Reg(R), JTI(J), MBB(M), Default(D) {}
249
250     /// Reg - the virtual register containing the index of the jump table entry
251     //. to jump to.
252     unsigned Reg;
253     /// JTI - the JumpTableIndex for this jump table in the function.
254     unsigned JTI;
255     /// MBB - the MBB into which to emit the code for the indirect jump.
256     MachineBasicBlock *MBB;
257     /// Default - the MBB of the default bb, which is a successor of the range
258     /// check MBB.  This is when updating PHI nodes in successors.
259     MachineBasicBlock *Default;
260   };
261   struct JumpTableHeader {
262     JumpTableHeader(APInt F, APInt L, const Value *SV, MachineBasicBlock *H,
263                     bool E = false)
264         : First(std::move(F)), Last(std::move(L)), SValue(SV), HeaderBB(H),
265           Emitted(E) {}
266     APInt First;
267     APInt Last;
268     const Value *SValue;
269     MachineBasicBlock *HeaderBB;
270     bool Emitted;
271   };
272   typedef std::pair<JumpTableHeader, JumpTable> JumpTableBlock;
273
274   struct BitTestCase {
275     BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr,
276                 BranchProbability Prob):
277       Mask(M), ThisBB(T), TargetBB(Tr), ExtraProb(Prob) { }
278     uint64_t Mask;
279     MachineBasicBlock *ThisBB;
280     MachineBasicBlock *TargetBB;
281     BranchProbability ExtraProb;
282   };
283
284   typedef SmallVector<BitTestCase, 3> BitTestInfo;
285
286   struct BitTestBlock {
287     BitTestBlock(APInt F, APInt R, const Value *SV, unsigned Rg, MVT RgVT,
288                  bool E, bool CR, MachineBasicBlock *P, MachineBasicBlock *D,
289                  BitTestInfo C, BranchProbability Pr)
290         : First(std::move(F)), Range(std::move(R)), SValue(SV), Reg(Rg),
291           RegVT(RgVT), Emitted(E), ContiguousRange(CR), Parent(P), Default(D),
292           Cases(std::move(C)), Prob(Pr) {}
293     APInt First;
294     APInt Range;
295     const Value *SValue;
296     unsigned Reg;
297     MVT RegVT;
298     bool Emitted;
299     bool ContiguousRange;
300     MachineBasicBlock *Parent;
301     MachineBasicBlock *Default;
302     BitTestInfo Cases;
303     BranchProbability Prob;
304     BranchProbability DefaultProb;
305   };
306
307   /// Check whether a range of clusters is dense enough for a jump table.
308   bool isDense(const CaseClusterVector &Clusters,
309                const SmallVectorImpl<unsigned> &TotalCases,
310                unsigned First, unsigned Last, unsigned MinDensity) const;
311
312   /// Build a jump table cluster from Clusters[First..Last]. Returns false if it
313   /// decides it's not a good idea.
314   bool buildJumpTable(const CaseClusterVector &Clusters, unsigned First,
315                       unsigned Last, const SwitchInst *SI,
316                       MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster);
317
318   /// Find clusters of cases suitable for jump table lowering.
319   void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI,
320                       MachineBasicBlock *DefaultMBB);
321
322   /// Check whether the range [Low,High] fits in a machine word.
323   bool rangeFitsInWord(const APInt &Low, const APInt &High);
324
325   /// Check whether these clusters are suitable for lowering with bit tests based
326   /// on the number of destinations, comparison metric, and range.
327   bool isSuitableForBitTests(unsigned NumDests, unsigned NumCmps,
328                              const APInt &Low, const APInt &High);
329
330   /// Build a bit test cluster from Clusters[First..Last]. Returns false if it
331   /// decides it's not a good idea.
332   bool buildBitTests(CaseClusterVector &Clusters, unsigned First, unsigned Last,
333                      const SwitchInst *SI, CaseCluster &BTCluster);
334
335   /// Find clusters of cases suitable for bit test lowering.
336   void findBitTestClusters(CaseClusterVector &Clusters, const SwitchInst *SI);
337
338   struct SwitchWorkListItem {
339     MachineBasicBlock *MBB;
340     CaseClusterIt FirstCluster;
341     CaseClusterIt LastCluster;
342     const ConstantInt *GE;
343     const ConstantInt *LT;
344     BranchProbability DefaultProb;
345   };
346   typedef SmallVector<SwitchWorkListItem, 4> SwitchWorkList;
347
348   /// Determine the rank by weight of CC in [First,Last]. If CC has more weight
349   /// than each cluster in the range, its rank is 0.
350   static unsigned caseClusterRank(const CaseCluster &CC, CaseClusterIt First,
351                                   CaseClusterIt Last);
352
353   /// Emit comparison and split W into two subtrees.
354   void splitWorkItem(SwitchWorkList &WorkList, const SwitchWorkListItem &W,
355                      Value *Cond, MachineBasicBlock *SwitchMBB);
356
357   /// Lower W.
358   void lowerWorkItem(SwitchWorkListItem W, Value *Cond,
359                      MachineBasicBlock *SwitchMBB,
360                      MachineBasicBlock *DefaultMBB);
361
362
363   /// A class which encapsulates all of the information needed to generate a
364   /// stack protector check and signals to isel via its state being initialized
365   /// that a stack protector needs to be generated.
366   ///
367   /// *NOTE* The following is a high level documentation of SelectionDAG Stack
368   /// Protector Generation. The reason that it is placed here is for a lack of
369   /// other good places to stick it.
370   ///
371   /// High Level Overview of SelectionDAG Stack Protector Generation:
372   ///
373   /// Previously, generation of stack protectors was done exclusively in the
374   /// pre-SelectionDAG Codegen LLVM IR Pass "Stack Protector". This necessitated
375   /// splitting basic blocks at the IR level to create the success/failure basic
376   /// blocks in the tail of the basic block in question. As a result of this,
377   /// calls that would have qualified for the sibling call optimization were no
378   /// longer eligible for optimization since said calls were no longer right in
379   /// the "tail position" (i.e. the immediate predecessor of a ReturnInst
380   /// instruction).
381   ///
382   /// Then it was noticed that since the sibling call optimization causes the
383   /// callee to reuse the caller's stack, if we could delay the generation of
384   /// the stack protector check until later in CodeGen after the sibling call
385   /// decision was made, we get both the tail call optimization and the stack
386   /// protector check!
387   ///
388   /// A few goals in solving this problem were:
389   ///
390   ///   1. Preserve the architecture independence of stack protector generation.
391   ///
392   ///   2. Preserve the normal IR level stack protector check for platforms like
393   ///      OpenBSD for which we support platform-specific stack protector
394   ///      generation.
395   ///
396   /// The main problem that guided the present solution is that one can not
397   /// solve this problem in an architecture independent manner at the IR level
398   /// only. This is because:
399   ///
400   ///   1. The decision on whether or not to perform a sibling call on certain
401   ///      platforms (for instance i386) requires lower level information
402   ///      related to available registers that can not be known at the IR level.
403   ///
404   ///   2. Even if the previous point were not true, the decision on whether to
405   ///      perform a tail call is done in LowerCallTo in SelectionDAG which
406   ///      occurs after the Stack Protector Pass. As a result, one would need to
407   ///      put the relevant callinst into the stack protector check success
408   ///      basic block (where the return inst is placed) and then move it back
409   ///      later at SelectionDAG/MI time before the stack protector check if the
410   ///      tail call optimization failed. The MI level option was nixed
411   ///      immediately since it would require platform-specific pattern
412   ///      matching. The SelectionDAG level option was nixed because
413   ///      SelectionDAG only processes one IR level basic block at a time
414   ///      implying one could not create a DAG Combine to move the callinst.
415   ///
416   /// To get around this problem a few things were realized:
417   ///
418   ///   1. While one can not handle multiple IR level basic blocks at the
419   ///      SelectionDAG Level, one can generate multiple machine basic blocks
420   ///      for one IR level basic block. This is how we handle bit tests and
421   ///      switches.
422   ///
423   ///   2. At the MI level, tail calls are represented via a special return
424   ///      MIInst called "tcreturn". Thus if we know the basic block in which we
425   ///      wish to insert the stack protector check, we get the correct behavior
426   ///      by always inserting the stack protector check right before the return
427   ///      statement. This is a "magical transformation" since no matter where
428   ///      the stack protector check intrinsic is, we always insert the stack
429   ///      protector check code at the end of the BB.
430   ///
431   /// Given the aforementioned constraints, the following solution was devised:
432   ///
433   ///   1. On platforms that do not support SelectionDAG stack protector check
434   ///      generation, allow for the normal IR level stack protector check
435   ///      generation to continue.
436   ///
437   ///   2. On platforms that do support SelectionDAG stack protector check
438   ///      generation:
439   ///
440   ///     a. Use the IR level stack protector pass to decide if a stack
441   ///        protector is required/which BB we insert the stack protector check
442   ///        in by reusing the logic already therein. If we wish to generate a
443   ///        stack protector check in a basic block, we place a special IR
444   ///        intrinsic called llvm.stackprotectorcheck right before the BB's
445   ///        returninst or if there is a callinst that could potentially be
446   ///        sibling call optimized, before the call inst.
447   ///
448   ///     b. Then when a BB with said intrinsic is processed, we codegen the BB
449   ///        normally via SelectBasicBlock. In said process, when we visit the
450   ///        stack protector check, we do not actually emit anything into the
451   ///        BB. Instead, we just initialize the stack protector descriptor
452   ///        class (which involves stashing information/creating the success
453   ///        mbbb and the failure mbb if we have not created one for this
454   ///        function yet) and export the guard variable that we are going to
455   ///        compare.
456   ///
457   ///     c. After we finish selecting the basic block, in FinishBasicBlock if
458   ///        the StackProtectorDescriptor attached to the SelectionDAGBuilder is
459   ///        initialized, we produce the validation code with one of these
460   ///        techniques:
461   ///          1) with a call to a guard check function
462   ///          2) with inlined instrumentation
463   ///
464   ///        1) We insert a call to the check function before the terminator.
465   ///
466   ///        2) We first find a splice point in the parent basic block
467   ///        before the terminator and then splice the terminator of said basic
468   ///        block into the success basic block. Then we code-gen a new tail for
469   ///        the parent basic block consisting of the two loads, the comparison,
470   ///        and finally two branches to the success/failure basic blocks. We
471   ///        conclude by code-gening the failure basic block if we have not
472   ///        code-gened it already (all stack protector checks we generate in
473   ///        the same function, use the same failure basic block).
474   class StackProtectorDescriptor {
475   public:
476     StackProtectorDescriptor()
477         : ParentMBB(nullptr), SuccessMBB(nullptr), FailureMBB(nullptr) {}
478
479     /// Returns true if all fields of the stack protector descriptor are
480     /// initialized implying that we should/are ready to emit a stack protector.
481     bool shouldEmitStackProtector() const {
482       return ParentMBB && SuccessMBB && FailureMBB;
483     }
484
485     bool shouldEmitFunctionBasedCheckStackProtector() const {
486       return ParentMBB && !SuccessMBB && !FailureMBB;
487     }
488
489     /// Initialize the stack protector descriptor structure for a new basic
490     /// block.
491     void initialize(const BasicBlock *BB, MachineBasicBlock *MBB,
492                     bool FunctionBasedInstrumentation) {
493       // Make sure we are not initialized yet.
494       assert(!shouldEmitStackProtector() && "Stack Protector Descriptor is "
495              "already initialized!");
496       ParentMBB = MBB;
497       if (!FunctionBasedInstrumentation) {
498         SuccessMBB = AddSuccessorMBB(BB, MBB, /* IsLikely */ true);
499         FailureMBB = AddSuccessorMBB(BB, MBB, /* IsLikely */ false, FailureMBB);
500       }
501     }
502
503     /// Reset state that changes when we handle different basic blocks.
504     ///
505     /// This currently includes:
506     ///
507     /// 1. The specific basic block we are generating a
508     /// stack protector for (ParentMBB).
509     ///
510     /// 2. The successor machine basic block that will contain the tail of
511     /// parent mbb after we create the stack protector check (SuccessMBB). This
512     /// BB is visited only on stack protector check success.
513     void resetPerBBState() {
514       ParentMBB = nullptr;
515       SuccessMBB = nullptr;
516     }
517
518     /// Reset state that only changes when we switch functions.
519     ///
520     /// This currently includes:
521     ///
522     /// 1. FailureMBB since we reuse the failure code path for all stack
523     /// protector checks created in an individual function.
524     ///
525     /// 2.The guard variable since the guard variable we are checking against is
526     /// always the same.
527     void resetPerFunctionState() {
528       FailureMBB = nullptr;
529     }
530
531     MachineBasicBlock *getParentMBB() { return ParentMBB; }
532     MachineBasicBlock *getSuccessMBB() { return SuccessMBB; }
533     MachineBasicBlock *getFailureMBB() { return FailureMBB; }
534
535   private:
536     /// The basic block for which we are generating the stack protector.
537     ///
538     /// As a result of stack protector generation, we will splice the
539     /// terminators of this basic block into the successor mbb SuccessMBB and
540     /// replace it with a compare/branch to the successor mbbs
541     /// SuccessMBB/FailureMBB depending on whether or not the stack protector
542     /// was violated.
543     MachineBasicBlock *ParentMBB;
544
545     /// A basic block visited on stack protector check success that contains the
546     /// terminators of ParentMBB.
547     MachineBasicBlock *SuccessMBB;
548
549     /// This basic block visited on stack protector check failure that will
550     /// contain a call to __stack_chk_fail().
551     MachineBasicBlock *FailureMBB;
552
553     /// Add a successor machine basic block to ParentMBB. If the successor mbb
554     /// has not been created yet (i.e. if SuccMBB = 0), then the machine basic
555     /// block will be created. Assign a large weight if IsLikely is true.
556     MachineBasicBlock *AddSuccessorMBB(const BasicBlock *BB,
557                                        MachineBasicBlock *ParentMBB,
558                                        bool IsLikely,
559                                        MachineBasicBlock *SuccMBB = nullptr);
560   };
561
562 private:
563   const TargetMachine &TM;
564 public:
565   /// Lowest valid SDNodeOrder. The special case 0 is reserved for scheduling
566   /// nodes without a corresponding SDNode.
567   static const unsigned LowestSDNodeOrder = 1;
568
569   SelectionDAG &DAG;
570   const DataLayout *DL;
571   AliasAnalysis *AA;
572   const TargetLibraryInfo *LibInfo;
573
574   /// SwitchCases - Vector of CaseBlock structures used to communicate
575   /// SwitchInst code generation information.
576   std::vector<CaseBlock> SwitchCases;
577   /// JTCases - Vector of JumpTable structures used to communicate
578   /// SwitchInst code generation information.
579   std::vector<JumpTableBlock> JTCases;
580   /// BitTestCases - Vector of BitTestBlock structures used to communicate
581   /// SwitchInst code generation information.
582   std::vector<BitTestBlock> BitTestCases;
583   /// A StackProtectorDescriptor structure used to communicate stack protector
584   /// information in between SelectBasicBlock and FinishBasicBlock.
585   StackProtectorDescriptor SPDescriptor;
586
587   // Emit PHI-node-operand constants only once even if used by multiple
588   // PHI nodes.
589   DenseMap<const Constant *, unsigned> ConstantsOut;
590
591   /// FuncInfo - Information about the function as a whole.
592   ///
593   FunctionLoweringInfo &FuncInfo;
594
595   /// GFI - Garbage collection metadata for the function.
596   GCFunctionInfo *GFI;
597
598   /// LPadToCallSiteMap - Map a landing pad to the call site indexes.
599   DenseMap<MachineBasicBlock*, SmallVector<unsigned, 4> > LPadToCallSiteMap;
600
601   /// HasTailCall - This is set to true if a call in the current
602   /// block has been translated as a tail call. In this case,
603   /// no subsequent DAG nodes should be created.
604   ///
605   bool HasTailCall;
606
607   LLVMContext *Context;
608
609   SelectionDAGBuilder(SelectionDAG &dag, FunctionLoweringInfo &funcinfo,
610                       CodeGenOpt::Level ol)
611     : CurInst(nullptr), SDNodeOrder(LowestSDNodeOrder), TM(dag.getTarget()),
612       DAG(dag), FuncInfo(funcinfo),
613       HasTailCall(false) {
614   }
615
616   void init(GCFunctionInfo *gfi, AliasAnalysis &aa,
617             const TargetLibraryInfo *li);
618
619   /// clear - Clear out the current SelectionDAG and the associated
620   /// state and prepare this SelectionDAGBuilder object to be used
621   /// for a new block. This doesn't clear out information about
622   /// additional blocks that are needed to complete switch lowering
623   /// or PHI node updating; that information is cleared out as it is
624   /// consumed.
625   void clear();
626
627   /// clearDanglingDebugInfo - Clear the dangling debug information
628   /// map. This function is separated from the clear so that debug
629   /// information that is dangling in a basic block can be properly
630   /// resolved in a different basic block. This allows the
631   /// SelectionDAG to resolve dangling debug information attached
632   /// to PHI nodes.
633   void clearDanglingDebugInfo();
634
635   /// getRoot - Return the current virtual root of the Selection DAG,
636   /// flushing any PendingLoad items. This must be done before emitting
637   /// a store or any other node that may need to be ordered after any
638   /// prior load instructions.
639   ///
640   SDValue getRoot();
641
642   /// getControlRoot - Similar to getRoot, but instead of flushing all the
643   /// PendingLoad items, flush all the PendingExports items. It is necessary
644   /// to do this before emitting a terminator instruction.
645   ///
646   SDValue getControlRoot();
647
648   SDLoc getCurSDLoc() const {
649     return SDLoc(CurInst, SDNodeOrder);
650   }
651
652   DebugLoc getCurDebugLoc() const {
653     return CurInst ? CurInst->getDebugLoc() : DebugLoc();
654   }
655
656   unsigned getSDNodeOrder() const { return SDNodeOrder; }
657
658   void CopyValueToVirtualRegister(const Value *V, unsigned Reg);
659
660   void visit(const Instruction &I);
661
662   void visit(unsigned Opcode, const User &I);
663
664   /// getCopyFromRegs - If there was virtual register allocated for the value V
665   /// emit CopyFromReg of the specified type Ty. Return empty SDValue() otherwise.
666   SDValue getCopyFromRegs(const Value *V, Type *Ty);
667
668   // resolveDanglingDebugInfo - if we saw an earlier dbg_value referring to V,
669   // generate the debug data structures now that we've seen its definition.
670   void resolveDanglingDebugInfo(const Value *V, SDValue Val);
671   SDValue getValue(const Value *V);
672   bool findValue(const Value *V) const;
673
674   SDValue getNonRegisterValue(const Value *V);
675   SDValue getValueImpl(const Value *V);
676
677   void setValue(const Value *V, SDValue NewN) {
678     SDValue &N = NodeMap[V];
679     assert(!N.getNode() && "Already set a value for this node!");
680     N = NewN;
681   }
682
683   void setUnusedArgValue(const Value *V, SDValue NewN) {
684     SDValue &N = UnusedArgNodeMap[V];
685     assert(!N.getNode() && "Already set a value for this node!");
686     N = NewN;
687   }
688
689   void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB,
690                             MachineBasicBlock *FBB, MachineBasicBlock *CurBB,
691                             MachineBasicBlock *SwitchBB,
692                             Instruction::BinaryOps Opc, BranchProbability TW,
693                             BranchProbability FW);
694   void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB,
695                                     MachineBasicBlock *FBB,
696                                     MachineBasicBlock *CurBB,
697                                     MachineBasicBlock *SwitchBB,
698                                     BranchProbability TW, BranchProbability FW);
699   bool ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases);
700   bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB);
701   void CopyToExportRegsIfNeeded(const Value *V);
702   void ExportFromCurrentBlock(const Value *V);
703   void LowerCallTo(ImmutableCallSite CS, SDValue Callee, bool IsTailCall,
704                    const BasicBlock *EHPadBB = nullptr);
705
706   // Lower range metadata from 0 to N to assert zext to an integer of nearest
707   // floor power of two.
708   SDValue lowerRangeToAssertZExt(SelectionDAG &DAG, const Instruction &I,
709                                  SDValue Op);
710
711   void populateCallLoweringInfo(TargetLowering::CallLoweringInfo &CLI,
712                                 ImmutableCallSite CS, unsigned ArgIdx,
713                                 unsigned NumArgs, SDValue Callee,
714                                 Type *ReturnTy, bool IsPatchPoint);
715
716   std::pair<SDValue, SDValue>
717   lowerInvokable(TargetLowering::CallLoweringInfo &CLI,
718                  const BasicBlock *EHPadBB = nullptr);
719
720   /// UpdateSplitBlock - When an MBB was split during scheduling, update the
721   /// references that need to refer to the last resulting block.
722   void UpdateSplitBlock(MachineBasicBlock *First, MachineBasicBlock *Last);
723
724   /// Describes a gc.statepoint or a gc.statepoint like thing for the purposes
725   /// of lowering into a STATEPOINT node.
726   struct StatepointLoweringInfo {
727     /// Bases[i] is the base pointer for Ptrs[i].  Together they denote the set
728     /// of gc pointers this STATEPOINT has to relocate.
729     SmallVector<const Value *, 16> Bases;
730     SmallVector<const Value *, 16> Ptrs;
731
732     /// The set of gc.relocate calls associated with this gc.statepoint.
733     SmallVector<const GCRelocateInst *, 16> GCRelocates;
734
735     /// The full list of gc arguments to the gc.statepoint being lowered.
736     ArrayRef<const Use> GCArgs;
737
738     /// The gc.statepoint instruction.
739     const Instruction *StatepointInstr = nullptr;
740
741     /// The list of gc transition arguments present in the gc.statepoint being
742     /// lowered.
743     ArrayRef<const Use> GCTransitionArgs;
744
745     /// The ID that the resulting STATEPOINT instruction has to report.
746     unsigned ID = -1;
747
748     /// Information regarding the underlying call instruction.
749     TargetLowering::CallLoweringInfo CLI;
750
751     /// The deoptimization state associated with this gc.statepoint call, if
752     /// any.
753     ArrayRef<const Use> DeoptState;
754
755     /// Flags associated with the meta arguments being lowered.
756     uint64_t StatepointFlags = -1;
757
758     /// The number of patchable bytes the call needs to get lowered into.
759     unsigned NumPatchBytes = -1;
760
761     /// The exception handling unwind destination, in case this represents an
762     /// invoke of gc.statepoint.
763     const BasicBlock *EHPadBB = nullptr;
764
765     explicit StatepointLoweringInfo(SelectionDAG &DAG) : CLI(DAG) {}
766   };
767
768   /// Lower \p SLI into a STATEPOINT instruction.
769   SDValue LowerAsSTATEPOINT(StatepointLoweringInfo &SLI);
770
771   // This function is responsible for the whole statepoint lowering process.
772   // It uniformly handles invoke and call statepoints.
773   void LowerStatepoint(ImmutableStatepoint Statepoint,
774                        const BasicBlock *EHPadBB = nullptr);
775
776   void LowerCallSiteWithDeoptBundle(ImmutableCallSite CS, SDValue Callee,
777                                     const BasicBlock *EHPadBB);
778
779   void LowerDeoptimizeCall(const CallInst *CI);
780   void LowerDeoptimizingReturn();
781
782   void LowerCallSiteWithDeoptBundleImpl(ImmutableCallSite CS, SDValue Callee,
783                                         const BasicBlock *EHPadBB,
784                                         bool VarArgDisallowed,
785                                         bool ForceVoidReturnTy);
786
787 private:
788   // Terminator instructions.
789   void visitRet(const ReturnInst &I);
790   void visitBr(const BranchInst &I);
791   void visitSwitch(const SwitchInst &I);
792   void visitIndirectBr(const IndirectBrInst &I);
793   void visitUnreachable(const UnreachableInst &I);
794   void visitCleanupRet(const CleanupReturnInst &I);
795   void visitCatchSwitch(const CatchSwitchInst &I);
796   void visitCatchRet(const CatchReturnInst &I);
797   void visitCatchPad(const CatchPadInst &I);
798   void visitCleanupPad(const CleanupPadInst &CPI);
799
800   BranchProbability getEdgeProbability(const MachineBasicBlock *Src,
801                                        const MachineBasicBlock *Dst) const;
802   void addSuccessorWithProb(
803       MachineBasicBlock *Src, MachineBasicBlock *Dst,
804       BranchProbability Prob = BranchProbability::getUnknown());
805
806 public:
807   void visitSwitchCase(CaseBlock &CB,
808                        MachineBasicBlock *SwitchBB);
809   void visitSPDescriptorParent(StackProtectorDescriptor &SPD,
810                                MachineBasicBlock *ParentBB);
811   void visitSPDescriptorFailure(StackProtectorDescriptor &SPD);
812   void visitBitTestHeader(BitTestBlock &B, MachineBasicBlock *SwitchBB);
813   void visitBitTestCase(BitTestBlock &BB,
814                         MachineBasicBlock* NextMBB,
815                         BranchProbability BranchProbToNext,
816                         unsigned Reg,
817                         BitTestCase &B,
818                         MachineBasicBlock *SwitchBB);
819   void visitJumpTable(JumpTable &JT);
820   void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH,
821                             MachineBasicBlock *SwitchBB);
822
823 private:
824   // These all get lowered before this pass.
825   void visitInvoke(const InvokeInst &I);
826   void visitResume(const ResumeInst &I);
827
828   void visitBinary(const User &I, unsigned OpCode);
829   void visitShift(const User &I, unsigned Opcode);
830   void visitAdd(const User &I)  { visitBinary(I, ISD::ADD); }
831   void visitFAdd(const User &I) { visitBinary(I, ISD::FADD); }
832   void visitSub(const User &I)  { visitBinary(I, ISD::SUB); }
833   void visitFSub(const User &I);
834   void visitMul(const User &I)  { visitBinary(I, ISD::MUL); }
835   void visitFMul(const User &I) { visitBinary(I, ISD::FMUL); }
836   void visitURem(const User &I) { visitBinary(I, ISD::UREM); }
837   void visitSRem(const User &I) { visitBinary(I, ISD::SREM); }
838   void visitFRem(const User &I) { visitBinary(I, ISD::FREM); }
839   void visitUDiv(const User &I) { visitBinary(I, ISD::UDIV); }
840   void visitSDiv(const User &I);
841   void visitFDiv(const User &I) { visitBinary(I, ISD::FDIV); }
842   void visitAnd (const User &I) { visitBinary(I, ISD::AND); }
843   void visitOr  (const User &I) { visitBinary(I, ISD::OR); }
844   void visitXor (const User &I) { visitBinary(I, ISD::XOR); }
845   void visitShl (const User &I) { visitShift(I, ISD::SHL); }
846   void visitLShr(const User &I) { visitShift(I, ISD::SRL); }
847   void visitAShr(const User &I) { visitShift(I, ISD::SRA); }
848   void visitICmp(const User &I);
849   void visitFCmp(const User &I);
850   // Visit the conversion instructions
851   void visitTrunc(const User &I);
852   void visitZExt(const User &I);
853   void visitSExt(const User &I);
854   void visitFPTrunc(const User &I);
855   void visitFPExt(const User &I);
856   void visitFPToUI(const User &I);
857   void visitFPToSI(const User &I);
858   void visitUIToFP(const User &I);
859   void visitSIToFP(const User &I);
860   void visitPtrToInt(const User &I);
861   void visitIntToPtr(const User &I);
862   void visitBitCast(const User &I);
863   void visitAddrSpaceCast(const User &I);
864
865   void visitExtractElement(const User &I);
866   void visitInsertElement(const User &I);
867   void visitShuffleVector(const User &I);
868
869   void visitExtractValue(const ExtractValueInst &I);
870   void visitInsertValue(const InsertValueInst &I);
871   void visitLandingPad(const LandingPadInst &I);
872
873   void visitGetElementPtr(const User &I);
874   void visitSelect(const User &I);
875
876   void visitAlloca(const AllocaInst &I);
877   void visitLoad(const LoadInst &I);
878   void visitStore(const StoreInst &I);
879   void visitMaskedLoad(const CallInst &I);
880   void visitMaskedStore(const CallInst &I);
881   void visitMaskedGather(const CallInst &I);
882   void visitMaskedScatter(const CallInst &I);
883   void visitAtomicCmpXchg(const AtomicCmpXchgInst &I);
884   void visitAtomicRMW(const AtomicRMWInst &I);
885   void visitFence(const FenceInst &I);
886   void visitPHI(const PHINode &I);
887   void visitCall(const CallInst &I);
888   bool visitMemCmpCall(const CallInst &I);
889   bool visitMemPCpyCall(const CallInst &I);
890   bool visitMemChrCall(const CallInst &I);
891   bool visitStrCpyCall(const CallInst &I, bool isStpcpy);
892   bool visitStrCmpCall(const CallInst &I);
893   bool visitStrLenCall(const CallInst &I);
894   bool visitStrNLenCall(const CallInst &I);
895   bool visitUnaryFloatCall(const CallInst &I, unsigned Opcode);
896   bool visitBinaryFloatCall(const CallInst &I, unsigned Opcode);
897   void visitAtomicLoad(const LoadInst &I);
898   void visitAtomicStore(const StoreInst &I);
899   void visitLoadFromSwiftError(const LoadInst &I);
900   void visitStoreToSwiftError(const StoreInst &I);
901
902   void visitInlineAsm(ImmutableCallSite CS);
903   const char *visitIntrinsicCall(const CallInst &I, unsigned Intrinsic);
904   void visitTargetIntrinsic(const CallInst &I, unsigned Intrinsic);
905
906   void visitVAStart(const CallInst &I);
907   void visitVAArg(const VAArgInst &I);
908   void visitVAEnd(const CallInst &I);
909   void visitVACopy(const CallInst &I);
910   void visitStackmap(const CallInst &I);
911   void visitPatchpoint(ImmutableCallSite CS,
912                        const BasicBlock *EHPadBB = nullptr);
913
914   // These two are implemented in StatepointLowering.cpp
915   void visitGCRelocate(const GCRelocateInst &I);
916   void visitGCResult(const GCResultInst &I);
917
918   void visitUserOp1(const Instruction &I) {
919     llvm_unreachable("UserOp1 should not exist at instruction selection time!");
920   }
921   void visitUserOp2(const Instruction &I) {
922     llvm_unreachable("UserOp2 should not exist at instruction selection time!");
923   }
924
925   void processIntegerCallValue(const Instruction &I,
926                                SDValue Value, bool IsSigned);
927
928   void HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB);
929
930   void emitInlineAsmError(ImmutableCallSite CS, const Twine &Message);
931
932   /// EmitFuncArgumentDbgValue - If V is an function argument then create
933   /// corresponding DBG_VALUE machine instruction for it now. At the end of
934   /// instruction selection, they will be inserted to the entry BB.
935   bool EmitFuncArgumentDbgValue(const Value *V, DILocalVariable *Variable,
936                                 DIExpression *Expr, DILocation *DL,
937                                 int64_t Offset, bool IsIndirect,
938                                 const SDValue &N);
939
940   /// Return the next block after MBB, or nullptr if there is none.
941   MachineBasicBlock *NextBlock(MachineBasicBlock *MBB);
942
943   /// Update the DAG and DAG builder with the relevant information after
944   /// a new root node has been created which could be a tail call.
945   void updateDAGForMaybeTailCall(SDValue MaybeTC);
946
947   /// Return the appropriate SDDbgValue based on N.
948   SDDbgValue *getDbgValue(SDValue N, DILocalVariable *Variable,
949                           DIExpression *Expr, int64_t Offset, DebugLoc dl,
950                           unsigned DbgSDNodeOrder);
951 };
952
953 /// RegsForValue - This struct represents the registers (physical or virtual)
954 /// that a particular set of values is assigned, and the type information about
955 /// the value. The most common situation is to represent one value at a time,
956 /// but struct or array values are handled element-wise as multiple values.  The
957 /// splitting of aggregates is performed recursively, so that we never have
958 /// aggregate-typed registers. The values at this point do not necessarily have
959 /// legal types, so each value may require one or more registers of some legal
960 /// type.
961 ///
962 struct RegsForValue {
963   /// ValueVTs - The value types of the values, which may not be legal, and
964   /// may need be promoted or synthesized from one or more registers.
965   ///
966   SmallVector<EVT, 4> ValueVTs;
967
968   /// RegVTs - The value types of the registers. This is the same size as
969   /// ValueVTs and it records, for each value, what the type of the assigned
970   /// register or registers are. (Individual values are never synthesized
971   /// from more than one type of register.)
972   ///
973   /// With virtual registers, the contents of RegVTs is redundant with TLI's
974   /// getRegisterType member function, however when with physical registers
975   /// it is necessary to have a separate record of the types.
976   ///
977   SmallVector<MVT, 4> RegVTs;
978
979   /// Regs - This list holds the registers assigned to the values.
980   /// Each legal or promoted value requires one register, and each
981   /// expanded value requires multiple registers.
982   ///
983   SmallVector<unsigned, 4> Regs;
984
985   RegsForValue();
986
987   RegsForValue(const SmallVector<unsigned, 4> &regs, MVT regvt, EVT valuevt);
988
989   RegsForValue(LLVMContext &Context, const TargetLowering &TLI,
990                const DataLayout &DL, unsigned Reg, Type *Ty);
991
992   /// append - Add the specified values to this one.
993   void append(const RegsForValue &RHS) {
994     ValueVTs.append(RHS.ValueVTs.begin(), RHS.ValueVTs.end());
995     RegVTs.append(RHS.RegVTs.begin(), RHS.RegVTs.end());
996     Regs.append(RHS.Regs.begin(), RHS.Regs.end());
997   }
998
999   /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from
1000   /// this value and returns the result as a ValueVTs value.  This uses
1001   /// Chain/Flag as the input and updates them for the output Chain/Flag.
1002   /// If the Flag pointer is NULL, no flag is used.
1003   SDValue getCopyFromRegs(SelectionDAG &DAG, FunctionLoweringInfo &FuncInfo,
1004                           const SDLoc &dl, SDValue &Chain, SDValue *Flag,
1005                           const Value *V = nullptr) const;
1006
1007   /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the specified
1008   /// value into the registers specified by this object.  This uses Chain/Flag
1009   /// as the input and updates them for the output Chain/Flag.  If the Flag
1010   /// pointer is nullptr, no flag is used.  If V is not nullptr, then it is used
1011   /// in printing better diagnostic messages on error.
1012   void getCopyToRegs(SDValue Val, SelectionDAG &DAG, const SDLoc &dl,
1013                      SDValue &Chain, SDValue *Flag, const Value *V = nullptr,
1014                      ISD::NodeType PreferredExtendType = ISD::ANY_EXTEND) const;
1015
1016   /// AddInlineAsmOperands - Add this value to the specified inlineasm node
1017   /// operand list.  This adds the code marker, matching input operand index
1018   /// (if applicable), and includes the number of values added into it.
1019   void AddInlineAsmOperands(unsigned Kind, bool HasMatching,
1020                             unsigned MatchingIdx, const SDLoc &dl,
1021                             SelectionDAG &DAG, std::vector<SDValue> &Ops) const;
1022 };
1023
1024 } // end namespace llvm
1025
1026 #endif