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/CodeGen/Analysis.h"
  21 #include "llvm/CodeGen/SelectionDAG.h"
  22 #include "llvm/CodeGen/SelectionDAGNodes.h"
  23 #include "llvm/IR/CallSite.h"
  24 #include "llvm/IR/Statepoint.h"
  25 #include "llvm/IR/Constants.h"
  26 #include "llvm/Support/ErrorHandling.h"
  27 #include "llvm/Target/TargetLowering.h"
  28 #include <vector>
  29
  30 namespace llvm {
  31
  32 class AddrSpaceCastInst;
  33 class AliasAnalysis;
  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(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     uint32_t Weight;
 158
 159     static CaseCluster range(const ConstantInt *Low, const ConstantInt *High,
 160                              MachineBasicBlock *MBB, uint32_t Weight) {
 161       CaseCluster C;
 162       C.Kind = CC_Range;
 163       C.Low = Low;
 164       C.High = High;
 165       C.MBB = MBB;
 166       C.Weight = Weight;
 167       return C;
 168     }
 169
 170     static CaseCluster jumpTable(const ConstantInt *Low,
 171                                  const ConstantInt *High, unsigned JTCasesIndex,
 172                                  uint32_t Weight) {
 173       CaseCluster C;
 174       C.Kind = CC_JumpTable;
 175       C.Low = Low;
 176       C.High = High;
 177       C.JTCasesIndex = JTCasesIndex;
 178       C.Weight = Weight;
 179       return C;
 180     }
 181
 182     static CaseCluster bitTests(const ConstantInt *Low, const ConstantInt *High,
 183                                 unsigned BTCasesIndex, uint32_t Weight) {
 184       CaseCluster C;
 185       C.Kind = CC_BitTests;
 186       C.Low = Low;
 187       C.High = High;
 188       C.BTCasesIndex = BTCasesIndex;
 189       C.Weight = Weight;
 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     uint32_t ExtraWeight;
 202
 203     CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits,
 204              uint32_t Weight):
 205       Mask(mask), BB(bb), Bits(bits), ExtraWeight(Weight) { }
 206
 207     CaseBits() : Mask(0), BB(nullptr), Bits(0), ExtraWeight(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,
 221               MachineBasicBlock *truebb, MachineBasicBlock *falsebb,
 222               MachineBasicBlock *me,
 223               uint32_t trueweight = 0, uint32_t falseweight = 0)
 224       : CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs),
 225         TrueBB(truebb), FalseBB(falsebb), ThisBB(me),
 226         TrueWeight(trueweight), FalseWeight(falseweight) { }
 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     // TrueWeight/FalseWeight - branch weights.
 243     uint32_t TrueWeight, FalseWeight;
 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(F), Last(L), SValue(SV), HeaderBB(H), Emitted(E) {}
 265     APInt First;
 266     APInt Last;
 267     const Value *SValue;
 268     MachineBasicBlock *HeaderBB;
 269     bool Emitted;
 270   };
 271   typedef std::pair<JumpTableHeader, JumpTable> JumpTableBlock;
 272
 273   struct BitTestCase {
 274     BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr,
 275                 uint32_t Weight):
 276       Mask(M), ThisBB(T), TargetBB(Tr), ExtraWeight(Weight) { }
 277     uint64_t Mask;
 278     MachineBasicBlock *ThisBB;
 279     MachineBasicBlock *TargetBB;
 280     uint32_t ExtraWeight;
 281   };
 282
 283   typedef SmallVector<BitTestCase, 3> BitTestInfo;
 284
 285   struct BitTestBlock {
 286     BitTestBlock(APInt F, APInt R, const Value* SV,
 287                  unsigned Rg, MVT RgVT, bool E,
 288                  MachineBasicBlock* P, MachineBasicBlock* D,
 289                  BitTestInfo C):
 290       First(F), Range(R), SValue(SV), Reg(Rg), RegVT(RgVT), Emitted(E),
 291       Parent(P), Default(D), Cases(std::move(C)) { }
 292     APInt First;
 293     APInt Range;
 294     const Value *SValue;
 295     unsigned Reg;
 296     MVT RegVT;
 297     bool Emitted;
 298     MachineBasicBlock *Parent;
 299     MachineBasicBlock *Default;
 300     BitTestInfo Cases;
 301   };
 302
 303   /// Minimum jump table density, in percent.
 304   enum { MinJumpTableDensity = 40 };
 305
 306   /// Check whether a range of clusters is dense enough for a jump table.
 307   bool isDense(const CaseClusterVector &Clusters, unsigned *TotalCases,
 308                unsigned First, unsigned Last);
 309
 310   /// Build a jump table cluster from Clusters[First..Last]. Returns false if it
 311   /// decides it's not a good idea.
 312   bool buildJumpTable(CaseClusterVector &Clusters, unsigned First,
 313                       unsigned Last, const SwitchInst *SI,
 314                       MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster);
 315
 316   /// Find clusters of cases suitable for jump table lowering.
 317   void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI,
 318                       MachineBasicBlock *DefaultMBB);
 319
 320   /// Check whether the range [Low,High] fits in a machine word.
 321   bool rangeFitsInWord(const APInt &Low, const APInt &High);
 322
 323   /// Check whether these clusters are suitable for lowering with bit tests based
 324   /// on the number of destinations, comparison metric, and range.
 325   bool isSuitableForBitTests(unsigned NumDests, unsigned NumCmps,
 326                              const APInt &Low, const APInt &High);
 327
 328   /// Build a bit test cluster from Clusters[First..Last]. Returns false if it
 329   /// decides it's not a good idea.
 330   bool buildBitTests(CaseClusterVector &Clusters, unsigned First, unsigned Last,
 331                      const SwitchInst *SI, CaseCluster &BTCluster);
 332
 333   /// Find clusters of cases suitable for bit test lowering.
 334   void findBitTestClusters(CaseClusterVector &Clusters, const SwitchInst *SI);
 335
 336   struct SwitchWorkListItem {
 337     MachineBasicBlock *MBB;
 338     CaseClusterIt FirstCluster;
 339     CaseClusterIt LastCluster;
 340     const ConstantInt *GE;
 341     const ConstantInt *LT;
 342   };
 343   typedef SmallVector<SwitchWorkListItem, 4> SwitchWorkList;
 344
 345   /// Determine the rank by weight of CC in [First,Last]. If CC has more weight
 346   /// than each cluster in the range, its rank is 0.
 347   static unsigned caseClusterRank(const CaseCluster &CC, CaseClusterIt First,
 348                                   CaseClusterIt Last);
 349
 350   /// Emit comparison and split W into two subtrees.
 351   void splitWorkItem(SwitchWorkList &WorkList, const SwitchWorkListItem &W,
 352                      Value *Cond, MachineBasicBlock *SwitchMBB);
 353
 354   /// Lower W.
 355   void lowerWorkItem(SwitchWorkListItem W, Value *Cond,
 356                      MachineBasicBlock *SwitchMBB,
 357                      MachineBasicBlock *DefaultMBB);
 358
 359
 360   /// A class which encapsulates all of the information needed to generate a
 361   /// stack protector check and signals to isel via its state being initialized
 362   /// that a stack protector needs to be generated.
 363   ///
 364   /// *NOTE* The following is a high level documentation of SelectionDAG Stack
 365   /// Protector Generation. The reason that it is placed here is for a lack of
 366   /// other good places to stick it.
 367   ///
 368   /// High Level Overview of SelectionDAG Stack Protector Generation:
 369   ///
 370   /// Previously, generation of stack protectors was done exclusively in the
 371   /// pre-SelectionDAG Codegen LLVM IR Pass "Stack Protector". This necessitated
 372   /// splitting basic blocks at the IR level to create the success/failure basic
 373   /// blocks in the tail of the basic block in question. As a result of this,
 374   /// calls that would have qualified for the sibling call optimization were no
 375   /// longer eligible for optimization since said calls were no longer right in
 376   /// the "tail position" (i.e. the immediate predecessor of a ReturnInst
 377   /// instruction).
 378   ///
 379   /// Then it was noticed that since the sibling call optimization causes the
 380   /// callee to reuse the caller's stack, if we could delay the generation of
 381   /// the stack protector check until later in CodeGen after the sibling call
 382   /// decision was made, we get both the tail call optimization and the stack
 383   /// protector check!
 384   ///
 385   /// A few goals in solving this problem were:
 386   ///
 387   ///   1. Preserve the architecture independence of stack protector generation.
 388   ///
 389   ///   2. Preserve the normal IR level stack protector check for platforms like
 390   ///      OpenBSD for which we support platform-specific stack protector
 391   ///      generation.
 392   ///
 393   /// The main problem that guided the present solution is that one can not
 394   /// solve this problem in an architecture independent manner at the IR level
 395   /// only. This is because:
 396   ///
 397   ///   1. The decision on whether or not to perform a sibling call on certain
 398   ///      platforms (for instance i386) requires lower level information
 399   ///      related to available registers that can not be known at the IR level.
 400   ///
 401   ///   2. Even if the previous point were not true, the decision on whether to
 402   ///      perform a tail call is done in LowerCallTo in SelectionDAG which
 403   ///      occurs after the Stack Protector Pass. As a result, one would need to
 404   ///      put the relevant callinst into the stack protector check success
 405   ///      basic block (where the return inst is placed) and then move it back
 406   ///      later at SelectionDAG/MI time before the stack protector check if the
 407   ///      tail call optimization failed. The MI level option was nixed
 408   ///      immediately since it would require platform-specific pattern
 409   ///      matching. The SelectionDAG level option was nixed because
 410   ///      SelectionDAG only processes one IR level basic block at a time
 411   ///      implying one could not create a DAG Combine to move the callinst.
 412   ///
 413   /// To get around this problem a few things were realized:
 414   ///
 415   ///   1. While one can not handle multiple IR level basic blocks at the
 416   ///      SelectionDAG Level, one can generate multiple machine basic blocks
 417   ///      for one IR level basic block. This is how we handle bit tests and
 418   ///      switches.
 419   ///
 420   ///   2. At the MI level, tail calls are represented via a special return
 421   ///      MIInst called "tcreturn". Thus if we know the basic block in which we
 422   ///      wish to insert the stack protector check, we get the correct behavior
 423   ///      by always inserting the stack protector check right before the return
 424   ///      statement. This is a "magical transformation" since no matter where
 425   ///      the stack protector check intrinsic is, we always insert the stack
 426   ///      protector check code at the end of the BB.
 427   ///
 428   /// Given the aforementioned constraints, the following solution was devised:
 429   ///
 430   ///   1. On platforms that do not support SelectionDAG stack protector check
 431   ///      generation, allow for the normal IR level stack protector check
 432   ///      generation to continue.
 433   ///
 434   ///   2. On platforms that do support SelectionDAG stack protector check
 435   ///      generation:
 436   ///
 437   ///     a. Use the IR level stack protector pass to decide if a stack
 438   ///        protector is required/which BB we insert the stack protector check
 439   ///        in by reusing the logic already therein. If we wish to generate a
 440   ///        stack protector check in a basic block, we place a special IR
 441   ///        intrinsic called llvm.stackprotectorcheck right before the BB's
 442   ///        returninst or if there is a callinst that could potentially be
 443   ///        sibling call optimized, before the call inst.
 444   ///
 445   ///     b. Then when a BB with said intrinsic is processed, we codegen the BB
 446   ///        normally via SelectBasicBlock. In said process, when we visit the
 447   ///        stack protector check, we do not actually emit anything into the
 448   ///        BB. Instead, we just initialize the stack protector descriptor
 449   ///        class (which involves stashing information/creating the success
 450   ///        mbbb and the failure mbb if we have not created one for this
 451   ///        function yet) and export the guard variable that we are going to
 452   ///        compare.
 453   ///
 454   ///     c. After we finish selecting the basic block, in FinishBasicBlock if
 455   ///        the StackProtectorDescriptor attached to the SelectionDAGBuilder is
 456   ///        initialized, we first find a splice point in the parent basic block
 457   ///        before the terminator and then splice the terminator of said basic
 458   ///        block into the success basic block. Then we code-gen a new tail for
 459   ///        the parent basic block consisting of the two loads, the comparison,
 460   ///        and finally two branches to the success/failure basic blocks. We
 461   ///        conclude by code-gening the failure basic block if we have not
 462   ///        code-gened it already (all stack protector checks we generate in
 463   ///        the same function, use the same failure basic block).
 464   class StackProtectorDescriptor {
 465   public:
 466     StackProtectorDescriptor() : ParentMBB(nullptr), SuccessMBB(nullptr),
 467                                  FailureMBB(nullptr), Guard(nullptr),
 468                                  GuardReg(0) { }
 469
 470     /// Returns true if all fields of the stack protector descriptor are
 471     /// initialized implying that we should/are ready to emit a stack protector.
 472     bool shouldEmitStackProtector() const {
 473       return ParentMBB && SuccessMBB && FailureMBB && Guard;
 474     }
 475
 476     /// Initialize the stack protector descriptor structure for a new basic
 477     /// block.
 478     void initialize(const BasicBlock *BB,
 479                     MachineBasicBlock *MBB,
 480                     const CallInst &StackProtCheckCall) {
 481       // Make sure we are not initialized yet.
 482       assert(!shouldEmitStackProtector() && "Stack Protector Descriptor is "
 483              "already initialized!");
 484       ParentMBB = MBB;
 485       SuccessMBB = AddSuccessorMBB(BB, MBB, /* IsLikely */ true);
 486       FailureMBB = AddSuccessorMBB(BB, MBB, /* IsLikely */ false, FailureMBB);
 487       if (!Guard)
 488         Guard = StackProtCheckCall.getArgOperand(0);
 489     }
 490
 491     /// Reset state that changes when we handle different basic blocks.
 492     ///
 493     /// This currently includes:
 494     ///
 495     /// 1. The specific basic block we are generating a
 496     /// stack protector for (ParentMBB).
 497     ///
 498     /// 2. The successor machine basic block that will contain the tail of
 499     /// parent mbb after we create the stack protector check (SuccessMBB). This
 500     /// BB is visited only on stack protector check success.
 501     void resetPerBBState() {
 502       ParentMBB = nullptr;
 503       SuccessMBB = nullptr;
 504     }
 505
 506     /// Reset state that only changes when we switch functions.
 507     ///
 508     /// This currently includes:
 509     ///
 510     /// 1. FailureMBB since we reuse the failure code path for all stack
 511     /// protector checks created in an individual function.
 512     ///
 513     /// 2.The guard variable since the guard variable we are checking against is
 514     /// always the same.
 515     void resetPerFunctionState() {
 516       FailureMBB = nullptr;
 517       Guard = nullptr;
 518     }
 519
 520     MachineBasicBlock *getParentMBB() { return ParentMBB; }
 521     MachineBasicBlock *getSuccessMBB() { return SuccessMBB; }
 522     MachineBasicBlock *getFailureMBB() { return FailureMBB; }
 523     const Value *getGuard() { return Guard; }
 524
 525     unsigned getGuardReg() const { return GuardReg; }
 526     void setGuardReg(unsigned R) { GuardReg = R; }
 527
 528   private:
 529     /// The basic block for which we are generating the stack protector.
 530     ///
 531     /// As a result of stack protector generation, we will splice the
 532     /// terminators of this basic block into the successor mbb SuccessMBB and
 533     /// replace it with a compare/branch to the successor mbbs
 534     /// SuccessMBB/FailureMBB depending on whether or not the stack protector
 535     /// was violated.
 536     MachineBasicBlock *ParentMBB;
 537
 538     /// A basic block visited on stack protector check success that contains the
 539     /// terminators of ParentMBB.
 540     MachineBasicBlock *SuccessMBB;
 541
 542     /// This basic block visited on stack protector check failure that will
 543     /// contain a call to __stack_chk_fail().
 544     MachineBasicBlock *FailureMBB;
 545
 546     /// The guard variable which we will compare against the stored value in the
 547     /// stack protector stack slot.
 548     const Value *Guard;
 549
 550     /// The virtual register holding the stack guard value.
 551     unsigned GuardReg;
 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   /// OptLevel - What optimization level we're generating code for.
 596   ///
 597   CodeGenOpt::Level OptLevel;
 598
 599   /// GFI - Garbage collection metadata for the function.
 600   GCFunctionInfo *GFI;
 601
 602   /// LPadToCallSiteMap - Map a landing pad to the call site indexes.
 603   DenseMap<MachineBasicBlock*, SmallVector<unsigned, 4> > LPadToCallSiteMap;
 604
 605   /// HasTailCall - This is set to true if a call in the current
 606   /// block has been translated as a tail call. In this case,
 607   /// no subsequent DAG nodes should be created.
 608   ///
 609   bool HasTailCall;
 610
 611   LLVMContext *Context;
 612
 613   SelectionDAGBuilder(SelectionDAG &dag, FunctionLoweringInfo &funcinfo,
 614                       CodeGenOpt::Level ol)
 615     : CurInst(nullptr), SDNodeOrder(LowestSDNodeOrder), TM(dag.getTarget()),
 616       DAG(dag), FuncInfo(funcinfo), OptLevel(ol),
 617       HasTailCall(false) {
 618   }
 619
 620   void init(GCFunctionInfo *gfi, AliasAnalysis &aa,
 621             const TargetLibraryInfo *li);
 622
 623   /// clear - Clear out the current SelectionDAG and the associated
 624   /// state and prepare this SelectionDAGBuilder object to be used
 625   /// for a new block. This doesn't clear out information about
 626   /// additional blocks that are needed to complete switch lowering
 627   /// or PHI node updating; that information is cleared out as it is
 628   /// consumed.
 629   void clear();
 630
 631   /// clearDanglingDebugInfo - Clear the dangling debug information
 632   /// map. This function is separated from the clear so that debug
 633   /// information that is dangling in a basic block can be properly
 634   /// resolved in a different basic block. This allows the
 635   /// SelectionDAG to resolve dangling debug information attached
 636   /// to PHI nodes.
 637   void clearDanglingDebugInfo();
 638
 639   /// getRoot - Return the current virtual root of the Selection DAG,
 640   /// flushing any PendingLoad items. This must be done before emitting
 641   /// a store or any other node that may need to be ordered after any
 642   /// prior load instructions.
 643   ///
 644   SDValue getRoot();
 645
 646   /// getControlRoot - Similar to getRoot, but instead of flushing all the
 647   /// PendingLoad items, flush all the PendingExports items. It is necessary
 648   /// to do this before emitting a terminator instruction.
 649   ///
 650   SDValue getControlRoot();
 651
 652   SDLoc getCurSDLoc() const {
 653     return SDLoc(CurInst, SDNodeOrder);
 654   }
 655
 656   DebugLoc getCurDebugLoc() const {
 657     return CurInst ? CurInst->getDebugLoc() : DebugLoc();
 658   }
 659
 660   unsigned getSDNodeOrder() const { return SDNodeOrder; }
 661
 662   void CopyValueToVirtualRegister(const Value *V, unsigned Reg);
 663
 664   void visit(const Instruction &I);
 665
 666   void visit(unsigned Opcode, const User &I);
 667
 668   /// getCopyFromRegs - If there was virtual register allocated for the value V
 669   /// emit CopyFromReg of the specified type Ty. Return empty SDValue() otherwise.
 670   SDValue getCopyFromRegs(const Value *V, Type *Ty);
 671
 672   // resolveDanglingDebugInfo - if we saw an earlier dbg_value referring to V,
 673   // generate the debug data structures now that we've seen its definition.
 674   void resolveDanglingDebugInfo(const Value *V, SDValue Val);
 675   SDValue getValue(const Value *V);
 676   bool findValue(const Value *V) const;
 677
 678   SDValue getNonRegisterValue(const Value *V);
 679   SDValue getValueImpl(const Value *V);
 680
 681   void setValue(const Value *V, SDValue NewN) {
 682     SDValue &N = NodeMap[V];
 683     assert(!N.getNode() && "Already set a value for this node!");
 684     N = NewN;
 685   }
 686
 687   void setUnusedArgValue(const Value *V, SDValue NewN) {
 688     SDValue &N = UnusedArgNodeMap[V];
 689     assert(!N.getNode() && "Already set a value for this node!");
 690     N = NewN;
 691   }
 692
 693   void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB,
 694                             MachineBasicBlock *FBB, MachineBasicBlock *CurBB,
 695                             MachineBasicBlock *SwitchBB,
 696                             Instruction::BinaryOps Opc,
 697                             uint32_t TW, uint32_t FW);
 698   void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB,
 699                                     MachineBasicBlock *FBB,
 700                                     MachineBasicBlock *CurBB,
 701                                     MachineBasicBlock *SwitchBB,
 702                                     uint32_t TW, uint32_t FW);
 703   bool ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases);
 704   bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB);
 705   void CopyToExportRegsIfNeeded(const Value *V);
 706   void ExportFromCurrentBlock(const Value *V);
 707   void LowerCallTo(ImmutableCallSite CS, SDValue Callee, bool IsTailCall,
 708                    MachineBasicBlock *LandingPad = nullptr);
 709
 710   std::pair<SDValue, SDValue> lowerCallOperands(
 711           ImmutableCallSite CS,
 712           unsigned ArgIdx,
 713           unsigned NumArgs,
 714           SDValue Callee,
 715           Type *ReturnTy,
 716           MachineBasicBlock *LandingPad = nullptr,
 717           bool IsPatchPoint = false);
 718
 719   /// UpdateSplitBlock - When an MBB was split during scheduling, update the
 720   /// references that need to refer to the last resulting block.
 721   void UpdateSplitBlock(MachineBasicBlock *First, MachineBasicBlock *Last);
 722
 723   // This function is responsible for the whole statepoint lowering process.
 724   // It uniformly handles invoke and call statepoints.
 725   void LowerStatepoint(ImmutableStatepoint Statepoint,
 726                        MachineBasicBlock *LandingPad = nullptr);
 727 private:
 728   std::pair<SDValue, SDValue> lowerInvokable(
 729           TargetLowering::CallLoweringInfo &CLI,
 730           MachineBasicBlock *LandingPad);
 731
 732   // Terminator instructions.
 733   void visitRet(const ReturnInst &I);
 734   void visitBr(const BranchInst &I);
 735   void visitSwitch(const SwitchInst &I);
 736   void visitIndirectBr(const IndirectBrInst &I);
 737   void visitUnreachable(const UnreachableInst &I);
 738
 739   uint32_t getEdgeWeight(const MachineBasicBlock *Src,
 740                          const MachineBasicBlock *Dst) const;
 741   void addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst,
 742                               uint32_t Weight = 0);
 743 public:
 744   void visitSwitchCase(CaseBlock &CB,
 745                        MachineBasicBlock *SwitchBB);
 746   void visitSPDescriptorParent(StackProtectorDescriptor &SPD,
 747                                MachineBasicBlock *ParentBB);
 748   void visitSPDescriptorFailure(StackProtectorDescriptor &SPD);
 749   void visitBitTestHeader(BitTestBlock &B, MachineBasicBlock *SwitchBB);
 750   void visitBitTestCase(BitTestBlock &BB,
 751                         MachineBasicBlock* NextMBB,
 752                         uint32_t BranchWeightToNext,
 753                         unsigned Reg,
 754                         BitTestCase &B,
 755                         MachineBasicBlock *SwitchBB);
 756   void visitJumpTable(JumpTable &JT);
 757   void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH,
 758                             MachineBasicBlock *SwitchBB);
 759
 760 private:
 761   // These all get lowered before this pass.
 762   void visitInvoke(const InvokeInst &I);
 763   void visitResume(const ResumeInst &I);
 764
 765   void visitBinary(const User &I, unsigned OpCode);
 766   void visitShift(const User &I, unsigned Opcode);
 767   void visitAdd(const User &I)  { visitBinary(I, ISD::ADD); }
 768   void visitFAdd(const User &I) { visitBinary(I, ISD::FADD); }
 769   void visitSub(const User &I)  { visitBinary(I, ISD::SUB); }
 770   void visitFSub(const User &I);
 771   void visitMul(const User &I)  { visitBinary(I, ISD::MUL); }
 772   void visitFMul(const User &I) { visitBinary(I, ISD::FMUL); }
 773   void visitURem(const User &I) { visitBinary(I, ISD::UREM); }
 774   void visitSRem(const User &I) { visitBinary(I, ISD::SREM); }
 775   void visitFRem(const User &I) { visitBinary(I, ISD::FREM); }
 776   void visitUDiv(const User &I) { visitBinary(I, ISD::UDIV); }
 777   void visitSDiv(const User &I);
 778   void visitFDiv(const User &I) { visitBinary(I, ISD::FDIV); }
 779   void visitAnd (const User &I) { visitBinary(I, ISD::AND); }
 780   void visitOr  (const User &I) { visitBinary(I, ISD::OR); }
 781   void visitXor (const User &I) { visitBinary(I, ISD::XOR); }
 782   void visitShl (const User &I) { visitShift(I, ISD::SHL); }
 783   void visitLShr(const User &I) { visitShift(I, ISD::SRL); }
 784   void visitAShr(const User &I) { visitShift(I, ISD::SRA); }
 785   void visitICmp(const User &I);
 786   void visitFCmp(const User &I);
 787   // Visit the conversion instructions
 788   void visitTrunc(const User &I);
 789   void visitZExt(const User &I);
 790   void visitSExt(const User &I);
 791   void visitFPTrunc(const User &I);
 792   void visitFPExt(const User &I);
 793   void visitFPToUI(const User &I);
 794   void visitFPToSI(const User &I);
 795   void visitUIToFP(const User &I);
 796   void visitSIToFP(const User &I);
 797   void visitPtrToInt(const User &I);
 798   void visitIntToPtr(const User &I);
 799   void visitBitCast(const User &I);
 800   void visitAddrSpaceCast(const User &I);
 801
 802   void visitExtractElement(const User &I);
 803   void visitInsertElement(const User &I);
 804   void visitShuffleVector(const User &I);
 805
 806   void visitExtractValue(const ExtractValueInst &I);
 807   void visitInsertValue(const InsertValueInst &I);
 808   void visitLandingPad(const LandingPadInst &I);
 809
 810   void visitGetElementPtr(const User &I);
 811   void visitSelect(const User &I);
 812
 813   void visitAlloca(const AllocaInst &I);
 814   void visitLoad(const LoadInst &I);
 815   void visitStore(const StoreInst &I);
 816   void visitMaskedLoad(const CallInst &I);
 817   void visitMaskedStore(const CallInst &I);
 818   void visitMaskedGather(const CallInst &I);
 819   void visitMaskedScatter(const CallInst &I);
 820   void visitAtomicCmpXchg(const AtomicCmpXchgInst &I);
 821   void visitAtomicRMW(const AtomicRMWInst &I);
 822   void visitFence(const FenceInst &I);
 823   void visitPHI(const PHINode &I);
 824   void visitCall(const CallInst &I);
 825   bool visitMemCmpCall(const CallInst &I);
 826   bool visitMemChrCall(const CallInst &I);
 827   bool visitStrCpyCall(const CallInst &I, bool isStpcpy);
 828   bool visitStrCmpCall(const CallInst &I);
 829   bool visitStrLenCall(const CallInst &I);
 830   bool visitStrNLenCall(const CallInst &I);
 831   bool visitUnaryFloatCall(const CallInst &I, unsigned Opcode);
 832   bool visitBinaryFloatCall(const CallInst &I, unsigned Opcode);
 833   void visitAtomicLoad(const LoadInst &I);
 834   void visitAtomicStore(const StoreInst &I);
 835
 836   void visitInlineAsm(ImmutableCallSite CS);
 837   const char *visitIntrinsicCall(const CallInst &I, unsigned Intrinsic);
 838   void visitTargetIntrinsic(const CallInst &I, unsigned Intrinsic);
 839
 840   void visitVAStart(const CallInst &I);
 841   void visitVAArg(const VAArgInst &I);
 842   void visitVAEnd(const CallInst &I);
 843   void visitVACopy(const CallInst &I);
 844   void visitStackmap(const CallInst &I);
 845   void visitPatchpoint(ImmutableCallSite CS,
 846                        MachineBasicBlock *LandingPad = nullptr);
 847
 848   // These three are implemented in StatepointLowering.cpp
 849   void visitStatepoint(const CallInst &I);
 850   void visitGCRelocate(const CallInst &I);
 851   void visitGCResult(const CallInst &I);
 852
 853   void visitUserOp1(const Instruction &I) {
 854     llvm_unreachable("UserOp1 should not exist at instruction selection time!");
 855   }
 856   void visitUserOp2(const Instruction &I) {
 857     llvm_unreachable("UserOp2 should not exist at instruction selection time!");
 858   }
 859
 860   void processIntegerCallValue(const Instruction &I,
 861                                SDValue Value, bool IsSigned);
 862
 863   void HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB);
 864
 865   /// EmitFuncArgumentDbgValue - If V is an function argument then create
 866   /// corresponding DBG_VALUE machine instruction for it now. At the end of
 867   /// instruction selection, they will be inserted to the entry BB.
 868   bool EmitFuncArgumentDbgValue(const Value *V, DILocalVariable *Variable,
 869                                 DIExpression *Expr, DILocation *DL,
 870                                 int64_t Offset, bool IsIndirect,
 871                                 const SDValue &N);
 872
 873   /// Return the next block after MBB, or nullptr if there is none.
 874   MachineBasicBlock *NextBlock(MachineBasicBlock *MBB);
 875
 876   /// Update the DAG and DAG builder with the relevant information after
 877   /// a new root node has been created which could be a tail call.
 878   void updateDAGForMaybeTailCall(SDValue MaybeTC);
 879 };
 880
 881 /// RegsForValue - This struct represents the registers (physical or virtual)
 882 /// that a particular set of values is assigned, and the type information about
 883 /// the value. The most common situation is to represent one value at a time,
 884 /// but struct or array values are handled element-wise as multiple values.  The
 885 /// splitting of aggregates is performed recursively, so that we never have
 886 /// aggregate-typed registers. The values at this point do not necessarily have
 887 /// legal types, so each value may require one or more registers of some legal
 888 /// type.
 889 ///
 890 struct RegsForValue {
 891   /// ValueVTs - The value types of the values, which may not be legal, and
 892   /// may need be promoted or synthesized from one or more registers.
 893   ///
 894   SmallVector<EVT, 4> ValueVTs;
 895
 896   /// RegVTs - The value types of the registers. This is the same size as
 897   /// ValueVTs and it records, for each value, what the type of the assigned
 898   /// register or registers are. (Individual values are never synthesized
 899   /// from more than one type of register.)
 900   ///
 901   /// With virtual registers, the contents of RegVTs is redundant with TLI's
 902   /// getRegisterType member function, however when with physical registers
 903   /// it is necessary to have a separate record of the types.
 904   ///
 905   SmallVector<MVT, 4> RegVTs;
 906
 907   /// Regs - This list holds the registers assigned to the values.
 908   /// Each legal or promoted value requires one register, and each
 909   /// expanded value requires multiple registers.
 910   ///
 911   SmallVector<unsigned, 4> Regs;
 912
 913   RegsForValue();
 914
 915   RegsForValue(const SmallVector<unsigned, 4> &regs, MVT regvt, EVT valuevt);
 916
 917   RegsForValue(LLVMContext &Context, const TargetLowering &TLI,
 918                const DataLayout &DL, unsigned Reg, Type *Ty);
 919
 920   /// append - Add the specified values to this one.
 921   void append(const RegsForValue &RHS) {
 922     ValueVTs.append(RHS.ValueVTs.begin(), RHS.ValueVTs.end());
 923     RegVTs.append(RHS.RegVTs.begin(), RHS.RegVTs.end());
 924     Regs.append(RHS.Regs.begin(), RHS.Regs.end());
 925   }
 926
 927   /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from
 928   /// this value and returns the result as a ValueVTs value.  This uses
 929   /// Chain/Flag as the input and updates them for the output Chain/Flag.
 930   /// If the Flag pointer is NULL, no flag is used.
 931   SDValue getCopyFromRegs(SelectionDAG &DAG, FunctionLoweringInfo &FuncInfo,
 932                           SDLoc dl,
 933                           SDValue &Chain, SDValue *Flag,
 934                           const Value *V = nullptr) const;
 935
 936   /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the specified
 937   /// value into the registers specified by this object.  This uses Chain/Flag
 938   /// as the input and updates them for the output Chain/Flag.  If the Flag
 939   /// pointer is nullptr, no flag is used.  If V is not nullptr, then it is used
 940   /// in printing better diagnostic messages on error.
 941   void
 942   getCopyToRegs(SDValue Val, SelectionDAG &DAG, SDLoc dl, SDValue &Chain,
 943                 SDValue *Flag, const Value *V = nullptr,
 944                 ISD::NodeType PreferredExtendType = ISD::ANY_EXTEND) const;
 945
 946   /// AddInlineAsmOperands - Add this value to the specified inlineasm node
 947   /// operand list.  This adds the code marker, matching input operand index
 948   /// (if applicable), and includes the number of values added into it.
 949   void AddInlineAsmOperands(unsigned Kind,
 950                             bool HasMatching, unsigned MatchingIdx, SDLoc dl,
 951                             SelectionDAG &DAG,
 952                             std::vector<SDValue> &Ops) const;
 953 };
 954
 955 } // end namespace llvm
 956
 957 #endif