LLVM  6.0.0svn
SelectionDAGISel.cpp
Go to the documentation of this file.
1 //===- SelectionDAGISel.cpp - Implement the SelectionDAGISel class --------===//
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 the SelectionDAGISel class.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "ScheduleDAGSDNodes.h"
16 #include "SelectionDAGBuilder.h"
17 #include "llvm/ADT/APInt.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/None.h"
21 #include "llvm/ADT/STLExtras.h"
22 #include "llvm/ADT/SmallPtrSet.h"
23 #include "llvm/ADT/SmallSet.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/ADT/Statistic.h"
26 #include "llvm/ADT/StringRef.h"
29 #include "llvm/Analysis/CFG.h"
32 #include "llvm/CodeGen/FastISel.h"
56 #include "llvm/IR/BasicBlock.h"
57 #include "llvm/IR/Constants.h"
58 #include "llvm/IR/DataLayout.h"
60 #include "llvm/IR/DebugLoc.h"
61 #include "llvm/IR/DiagnosticInfo.h"
62 #include "llvm/IR/Dominators.h"
63 #include "llvm/IR/Function.h"
64 #include "llvm/IR/InlineAsm.h"
65 #include "llvm/IR/InstrTypes.h"
66 #include "llvm/IR/Instruction.h"
67 #include "llvm/IR/Instructions.h"
68 #include "llvm/IR/IntrinsicInst.h"
69 #include "llvm/IR/Intrinsics.h"
70 #include "llvm/IR/Metadata.h"
71 #include "llvm/IR/Type.h"
72 #include "llvm/IR/User.h"
73 #include "llvm/IR/Value.h"
74 #include "llvm/MC/MCInstrDesc.h"
75 #include "llvm/MC/MCRegisterInfo.h"
76 #include "llvm/Pass.h"
78 #include "llvm/Support/Casting.h"
79 #include "llvm/Support/CodeGen.h"
81 #include "llvm/Support/Compiler.h"
82 #include "llvm/Support/Debug.h"
84 #include "llvm/Support/KnownBits.h"
85 #include "llvm/Support/Timer.h"
91 #include <algorithm>
92 #include <cassert>
93 #include <cstdint>
94 #include <iterator>
95 #include <limits>
96 #include <memory>
97 #include <string>
98 #include <utility>
99 #include <vector>
100 
101 using namespace llvm;
102 
103 #define DEBUG_TYPE "isel"
104 
105 STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on");
106 STATISTIC(NumFastIselSuccess, "Number of instructions fast isel selected");
107 STATISTIC(NumFastIselBlocks, "Number of blocks selected entirely by fast isel");
108 STATISTIC(NumDAGBlocks, "Number of blocks selected using DAG");
109 STATISTIC(NumDAGIselRetries,"Number of times dag isel has to try another path");
110 STATISTIC(NumEntryBlocks, "Number of entry blocks encountered");
111 STATISTIC(NumFastIselFailLowerArguments,
112  "Number of entry blocks where fast isel failed to lower arguments");
113 
115  "fast-isel-abort", cl::Hidden,
116  cl::desc("Enable abort calls when \"fast\" instruction selection "
117  "fails to lower an instruction: 0 disable the abort, 1 will "
118  "abort but for args, calls and terminators, 2 will also "
119  "abort for argument lowering, and 3 will never fallback "
120  "to SelectionDAG."));
121 
123  "fast-isel-report-on-fallback", cl::Hidden,
124  cl::desc("Emit a diagnostic when \"fast\" instruction selection "
125  "falls back to SelectionDAG."));
126 
127 static cl::opt<bool>
128 UseMBPI("use-mbpi",
129  cl::desc("use Machine Branch Probability Info"),
130  cl::init(true), cl::Hidden);
131 
132 #ifndef NDEBUG
134 FilterDAGBasicBlockName("filter-view-dags", cl::Hidden,
135  cl::desc("Only display the basic block whose name "
136  "matches this for all view-*-dags options"));
137 static cl::opt<bool>
138 ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
139  cl::desc("Pop up a window to show dags before the first "
140  "dag combine pass"));
141 static cl::opt<bool>
142 ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden,
143  cl::desc("Pop up a window to show dags before legalize types"));
144 static cl::opt<bool>
145 ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
146  cl::desc("Pop up a window to show dags before legalize"));
147 static cl::opt<bool>
148 ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
149  cl::desc("Pop up a window to show dags before the second "
150  "dag combine pass"));
151 static cl::opt<bool>
152 ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden,
153  cl::desc("Pop up a window to show dags before the post legalize types"
154  " dag combine pass"));
155 static cl::opt<bool>
156 ViewISelDAGs("view-isel-dags", cl::Hidden,
157  cl::desc("Pop up a window to show isel dags as they are selected"));
158 static cl::opt<bool>
159 ViewSchedDAGs("view-sched-dags", cl::Hidden,
160  cl::desc("Pop up a window to show sched dags as they are processed"));
161 static cl::opt<bool>
162 ViewSUnitDAGs("view-sunit-dags", cl::Hidden,
163  cl::desc("Pop up a window to show SUnit dags after they are processed"));
164 #else
165 static const bool ViewDAGCombine1 = false,
166  ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false,
167  ViewDAGCombine2 = false,
168  ViewDAGCombineLT = false,
169  ViewISelDAGs = false, ViewSchedDAGs = false,
170  ViewSUnitDAGs = false;
171 #endif
172 
173 //===---------------------------------------------------------------------===//
174 ///
175 /// RegisterScheduler class - Track the registration of instruction schedulers.
176 ///
177 //===---------------------------------------------------------------------===//
179 
180 //===---------------------------------------------------------------------===//
181 ///
182 /// ISHeuristic command line option for instruction schedulers.
183 ///
184 //===---------------------------------------------------------------------===//
187 ISHeuristic("pre-RA-sched",
189  cl::desc("Instruction schedulers available (before register"
190  " allocation):"));
191 
192 static RegisterScheduler
193 defaultListDAGScheduler("default", "Best scheduler for the target",
195 
196 namespace llvm {
197 
198  //===--------------------------------------------------------------------===//
199  /// \brief This class is used by SelectionDAGISel to temporarily override
200  /// the optimization level on a per-function basis.
202  SelectionDAGISel &IS;
203  CodeGenOpt::Level SavedOptLevel;
204  bool SavedFastISel;
205 
206  public:
208  CodeGenOpt::Level NewOptLevel) : IS(ISel) {
209  SavedOptLevel = IS.OptLevel;
210  if (NewOptLevel == SavedOptLevel)
211  return;
212  IS.OptLevel = NewOptLevel;
213  IS.TM.setOptLevel(NewOptLevel);
214  DEBUG(dbgs() << "\nChanging optimization level for Function "
215  << IS.MF->getFunction().getName() << "\n");
216  DEBUG(dbgs() << "\tBefore: -O" << SavedOptLevel
217  << " ; After: -O" << NewOptLevel << "\n");
218  SavedFastISel = IS.TM.Options.EnableFastISel;
219  if (NewOptLevel == CodeGenOpt::None) {
221  DEBUG(dbgs() << "\tFastISel is "
222  << (IS.TM.Options.EnableFastISel ? "enabled" : "disabled")
223  << "\n");
224  }
225  }
226 
228  if (IS.OptLevel == SavedOptLevel)
229  return;
230  DEBUG(dbgs() << "\nRestoring optimization level for Function "
231  << IS.MF->getFunction().getName() << "\n");
232  DEBUG(dbgs() << "\tBefore: -O" << IS.OptLevel
233  << " ; After: -O" << SavedOptLevel << "\n");
234  IS.OptLevel = SavedOptLevel;
235  IS.TM.setOptLevel(SavedOptLevel);
236  IS.TM.setFastISel(SavedFastISel);
237  }
238  };
239 
240  //===--------------------------------------------------------------------===//
241  /// createDefaultScheduler - This creates an instruction scheduler appropriate
242  /// for the target.
244  CodeGenOpt::Level OptLevel) {
245  const TargetLowering *TLI = IS->TLI;
246  const TargetSubtargetInfo &ST = IS->MF->getSubtarget();
247 
248  // Try first to see if the Target has its own way of selecting a scheduler
249  if (auto *SchedulerCtor = ST.getDAGScheduler(OptLevel)) {
250  return SchedulerCtor(IS, OptLevel);
251  }
252 
253  if (OptLevel == CodeGenOpt::None ||
256  return createSourceListDAGScheduler(IS, OptLevel);
258  return createBURRListDAGScheduler(IS, OptLevel);
260  return createHybridListDAGScheduler(IS, OptLevel);
261  if (TLI->getSchedulingPreference() == Sched::VLIW)
262  return createVLIWDAGScheduler(IS, OptLevel);
264  "Unknown sched type!");
265  return createILPListDAGScheduler(IS, OptLevel);
266  }
267 
268 } // end namespace llvm
269 
270 // EmitInstrWithCustomInserter - This method should be implemented by targets
271 // that mark instructions with the 'usesCustomInserter' flag. These
272 // instructions are special in various ways, which require special support to
273 // insert. The specified MachineInstr is created but not inserted into any
274 // basic blocks, and this method is called to expand it into a sequence of
275 // instructions, potentially also creating new basic blocks and control flow.
276 // When new basic blocks are inserted and the edges from MBB to its successors
277 // are modified, the method should insert pairs of <OldSucc, NewSucc> into the
278 // DenseMap.
281  MachineBasicBlock *MBB) const {
282 #ifndef NDEBUG
283  dbgs() << "If a target marks an instruction with "
284  "'usesCustomInserter', it must implement "
285  "TargetLowering::EmitInstrWithCustomInserter!";
286 #endif
287  llvm_unreachable(nullptr);
288 }
289 
291  SDNode *Node) const {
292  assert(!MI.hasPostISelHook() &&
293  "If a target marks an instruction with 'hasPostISelHook', "
294  "it must implement TargetLowering::AdjustInstrPostInstrSelection!");
295 }
296 
297 //===----------------------------------------------------------------------===//
298 // SelectionDAGISel code
299 //===----------------------------------------------------------------------===//
300 
302  CodeGenOpt::Level OL) :
303  MachineFunctionPass(ID), TM(tm),
304  FuncInfo(new FunctionLoweringInfo()),
305  CurDAG(new SelectionDAG(tm, OL)),
306  SDB(new SelectionDAGBuilder(*CurDAG, *FuncInfo, OL)),
307  AA(), GFI(),
308  OptLevel(OL),
309  DAGSize(0) {
316  }
317 
319  delete SDB;
320  delete CurDAG;
321  delete FuncInfo;
322 }
323 
325  if (OptLevel != CodeGenOpt::None)
335 }
336 
337 /// SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that
338 /// may trap on it. In this case we have to split the edge so that the path
339 /// through the predecessor block that doesn't go to the phi block doesn't
340 /// execute the possibly trapping instruction. If available, we pass domtree
341 /// and loop info to be updated when we split critical edges. This is because
342 /// SelectionDAGISel preserves these analyses.
343 /// This is required for correctness, so it must be done at -O0.
344 ///
346  LoopInfo *LI) {
347  // Loop for blocks with phi nodes.
348  for (BasicBlock &BB : Fn) {
349  PHINode *PN = dyn_cast<PHINode>(BB.begin());
350  if (!PN) continue;
351 
352  ReprocessBlock:
353  // For each block with a PHI node, check to see if any of the input values
354  // are potentially trapping constant expressions. Constant expressions are
355  // the only potentially trapping value that can occur as the argument to a
356  // PHI.
357  for (BasicBlock::iterator I = BB.begin(); (PN = dyn_cast<PHINode>(I)); ++I)
358  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
360  if (!CE || !CE->canTrap()) continue;
361 
362  // The only case we have to worry about is when the edge is critical.
363  // Since this block has a PHI Node, we assume it has multiple input
364  // edges: check to see if the pred has multiple successors.
365  BasicBlock *Pred = PN->getIncomingBlock(i);
366  if (Pred->getTerminator()->getNumSuccessors() == 1)
367  continue;
368 
369  // Okay, we have to split this edge.
371  Pred->getTerminator(), GetSuccessorNumber(Pred, &BB),
373  goto ReprocessBlock;
374  }
375  }
376 }
377 
379  // If we already selected that function, we do not need to run SDISel.
380  if (mf.getProperties().hasProperty(
382  return false;
383  // Do some sanity-checking on the command-line options.
385  "-fast-isel-abort > 0 requires -fast-isel");
386 
387  const Function &Fn = mf.getFunction();
388  MF = &mf;
389 
390  // Reset the target options before resetting the optimization
391  // level below.
392  // FIXME: This is a horrible hack and should be processed via
393  // codegen looking at the optimization level explicitly when
394  // it wants to look at it.
396  // Reset OptLevel to None for optnone functions.
397  CodeGenOpt::Level NewOptLevel = OptLevel;
398  if (OptLevel != CodeGenOpt::None && skipFunction(Fn))
399  NewOptLevel = CodeGenOpt::None;
400  OptLevelChanger OLC(*this, NewOptLevel);
401 
404  RegInfo = &MF->getRegInfo();
405  LibInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
406  GFI = Fn.hasGC() ? &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn) : nullptr;
407  ORE = make_unique<OptimizationRemarkEmitter>(&Fn);
408  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
409  DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
410  auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
411  LoopInfo *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
412 
413  DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n");
414 
415  SplitCriticalSideEffectEdges(const_cast<Function &>(Fn), DT, LI);
416 
417  CurDAG->init(*MF, *ORE, this);
418  FuncInfo->set(Fn, *MF, CurDAG);
419 
420  // Now get the optional analyzes if we want to.
421  // This is based on the possibly changed OptLevel (after optnone is taken
422  // into account). That's unfortunate but OK because it just means we won't
423  // ask for passes that have been required anyway.
424 
426  FuncInfo->BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
427  else
428  FuncInfo->BPI = nullptr;
429 
430  if (OptLevel != CodeGenOpt::None)
431  AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
432  else
433  AA = nullptr;
434 
435  SDB->init(GFI, AA, LibInfo);
436 
437  MF->setHasInlineAsm(false);
438 
439  FuncInfo->SplitCSR = false;
440 
441  // We split CSR if the target supports it for the given function
442  // and the function has only return exits.
444  FuncInfo->SplitCSR = true;
445 
446  // Collect all the return blocks.
447  for (const BasicBlock &BB : Fn) {
448  if (!succ_empty(&BB))
449  continue;
450 
451  const TerminatorInst *Term = BB.getTerminator();
452  if (isa<UnreachableInst>(Term) || isa<ReturnInst>(Term))
453  continue;
454 
455  // Bail out if the exit block is not Return nor Unreachable.
456  FuncInfo->SplitCSR = false;
457  break;
458  }
459  }
460 
461  MachineBasicBlock *EntryMBB = &MF->front();
462  if (FuncInfo->SplitCSR)
463  // This performs initialization so lowering for SplitCSR will be correct.
464  TLI->initializeSplitCSR(EntryMBB);
465 
466  SelectAllBasicBlocks(Fn);
468  DiagnosticInfoISelFallback DiagFallback(Fn);
469  Fn.getContext().diagnose(DiagFallback);
470  }
471 
472  // If the first basic block in the function has live ins that need to be
473  // copied into vregs, emit the copies into the top of the block before
474  // emitting the code for the block.
476  RegInfo->EmitLiveInCopies(EntryMBB, TRI, *TII);
477 
478  // Insert copies in the entry block and the return blocks.
479  if (FuncInfo->SplitCSR) {
481  // Collect all the return blocks.
482  for (MachineBasicBlock &MBB : mf) {
483  if (!MBB.succ_empty())
484  continue;
485 
486  MachineBasicBlock::iterator Term = MBB.getFirstTerminator();
487  if (Term != MBB.end() && Term->isReturn()) {
488  Returns.push_back(&MBB);
489  continue;
490  }
491  }
492  TLI->insertCopiesSplitCSR(EntryMBB, Returns);
493  }
494 
496  if (!FuncInfo->ArgDbgValues.empty())
497  for (std::pair<unsigned, unsigned> LI : RegInfo->liveins())
498  if (LI.second)
499  LiveInMap.insert(LI);
500 
501  // Insert DBG_VALUE instructions for function arguments to the entry block.
502  for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; ++i) {
504  bool hasFI = MI->getOperand(0).isFI();
505  unsigned Reg =
506  hasFI ? TRI.getFrameRegister(*MF) : MI->getOperand(0).getReg();
508  EntryMBB->insert(EntryMBB->begin(), MI);
509  else {
511  if (Def) {
512  MachineBasicBlock::iterator InsertPos = Def;
513  // FIXME: VR def may not be in entry block.
514  Def->getParent()->insert(std::next(InsertPos), MI);
515  } else
516  DEBUG(dbgs() << "Dropping debug info for dead vreg"
517  << TargetRegisterInfo::virtReg2Index(Reg) << "\n");
518  }
519 
520  // If Reg is live-in then update debug info to track its copy in a vreg.
521  DenseMap<unsigned, unsigned>::iterator LDI = LiveInMap.find(Reg);
522  if (LDI != LiveInMap.end()) {
523  assert(!hasFI && "There's no handling of frame pointer updating here yet "
524  "- add if needed");
525  MachineInstr *Def = RegInfo->getVRegDef(LDI->second);
526  MachineBasicBlock::iterator InsertPos = Def;
527  const MDNode *Variable = MI->getDebugVariable();
528  const MDNode *Expr = MI->getDebugExpression();
529  DebugLoc DL = MI->getDebugLoc();
530  bool IsIndirect = MI->isIndirectDebugValue();
531  if (IsIndirect)
532  assert(MI->getOperand(1).getImm() == 0 &&
533  "DBG_VALUE with nonzero offset");
534  assert(cast<DILocalVariable>(Variable)->isValidLocationForIntrinsic(DL) &&
535  "Expected inlined-at fields to agree");
536  // Def is never a terminator here, so it is ok to increment InsertPos.
537  BuildMI(*EntryMBB, ++InsertPos, DL, TII->get(TargetOpcode::DBG_VALUE),
538  IsIndirect, LDI->second, Variable, Expr);
539 
540  // If this vreg is directly copied into an exported register then
541  // that COPY instructions also need DBG_VALUE, if it is the only
542  // user of LDI->second.
543  MachineInstr *CopyUseMI = nullptr;
545  UI = RegInfo->use_instr_begin(LDI->second),
546  E = RegInfo->use_instr_end(); UI != E; ) {
547  MachineInstr *UseMI = &*(UI++);
548  if (UseMI->isDebugValue()) continue;
549  if (UseMI->isCopy() && !CopyUseMI && UseMI->getParent() == EntryMBB) {
550  CopyUseMI = UseMI; continue;
551  }
552  // Otherwise this is another use or second copy use.
553  CopyUseMI = nullptr; break;
554  }
555  if (CopyUseMI) {
556  // Use MI's debug location, which describes where Variable was
557  // declared, rather than whatever is attached to CopyUseMI.
558  MachineInstr *NewMI =
559  BuildMI(*MF, DL, TII->get(TargetOpcode::DBG_VALUE), IsIndirect,
560  CopyUseMI->getOperand(0).getReg(), Variable, Expr);
561  MachineBasicBlock::iterator Pos = CopyUseMI;
562  EntryMBB->insertAfter(Pos, NewMI);
563  }
564  }
565  }
566 
567  // Determine if there are any calls in this machine function.
568  MachineFrameInfo &MFI = MF->getFrameInfo();
569  for (const auto &MBB : *MF) {
570  if (MFI.hasCalls() && MF->hasInlineAsm())
571  break;
572 
573  for (const auto &MI : MBB) {
574  const MCInstrDesc &MCID = TII->get(MI.getOpcode());
575  if ((MCID.isCall() && !MCID.isReturn()) ||
576  MI.isStackAligningInlineAsm()) {
577  MFI.setHasCalls(true);
578  }
579  if (MI.isInlineAsm()) {
580  MF->setHasInlineAsm(true);
581  }
582  }
583  }
584 
585  // Determine if there is a call to setjmp in the machine function.
586  MF->setExposesReturnsTwice(Fn.callsFunctionThatReturnsTwice());
587 
588  // Replace forward-declared registers with the registers containing
589  // the desired value.
590  MachineRegisterInfo &MRI = MF->getRegInfo();
593  I != E; ++I) {
594  unsigned From = I->first;
595  unsigned To = I->second;
596  // If To is also scheduled to be replaced, find what its ultimate
597  // replacement is.
598  while (true) {
600  if (J == E) break;
601  To = J->second;
602  }
603  // Make sure the new register has a sufficiently constrained register class.
606  MRI.constrainRegClass(To, MRI.getRegClass(From));
607  // Replace it.
608 
609 
610  // Replacing one register with another won't touch the kill flags.
611  // We need to conservatively clear the kill flags as a kill on the old
612  // register might dominate existing uses of the new register.
613  if (!MRI.use_empty(To))
614  MRI.clearKillFlags(From);
615  MRI.replaceRegWith(From, To);
616  }
617 
618  TLI->finalizeLowering(*MF);
619 
620  // Release function-specific state. SDB and CurDAG are already cleared
621  // at this point.
622  FuncInfo->clear();
623 
624  DEBUG(dbgs() << "*** MachineFunction at end of ISel ***\n");
625  DEBUG(MF->print(dbgs()));
626 
627  return true;
628 }
629 
633  bool ShouldAbort) {
634  // Print the function name explicitly if we don't have a debug location (which
635  // makes the diagnostic less useful) or if we're going to emit a raw error.
636  if (!R.getLocation().isValid() || ShouldAbort)
637  R << (" (in function: " + MF.getName() + ")").str();
638 
639  if (ShouldAbort)
641 
642  ORE.emit(R);
643 }
644 
645 void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,
647  bool &HadTailCall) {
648  // Allow creating illegal types during DAG building for the basic block.
650 
651  // Lower the instructions. If a call is emitted as a tail call, cease emitting
652  // nodes for this block.
653  for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I) {
654  if (!ElidedArgCopyInstrs.count(&*I))
655  SDB->visit(*I);
656  }
657 
658  // Make sure the root of the DAG is up-to-date.
660  HadTailCall = SDB->HasTailCall;
661  SDB->clear();
662 
663  // Final step, emit the lowered DAG as machine code.
664  CodeGenAndEmitDAG();
665 }
666 
667 void SelectionDAGISel::ComputeLiveOutVRegInfo() {
668  SmallPtrSet<SDNode*, 16> VisitedNodes;
669  SmallVector<SDNode*, 128> Worklist;
670 
671  Worklist.push_back(CurDAG->getRoot().getNode());
672 
673  KnownBits Known;
674 
675  do {
676  SDNode *N = Worklist.pop_back_val();
677 
678  // If we've already seen this node, ignore it.
679  if (!VisitedNodes.insert(N).second)
680  continue;
681 
682  // Otherwise, add all chain operands to the worklist.
683  for (const SDValue &Op : N->op_values())
684  if (Op.getValueType() == MVT::Other)
685  Worklist.push_back(Op.getNode());
686 
687  // If this is a CopyToReg with a vreg dest, process it.
688  if (N->getOpcode() != ISD::CopyToReg)
689  continue;
690 
691  unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();
693  continue;
694 
695  // Ignore non-scalar or non-integer values.
696  SDValue Src = N->getOperand(2);
697  EVT SrcVT = Src.getValueType();
698  if (!SrcVT.isInteger() || SrcVT.isVector())
699  continue;
700 
701  unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);
702  CurDAG->computeKnownBits(Src, Known);
703  FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, Known);
704  } while (!Worklist.empty());
705 }
706 
707 void SelectionDAGISel::CodeGenAndEmitDAG() {
708  StringRef GroupName = "sdag";
709  StringRef GroupDescription = "Instruction Selection and Scheduling";
710  std::string BlockName;
711  int BlockNumber = -1;
712  (void)BlockNumber;
713  bool MatchFilterBB = false; (void)MatchFilterBB;
714 
715  // Pre-type legalization allow creation of any node types.
717 
718 #ifndef NDEBUG
719  MatchFilterBB = (FilterDAGBasicBlockName.empty() ||
722 #endif
723 #ifdef NDEBUG
724  if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs ||
727 #endif
728  {
729  BlockNumber = FuncInfo->MBB->getNumber();
730  BlockName =
731  (MF->getName() + ":" + FuncInfo->MBB->getBasicBlock()->getName()).str();
732  }
733  DEBUG(dbgs() << "Initial selection DAG: " << printMBBReference(*FuncInfo->MBB)
734  << " '" << BlockName << "'\n";
735  CurDAG->dump());
736 
737  if (ViewDAGCombine1 && MatchFilterBB)
738  CurDAG->viewGraph("dag-combine1 input for " + BlockName);
739 
740  // Run the DAG combiner in pre-legalize mode.
741  {
742  NamedRegionTimer T("combine1", "DAG Combining 1", GroupName,
743  GroupDescription, TimePassesIsEnabled);
745  }
746 
747  DEBUG(dbgs() << "Optimized lowered selection DAG: "
748  << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
749  << "'\n";
750  CurDAG->dump());
751 
752  // Second step, hack on the DAG until it only uses operations and types that
753  // the target supports.
754  if (ViewLegalizeTypesDAGs && MatchFilterBB)
755  CurDAG->viewGraph("legalize-types input for " + BlockName);
756 
757  bool Changed;
758  {
759  NamedRegionTimer T("legalize_types", "Type Legalization", GroupName,
760  GroupDescription, TimePassesIsEnabled);
761  Changed = CurDAG->LegalizeTypes();
762  }
763 
764  DEBUG(dbgs() << "Type-legalized selection DAG: "
765  << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
766  << "'\n";
767  CurDAG->dump());
768 
769  // Only allow creation of legal node types.
771 
772  if (Changed) {
773  if (ViewDAGCombineLT && MatchFilterBB)
774  CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
775 
776  // Run the DAG combiner in post-type-legalize mode.
777  {
778  NamedRegionTimer T("combine_lt", "DAG Combining after legalize types",
779  GroupName, GroupDescription, TimePassesIsEnabled);
781  }
782 
783  DEBUG(dbgs() << "Optimized type-legalized selection DAG: "
784  << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
785  << "'\n";
786  CurDAG->dump());
787  }
788 
789  {
790  NamedRegionTimer T("legalize_vec", "Vector Legalization", GroupName,
791  GroupDescription, TimePassesIsEnabled);
792  Changed = CurDAG->LegalizeVectors();
793  }
794 
795  if (Changed) {
796  DEBUG(dbgs() << "Vector-legalized selection DAG: "
797  << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
798  << "'\n";
799  CurDAG->dump());
800 
801  {
802  NamedRegionTimer T("legalize_types2", "Type Legalization 2", GroupName,
803  GroupDescription, TimePassesIsEnabled);
805  }
806 
807  DEBUG(dbgs() << "Vector/type-legalized selection DAG: "
808  << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
809  << "'\n";
810  CurDAG->dump());
811 
812  if (ViewDAGCombineLT && MatchFilterBB)
813  CurDAG->viewGraph("dag-combine-lv input for " + BlockName);
814 
815  // Run the DAG combiner in post-type-legalize mode.
816  {
817  NamedRegionTimer T("combine_lv", "DAG Combining after legalize vectors",
818  GroupName, GroupDescription, TimePassesIsEnabled);
820  }
821 
822  DEBUG(dbgs() << "Optimized vector-legalized selection DAG: "
823  << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
824  << "'\n";
825  CurDAG->dump());
826  }
827 
828  if (ViewLegalizeDAGs && MatchFilterBB)
829  CurDAG->viewGraph("legalize input for " + BlockName);
830 
831  {
832  NamedRegionTimer T("legalize", "DAG Legalization", GroupName,
833  GroupDescription, TimePassesIsEnabled);
834  CurDAG->Legalize();
835  }
836 
837  DEBUG(dbgs() << "Legalized selection DAG: "
838  << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
839  << "'\n";
840  CurDAG->dump());
841 
842  if (ViewDAGCombine2 && MatchFilterBB)
843  CurDAG->viewGraph("dag-combine2 input for " + BlockName);
844 
845  // Run the DAG combiner in post-legalize mode.
846  {
847  NamedRegionTimer T("combine2", "DAG Combining 2", GroupName,
848  GroupDescription, TimePassesIsEnabled);
850  }
851 
852  DEBUG(dbgs() << "Optimized legalized selection DAG: "
853  << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
854  << "'\n";
855  CurDAG->dump());
856 
857  if (OptLevel != CodeGenOpt::None)
858  ComputeLiveOutVRegInfo();
859 
860  if (ViewISelDAGs && MatchFilterBB)
861  CurDAG->viewGraph("isel input for " + BlockName);
862 
863  // Third, instruction select all of the operations to machine code, adding the
864  // code to the MachineBasicBlock.
865  {
866  NamedRegionTimer T("isel", "Instruction Selection", GroupName,
867  GroupDescription, TimePassesIsEnabled);
868  DoInstructionSelection();
869  }
870 
871  DEBUG(dbgs() << "Selected selection DAG: "
872  << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
873  << "'\n";
874  CurDAG->dump());
875 
876  if (ViewSchedDAGs && MatchFilterBB)
877  CurDAG->viewGraph("scheduler input for " + BlockName);
878 
879  // Schedule machine code.
880  ScheduleDAGSDNodes *Scheduler = CreateScheduler();
881  {
882  NamedRegionTimer T("sched", "Instruction Scheduling", GroupName,
883  GroupDescription, TimePassesIsEnabled);
884  Scheduler->Run(CurDAG, FuncInfo->MBB);
885  }
886 
887  if (ViewSUnitDAGs && MatchFilterBB)
888  Scheduler->viewGraph();
889 
890  // Emit machine code to BB. This can change 'BB' to the last block being
891  // inserted into.
892  MachineBasicBlock *FirstMBB = FuncInfo->MBB, *LastMBB;
893  {
894  NamedRegionTimer T("emit", "Instruction Creation", GroupName,
895  GroupDescription, TimePassesIsEnabled);
896 
897  // FuncInfo->InsertPt is passed by reference and set to the end of the
898  // scheduled instructions.
899  LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(FuncInfo->InsertPt);
900  }
901 
902  // If the block was split, make sure we update any references that are used to
903  // update PHI nodes later on.
904  if (FirstMBB != LastMBB)
905  SDB->UpdateSplitBlock(FirstMBB, LastMBB);
906 
907  // Free the scheduler state.
908  {
909  NamedRegionTimer T("cleanup", "Instruction Scheduling Cleanup", GroupName,
910  GroupDescription, TimePassesIsEnabled);
911  delete Scheduler;
912  }
913 
914  // Free the SelectionDAG state, now that we're finished with it.
915  CurDAG->clear();
916 }
917 
918 namespace {
919 
920 /// ISelUpdater - helper class to handle updates of the instruction selection
921 /// graph.
922 class ISelUpdater : public SelectionDAG::DAGUpdateListener {
923  SelectionDAG::allnodes_iterator &ISelPosition;
924 
925 public:
926  ISelUpdater(SelectionDAG &DAG, SelectionDAG::allnodes_iterator &isp)
927  : SelectionDAG::DAGUpdateListener(DAG), ISelPosition(isp) {}
928 
929  /// NodeDeleted - Handle nodes deleted from the graph. If the node being
930  /// deleted is the current ISelPosition node, update ISelPosition.
931  ///
932  void NodeDeleted(SDNode *N, SDNode *E) override {
933  if (ISelPosition == SelectionDAG::allnodes_iterator(N))
934  ++ISelPosition;
935  }
936 };
937 
938 } // end anonymous namespace
939 
940 void SelectionDAGISel::DoInstructionSelection() {
941  DEBUG(dbgs() << "===== Instruction selection begins: "
942  << printMBBReference(*FuncInfo->MBB) << " '"
943  << FuncInfo->MBB->getName() << "'\n");
944 
946 
947  // Select target instructions for the DAG.
948  {
949  // Number all nodes with a topological order and set DAGSize.
951 
952  // Create a dummy node (which is not added to allnodes), that adds
953  // a reference to the root node, preventing it from being deleted,
954  // and tracking any changes of the root.
957  ++ISelPosition;
958 
959  // Make sure that ISelPosition gets properly updated when nodes are deleted
960  // in calls made from this function.
961  ISelUpdater ISU(*CurDAG, ISelPosition);
962 
963  // The AllNodes list is now topological-sorted. Visit the
964  // nodes by starting at the end of the list (the root of the
965  // graph) and preceding back toward the beginning (the entry
966  // node).
967  while (ISelPosition != CurDAG->allnodes_begin()) {
968  SDNode *Node = &*--ISelPosition;
969  // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
970  // but there are currently some corner cases that it misses. Also, this
971  // makes it theoretically possible to disable the DAGCombiner.
972  if (Node->use_empty())
973  continue;
974 
975  // When we are using non-default rounding modes or FP exception behavior
976  // FP operations are represented by StrictFP pseudo-operations. They
977  // need to be simplified here so that the target-specific instruction
978  // selectors know how to handle them.
979  //
980  // If the current node is a strict FP pseudo-op, the isStrictFPOp()
981  // function will provide the corresponding normal FP opcode to which the
982  // node should be mutated.
983  //
984  // FIXME: The backends need a way to handle FP constraints.
985  if (Node->isStrictFPOpcode())
986  Node = CurDAG->mutateStrictFPToFP(Node);
987 
988  Select(Node);
989  }
990 
991  CurDAG->setRoot(Dummy.getValue());
992  }
993 
994  DEBUG(dbgs() << "===== Instruction selection ends:\n");
995 
997 }
998 
1000  for (const User *U : CPI->users()) {
1001  if (const IntrinsicInst *EHPtrCall = dyn_cast<IntrinsicInst>(U)) {
1002  Intrinsic::ID IID = EHPtrCall->getIntrinsicID();
1003  if (IID == Intrinsic::eh_exceptionpointer ||
1004  IID == Intrinsic::eh_exceptioncode)
1005  return true;
1006  }
1007  }
1008  return false;
1009 }
1010 
1011 /// PrepareEHLandingPad - Emit an EH_LABEL, set up live-in registers, and
1012 /// do other setup for EH landing-pad blocks.
1013 bool SelectionDAGISel::PrepareEHLandingPad() {
1014  MachineBasicBlock *MBB = FuncInfo->MBB;
1015  const Constant *PersonalityFn = FuncInfo->Fn->getPersonalityFn();
1016  const BasicBlock *LLVMBB = MBB->getBasicBlock();
1017  const TargetRegisterClass *PtrRC =
1019 
1020  // Catchpads have one live-in register, which typically holds the exception
1021  // pointer or code.
1022  if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHI())) {
1023  if (hasExceptionPointerOrCodeUser(CPI)) {
1024  // Get or create the virtual register to hold the pointer or code. Mark
1025  // the live in physreg and copy into the vreg.
1026  MCPhysReg EHPhysReg = TLI->getExceptionPointerRegister(PersonalityFn);
1027  assert(EHPhysReg && "target lacks exception pointer register");
1028  MBB->addLiveIn(EHPhysReg);
1029  unsigned VReg = FuncInfo->getCatchPadExceptionPointerVReg(CPI, PtrRC);
1031  TII->get(TargetOpcode::COPY), VReg)
1032  .addReg(EHPhysReg, RegState::Kill);
1033  }
1034  return true;
1035  }
1036 
1037  if (!LLVMBB->isLandingPad())
1038  return true;
1039 
1040  // Add a label to mark the beginning of the landing pad. Deletion of the
1041  // landing pad can thus be detected via the MachineModuleInfo.
1042  MCSymbol *Label = MF->addLandingPad(MBB);
1043 
1044  // Assign the call site to the landing pad's begin label.
1046 
1047  const MCInstrDesc &II = TII->get(TargetOpcode::EH_LABEL);
1048  BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II)
1049  .addSym(Label);
1050 
1051  // Mark exception register as live in.
1052  if (unsigned Reg = TLI->getExceptionPointerRegister(PersonalityFn))
1054 
1055  // Mark exception selector register as live in.
1056  if (unsigned Reg = TLI->getExceptionSelectorRegister(PersonalityFn))
1058 
1059  return true;
1060 }
1061 
1062 /// isFoldedOrDeadInstruction - Return true if the specified instruction is
1063 /// side-effect free and is either dead or folded into a generated instruction.
1064 /// Return false if it needs to be emitted.
1067  return !I->mayWriteToMemory() && // Side-effecting instructions aren't folded.
1068  !isa<TerminatorInst>(I) && // Terminators aren't folded.
1069  !isa<DbgInfoIntrinsic>(I) && // Debug instructions aren't folded.
1070  !I->isEHPad() && // EH pad instructions aren't folded.
1071  !FuncInfo->isExportedInst(I); // Exported instrs must be computed.
1072 }
1073 
1074 /// Set up SwiftErrorVals by going through the function. If the function has
1075 /// swifterror argument, it will be the first entry.
1076 static void setupSwiftErrorVals(const Function &Fn, const TargetLowering *TLI,
1078  if (!TLI->supportSwiftError())
1079  return;
1080 
1081  FuncInfo->SwiftErrorVals.clear();
1082  FuncInfo->SwiftErrorVRegDefMap.clear();
1083  FuncInfo->SwiftErrorVRegUpwardsUse.clear();
1084  FuncInfo->SwiftErrorVRegDefUses.clear();
1085  FuncInfo->SwiftErrorArg = nullptr;
1086 
1087  // Check if function has a swifterror argument.
1088  bool HaveSeenSwiftErrorArg = false;
1089  for (Function::const_arg_iterator AI = Fn.arg_begin(), AE = Fn.arg_end();
1090  AI != AE; ++AI)
1091  if (AI->hasSwiftErrorAttr()) {
1092  assert(!HaveSeenSwiftErrorArg &&
1093  "Must have only one swifterror parameter");
1094  (void)HaveSeenSwiftErrorArg; // silence warning.
1095  HaveSeenSwiftErrorArg = true;
1096  FuncInfo->SwiftErrorArg = &*AI;
1097  FuncInfo->SwiftErrorVals.push_back(&*AI);
1098  }
1099 
1100  for (const auto &LLVMBB : Fn)
1101  for (const auto &Inst : LLVMBB) {
1102  if (const AllocaInst *Alloca = dyn_cast<AllocaInst>(&Inst))
1103  if (Alloca->isSwiftError())
1104  FuncInfo->SwiftErrorVals.push_back(Alloca);
1105  }
1106 }
1107 
1109  FastISel *FastIS,
1110  const TargetLowering *TLI,
1111  const TargetInstrInfo *TII,
1113  if (!TLI->supportSwiftError())
1114  return;
1115 
1116  // We only need to do this when we have swifterror parameter or swifterror
1117  // alloc.
1118  if (FuncInfo->SwiftErrorVals.empty())
1119  return;
1120 
1121  assert(FuncInfo->MBB == &*FuncInfo->MF->begin() &&
1122  "expected to insert into entry block");
1123  auto &DL = FuncInfo->MF->getDataLayout();
1124  auto const *RC = TLI->getRegClassFor(TLI->getPointerTy(DL));
1125  for (const auto *SwiftErrorVal : FuncInfo->SwiftErrorVals) {
1126  // We will always generate a copy from the argument. It is always used at
1127  // least by the 'return' of the swifterror.
1128  if (FuncInfo->SwiftErrorArg && FuncInfo->SwiftErrorArg == SwiftErrorVal)
1129  continue;
1130  unsigned VReg = FuncInfo->MF->getRegInfo().createVirtualRegister(RC);
1131  // Assign Undef to Vreg. We construct MI directly to make sure it works
1132  // with FastISel.
1133  BuildMI(*FuncInfo->MBB, FuncInfo->MBB->getFirstNonPHI(),
1134  SDB->getCurDebugLoc(), TII->get(TargetOpcode::IMPLICIT_DEF),
1135  VReg);
1136 
1137  // Keep FastIS informed about the value we just inserted.
1138  if (FastIS)
1139  FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
1140 
1141  FuncInfo->setCurrentSwiftErrorVReg(FuncInfo->MBB, SwiftErrorVal, VReg);
1142  }
1143 }
1144 
1145 /// Collect llvm.dbg.declare information. This is done after argument lowering
1146 /// in case the declarations refer to arguments.
1148  MachineFunction *MF = FuncInfo->MF;
1149  const DataLayout &DL = MF->getDataLayout();
1150  for (const BasicBlock &BB : *FuncInfo->Fn) {
1151  for (const Instruction &I : BB) {
1152  const DbgDeclareInst *DI = dyn_cast<DbgDeclareInst>(&I);
1153  if (!DI)
1154  continue;
1155 
1156  assert(DI->getVariable() && "Missing variable");
1157  assert(DI->getDebugLoc() && "Missing location");
1158  const Value *Address = DI->getAddress();
1159  if (!Address)
1160  continue;
1161 
1162  // Look through casts and constant offset GEPs. These mostly come from
1163  // inalloca.
1164  APInt Offset(DL.getTypeSizeInBits(Address->getType()), 0);
1165  Address = Address->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
1166 
1167  // Check if the variable is a static alloca or a byval or inalloca
1168  // argument passed in memory. If it is not, then we will ignore this
1169  // intrinsic and handle this during isel like dbg.value.
1170  int FI = std::numeric_limits<int>::max();
1171  if (const auto *AI = dyn_cast<AllocaInst>(Address)) {
1172  auto SI = FuncInfo->StaticAllocaMap.find(AI);
1173  if (SI != FuncInfo->StaticAllocaMap.end())
1174  FI = SI->second;
1175  } else if (const auto *Arg = dyn_cast<Argument>(Address))
1176  FI = FuncInfo->getArgumentFrameIndex(Arg);
1177 
1178  if (FI == std::numeric_limits<int>::max())
1179  continue;
1180 
1181  DIExpression *Expr = DI->getExpression();
1182  if (Offset.getBoolValue())
1184  Offset.getZExtValue());
1185  MF->setVariableDbgInfo(DI->getVariable(), Expr, FI, DI->getDebugLoc());
1186  }
1187  }
1188 }
1189 
1190 /// Propagate swifterror values through the machine function CFG.
1192  auto *TLI = FuncInfo->TLI;
1193  if (!TLI->supportSwiftError())
1194  return;
1195 
1196  // We only need to do this when we have swifterror parameter or swifterror
1197  // alloc.
1198  if (FuncInfo->SwiftErrorVals.empty())
1199  return;
1200 
1201  // For each machine basic block in reverse post order.
1203  for (MachineBasicBlock *MBB : RPOT) {
1204  // For each swifterror value in the function.
1205  for(const auto *SwiftErrorVal : FuncInfo->SwiftErrorVals) {
1206  auto Key = std::make_pair(MBB, SwiftErrorVal);
1207  auto UUseIt = FuncInfo->SwiftErrorVRegUpwardsUse.find(Key);
1208  auto VRegDefIt = FuncInfo->SwiftErrorVRegDefMap.find(Key);
1209  bool UpwardsUse = UUseIt != FuncInfo->SwiftErrorVRegUpwardsUse.end();
1210  unsigned UUseVReg = UpwardsUse ? UUseIt->second : 0;
1211  bool DownwardDef = VRegDefIt != FuncInfo->SwiftErrorVRegDefMap.end();
1212  assert(!(UpwardsUse && !DownwardDef) &&
1213  "We can't have an upwards use but no downwards def");
1214 
1215  // If there is no upwards exposed use and an entry for the swifterror in
1216  // the def map for this value we don't need to do anything: We already
1217  // have a downward def for this basic block.
1218  if (!UpwardsUse && DownwardDef)
1219  continue;
1220 
1221  // Otherwise we either have an upwards exposed use vreg that we need to
1222  // materialize or need to forward the downward def from predecessors.
1223 
1224  // Check whether we have a single vreg def from all predecessors.
1225  // Otherwise we need a phi.
1228  for (auto *Pred : MBB->predecessors()) {
1229  if (!Visited.insert(Pred).second)
1230  continue;
1231  VRegs.push_back(std::make_pair(
1232  Pred, FuncInfo->getOrCreateSwiftErrorVReg(Pred, SwiftErrorVal)));
1233  if (Pred != MBB)
1234  continue;
1235  // We have a self-edge.
1236  // If there was no upwards use in this basic block there is now one: the
1237  // phi needs to use it self.
1238  if (!UpwardsUse) {
1239  UpwardsUse = true;
1240  UUseIt = FuncInfo->SwiftErrorVRegUpwardsUse.find(Key);
1241  assert(UUseIt != FuncInfo->SwiftErrorVRegUpwardsUse.end());
1242  UUseVReg = UUseIt->second;
1243  }
1244  }
1245 
1246  // We need a phi node if we have more than one predecessor with different
1247  // downward defs.
1248  bool needPHI =
1249  VRegs.size() >= 1 &&
1250  std::find_if(
1251  VRegs.begin(), VRegs.end(),
1252  [&](const std::pair<const MachineBasicBlock *, unsigned> &V)
1253  -> bool { return V.second != VRegs[0].second; }) !=
1254  VRegs.end();
1255 
1256  // If there is no upwards exposed used and we don't need a phi just
1257  // forward the swifterror vreg from the predecessor(s).
1258  if (!UpwardsUse && !needPHI) {
1259  assert(!VRegs.empty() &&
1260  "No predecessors? The entry block should bail out earlier");
1261  // Just forward the swifterror vreg from the predecessor(s).
1262  FuncInfo->setCurrentSwiftErrorVReg(MBB, SwiftErrorVal, VRegs[0].second);
1263  continue;
1264  }
1265 
1266  auto DLoc = isa<Instruction>(SwiftErrorVal)
1267  ? dyn_cast<Instruction>(SwiftErrorVal)->getDebugLoc()
1268  : DebugLoc();
1269  const auto *TII = FuncInfo->MF->getSubtarget().getInstrInfo();
1270 
1271  // If we don't need a phi create a copy to the upward exposed vreg.
1272  if (!needPHI) {
1273  assert(UpwardsUse);
1274  assert(!VRegs.empty() &&
1275  "No predecessors? Is the Calling Convention correct?");
1276  unsigned DestReg = UUseVReg;
1277  BuildMI(*MBB, MBB->getFirstNonPHI(), DLoc, TII->get(TargetOpcode::COPY),
1278  DestReg)
1279  .addReg(VRegs[0].second);
1280  continue;
1281  }
1282 
1283  // We need a phi: if there is an upwards exposed use we already have a
1284  // destination virtual register number otherwise we generate a new one.
1285  auto &DL = FuncInfo->MF->getDataLayout();
1286  auto const *RC = TLI->getRegClassFor(TLI->getPointerTy(DL));
1287  unsigned PHIVReg =
1288  UpwardsUse ? UUseVReg
1289  : FuncInfo->MF->getRegInfo().createVirtualRegister(RC);
1290  MachineInstrBuilder SwiftErrorPHI =
1291  BuildMI(*MBB, MBB->getFirstNonPHI(), DLoc,
1292  TII->get(TargetOpcode::PHI), PHIVReg);
1293  for (auto BBRegPair : VRegs) {
1294  SwiftErrorPHI.addReg(BBRegPair.second).addMBB(BBRegPair.first);
1295  }
1296 
1297  // We did not have a definition in this block before: store the phi's vreg
1298  // as this block downward exposed def.
1299  if (!UpwardsUse)
1300  FuncInfo->setCurrentSwiftErrorVReg(MBB, SwiftErrorVal, PHIVReg);
1301  }
1302  }
1303 }
1304 
1309  if (!TLI->supportSwiftError() || FuncInfo->SwiftErrorVals.empty())
1310  return;
1311 
1312  // Iterator over instructions and assign vregs to swifterror defs and uses.
1313  for (auto It = Begin; It != End; ++It) {
1314  ImmutableCallSite CS(&*It);
1315  if (CS) {
1316  // A call-site with a swifterror argument is both use and def.
1317  const Value *SwiftErrorAddr = nullptr;
1318  for (auto &Arg : CS.args()) {
1319  if (!Arg->isSwiftError())
1320  continue;
1321  // Use of swifterror.
1322  assert(!SwiftErrorAddr && "Cannot have multiple swifterror arguments");
1323  SwiftErrorAddr = &*Arg;
1324  assert(SwiftErrorAddr->isSwiftError() &&
1325  "Must have a swifterror value argument");
1326  unsigned VReg; bool CreatedReg;
1327  std::tie(VReg, CreatedReg) = FuncInfo->getOrCreateSwiftErrorVRegUseAt(
1328  &*It, FuncInfo->MBB, SwiftErrorAddr);
1329  assert(CreatedReg);
1330  }
1331  if (!SwiftErrorAddr)
1332  continue;
1333 
1334  // Def of swifterror.
1335  unsigned VReg; bool CreatedReg;
1336  std::tie(VReg, CreatedReg) =
1337  FuncInfo->getOrCreateSwiftErrorVRegDefAt(&*It);
1338  assert(CreatedReg);
1339  FuncInfo->setCurrentSwiftErrorVReg(FuncInfo->MBB, SwiftErrorAddr, VReg);
1340 
1341  // A load is a use.
1342  } else if (const LoadInst *LI = dyn_cast<const LoadInst>(&*It)) {
1343  const Value *V = LI->getOperand(0);
1344  if (!V->isSwiftError())
1345  continue;
1346 
1347  unsigned VReg; bool CreatedReg;
1348  std::tie(VReg, CreatedReg) =
1349  FuncInfo->getOrCreateSwiftErrorVRegUseAt(LI, FuncInfo->MBB, V);
1350  assert(CreatedReg);
1351 
1352  // A store is a def.
1353  } else if (const StoreInst *SI = dyn_cast<const StoreInst>(&*It)) {
1354  const Value *SwiftErrorAddr = SI->getOperand(1);
1355  if (!SwiftErrorAddr->isSwiftError())
1356  continue;
1357 
1358  // Def of swifterror.
1359  unsigned VReg; bool CreatedReg;
1360  std::tie(VReg, CreatedReg) =
1361  FuncInfo->getOrCreateSwiftErrorVRegDefAt(&*It);
1362  assert(CreatedReg);
1363  FuncInfo->setCurrentSwiftErrorVReg(FuncInfo->MBB, SwiftErrorAddr, VReg);
1364 
1365  // A return in a swiferror returning function is a use.
1366  } else if (const ReturnInst *R = dyn_cast<const ReturnInst>(&*It)) {
1367  const Function *F = R->getParent()->getParent();
1368  if(!F->getAttributes().hasAttrSomewhere(Attribute::SwiftError))
1369  continue;
1370 
1371  unsigned VReg; bool CreatedReg;
1372  std::tie(VReg, CreatedReg) = FuncInfo->getOrCreateSwiftErrorVRegUseAt(
1373  R, FuncInfo->MBB, FuncInfo->SwiftErrorArg);
1374  assert(CreatedReg);
1375  }
1376  }
1377 }
1378 
1379 void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) {
1380  FastISelFailed = false;
1381  // Initialize the Fast-ISel state, if needed.
1382  FastISel *FastIS = nullptr;
1384  FastIS = TLI->createFastISel(*FuncInfo, LibInfo);
1385 
1387 
1389 
1390  // Lower arguments up front. An RPO iteration always visits the entry block
1391  // first.
1392  assert(*RPOT.begin() == &Fn.getEntryBlock());
1393  ++NumEntryBlocks;
1394 
1395  // Set up FuncInfo for ISel. Entry blocks never have PHIs.
1398 
1399  if (!FastIS) {
1400  LowerArguments(Fn);
1401  } else {
1402  // See if fast isel can lower the arguments.
1403  FastIS->startNewBlock();
1404  if (!FastIS->lowerArguments()) {
1405  FastISelFailed = true;
1406  // Fast isel failed to lower these arguments
1407  ++NumFastIselFailLowerArguments;
1408 
1409  OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1410  Fn.getSubprogram(),
1411  &Fn.getEntryBlock());
1412  R << "FastISel didn't lower all arguments: "
1413  << ore::NV("Prototype", Fn.getType());
1415 
1416  // Use SelectionDAG argument lowering
1417  LowerArguments(Fn);
1419  SDB->clear();
1420  CodeGenAndEmitDAG();
1421  }
1422 
1423  // If we inserted any instructions at the beginning, make a note of
1424  // where they are, so we can be sure to emit subsequent instructions
1425  // after them.
1426  if (FuncInfo->InsertPt != FuncInfo->MBB->begin())
1427  FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
1428  else
1429  FastIS->setLastLocalValue(nullptr);
1430  }
1432 
1434 
1435  // Iterate over all basic blocks in the function.
1436  for (const BasicBlock *LLVMBB : RPOT) {
1437  if (OptLevel != CodeGenOpt::None) {
1438  bool AllPredsVisited = true;
1439  for (const_pred_iterator PI = pred_begin(LLVMBB), PE = pred_end(LLVMBB);
1440  PI != PE; ++PI) {
1441  if (!FuncInfo->VisitedBBs.count(*PI)) {
1442  AllPredsVisited = false;
1443  break;
1444  }
1445  }
1446 
1447  if (AllPredsVisited) {
1448  for (BasicBlock::const_iterator I = LLVMBB->begin();
1449  const PHINode *PN = dyn_cast<PHINode>(I); ++I)
1451  } else {
1452  for (BasicBlock::const_iterator I = LLVMBB->begin();
1453  const PHINode *PN = dyn_cast<PHINode>(I); ++I)
1455  }
1456 
1457  FuncInfo->VisitedBBs.insert(LLVMBB);
1458  }
1459 
1460  BasicBlock::const_iterator const Begin =
1461  LLVMBB->getFirstNonPHI()->getIterator();
1462  BasicBlock::const_iterator const End = LLVMBB->end();
1464 
1465  FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB];
1466  if (!FuncInfo->MBB)
1467  continue; // Some blocks like catchpads have no code or MBB.
1468 
1469  // Insert new instructions after any phi or argument setup code.
1470  FuncInfo->InsertPt = FuncInfo->MBB->end();
1471 
1472  // Setup an EH landing-pad block.
1475  if (LLVMBB->isEHPad())
1476  if (!PrepareEHLandingPad())
1477  continue;
1478 
1479  // Before doing SelectionDAG ISel, see if FastISel has been requested.
1480  if (FastIS) {
1481  if (LLVMBB != &Fn.getEntryBlock())
1482  FastIS->startNewBlock();
1483 
1484  unsigned NumFastIselRemaining = std::distance(Begin, End);
1485 
1486  // Pre-assign swifterror vregs.
1487  preassignSwiftErrorRegs(TLI, FuncInfo, Begin, End);
1488 
1489  // Do FastISel on as many instructions as possible.
1490  for (; BI != Begin; --BI) {
1491  const Instruction *Inst = &*std::prev(BI);
1492 
1493  // If we no longer require this instruction, skip it.
1494  if (isFoldedOrDeadInstruction(Inst, FuncInfo) ||
1495  ElidedArgCopyInstrs.count(Inst)) {
1496  --NumFastIselRemaining;
1497  continue;
1498  }
1499 
1500  // Bottom-up: reset the insert pos at the top, after any local-value
1501  // instructions.
1502  FastIS->recomputeInsertPt();
1503 
1504  // Try to select the instruction with FastISel.
1505  if (FastIS->selectInstruction(Inst)) {
1506  --NumFastIselRemaining;
1507  ++NumFastIselSuccess;
1508  // If fast isel succeeded, skip over all the folded instructions, and
1509  // then see if there is a load right before the selected instructions.
1510  // Try to fold the load if so.
1511  const Instruction *BeforeInst = Inst;
1512  while (BeforeInst != &*Begin) {
1513  BeforeInst = &*std::prev(BasicBlock::const_iterator(BeforeInst));
1514  if (!isFoldedOrDeadInstruction(BeforeInst, FuncInfo))
1515  break;
1516  }
1517  if (BeforeInst != Inst && isa<LoadInst>(BeforeInst) &&
1518  BeforeInst->hasOneUse() &&
1519  FastIS->tryToFoldLoad(cast<LoadInst>(BeforeInst), Inst)) {
1520  // If we succeeded, don't re-select the load.
1521  BI = std::next(BasicBlock::const_iterator(BeforeInst));
1522  --NumFastIselRemaining;
1523  ++NumFastIselSuccess;
1524  }
1525  continue;
1526  }
1527 
1528  FastISelFailed = true;
1529 
1530  // Then handle certain instructions as single-LLVM-Instruction blocks.
1531  // We cannot separate out GCrelocates to their own blocks since we need
1532  // to keep track of gc-relocates for a particular gc-statepoint. This is
1533  // done by SelectionDAGBuilder::LowerAsSTATEPOINT, called before
1534  // visitGCRelocate.
1535  if (isa<CallInst>(Inst) && !isStatepoint(Inst) && !isGCRelocate(Inst)) {
1536  OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1537  Inst->getDebugLoc(), LLVMBB);
1538 
1539  R << "FastISel missed call";
1540 
1541  if (R.isEnabled() || EnableFastISelAbort) {
1542  std::string InstStrStorage;
1543  raw_string_ostream InstStr(InstStrStorage);
1544  InstStr << *Inst;
1545 
1546  R << ": " << InstStr.str();
1547  }
1548 
1550 
1551  if (!Inst->getType()->isVoidTy() && !Inst->getType()->isTokenTy() &&
1552  !Inst->use_empty()) {
1553  unsigned &R = FuncInfo->ValueMap[Inst];
1554  if (!R)
1555  R = FuncInfo->CreateRegs(Inst->getType());
1556  }
1557 
1558  bool HadTailCall = false;
1560  SelectBasicBlock(Inst->getIterator(), BI, HadTailCall);
1561 
1562  // If the call was emitted as a tail call, we're done with the block.
1563  // We also need to delete any previously emitted instructions.
1564  if (HadTailCall) {
1565  FastIS->removeDeadCode(SavedInsertPt, FuncInfo->MBB->end());
1566  --BI;
1567  break;
1568  }
1569 
1570  // Recompute NumFastIselRemaining as Selection DAG instruction
1571  // selection may have handled the call, input args, etc.
1572  unsigned RemainingNow = std::distance(Begin, BI);
1573  NumFastIselFailures += NumFastIselRemaining - RemainingNow;
1574  NumFastIselRemaining = RemainingNow;
1575  continue;
1576  }
1577 
1578  OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1579  Inst->getDebugLoc(), LLVMBB);
1580 
1581  bool ShouldAbort = EnableFastISelAbort;
1582  if (isa<TerminatorInst>(Inst)) {
1583  // Use a different message for terminator misses.
1584  R << "FastISel missed terminator";
1585  // Don't abort for terminator unless the level is really high
1586  ShouldAbort = (EnableFastISelAbort > 2);
1587  } else {
1588  R << "FastISel missed";
1589  }
1590 
1591  if (R.isEnabled() || EnableFastISelAbort) {
1592  std::string InstStrStorage;
1593  raw_string_ostream InstStr(InstStrStorage);
1594  InstStr << *Inst;
1595  R << ": " << InstStr.str();
1596  }
1597 
1598  reportFastISelFailure(*MF, *ORE, R, ShouldAbort);
1599 
1600  NumFastIselFailures += NumFastIselRemaining;
1601  break;
1602  }
1603 
1604  FastIS->recomputeInsertPt();
1605  }
1606 
1607  if (getAnalysis<StackProtector>().shouldEmitSDCheck(*LLVMBB)) {
1608  bool FunctionBasedInstrumentation =
1610  SDB->SPDescriptor.initialize(LLVMBB, FuncInfo->MBBMap[LLVMBB],
1611  FunctionBasedInstrumentation);
1612  }
1613 
1614  if (Begin != BI)
1615  ++NumDAGBlocks;
1616  else
1617  ++NumFastIselBlocks;
1618 
1619  if (Begin != BI) {
1620  // Run SelectionDAG instruction selection on the remainder of the block
1621  // not handled by FastISel. If FastISel is not run, this is the entire
1622  // block.
1623  bool HadTailCall;
1624  SelectBasicBlock(Begin, BI, HadTailCall);
1625 
1626  // But if FastISel was run, we already selected some of the block.
1627  // If we emitted a tail-call, we need to delete any previously emitted
1628  // instruction that follows it.
1629  if (HadTailCall && FuncInfo->InsertPt != FuncInfo->MBB->end())
1631  }
1632 
1633  FinishBasicBlock();
1634  FuncInfo->PHINodesToUpdate.clear();
1635  ElidedArgCopyInstrs.clear();
1636  }
1637 
1639 
1640  delete FastIS;
1642  SDB->SPDescriptor.resetPerFunctionState();
1643 }
1644 
1645 /// Given that the input MI is before a partial terminator sequence TSeq, return
1646 /// true if M + TSeq also a partial terminator sequence.
1647 ///
1648 /// A Terminator sequence is a sequence of MachineInstrs which at this point in
1649 /// lowering copy vregs into physical registers, which are then passed into
1650 /// terminator instructors so we can satisfy ABI constraints. A partial
1651 /// terminator sequence is an improper subset of a terminator sequence (i.e. it
1652 /// may be the whole terminator sequence).
1654  // If we do not have a copy or an implicit def, we return true if and only if
1655  // MI is a debug value.
1656  if (!MI.isCopy() && !MI.isImplicitDef())
1657  // Sometimes DBG_VALUE MI sneak in between the copies from the vregs to the
1658  // physical registers if there is debug info associated with the terminator
1659  // of our mbb. We want to include said debug info in our terminator
1660  // sequence, so we return true in that case.
1661  return MI.isDebugValue();
1662 
1663  // We have left the terminator sequence if we are not doing one of the
1664  // following:
1665  //
1666  // 1. Copying a vreg into a physical register.
1667  // 2. Copying a vreg into a vreg.
1668  // 3. Defining a register via an implicit def.
1669 
1670  // OPI should always be a register definition...
1672  if (!OPI->isReg() || !OPI->isDef())
1673  return false;
1674 
1675  // Defining any register via an implicit def is always ok.
1676  if (MI.isImplicitDef())
1677  return true;
1678 
1679  // Grab the copy source...
1681  ++OPI2;
1682  assert(OPI2 != MI.operands_end()
1683  && "Should have a copy implying we should have 2 arguments.");
1684 
1685  // Make sure that the copy dest is not a vreg when the copy source is a
1686  // physical register.
1687  if (!OPI2->isReg() ||
1690  return false;
1691 
1692  return true;
1693 }
1694 
1695 /// Find the split point at which to splice the end of BB into its success stack
1696 /// protector check machine basic block.
1697 ///
1698 /// On many platforms, due to ABI constraints, terminators, even before register
1699 /// allocation, use physical registers. This creates an issue for us since
1700 /// physical registers at this point can not travel across basic
1701 /// blocks. Luckily, selectiondag always moves physical registers into vregs
1702 /// when they enter functions and moves them through a sequence of copies back
1703 /// into the physical registers right before the terminator creating a
1704 /// ``Terminator Sequence''. This function is searching for the beginning of the
1705 /// terminator sequence so that we can ensure that we splice off not just the
1706 /// terminator, but additionally the copies that move the vregs into the
1707 /// physical registers.
1711  //
1712  if (SplitPoint == BB->begin())
1713  return SplitPoint;
1714 
1715  MachineBasicBlock::iterator Start = BB->begin();
1716  MachineBasicBlock::iterator Previous = SplitPoint;
1717  --Previous;
1718 
1719  while (MIIsInTerminatorSequence(*Previous)) {
1720  SplitPoint = Previous;
1721  if (Previous == Start)
1722  break;
1723  --Previous;
1724  }
1725 
1726  return SplitPoint;
1727 }
1728 
1729 void
1730 SelectionDAGISel::FinishBasicBlock() {
1731  DEBUG(dbgs() << "Total amount of phi nodes to update: "
1732  << FuncInfo->PHINodesToUpdate.size() << "\n";
1733  for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i)
1734  dbgs() << "Node " << i << " : ("
1735  << FuncInfo->PHINodesToUpdate[i].first
1736  << ", " << FuncInfo->PHINodesToUpdate[i].second << ")\n");
1737 
1738  // Next, now that we know what the last MBB the LLVM BB expanded is, update
1739  // PHI nodes in successors.
1740  for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) {
1742  assert(PHI->isPHI() &&
1743  "This is not a machine PHI node that we are updating!");
1744  if (!FuncInfo->MBB->isSuccessor(PHI->getParent()))
1745  continue;
1746  PHI.addReg(FuncInfo->PHINodesToUpdate[i].second).addMBB(FuncInfo->MBB);
1747  }
1748 
1749  // Handle stack protector.
1750  if (SDB->SPDescriptor.shouldEmitFunctionBasedCheckStackProtector()) {
1751  // The target provides a guard check function. There is no need to
1752  // generate error handling code or to split current basic block.
1753  MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
1754 
1755  // Add load and check to the basicblock.
1756  FuncInfo->MBB = ParentMBB;
1757  FuncInfo->InsertPt =
1760  CurDAG->setRoot(SDB->getRoot());
1761  SDB->clear();
1762  CodeGenAndEmitDAG();
1763 
1764  // Clear the Per-BB State.
1765  SDB->SPDescriptor.resetPerBBState();
1766  } else if (SDB->SPDescriptor.shouldEmitStackProtector()) {
1767  MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
1768  MachineBasicBlock *SuccessMBB = SDB->SPDescriptor.getSuccessMBB();
1769 
1770  // Find the split point to split the parent mbb. At the same time copy all
1771  // physical registers used in the tail of parent mbb into virtual registers
1772  // before the split point and back into physical registers after the split
1773  // point. This prevents us needing to deal with Live-ins and many other
1774  // register allocation issues caused by us splitting the parent mbb. The
1775  // register allocator will clean up said virtual copies later on.
1776  MachineBasicBlock::iterator SplitPoint =
1778 
1779  // Splice the terminator of ParentMBB into SuccessMBB.
1780  SuccessMBB->splice(SuccessMBB->end(), ParentMBB,
1781  SplitPoint,
1782  ParentMBB->end());
1783 
1784  // Add compare/jump on neq/jump to the parent BB.
1785  FuncInfo->MBB = ParentMBB;
1786  FuncInfo->InsertPt = ParentMBB->end();
1788  CurDAG->setRoot(SDB->getRoot());
1789  SDB->clear();
1790  CodeGenAndEmitDAG();
1791 
1792  // CodeGen Failure MBB if we have not codegened it yet.
1793  MachineBasicBlock *FailureMBB = SDB->SPDescriptor.getFailureMBB();
1794  if (FailureMBB->empty()) {
1795  FuncInfo->MBB = FailureMBB;
1796  FuncInfo->InsertPt = FailureMBB->end();
1798  CurDAG->setRoot(SDB->getRoot());
1799  SDB->clear();
1800  CodeGenAndEmitDAG();
1801  }
1802 
1803  // Clear the Per-BB State.
1804  SDB->SPDescriptor.resetPerBBState();
1805  }
1806 
1807  // Lower each BitTestBlock.
1808  for (auto &BTB : SDB->BitTestCases) {
1809  // Lower header first, if it wasn't already lowered
1810  if (!BTB.Emitted) {
1811  // Set the current basic block to the mbb we wish to insert the code into
1812  FuncInfo->MBB = BTB.Parent;
1813  FuncInfo->InsertPt = FuncInfo->MBB->end();
1814  // Emit the code
1816  CurDAG->setRoot(SDB->getRoot());
1817  SDB->clear();
1818  CodeGenAndEmitDAG();
1819  }
1820 
1821  BranchProbability UnhandledProb = BTB.Prob;
1822  for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; ++j) {
1823  UnhandledProb -= BTB.Cases[j].ExtraProb;
1824  // Set the current basic block to the mbb we wish to insert the code into
1825  FuncInfo->MBB = BTB.Cases[j].ThisBB;
1826  FuncInfo->InsertPt = FuncInfo->MBB->end();
1827  // Emit the code
1828 
1829  // If all cases cover a contiguous range, it is not necessary to jump to
1830  // the default block after the last bit test fails. This is because the
1831  // range check during bit test header creation has guaranteed that every
1832  // case here doesn't go outside the range. In this case, there is no need
1833  // to perform the last bit test, as it will always be true. Instead, make
1834  // the second-to-last bit-test fall through to the target of the last bit
1835  // test, and delete the last bit test.
1836 
1837  MachineBasicBlock *NextMBB;
1838  if (BTB.ContiguousRange && j + 2 == ej) {
1839  // Second-to-last bit-test with contiguous range: fall through to the
1840  // target of the final bit test.
1841  NextMBB = BTB.Cases[j + 1].TargetBB;
1842  } else if (j + 1 == ej) {
1843  // For the last bit test, fall through to Default.
1844  NextMBB = BTB.Default;
1845  } else {
1846  // Otherwise, fall through to the next bit test.
1847  NextMBB = BTB.Cases[j + 1].ThisBB;
1848  }
1849 
1850  SDB->visitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j],
1851  FuncInfo->MBB);
1852 
1853  CurDAG->setRoot(SDB->getRoot());
1854  SDB->clear();
1855  CodeGenAndEmitDAG();
1856 
1857  if (BTB.ContiguousRange && j + 2 == ej) {
1858  // Since we're not going to use the final bit test, remove it.
1859  BTB.Cases.pop_back();
1860  break;
1861  }
1862  }
1863 
1864  // Update PHI Nodes
1865  for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
1866  pi != pe; ++pi) {
1867  MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
1868  MachineBasicBlock *PHIBB = PHI->getParent();
1869  assert(PHI->isPHI() &&
1870  "This is not a machine PHI node that we are updating!");
1871  // This is "default" BB. We have two jumps to it. From "header" BB and
1872  // from last "case" BB, unless the latter was skipped.
1873  if (PHIBB == BTB.Default) {
1874  PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(BTB.Parent);
1875  if (!BTB.ContiguousRange) {
1876  PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)
1877  .addMBB(BTB.Cases.back().ThisBB);
1878  }
1879  }
1880  // One of "cases" BB.
1881  for (unsigned j = 0, ej = BTB.Cases.size();
1882  j != ej; ++j) {
1883  MachineBasicBlock* cBB = BTB.Cases[j].ThisBB;
1884  if (cBB->isSuccessor(PHIBB))
1885  PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(cBB);
1886  }
1887  }
1888  }
1889  SDB->BitTestCases.clear();
1890 
1891  // If the JumpTable record is filled in, then we need to emit a jump table.
1892  // Updating the PHI nodes is tricky in this case, since we need to determine
1893  // whether the PHI is a successor of the range check MBB or the jump table MBB
1894  for (unsigned i = 0, e = SDB->JTCases.size(); i != e; ++i) {
1895  // Lower header first, if it wasn't already lowered
1896  if (!SDB->JTCases[i].first.Emitted) {
1897  // Set the current basic block to the mbb we wish to insert the code into
1898  FuncInfo->MBB = SDB->JTCases[i].first.HeaderBB;
1899  FuncInfo->InsertPt = FuncInfo->MBB->end();
1900  // Emit the code
1901  SDB->visitJumpTableHeader(SDB->JTCases[i].second, SDB->JTCases[i].first,
1902  FuncInfo->MBB);
1903  CurDAG->setRoot(SDB->getRoot());
1904  SDB->clear();
1905  CodeGenAndEmitDAG();
1906  }
1907 
1908  // Set the current basic block to the mbb we wish to insert the code into
1909  FuncInfo->MBB = SDB->JTCases[i].second.MBB;
1910  FuncInfo->InsertPt = FuncInfo->MBB->end();
1911  // Emit the code
1912  SDB->visitJumpTable(SDB->JTCases[i].second);
1913  CurDAG->setRoot(SDB->getRoot());
1914  SDB->clear();
1915  CodeGenAndEmitDAG();
1916 
1917  // Update PHI Nodes
1918  for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
1919  pi != pe; ++pi) {
1920  MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
1921  MachineBasicBlock *PHIBB = PHI->getParent();
1922  assert(PHI->isPHI() &&
1923  "This is not a machine PHI node that we are updating!");
1924  // "default" BB. We can go there only from header BB.
1925  if (PHIBB == SDB->JTCases[i].second.Default)
1926  PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)
1927  .addMBB(SDB->JTCases[i].first.HeaderBB);
1928  // JT BB. Just iterate over successors here
1929  if (FuncInfo->MBB->isSuccessor(PHIBB))
1930  PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(FuncInfo->MBB);
1931  }
1932  }
1933  SDB->JTCases.clear();
1934 
1935  // If we generated any switch lowering information, build and codegen any
1936  // additional DAGs necessary.
1937  for (unsigned i = 0, e = SDB->SwitchCases.size(); i != e; ++i) {
1938  // Set the current basic block to the mbb we wish to insert the code into
1939  FuncInfo->MBB = SDB->SwitchCases[i].ThisBB;
1940  FuncInfo->InsertPt = FuncInfo->MBB->end();
1941 
1942  // Determine the unique successors.
1944  Succs.push_back(SDB->SwitchCases[i].TrueBB);
1945  if (SDB->SwitchCases[i].TrueBB != SDB->SwitchCases[i].FalseBB)
1946  Succs.push_back(SDB->SwitchCases[i].FalseBB);
1947 
1948  // Emit the code. Note that this could result in FuncInfo->MBB being split.
1950  CurDAG->setRoot(SDB->getRoot());
1951  SDB->clear();
1952  CodeGenAndEmitDAG();
1953 
1954  // Remember the last block, now that any splitting is done, for use in
1955  // populating PHI nodes in successors.
1956  MachineBasicBlock *ThisBB = FuncInfo->MBB;
1957 
1958  // Handle any PHI nodes in successors of this chunk, as if we were coming
1959  // from the original BB before switch expansion. Note that PHI nodes can
1960  // occur multiple times in PHINodesToUpdate. We have to be very careful to
1961  // handle them the right number of times.
1962  for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1963  FuncInfo->MBB = Succs[i];
1964  FuncInfo->InsertPt = FuncInfo->MBB->end();
1965  // FuncInfo->MBB may have been removed from the CFG if a branch was
1966  // constant folded.
1967  if (ThisBB->isSuccessor(FuncInfo->MBB)) {
1969  MBBI = FuncInfo->MBB->begin(), MBBE = FuncInfo->MBB->end();
1970  MBBI != MBBE && MBBI->isPHI(); ++MBBI) {
1971  MachineInstrBuilder PHI(*MF, MBBI);
1972  // This value for this PHI node is recorded in PHINodesToUpdate.
1973  for (unsigned pn = 0; ; ++pn) {
1974  assert(pn != FuncInfo->PHINodesToUpdate.size() &&
1975  "Didn't find PHI entry!");
1976  if (FuncInfo->PHINodesToUpdate[pn].first == PHI) {
1977  PHI.addReg(FuncInfo->PHINodesToUpdate[pn].second).addMBB(ThisBB);
1978  break;
1979  }
1980  }
1981  }
1982  }
1983  }
1984  }
1985  SDB->SwitchCases.clear();
1986 }
1987 
1988 /// Create the scheduler. If a specific scheduler was specified
1989 /// via the SchedulerRegistry, use it, otherwise select the
1990 /// one preferred by the target.
1991 ///
1992 ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {
1993  return ISHeuristic(this, OptLevel);
1994 }
1995 
1996 //===----------------------------------------------------------------------===//
1997 // Helper functions used by the generated instruction selector.
1998 //===----------------------------------------------------------------------===//
1999 // Calls to these methods are generated by tblgen.
2000 
2001 /// CheckAndMask - The isel is trying to match something like (and X, 255). If
2002 /// the dag combiner simplified the 255, we still want to match. RHS is the
2003 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
2004 /// specified in the .td file (e.g. 255).
2006  int64_t DesiredMaskS) const {
2007  const APInt &ActualMask = RHS->getAPIntValue();
2008  const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
2009 
2010  // If the actual mask exactly matches, success!
2011  if (ActualMask == DesiredMask)
2012  return true;
2013 
2014  // If the actual AND mask is allowing unallowed bits, this doesn't match.
2015  if (ActualMask.intersects(~DesiredMask))
2016  return false;
2017 
2018  // Otherwise, the DAG Combiner may have proven that the value coming in is
2019  // either already zero or is not demanded. Check for known zero input bits.
2020  APInt NeededMask = DesiredMask & ~ActualMask;
2021  if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
2022  return true;
2023 
2024  // TODO: check to see if missing bits are just not demanded.
2025 
2026  // Otherwise, this pattern doesn't match.
2027  return false;
2028 }
2029 
2030 /// CheckOrMask - The isel is trying to match something like (or X, 255). If
2031 /// the dag combiner simplified the 255, we still want to match. RHS is the
2032 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
2033 /// specified in the .td file (e.g. 255).
2035  int64_t DesiredMaskS) const {
2036  const APInt &ActualMask = RHS->getAPIntValue();
2037  const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
2038 
2039  // If the actual mask exactly matches, success!
2040  if (ActualMask == DesiredMask)
2041  return true;
2042 
2043  // If the actual AND mask is allowing unallowed bits, this doesn't match.
2044  if (ActualMask.intersects(~DesiredMask))
2045  return false;
2046 
2047  // Otherwise, the DAG Combiner may have proven that the value coming in is
2048  // either already zero or is not demanded. Check for known zero input bits.
2049  APInt NeededMask = DesiredMask & ~ActualMask;
2050 
2051  KnownBits Known;
2052  CurDAG->computeKnownBits(LHS, Known);
2053 
2054  // If all the missing bits in the or are already known to be set, match!
2055  if (NeededMask.isSubsetOf(Known.One))
2056  return true;
2057 
2058  // TODO: check to see if missing bits are just not demanded.
2059 
2060  // Otherwise, this pattern doesn't match.
2061  return false;
2062 }
2063 
2064 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
2065 /// by tblgen. Others should not call it.
2067  const SDLoc &DL) {
2068  std::vector<SDValue> InOps;
2069  std::swap(InOps, Ops);
2070 
2071  Ops.push_back(InOps[InlineAsm::Op_InputChain]); // 0
2072  Ops.push_back(InOps[InlineAsm::Op_AsmString]); // 1
2073  Ops.push_back(InOps[InlineAsm::Op_MDNode]); // 2, !srcloc
2074  Ops.push_back(InOps[InlineAsm::Op_ExtraInfo]); // 3 (SideEffect, AlignStack)
2075 
2076  unsigned i = InlineAsm::Op_FirstOperand, e = InOps.size();
2077  if (InOps[e-1].getValueType() == MVT::Glue)
2078  --e; // Don't process a glue operand if it is here.
2079 
2080  while (i != e) {
2081  unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue();
2082  if (!InlineAsm::isMemKind(Flags)) {
2083  // Just skip over this operand, copying the operands verbatim.
2084  Ops.insert(Ops.end(), InOps.begin()+i,
2085  InOps.begin()+i+InlineAsm::getNumOperandRegisters(Flags) + 1);
2086  i += InlineAsm::getNumOperandRegisters(Flags) + 1;
2087  } else {
2089  "Memory operand with multiple values?");
2090 
2091  unsigned TiedToOperand;
2092  if (InlineAsm::isUseOperandTiedToDef(Flags, TiedToOperand)) {
2093  // We need the constraint ID from the operand this is tied to.
2094  unsigned CurOp = InlineAsm::Op_FirstOperand;
2095  Flags = cast<ConstantSDNode>(InOps[CurOp])->getZExtValue();
2096  for (; TiedToOperand; --TiedToOperand) {
2097  CurOp += InlineAsm::getNumOperandRegisters(Flags)+1;
2098  Flags = cast<ConstantSDNode>(InOps[CurOp])->getZExtValue();
2099  }
2100  }
2101 
2102  // Otherwise, this is a memory operand. Ask the target to select it.
2103  std::vector<SDValue> SelOps;
2104  unsigned ConstraintID = InlineAsm::getMemoryConstraintID(Flags);
2105  if (SelectInlineAsmMemoryOperand(InOps[i+1], ConstraintID, SelOps))
2106  report_fatal_error("Could not match memory address. Inline asm"
2107  " failure!");
2108 
2109  // Add this to the output node.
2110  unsigned NewFlags =
2112  NewFlags = InlineAsm::getFlagWordForMem(NewFlags, ConstraintID);
2113  Ops.push_back(CurDAG->getTargetConstant(NewFlags, DL, MVT::i32));
2114  Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
2115  i += 2;
2116  }
2117  }
2118 
2119  // Add the glue input back if present.
2120  if (e != InOps.size())
2121  Ops.push_back(InOps.back());
2122 }
2123 
2124 /// findGlueUse - Return use of MVT::Glue value produced by the specified
2125 /// SDNode.
2126 ///
2128  unsigned FlagResNo = N->getNumValues()-1;
2129  for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
2130  SDUse &Use = I.getUse();
2131  if (Use.getResNo() == FlagResNo)
2132  return Use.getUser();
2133  }
2134  return nullptr;
2135 }
2136 
2137 /// findNonImmUse - Return true if "Use" is a non-immediate use of "Def".
2138 /// This function iteratively traverses up the operand chain, ignoring
2139 /// certain nodes.
2140 static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse,
2141  SDNode *Root, SmallPtrSetImpl<SDNode*> &Visited,
2142  bool IgnoreChains) {
2143  // The NodeID's are given uniques ID's where a node ID is guaranteed to be
2144  // greater than all of its (recursive) operands. If we scan to a point where
2145  // 'use' is smaller than the node we're scanning for, then we know we will
2146  // never find it.
2147  //
2148  // The Use may be -1 (unassigned) if it is a newly allocated node. This can
2149  // happen because we scan down to newly selected nodes in the case of glue
2150  // uses.
2151  std::vector<SDNode *> WorkList;
2152  WorkList.push_back(Use);
2153 
2154  while (!WorkList.empty()) {
2155  Use = WorkList.back();
2156  WorkList.pop_back();
2157  if (Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1)
2158  continue;
2159 
2160  // Don't revisit nodes if we already scanned it and didn't fail, we know we
2161  // won't fail if we scan it again.
2162  if (!Visited.insert(Use).second)
2163  continue;
2164 
2165  for (const SDValue &Op : Use->op_values()) {
2166  // Ignore chain uses, they are validated by HandleMergeInputChains.
2167  if (Op.getValueType() == MVT::Other && IgnoreChains)
2168  continue;
2169 
2170  SDNode *N = Op.getNode();
2171  if (N == Def) {
2172  if (Use == ImmedUse || Use == Root)
2173  continue; // We are not looking for immediate use.
2174  assert(N != Root);
2175  return true;
2176  }
2177 
2178  // Traverse up the operand chain.
2179  WorkList.push_back(N);
2180  }
2181  }
2182  return false;
2183 }
2184 
2185 /// IsProfitableToFold - Returns true if it's profitable to fold the specific
2186 /// operand node N of U during instruction selection that starts at Root.
2188  SDNode *Root) const {
2189  if (OptLevel == CodeGenOpt::None) return false;
2190  return N.hasOneUse();
2191 }
2192 
2193 /// IsLegalToFold - Returns true if the specific operand node N of
2194 /// U can be folded during instruction selection that starts at Root.
2197  bool IgnoreChains) {
2198  if (OptLevel == CodeGenOpt::None) return false;
2199 
2200  // If Root use can somehow reach N through a path that that doesn't contain
2201  // U then folding N would create a cycle. e.g. In the following
2202  // diagram, Root can reach N through X. If N is folded into into Root, then
2203  // X is both a predecessor and a successor of U.
2204  //
2205  // [N*] //
2206  // ^ ^ //
2207  // / \ //
2208  // [U*] [X]? //
2209  // ^ ^ //
2210  // \ / //
2211  // \ / //
2212  // [Root*] //
2213  //
2214  // * indicates nodes to be folded together.
2215  //
2216  // If Root produces glue, then it gets (even more) interesting. Since it
2217  // will be "glued" together with its glue use in the scheduler, we need to
2218  // check if it might reach N.
2219  //
2220  // [N*] //
2221  // ^ ^ //
2222  // / \ //
2223  // [U*] [X]? //
2224  // ^ ^ //
2225  // \ \ //
2226  // \ | //
2227  // [Root*] | //
2228  // ^ | //
2229  // f | //
2230  // | / //
2231  // [Y] / //
2232  // ^ / //
2233  // f / //
2234  // | / //
2235  // [GU] //
2236  //
2237  // If GU (glue use) indirectly reaches N (the load), and Root folds N
2238  // (call it Fold), then X is a predecessor of GU and a successor of
2239  // Fold. But since Fold and GU are glued together, this will create
2240  // a cycle in the scheduling graph.
2241 
2242  // If the node has glue, walk down the graph to the "lowest" node in the
2243  // glueged set.
2244  EVT VT = Root->getValueType(Root->getNumValues()-1);
2245  while (VT == MVT::Glue) {
2246  SDNode *GU = findGlueUse(Root);
2247  if (!GU)
2248  break;
2249  Root = GU;
2250  VT = Root->getValueType(Root->getNumValues()-1);
2251 
2252  // If our query node has a glue result with a use, we've walked up it. If
2253  // the user (which has already been selected) has a chain or indirectly uses
2254  // the chain, our WalkChainUsers predicate will not consider it. Because of
2255  // this, we cannot ignore chains in this predicate.
2256  IgnoreChains = false;
2257  }
2258 
2259  SmallPtrSet<SDNode*, 16> Visited;
2260  return !findNonImmUse(Root, N.getNode(), U, Root, Visited, IgnoreChains);
2261 }
2262 
2263 void SelectionDAGISel::Select_INLINEASM(SDNode *N) {
2264  SDLoc DL(N);
2265 
2266  std::vector<SDValue> Ops(N->op_begin(), N->op_end());
2268 
2269  const EVT VTs[] = {MVT::Other, MVT::Glue};
2270  SDValue New = CurDAG->getNode(ISD::INLINEASM, DL, VTs, Ops);
2271  New->setNodeId(-1);
2272  ReplaceUses(N, New.getNode());
2273  CurDAG->RemoveDeadNode(N);
2274 }
2275 
2276 void SelectionDAGISel::Select_READ_REGISTER(SDNode *Op) {
2277  SDLoc dl(Op);
2279  const MDString *RegStr = dyn_cast<MDString>(MD->getMD()->getOperand(0));
2280  unsigned Reg =
2281  TLI->getRegisterByName(RegStr->getString().data(), Op->getValueType(0),
2282  *CurDAG);
2283  SDValue New = CurDAG->getCopyFromReg(
2284  Op->getOperand(0), dl, Reg, Op->getValueType(0));
2285  New->setNodeId(-1);
2286  ReplaceUses(Op, New.getNode());
2287  CurDAG->RemoveDeadNode(Op);
2288 }
2289 
2290 void SelectionDAGISel::Select_WRITE_REGISTER(SDNode *Op) {
2291  SDLoc dl(Op);
2293  const MDString *RegStr = dyn_cast<MDString>(MD->getMD()->getOperand(0));
2294  unsigned Reg = TLI->getRegisterByName(RegStr->getString().data(),
2295  Op->getOperand(2).getValueType(),
2296  *CurDAG);
2297  SDValue New = CurDAG->getCopyToReg(
2298  Op->getOperand(0), dl, Reg, Op->getOperand(2));
2299  New->setNodeId(-1);
2300  ReplaceUses(Op, New.getNode());
2301  CurDAG->RemoveDeadNode(Op);
2302 }
2303 
2304 void SelectionDAGISel::Select_UNDEF(SDNode *N) {
2305  CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF, N->getValueType(0));
2306 }
2307 
2308 /// GetVBR - decode a vbr encoding whose top bit is set.
2309 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline uint64_t
2310 GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {
2311  assert(Val >= 128 && "Not a VBR");
2312  Val &= 127; // Remove first vbr bit.
2313 
2314  unsigned Shift = 7;
2315  uint64_t NextBits;
2316  do {
2317  NextBits = MatcherTable[Idx++];
2318  Val |= (NextBits&127) << Shift;
2319  Shift += 7;
2320  } while (NextBits & 128);
2321 
2322  return Val;
2323 }
2324 
2325 /// When a match is complete, this method updates uses of interior chain results
2326 /// to use the new results.
2327 void SelectionDAGISel::UpdateChains(
2328  SDNode *NodeToMatch, SDValue InputChain,
2329  SmallVectorImpl<SDNode *> &ChainNodesMatched, bool isMorphNodeTo) {
2330  SmallVector<SDNode*, 4> NowDeadNodes;
2331 
2332  // Now that all the normal results are replaced, we replace the chain and
2333  // glue results if present.
2334  if (!ChainNodesMatched.empty()) {
2335  assert(InputChain.getNode() &&
2336  "Matched input chains but didn't produce a chain");
2337  // Loop over all of the nodes we matched that produced a chain result.
2338  // Replace all the chain results with the final chain we ended up with.
2339  for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2340  SDNode *ChainNode = ChainNodesMatched[i];
2341  // If ChainNode is null, it's because we replaced it on a previous
2342  // iteration and we cleared it out of the map. Just skip it.
2343  if (!ChainNode)
2344  continue;
2345 
2346  assert(ChainNode->getOpcode() != ISD::DELETED_NODE &&
2347  "Deleted node left in chain");
2348 
2349  // Don't replace the results of the root node if we're doing a
2350  // MorphNodeTo.
2351  if (ChainNode == NodeToMatch && isMorphNodeTo)
2352  continue;
2353 
2354  SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);
2355  if (ChainVal.getValueType() == MVT::Glue)
2356  ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
2357  assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
2359  *CurDAG, [&](SDNode *N, SDNode *E) {
2360  std::replace(ChainNodesMatched.begin(), ChainNodesMatched.end(), N,
2361  static_cast<SDNode *>(nullptr));
2362  });
2363  CurDAG->ReplaceAllUsesOfValueWith(ChainVal, InputChain);
2364 
2365  // If the node became dead and we haven't already seen it, delete it.
2366  if (ChainNode != NodeToMatch && ChainNode->use_empty() &&
2367  !std::count(NowDeadNodes.begin(), NowDeadNodes.end(), ChainNode))
2368  NowDeadNodes.push_back(ChainNode);
2369  }
2370  }
2371 
2372  if (!NowDeadNodes.empty())
2373  CurDAG->RemoveDeadNodes(NowDeadNodes);
2374 
2375  DEBUG(dbgs() << "ISEL: Match complete!\n");
2376 }
2377 
2382 };
2383 
2384 /// WalkChainUsers - Walk down the users of the specified chained node that is
2385 /// part of the pattern we're matching, looking at all of the users we find.
2386 /// This determines whether something is an interior node, whether we have a
2387 /// non-pattern node in between two pattern nodes (which prevent folding because
2388 /// it would induce a cycle) and whether we have a TokenFactor node sandwiched
2389 /// between pattern nodes (in which case the TF becomes part of the pattern).
2390 ///
2391 /// The walk we do here is guaranteed to be small because we quickly get down to
2392 /// already selected nodes "below" us.
2393 static ChainResult
2394 WalkChainUsers(const SDNode *ChainedNode,
2395  SmallVectorImpl<SDNode *> &ChainedNodesInPattern,
2396  DenseMap<const SDNode *, ChainResult> &TokenFactorResult,
2397  SmallVectorImpl<SDNode *> &InteriorChainedNodes) {
2398  ChainResult Result = CR_Simple;
2399 
2400  for (SDNode::use_iterator UI = ChainedNode->use_begin(),
2401  E = ChainedNode->use_end(); UI != E; ++UI) {
2402  // Make sure the use is of the chain, not some other value we produce.
2403  if (UI.getUse().getValueType() != MVT::Other) continue;
2404 
2405  SDNode *User = *UI;
2406 
2407  if (User->getOpcode() == ISD::HANDLENODE) // Root of the graph.
2408  continue;
2409 
2410  // If we see an already-selected machine node, then we've gone beyond the
2411  // pattern that we're selecting down into the already selected chunk of the
2412  // DAG.
2413  unsigned UserOpcode = User->getOpcode();
2414  if (User->isMachineOpcode() ||
2415  UserOpcode == ISD::CopyToReg ||
2416  UserOpcode == ISD::CopyFromReg ||
2417  UserOpcode == ISD::INLINEASM ||
2418  UserOpcode == ISD::EH_LABEL ||
2419  UserOpcode == ISD::LIFETIME_START ||
2420  UserOpcode == ISD::LIFETIME_END) {
2421  // If their node ID got reset to -1 then they've already been selected.
2422  // Treat them like a MachineOpcode.
2423  if (User->getNodeId() == -1)
2424  continue;
2425  }
2426 
2427  // If we have a TokenFactor, we handle it specially.
2428  if (User->getOpcode() != ISD::TokenFactor) {
2429  // If the node isn't a token factor and isn't part of our pattern, then it
2430  // must be a random chained node in between two nodes we're selecting.
2431  // This happens when we have something like:
2432  // x = load ptr
2433  // call
2434  // y = x+4
2435  // store y -> ptr
2436  // Because we structurally match the load/store as a read/modify/write,
2437  // but the call is chained between them. We cannot fold in this case
2438  // because it would induce a cycle in the graph.
2439  if (!std::count(ChainedNodesInPattern.begin(),
2440  ChainedNodesInPattern.end(), User))
2441  return CR_InducesCycle;
2442 
2443  // Otherwise we found a node that is part of our pattern. For example in:
2444  // x = load ptr
2445  // y = x+4
2446  // store y -> ptr
2447  // This would happen when we're scanning down from the load and see the
2448  // store as a user. Record that there is a use of ChainedNode that is
2449  // part of the pattern and keep scanning uses.
2450  Result = CR_LeadsToInteriorNode;
2451  InteriorChainedNodes.push_back(User);
2452  continue;
2453  }
2454 
2455  // If we found a TokenFactor, there are two cases to consider: first if the
2456  // TokenFactor is just hanging "below" the pattern we're matching (i.e. no
2457  // uses of the TF are in our pattern) we just want to ignore it. Second,
2458  // the TokenFactor can be sandwiched in between two chained nodes, like so:
2459  // [Load chain]
2460  // ^
2461  // |
2462  // [Load]
2463  // ^ ^
2464  // | \ DAG's like cheese
2465  // / \ do you?
2466  // / |
2467  // [TokenFactor] [Op]
2468  // ^ ^
2469  // | |
2470  // \ /
2471  // \ /
2472  // [Store]
2473  //
2474  // In this case, the TokenFactor becomes part of our match and we rewrite it
2475  // as a new TokenFactor.
2476  //
2477  // To distinguish these two cases, do a recursive walk down the uses.
2478  auto MemoizeResult = TokenFactorResult.find(User);
2479  bool Visited = MemoizeResult != TokenFactorResult.end();
2480  // Recursively walk chain users only if the result is not memoized.
2481  if (!Visited) {
2482  auto Res = WalkChainUsers(User, ChainedNodesInPattern, TokenFactorResult,
2483  InteriorChainedNodes);
2484  MemoizeResult = TokenFactorResult.insert(std::make_pair(User, Res)).first;
2485  }
2486  switch (MemoizeResult->second) {
2487  case CR_Simple:
2488  // If the uses of the TokenFactor are just already-selected nodes, ignore
2489  // it, it is "below" our pattern.
2490  continue;
2491  case CR_InducesCycle:
2492  // If the uses of the TokenFactor lead to nodes that are not part of our
2493  // pattern that are not selected, folding would turn this into a cycle,
2494  // bail out now.
2495  return CR_InducesCycle;
2497  break; // Otherwise, keep processing.
2498  }
2499 
2500  // Okay, we know we're in the interesting interior case. The TokenFactor
2501  // is now going to be considered part of the pattern so that we rewrite its
2502  // uses (it may have uses that are not part of the pattern) with the
2503  // ultimate chain result of the generated code. We will also add its chain
2504  // inputs as inputs to the ultimate TokenFactor we create.
2505  Result = CR_LeadsToInteriorNode;
2506  if (!Visited) {
2507  ChainedNodesInPattern.push_back(User);
2508  InteriorChainedNodes.push_back(User);
2509  }
2510  }
2511 
2512  return Result;
2513 }
2514 
2515 /// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
2516 /// operation for when the pattern matched at least one node with a chains. The
2517 /// input vector contains a list of all of the chained nodes that we match. We
2518 /// must determine if this is a valid thing to cover (i.e. matching it won't
2519 /// induce cycles in the DAG) and if so, creating a TokenFactor node. that will
2520 /// be used as the input node chain for the generated nodes.
2521 static SDValue
2523  SelectionDAG *CurDAG) {
2524  // Used for memoization. Without it WalkChainUsers could take exponential
2525  // time to run.
2526  DenseMap<const SDNode *, ChainResult> TokenFactorResult;
2527  // Walk all of the chained nodes we've matched, recursively scanning down the
2528  // users of the chain result. This adds any TokenFactor nodes that are caught
2529  // in between chained nodes to the chained and interior nodes list.
2530  SmallVector<SDNode*, 3> InteriorChainedNodes;
2531  for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2532  if (WalkChainUsers(ChainNodesMatched[i], ChainNodesMatched,
2533  TokenFactorResult,
2534  InteriorChainedNodes) == CR_InducesCycle)
2535  return SDValue(); // Would induce a cycle.
2536  }
2537 
2538  // Okay, we have walked all the matched nodes and collected TokenFactor nodes
2539  // that we are interested in. Form our input TokenFactor node.
2540  SmallVector<SDValue, 3> InputChains;
2541  for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2542  // Add the input chain of this node to the InputChains list (which will be
2543  // the operands of the generated TokenFactor) if it's not an interior node.
2544  SDNode *N = ChainNodesMatched[i];
2545  if (N->getOpcode() != ISD::TokenFactor) {
2546  if (std::count(InteriorChainedNodes.begin(),InteriorChainedNodes.end(),N))
2547  continue;
2548 
2549  // Otherwise, add the input chain.
2550  SDValue InChain = ChainNodesMatched[i]->getOperand(0);
2551  assert(InChain.getValueType() == MVT::Other && "Not a chain");
2552  InputChains.push_back(InChain);
2553  continue;
2554  }
2555 
2556  // If we have a token factor, we want to add all inputs of the token factor
2557  // that are not part of the pattern we're matching.
2558  for (const SDValue &Op : N->op_values()) {
2559  if (!std::count(ChainNodesMatched.begin(), ChainNodesMatched.end(),
2560  Op.getNode()))
2561  InputChains.push_back(Op);
2562  }
2563  }
2564 
2565  if (InputChains.size() == 1)
2566  return InputChains[0];
2567  return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]),
2568  MVT::Other, InputChains);
2569 }
2570 
2571 /// MorphNode - Handle morphing a node in place for the selector.
2572 SDNode *SelectionDAGISel::
2573 MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
2574  ArrayRef<SDValue> Ops, unsigned EmitNodeInfo) {
2575  // It is possible we're using MorphNodeTo to replace a node with no
2576  // normal results with one that has a normal result (or we could be
2577  // adding a chain) and the input could have glue and chains as well.
2578  // In this case we need to shift the operands down.
2579  // FIXME: This is a horrible hack and broken in obscure cases, no worse
2580  // than the old isel though.
2581  int OldGlueResultNo = -1, OldChainResultNo = -1;
2582 
2583  unsigned NTMNumResults = Node->getNumValues();
2584  if (Node->getValueType(NTMNumResults-1) == MVT::Glue) {
2585  OldGlueResultNo = NTMNumResults-1;
2586  if (NTMNumResults != 1 &&
2587  Node->getValueType(NTMNumResults-2) == MVT::Other)
2588  OldChainResultNo = NTMNumResults-2;
2589  } else if (Node->getValueType(NTMNumResults-1) == MVT::Other)
2590  OldChainResultNo = NTMNumResults-1;
2591 
2592  // Call the underlying SelectionDAG routine to do the transmogrification. Note
2593  // that this deletes operands of the old node that become dead.
2594  SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops);
2595 
2596  // MorphNodeTo can operate in two ways: if an existing node with the
2597  // specified operands exists, it can just return it. Otherwise, it
2598  // updates the node in place to have the requested operands.
2599  if (Res == Node) {
2600  // If we updated the node in place, reset the node ID. To the isel,
2601  // this should be just like a newly allocated machine node.
2602  Res->setNodeId(-1);
2603  }
2604 
2605  unsigned ResNumResults = Res->getNumValues();
2606  // Move the glue if needed.
2607  if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 &&
2608  (unsigned)OldGlueResultNo != ResNumResults-1)
2609  CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldGlueResultNo),
2610  SDValue(Res, ResNumResults-1));
2611 
2612  if ((EmitNodeInfo & OPFL_GlueOutput) != 0)
2613  --ResNumResults;
2614 
2615  // Move the chain reference if needed.
2616  if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
2617  (unsigned)OldChainResultNo != ResNumResults-1)
2618  CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldChainResultNo),
2619  SDValue(Res, ResNumResults-1));
2620 
2621  // Otherwise, no replacement happened because the node already exists. Replace
2622  // Uses of the old node with the new one.
2623  if (Res != Node) {
2624  CurDAG->ReplaceAllUsesWith(Node, Res);
2625  CurDAG->RemoveDeadNode(Node);
2626  }
2627 
2628  return Res;
2629 }
2630 
2631 /// CheckSame - Implements OP_CheckSame.
2632 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2633 CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2634  SDValue N,
2635  const SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) {
2636  // Accept if it is exactly the same as a previously recorded node.
2637  unsigned RecNo = MatcherTable[MatcherIndex++];
2638  assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2639  return N == RecordedNodes[RecNo].first;
2640 }
2641 
2642 /// CheckChildSame - Implements OP_CheckChildXSame.
2643 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2644 CheckChildSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2645  SDValue N,
2646  const SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes,
2647  unsigned ChildNo) {
2648  if (ChildNo >= N.getNumOperands())
2649  return false; // Match fails if out of range child #.
2650  return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo),
2651  RecordedNodes);
2652 }
2653 
2654 /// CheckPatternPredicate - Implements OP_CheckPatternPredicate.
2655 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2656 CheckPatternPredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2657  const SelectionDAGISel &SDISel) {
2658  return SDISel.CheckPatternPredicate(MatcherTable[MatcherIndex++]);
2659 }
2660 
2661 /// CheckNodePredicate - Implements OP_CheckNodePredicate.
2662 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2663 CheckNodePredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2664  const SelectionDAGISel &SDISel, SDNode *N) {
2665  return SDISel.CheckNodePredicate(N, MatcherTable[MatcherIndex++]);
2666 }
2667 
2668 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2669 CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2670  SDNode *N) {
2671  uint16_t Opc = MatcherTable[MatcherIndex++];
2672  Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
2673  return N->getOpcode() == Opc;
2674 }
2675 
2676 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2677 CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2678  const TargetLowering *TLI, const DataLayout &DL) {
2679  MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2680  if (N.getValueType() == VT) return true;
2681 
2682  // Handle the case when VT is iPTR.
2683  return VT == MVT::iPTR && N.getValueType() == TLI->getPointerTy(DL);
2684 }
2685 
2686 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2687 CheckChildType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2688  SDValue N, const TargetLowering *TLI, const DataLayout &DL,
2689  unsigned ChildNo) {
2690  if (ChildNo >= N.getNumOperands())
2691  return false; // Match fails if out of range child #.
2692  return ::CheckType(MatcherTable, MatcherIndex, N.getOperand(ChildNo), TLI,
2693  DL);
2694 }
2695 
2696 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2697 CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2698  SDValue N) {
2699  return cast<CondCodeSDNode>(N)->get() ==
2700  (ISD::CondCode)MatcherTable[MatcherIndex++];
2701 }
2702 
2703 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2704 CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2705  SDValue N, const TargetLowering *TLI, const DataLayout &DL) {
2706  MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2707  if (cast<VTSDNode>(N)->getVT() == VT)
2708  return true;
2709 
2710  // Handle the case when VT is iPTR.
2711  return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI->getPointerTy(DL);
2712 }
2713 
2714 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2715 CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2716  SDValue N) {
2717  int64_t Val = MatcherTable[MatcherIndex++];
2718  if (Val & 128)
2719  Val = GetVBR(Val, MatcherTable, MatcherIndex);
2720 
2722  return C && C->getSExtValue() == Val;
2723 }
2724 
2725 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2726 CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2727  SDValue N, unsigned ChildNo) {
2728  if (ChildNo >= N.getNumOperands())
2729  return false; // Match fails if out of range child #.
2730  return ::CheckInteger(MatcherTable, MatcherIndex, N.getOperand(ChildNo));
2731 }
2732 
2733 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2734 CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2735  SDValue N, const SelectionDAGISel &SDISel) {
2736  int64_t Val = MatcherTable[MatcherIndex++];
2737  if (Val & 128)
2738  Val = GetVBR(Val, MatcherTable, MatcherIndex);
2739 
2740  if (N->getOpcode() != ISD::AND) return false;
2741 
2743  return C && SDISel.CheckAndMask(N.getOperand(0), C, Val);
2744 }
2745 
2746 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2747 CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2748  SDValue N, const SelectionDAGISel &SDISel) {
2749  int64_t Val = MatcherTable[MatcherIndex++];
2750  if (Val & 128)
2751  Val = GetVBR(Val, MatcherTable, MatcherIndex);
2752 
2753  if (N->getOpcode() != ISD::OR) return false;
2754 
2756  return C && SDISel.CheckOrMask(N.getOperand(0), C, Val);
2757 }
2758 
2759 /// IsPredicateKnownToFail - If we know how and can do so without pushing a
2760 /// scope, evaluate the current node. If the current predicate is known to
2761 /// fail, set Result=true and return anything. If the current predicate is
2762 /// known to pass, set Result=false and return the MatcherIndex to continue
2763 /// with. If the current predicate is unknown, set Result=false and return the
2764 /// MatcherIndex to continue with.
2765 static unsigned IsPredicateKnownToFail(const unsigned char *Table,
2766  unsigned Index, SDValue N,
2767  bool &Result,
2768  const SelectionDAGISel &SDISel,
2769  SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) {
2770  switch (Table[Index++]) {
2771  default:
2772  Result = false;
2773  return Index-1; // Could not evaluate this predicate.
2775  Result = !::CheckSame(Table, Index, N, RecordedNodes);
2776  return Index;
2781  Result = !::CheckChildSame(Table, Index, N, RecordedNodes,
2782  Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Same);
2783  return Index;
2785  Result = !::CheckPatternPredicate(Table, Index, SDISel);
2786  return Index;
2788  Result = !::CheckNodePredicate(Table, Index, SDISel, N.getNode());
2789  return Index;
2791  Result = !::CheckOpcode(Table, Index, N.getNode());
2792  return Index;
2794  Result = !::CheckType(Table, Index, N, SDISel.TLI,
2795  SDISel.CurDAG->getDataLayout());
2796  return Index;
2798  unsigned Res = Table[Index++];
2799  Result = !::CheckType(Table, Index, N.getValue(Res), SDISel.TLI,
2800  SDISel.CurDAG->getDataLayout());
2801  return Index;
2802  }
2811  Result = !::CheckChildType(
2812  Table, Index, N, SDISel.TLI, SDISel.CurDAG->getDataLayout(),
2813  Table[Index - 1] - SelectionDAGISel::OPC_CheckChild0Type);
2814  return Index;
2816  Result = !::CheckCondCode(Table, Index, N);
2817  return Index;
2819  Result = !::CheckValueType(Table, Index, N, SDISel.TLI,
2820  SDISel.CurDAG->getDataLayout());
2821  return Index;
2823  Result = !::CheckInteger(Table, Index, N);
2824  return Index;
2830  Result = !::CheckChildInteger(Table, Index, N,
2831  Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Integer);
2832  return Index;
2834  Result = !::CheckAndImm(Table, Index, N, SDISel);
2835  return Index;
2837  Result = !::CheckOrImm(Table, Index, N, SDISel);
2838  return Index;
2839  }
2840 }
2841 
2842 namespace {
2843 
2844 struct MatchScope {
2845  /// FailIndex - If this match fails, this is the index to continue with.
2846  unsigned FailIndex;
2847 
2848  /// NodeStack - The node stack when the scope was formed.
2849  SmallVector<SDValue, 4> NodeStack;
2850 
2851  /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
2852  unsigned NumRecordedNodes;
2853 
2854  /// NumMatchedMemRefs - The number of matched memref entries.
2855  unsigned NumMatchedMemRefs;
2856 
2857  /// InputChain/InputGlue - The current chain/glue
2858  SDValue InputChain, InputGlue;
2859 
2860  /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.
2861  bool HasChainNodesMatched;
2862 };
2863 
2864 /// \\brief A DAG update listener to keep the matching state
2865 /// (i.e. RecordedNodes and MatchScope) uptodate if the target is allowed to
2866 /// change the DAG while matching. X86 addressing mode matcher is an example
2867 /// for this.
2868 class MatchStateUpdater : public SelectionDAG::DAGUpdateListener
2869 {
2870  SDNode **NodeToMatch;
2872  SmallVectorImpl<MatchScope> &MatchScopes;
2873 
2874 public:
2875  MatchStateUpdater(SelectionDAG &DAG, SDNode **NodeToMatch,
2876  SmallVectorImpl<std::pair<SDValue, SDNode *>> &RN,
2878  : SelectionDAG::DAGUpdateListener(DAG), NodeToMatch(NodeToMatch),
2879  RecordedNodes(RN), MatchScopes(MS) {}
2880 
2881  void NodeDeleted(SDNode *N, SDNode *E) override {
2882  // Some early-returns here to avoid the search if we deleted the node or
2883  // if the update comes from MorphNodeTo (MorphNodeTo is the last thing we
2884  // do, so it's unnecessary to update matching state at that point).
2885  // Neither of these can occur currently because we only install this
2886  // update listener during matching a complex patterns.
2887  if (!E || E->isMachineOpcode())
2888  return;
2889  // Check if NodeToMatch was updated.
2890  if (N == *NodeToMatch)
2891  *NodeToMatch = E;
2892  // Performing linear search here does not matter because we almost never
2893  // run this code. You'd have to have a CSE during complex pattern
2894  // matching.
2895  for (auto &I : RecordedNodes)
2896  if (I.first.getNode() == N)
2897  I.first.setNode(E);
2898 
2899  for (auto &I : MatchScopes)
2900  for (auto &J : I.NodeStack)
2901  if (J.getNode() == N)
2902  J.setNode(E);
2903  }
2904 };
2905 
2906 } // end anonymous namespace
2907 
2909  const unsigned char *MatcherTable,
2910  unsigned TableSize) {
2911  // FIXME: Should these even be selected? Handle these cases in the caller?
2912  switch (NodeToMatch->getOpcode()) {
2913  default:
2914  break;
2915  case ISD::EntryToken: // These nodes remain the same.
2916  case ISD::BasicBlock:
2917  case ISD::Register:
2918  case ISD::RegisterMask:
2919  case ISD::HANDLENODE:
2920  case ISD::MDNODE_SDNODE:
2921  case ISD::TargetConstant:
2922  case ISD::TargetConstantFP:
2924  case ISD::TargetFrameIndex:
2926  case ISD::MCSymbol:
2928  case ISD::TargetJumpTable:
2931  case ISD::TokenFactor:
2932  case ISD::CopyFromReg:
2933  case ISD::CopyToReg:
2934  case ISD::EH_LABEL:
2935  case ISD::ANNOTATION_LABEL:
2936  case ISD::LIFETIME_START:
2937  case ISD::LIFETIME_END:
2938  NodeToMatch->setNodeId(-1); // Mark selected.
2939  return;
2940  case ISD::AssertSext:
2941  case ISD::AssertZext:
2942  CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, 0),
2943  NodeToMatch->getOperand(0));
2944  CurDAG->RemoveDeadNode(NodeToMatch);
2945  return;
2946  case ISD::INLINEASM:
2947  Select_INLINEASM(NodeToMatch);
2948  return;
2949  case ISD::READ_REGISTER:
2950  Select_READ_REGISTER(NodeToMatch);
2951  return;
2952  case ISD::WRITE_REGISTER:
2953  Select_WRITE_REGISTER(NodeToMatch);
2954  return;
2955  case ISD::UNDEF:
2956  Select_UNDEF(NodeToMatch);
2957  return;
2958  }
2959 
2960  assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
2961 
2962  // Set up the node stack with NodeToMatch as the only node on the stack.
2963  SmallVector<SDValue, 8> NodeStack;
2964  SDValue N = SDValue(NodeToMatch, 0);
2965  NodeStack.push_back(N);
2966 
2967  // MatchScopes - Scopes used when matching, if a match failure happens, this
2968  // indicates where to continue checking.
2969  SmallVector<MatchScope, 8> MatchScopes;
2970 
2971  // RecordedNodes - This is the set of nodes that have been recorded by the
2972  // state machine. The second value is the parent of the node, or null if the
2973  // root is recorded.
2974  SmallVector<std::pair<SDValue, SDNode*>, 8> RecordedNodes;
2975 
2976  // MatchedMemRefs - This is the set of MemRef's we've seen in the input
2977  // pattern.
2978  SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
2979 
2980  // These are the current input chain and glue for use when generating nodes.
2981  // Various Emit operations change these. For example, emitting a copytoreg
2982  // uses and updates these.
2983  SDValue InputChain, InputGlue;
2984 
2985  // ChainNodesMatched - If a pattern matches nodes that have input/output
2986  // chains, the OPC_EmitMergeInputChains operation is emitted which indicates
2987  // which ones they are. The result is captured into this list so that we can
2988  // update the chain results when the pattern is complete.
2989  SmallVector<SDNode*, 3> ChainNodesMatched;
2990 
2991  DEBUG(dbgs() << "ISEL: Starting pattern match on root node: ";
2992  NodeToMatch->dump(CurDAG);
2993  dbgs() << '\n');
2994 
2995  // Determine where to start the interpreter. Normally we start at opcode #0,
2996  // but if the state machine starts with an OPC_SwitchOpcode, then we
2997  // accelerate the first lookup (which is guaranteed to be hot) with the
2998  // OpcodeOffset table.
2999  unsigned MatcherIndex = 0;
3000 
3001  if (!OpcodeOffset.empty()) {
3002  // Already computed the OpcodeOffset table, just index into it.
3003  if (N.getOpcode() < OpcodeOffset.size())
3004  MatcherIndex = OpcodeOffset[N.getOpcode()];
3005  DEBUG(dbgs() << " Initial Opcode index to " << MatcherIndex << "\n");
3006 
3007  } else if (MatcherTable[0] == OPC_SwitchOpcode) {
3008  // Otherwise, the table isn't computed, but the state machine does start
3009  // with an OPC_SwitchOpcode instruction. Populate the table now, since this
3010  // is the first time we're selecting an instruction.
3011  unsigned Idx = 1;
3012  while (true) {
3013  // Get the size of this case.
3014  unsigned CaseSize = MatcherTable[Idx++];
3015  if (CaseSize & 128)
3016  CaseSize = GetVBR(CaseSize, MatcherTable, Idx);
3017  if (CaseSize == 0) break;
3018 
3019  // Get the opcode, add the index to the table.
3020  uint16_t Opc = MatcherTable[Idx++];
3021  Opc |= (unsigned short)MatcherTable[Idx++] << 8;
3022  if (Opc >= OpcodeOffset.size())
3023  OpcodeOffset.resize((Opc+1)*2);
3024  OpcodeOffset[Opc] = Idx;
3025  Idx += CaseSize;
3026  }
3027 
3028  // Okay, do the lookup for the first opcode.
3029  if (N.getOpcode() < OpcodeOffset.size())
3030  MatcherIndex = OpcodeOffset[N.getOpcode()];
3031  }
3032 
3033  while (true) {
3034  assert(MatcherIndex < TableSize && "Invalid index");
3035 #ifndef NDEBUG
3036  unsigned CurrentOpcodeIndex = MatcherIndex;
3037 #endif
3038  BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++];
3039  switch (Opcode) {
3040  case OPC_Scope: {
3041  // Okay, the semantics of this operation are that we should push a scope
3042  // then evaluate the first child. However, pushing a scope only to have
3043  // the first check fail (which then pops it) is inefficient. If we can
3044  // determine immediately that the first check (or first several) will
3045  // immediately fail, don't even bother pushing a scope for them.
3046  unsigned FailIndex;
3047 
3048  while (true) {
3049  unsigned NumToSkip = MatcherTable[MatcherIndex++];
3050  if (NumToSkip & 128)
3051  NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
3052  // Found the end of the scope with no match.
3053  if (NumToSkip == 0) {
3054  FailIndex = 0;
3055  break;
3056  }
3057 
3058  FailIndex = MatcherIndex+NumToSkip;
3059 
3060  unsigned MatcherIndexOfPredicate = MatcherIndex;
3061  (void)MatcherIndexOfPredicate; // silence warning.
3062 
3063  // If we can't evaluate this predicate without pushing a scope (e.g. if
3064  // it is a 'MoveParent') or if the predicate succeeds on this node, we
3065  // push the scope and evaluate the full predicate chain.
3066  bool Result;
3067  MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,
3068  Result, *this, RecordedNodes);
3069  if (!Result)
3070  break;
3071 
3072  DEBUG(dbgs() << " Skipped scope entry (due to false predicate) at "
3073  << "index " << MatcherIndexOfPredicate
3074  << ", continuing at " << FailIndex << "\n");
3075  ++NumDAGIselRetries;
3076 
3077  // Otherwise, we know that this case of the Scope is guaranteed to fail,
3078  // move to the next case.
3079  MatcherIndex = FailIndex;
3080  }
3081 
3082  // If the whole scope failed to match, bail.
3083  if (FailIndex == 0) break;
3084 
3085  // Push a MatchScope which indicates where to go if the first child fails
3086  // to match.
3087  MatchScope NewEntry;
3088  NewEntry.FailIndex = FailIndex;
3089  NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
3090  NewEntry.NumRecordedNodes = RecordedNodes.size();
3091  NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
3092  NewEntry.InputChain = InputChain;
3093  NewEntry.InputGlue = InputGlue;
3094  NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
3095  MatchScopes.push_back(NewEntry);
3096  continue;
3097  }
3098  case OPC_RecordNode: {
3099  // Remember this node, it may end up being an operand in the pattern.
3100  SDNode *Parent = nullptr;
3101  if (NodeStack.size() > 1)
3102  Parent = NodeStack[NodeStack.size()-2].getNode();
3103  RecordedNodes.push_back(std::make_pair(N, Parent));
3104  continue;
3105  }
3106 
3110  case OPC_RecordChild6: case OPC_RecordChild7: {
3111  unsigned ChildNo = Opcode-OPC_RecordChild0;
3112  if (ChildNo >= N.getNumOperands())
3113  break; // Match fails if out of range child #.
3114 
3115  RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo),
3116  N.getNode()));
3117  continue;
3118  }
3119  case OPC_RecordMemRef:
3120  MatchedMemRefs.push_back(cast<MemSDNode>(N)->getMemOperand());
3121  continue;
3122 
3123  case OPC_CaptureGlueInput:
3124  // If the current node has an input glue, capture it in InputGlue.
3125  if (N->getNumOperands() != 0 &&
3126  N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue)
3127  InputGlue = N->getOperand(N->getNumOperands()-1);
3128  continue;
3129 
3130  case OPC_MoveChild: {
3131  unsigned ChildNo = MatcherTable[MatcherIndex++];
3132  if (ChildNo >= N.getNumOperands())
3133  break; // Match fails if out of range child #.
3134  N = N.getOperand(ChildNo);
3135  NodeStack.push_back(N);
3136  continue;
3137  }
3138 
3139  case OPC_MoveChild0: case OPC_MoveChild1:
3140  case OPC_MoveChild2: case OPC_MoveChild3:
3141  case OPC_MoveChild4: case OPC_MoveChild5:
3142  case OPC_MoveChild6: case OPC_MoveChild7: {
3143  unsigned ChildNo = Opcode-OPC_MoveChild0;
3144  if (ChildNo >= N.getNumOperands())
3145  break; // Match fails if out of range child #.
3146  N = N.getOperand(ChildNo);
3147  NodeStack.push_back(N);
3148  continue;
3149  }
3150 
3151  case OPC_MoveParent:
3152  // Pop the current node off the NodeStack.
3153  NodeStack.pop_back();
3154  assert(!NodeStack.empty() && "Node stack imbalance!");
3155  N = NodeStack.back();
3156  continue;
3157 
3158  case OPC_CheckSame:
3159  if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break;
3160  continue;
3161 
3164  if (!::CheckChildSame(MatcherTable, MatcherIndex, N, RecordedNodes,
3165  Opcode-OPC_CheckChild0Same))
3166  break;
3167  continue;
3168 
3170  if (!::CheckPatternPredicate(MatcherTable, MatcherIndex, *this)) break;
3171  continue;
3172  case OPC_CheckPredicate:
3173  if (!::CheckNodePredicate(MatcherTable, MatcherIndex, *this,
3174  N.getNode()))
3175  break;
3176  continue;
3177  case OPC_CheckComplexPat: {
3178  unsigned CPNum = MatcherTable[MatcherIndex++];
3179  unsigned RecNo = MatcherTable[MatcherIndex++];
3180  assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat");
3181 
3182  // If target can modify DAG during matching, keep the matching state
3183  // consistent.
3184  std::unique_ptr<MatchStateUpdater> MSU;
3186  MSU.reset(new MatchStateUpdater(*CurDAG, &NodeToMatch, RecordedNodes,
3187  MatchScopes));
3188 
3189  if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second,
3190  RecordedNodes[RecNo].first, CPNum,
3191  RecordedNodes))
3192  break;
3193  continue;
3194  }
3195  case OPC_CheckOpcode:
3196  if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break;
3197  continue;
3198 
3199  case OPC_CheckType:
3200  if (!::CheckType(MatcherTable, MatcherIndex, N, TLI,
3201  CurDAG->getDataLayout()))
3202  break;
3203  continue;
3204 
3205  case OPC_CheckTypeRes: {
3206  unsigned Res = MatcherTable[MatcherIndex++];
3207  if (!::CheckType(MatcherTable, MatcherIndex, N.getValue(Res), TLI,
3208  CurDAG->getDataLayout()))
3209  break;
3210  continue;
3211  }
3212 
3213  case OPC_SwitchOpcode: {
3214  unsigned CurNodeOpcode = N.getOpcode();
3215  unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3216  unsigned CaseSize;
3217  while (true) {
3218  // Get the size of this case.
3219  CaseSize = MatcherTable[MatcherIndex++];
3220  if (CaseSize & 128)
3221  CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3222  if (CaseSize == 0) break;
3223 
3224  uint16_t Opc = MatcherTable[MatcherIndex++];
3225  Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
3226 
3227  // If the opcode matches, then we will execute this case.
3228  if (CurNodeOpcode == Opc)
3229  break;
3230 
3231  // Otherwise, skip over this case.
3232  MatcherIndex += CaseSize;
3233  }
3234 
3235  // If no cases matched, bail out.
3236  if (CaseSize == 0) break;
3237 
3238  // Otherwise, execute the case we found.
3239  DEBUG(dbgs() << " OpcodeSwitch from " << SwitchStart
3240  << " to " << MatcherIndex << "\n");
3241  continue;
3242  }
3243 
3244  case OPC_SwitchType: {
3245  MVT CurNodeVT = N.getSimpleValueType();
3246  unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3247  unsigned CaseSize;
3248  while (true) {
3249  // Get the size of this case.
3250  CaseSize = MatcherTable[MatcherIndex++];
3251  if (CaseSize & 128)
3252  CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3253  if (CaseSize == 0) break;
3254 
3255  MVT CaseVT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3256  if (CaseVT == MVT::iPTR)
3257  CaseVT = TLI->getPointerTy(CurDAG->getDataLayout());
3258 
3259  // If the VT matches, then we will execute this case.
3260  if (CurNodeVT == CaseVT)
3261  break;
3262 
3263  // Otherwise, skip over this case.
3264  MatcherIndex += CaseSize;
3265  }
3266 
3267  // If no cases matched, bail out.
3268  if (CaseSize == 0) break;
3269 
3270  // Otherwise, execute the case we found.
3271  DEBUG(dbgs() << " TypeSwitch[" << EVT(CurNodeVT).getEVTString()
3272  << "] from " << SwitchStart << " to " << MatcherIndex<<'\n');
3273  continue;
3274  }
3279  if (!::CheckChildType(MatcherTable, MatcherIndex, N, TLI,
3280  CurDAG->getDataLayout(),
3281  Opcode - OPC_CheckChild0Type))
3282  break;
3283  continue;
3284  case OPC_CheckCondCode:
3285  if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break;
3286  continue;
3287  case OPC_CheckValueType:
3288  if (!::CheckValueType(MatcherTable, MatcherIndex, N, TLI,
3289  CurDAG->getDataLayout()))
3290  break;
3291  continue;
3292  case OPC_CheckInteger:
3293  if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break;
3294  continue;
3298  if (!::CheckChildInteger(MatcherTable, MatcherIndex, N,
3299  Opcode-OPC_CheckChild0Integer)) break;
3300  continue;
3301  case OPC_CheckAndImm:
3302  if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break;
3303  continue;
3304  case OPC_CheckOrImm:
3305  if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break;
3306  continue;
3307 
3309  assert(NodeStack.size() != 1 && "No parent node");
3310  // Verify that all intermediate nodes between the root and this one have
3311  // a single use.
3312  bool HasMultipleUses = false;
3313  for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i)
3314  if (!NodeStack[i].getNode()->hasOneUse()) {
3315  HasMultipleUses = true;
3316  break;
3317  }
3318  if (HasMultipleUses) break;
3319 
3320  // Check to see that the target thinks this is profitable to fold and that
3321  // we can fold it without inducing cycles in the graph.
3322  if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3323  NodeToMatch) ||
3324  !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3325  NodeToMatch, OptLevel,
3326  true/*We validate our own chains*/))
3327  break;
3328 
3329  continue;
3330  }
3331  case OPC_EmitInteger: {
3333  (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3334  int64_t Val = MatcherTable[MatcherIndex++];
3335  if (Val & 128)
3336  Val = GetVBR(Val, MatcherTable, MatcherIndex);
3337  RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3338  CurDAG->getTargetConstant(Val, SDLoc(NodeToMatch),
3339  VT), nullptr));
3340  continue;
3341  }
3342  case OPC_EmitRegister: {
3344  (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3345  unsigned RegNo = MatcherTable[MatcherIndex++];
3346  RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3347  CurDAG->getRegister(RegNo, VT), nullptr));
3348  continue;
3349  }
3350  case OPC_EmitRegister2: {
3351  // For targets w/ more than 256 register names, the register enum
3352  // values are stored in two bytes in the matcher table (just like
3353  // opcodes).
3355  (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3356  unsigned RegNo = MatcherTable[MatcherIndex++];
3357  RegNo |= MatcherTable[MatcherIndex++] << 8;
3358  RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3359  CurDAG->getRegister(RegNo, VT), nullptr));
3360  continue;
3361  }
3362 
3363  case OPC_EmitConvertToTarget: {
3364  // Convert from IMM/FPIMM to target version.
3365  unsigned RecNo = MatcherTable[MatcherIndex++];
3366  assert(RecNo < RecordedNodes.size() && "Invalid EmitConvertToTarget");
3367  SDValue Imm = RecordedNodes[RecNo].first;
3368 
3369  if (Imm->getOpcode() == ISD::Constant) {
3370  const ConstantInt *Val=cast<ConstantSDNode>(Imm)->getConstantIntValue();
3371  Imm = CurDAG->getTargetConstant(*Val, SDLoc(NodeToMatch),
3372  Imm.getValueType());
3373  } else if (Imm->getOpcode() == ISD::ConstantFP) {
3374  const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
3375  Imm = CurDAG->getTargetConstantFP(*Val, SDLoc(NodeToMatch),
3376  Imm.getValueType());
3377  }
3378 
3379  RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second));
3380  continue;
3381  }
3382 
3383  case OPC_EmitMergeInputChains1_0: // OPC_EmitMergeInputChains, 1, 0
3384  case OPC_EmitMergeInputChains1_1: // OPC_EmitMergeInputChains, 1, 1
3385  case OPC_EmitMergeInputChains1_2: { // OPC_EmitMergeInputChains, 1, 2
3386  // These are space-optimized forms of OPC_EmitMergeInputChains.
3387  assert(!InputChain.getNode() &&
3388  "EmitMergeInputChains should be the first chain producing node");
3389  assert(ChainNodesMatched.empty() &&
3390  "Should only have one EmitMergeInputChains per match");
3391 
3392  // Read all of the chained nodes.
3393  unsigned RecNo = Opcode - OPC_EmitMergeInputChains1_0;
3394  assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3395  ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3396 
3397  // FIXME: What if other value results of the node have uses not matched
3398  // by this pattern?
3399  if (ChainNodesMatched.back() != NodeToMatch &&
3400  !RecordedNodes[RecNo].first.hasOneUse()) {
3401  ChainNodesMatched.clear();
3402  break;
3403  }
3404 
3405  // Merge the input chains if they are not intra-pattern references.
3406  InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3407 
3408  if (!InputChain.getNode())
3409  break; // Failed to merge.
3410  continue;
3411  }
3412 
3413  case OPC_EmitMergeInputChains: {
3414  assert(!InputChain.getNode() &&
3415  "EmitMergeInputChains should be the first chain producing node");
3416  // This node gets a list of nodes we matched in the input that have
3417  // chains. We want to token factor all of the input chains to these nodes
3418  // together. However, if any of the input chains is actually one of the
3419  // nodes matched in this pattern, then we have an intra-match reference.
3420  // Ignore these because the newly token factored chain should not refer to
3421  // the old nodes.
3422  unsigned NumChains = MatcherTable[MatcherIndex++];
3423  assert(NumChains != 0 && "Can't TF zero chains");
3424 
3425  assert(ChainNodesMatched.empty() &&
3426  "Should only have one EmitMergeInputChains per match");
3427 
3428  // Read all of the chained nodes.
3429  for (unsigned i = 0; i != NumChains; ++i) {
3430  unsigned RecNo = MatcherTable[MatcherIndex++];
3431  assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3432  ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3433 
3434  // FIXME: What if other value results of the node have uses not matched
3435  // by this pattern?
3436  if (ChainNodesMatched.back() != NodeToMatch &&
3437  !RecordedNodes[RecNo].first.hasOneUse()) {
3438  ChainNodesMatched.clear();
3439  break;
3440  }
3441  }
3442 
3443  // If the inner loop broke out, the match fails.
3444  if (ChainNodesMatched.empty())
3445  break;
3446 
3447  // Merge the input chains if they are not intra-pattern references.
3448  InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3449 
3450  if (!InputChain.getNode())
3451  break; // Failed to merge.
3452 
3453  continue;
3454  }
3455 
3456  case OPC_EmitCopyToReg: {
3457  unsigned RecNo = MatcherTable[MatcherIndex++];
3458  assert(RecNo < RecordedNodes.size() && "Invalid EmitCopyToReg");
3459  unsigned DestPhysReg = MatcherTable[MatcherIndex++];
3460 
3461  if (!InputChain.getNode())
3462  InputChain = CurDAG->getEntryNode();
3463 
3464  InputChain = CurDAG->getCopyToReg(InputChain, SDLoc(NodeToMatch),
3465  DestPhysReg, RecordedNodes[RecNo].first,
3466  InputGlue);
3467 
3468  InputGlue = InputChain.getValue(1);
3469  continue;
3470  }
3471 
3472  case OPC_EmitNodeXForm: {
3473  unsigned XFormNo = MatcherTable[MatcherIndex++];
3474  unsigned RecNo = MatcherTable[MatcherIndex++];
3475  assert(RecNo < RecordedNodes.size() && "Invalid EmitNodeXForm");
3476  SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo);
3477  RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, nullptr));
3478  continue;
3479  }
3480  case OPC_Coverage: {
3481  // This is emitted right before MorphNode/EmitNode.
3482  // So it should be safe to assume that this node has been selected
3483  unsigned index = MatcherTable[MatcherIndex++];
3484  index |= (MatcherTable[MatcherIndex++] << 8);
3485  dbgs() << "COVERED: " << getPatternForIndex(index) << "\n";
3486  dbgs() << "INCLUDED: " << getIncludePathForIndex(index) << "\n";
3487  continue;
3488  }
3489 
3490  case OPC_EmitNode: case OPC_MorphNodeTo:
3491  case OPC_EmitNode0: case OPC_EmitNode1: case OPC_EmitNode2:
3493  uint16_t TargetOpc = MatcherTable[MatcherIndex++];
3494  TargetOpc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
3495  unsigned EmitNodeInfo = MatcherTable[MatcherIndex++];
3496  // Get the result VT list.
3497  unsigned NumVTs;
3498  // If this is one of the compressed forms, get the number of VTs based
3499  // on the Opcode. Otherwise read the next byte from the table.
3500  if (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2)
3501  NumVTs = Opcode - OPC_MorphNodeTo0;
3502  else if (Opcode >= OPC_EmitNode0 && Opcode <= OPC_EmitNode2)
3503  NumVTs = Opcode - OPC_EmitNode0;
3504  else
3505  NumVTs = MatcherTable[MatcherIndex++];
3506  SmallVector<EVT, 4> VTs;
3507  for (unsigned i = 0; i != NumVTs; ++i) {
3509  (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3510  if (VT == MVT::iPTR)
3511  VT = TLI->getPointerTy(CurDAG->getDataLayout()).SimpleTy;
3512  VTs.push_back(VT);
3513  }
3514 
3515  if (EmitNodeInfo & OPFL_Chain)
3516  VTs.push_back(MVT::Other);
3517  if (EmitNodeInfo & OPFL_GlueOutput)
3518  VTs.push_back(MVT::Glue);
3519 
3520  // This is hot code, so optimize the two most common cases of 1 and 2
3521  // results.
3522  SDVTList VTList;
3523  if (VTs.size() == 1)
3524  VTList = CurDAG->getVTList(VTs[0]);
3525  else if (VTs.size() == 2)
3526  VTList = CurDAG->getVTList(VTs[0], VTs[1]);
3527  else
3528  VTList = CurDAG->getVTList(VTs);
3529 
3530  // Get the operand list.
3531  unsigned NumOps = MatcherTable[MatcherIndex++];
3533  for (unsigned i = 0; i != NumOps; ++i) {
3534  unsigned RecNo = MatcherTable[MatcherIndex++];
3535  if (RecNo & 128)
3536  RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
3537 
3538  assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");
3539  Ops.push_back(RecordedNodes[RecNo].first);
3540  }
3541 
3542  // If there are variadic operands to add, handle them now.
3543  if (EmitNodeInfo & OPFL_VariadicInfo) {
3544  // Determine the start index to copy from.
3545  unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
3546  FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
3547  assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
3548  "Invalid variadic node");
3549  // Copy all of the variadic operands, not including a potential glue
3550  // input.
3551  for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
3552  i != e; ++i) {
3553  SDValue V = NodeToMatch->getOperand(i);
3554  if (V.getValueType() == MVT::Glue) break;
3555  Ops.push_back(V);
3556  }
3557  }
3558 
3559  // If this has chain/glue inputs, add them.
3560  if (EmitNodeInfo & OPFL_Chain)
3561  Ops.push_back(InputChain);
3562  if ((EmitNodeInfo & OPFL_GlueInput) && InputGlue.getNode() != nullptr)
3563  Ops.push_back(InputGlue);
3564 
3565  // Create the node.
3566  SDNode *Res = nullptr;
3567  bool IsMorphNodeTo = Opcode == OPC_MorphNodeTo ||
3568  (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2);
3569  if (!IsMorphNodeTo) {
3570  // If this is a normal EmitNode command, just create the new node and
3571  // add the results to the RecordedNodes list.
3572  Res = CurDAG->getMachineNode(TargetOpc, SDLoc(NodeToMatch),
3573  VTList, Ops);
3574 
3575  // Add all the non-glue/non-chain results to the RecordedNodes list.
3576  for (unsigned i = 0, e = VTs.size(); i != e; ++i) {
3577  if (VTs[i] == MVT::Other || VTs[i] == MVT::Glue) break;
3578  RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i),
3579  nullptr));
3580  }
3581  } else {
3582  assert(NodeToMatch->getOpcode() != ISD::DELETED_NODE &&
3583  "NodeToMatch was removed partway through selection");
3585  SDNode *E) {
3586  CurDAG->salvageDebugInfo(*N);
3587  auto &Chain = ChainNodesMatched;
3588  assert((!E || !is_contained(Chain, N)) &&
3589  "Chain node replaced during MorphNode");
3590  Chain.erase(std::remove(Chain.begin(), Chain.end(), N), Chain.end());
3591  });
3592  Res = MorphNode(NodeToMatch, TargetOpc, VTList, Ops, EmitNodeInfo);
3593  }
3594 
3595  // If the node had chain/glue results, update our notion of the current
3596  // chain and glue.
3597  if (EmitNodeInfo & OPFL_GlueOutput) {
3598  InputGlue = SDValue(Res, VTs.size()-1);
3599  if (EmitNodeInfo & OPFL_Chain)
3600  InputChain = SDValue(Res, VTs.size()-2);
3601  } else if (EmitNodeInfo & OPFL_Chain)
3602  InputChain = SDValue(Res, VTs.size()-1);
3603 
3604  // If the OPFL_MemRefs glue is set on this node, slap all of the
3605  // accumulated memrefs onto it.
3606  //
3607  // FIXME: This is vastly incorrect for patterns with multiple outputs
3608  // instructions that access memory and for ComplexPatterns that match
3609  // loads.
3610  if (EmitNodeInfo & OPFL_MemRefs) {
3611  // Only attach load or store memory operands if the generated
3612  // instruction may load or store.
3613  const MCInstrDesc &MCID = TII->get(TargetOpc);
3614  bool mayLoad = MCID.mayLoad();
3615  bool mayStore = MCID.mayStore();
3616 
3617  unsigned NumMemRefs = 0;
3619  MatchedMemRefs.begin(), E = MatchedMemRefs.end(); I != E; ++I) {
3620  if ((*I)->isLoad()) {
3621  if (mayLoad)
3622  ++NumMemRefs;
3623  } else if ((*I)->isStore()) {
3624  if (mayStore)
3625  ++NumMemRefs;
3626  } else {
3627  ++NumMemRefs;
3628  }
3629  }
3630 
3631  MachineSDNode::mmo_iterator MemRefs =
3632  MF->allocateMemRefsArray(NumMemRefs);
3633 
3634  MachineSDNode::mmo_iterator MemRefsPos = MemRefs;
3636  MatchedMemRefs.begin(), E = MatchedMemRefs.end(); I != E; ++I) {
3637  if ((*I)->isLoad()) {
3638  if (mayLoad)
3639  *MemRefsPos++ = *I;
3640  } else if ((*I)->isStore()) {
3641  if (mayStore)
3642  *MemRefsPos++ = *I;
3643  } else {
3644  *MemRefsPos++ = *I;
3645  }
3646  }
3647 
3648  cast<MachineSDNode>(Res)
3649  ->setMemRefs(MemRefs, MemRefs + NumMemRefs);
3650  }
3651 
3652  DEBUG(dbgs() << " "
3653  << (IsMorphNodeTo ? "Morphed" : "Created")
3654  << " node: "; Res->dump(CurDAG); dbgs() << "\n");
3655 
3656  // If this was a MorphNodeTo then we're completely done!
3657  if (IsMorphNodeTo) {
3658  // Update chain uses.
3659  UpdateChains(Res, InputChain, ChainNodesMatched, true);
3660  return;
3661  }
3662  continue;
3663  }
3664 
3665  case OPC_CompleteMatch: {
3666  // The match has been completed, and any new nodes (if any) have been
3667  // created. Patch up references to the matched dag to use the newly
3668  // created nodes.
3669  unsigned NumResults = MatcherTable[MatcherIndex++];
3670 
3671  for (unsigned i = 0; i != NumResults; ++i) {
3672  unsigned ResSlot = MatcherTable[MatcherIndex++];
3673  if (ResSlot & 128)
3674  ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);
3675 
3676  assert(ResSlot < RecordedNodes.size() && "Invalid CompleteMatch");
3677  SDValue Res = RecordedNodes[ResSlot].first;
3678 
3679  assert(i < NodeToMatch->getNumValues() &&
3680  NodeToMatch->getValueType(i) != MVT::Other &&
3681  NodeToMatch->getValueType(i) != MVT::Glue &&
3682  "Invalid number of results to complete!");
3683  assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
3684  NodeToMatch->getValueType(i) == MVT::iPTR ||
3685  Res.getValueType() == MVT::iPTR ||
3686  NodeToMatch->getValueType(i).getSizeInBits() ==
3687  Res.getValueSizeInBits()) &&
3688  "invalid replacement");
3689  CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, i), Res);
3690  }
3691 
3692  // Update chain uses.
3693  UpdateChains(NodeToMatch, InputChain, ChainNodesMatched, false);
3694 
3695  // If the root node defines glue, we need to update it to the glue result.
3696  // TODO: This never happens in our tests and I think it can be removed /
3697  // replaced with an assert, but if we do it this the way the change is
3698  // NFC.
3699  if (NodeToMatch->getValueType(NodeToMatch->getNumValues() - 1) ==
3700  MVT::Glue &&
3701  InputGlue.getNode())
3703  SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1), InputGlue);
3704 
3705  assert(NodeToMatch->use_empty() &&
3706  "Didn't replace all uses of the node?");
3707  CurDAG->RemoveDeadNode(NodeToMatch);
3708 
3709  return;
3710  }
3711  }
3712 
3713  // If the code reached this point, then the match failed. See if there is
3714  // another child to try in the current 'Scope', otherwise pop it until we
3715  // find a case to check.
3716  DEBUG(dbgs() << " Match failed at index " << CurrentOpcodeIndex << "\n");
3717  ++NumDAGIselRetries;
3718  while (true) {
3719  if (MatchScopes.empty()) {
3720  CannotYetSelect(NodeToMatch);
3721  return;
3722  }
3723 
3724  // Restore the interpreter state back to the point where the scope was
3725  // formed.
3726  MatchScope &LastScope = MatchScopes.back();
3727  RecordedNodes.resize(LastScope.NumRecordedNodes);
3728  NodeStack.clear();
3729  NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());
3730  N = NodeStack.back();
3731 
3732  if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
3733  MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
3734  MatcherIndex = LastScope.FailIndex;
3735 
3736  DEBUG(dbgs() << " Continuing at " << MatcherIndex << "\n");
3737 
3738  InputChain = LastScope.InputChain;
3739  InputGlue = LastScope.InputGlue;
3740  if (!LastScope.HasChainNodesMatched)
3741  ChainNodesMatched.clear();
3742 
3743  // Check to see what the offset is at the new MatcherIndex. If it is zero
3744  // we have reached the end of this scope, otherwise we have another child
3745  // in the current scope to try.
3746  unsigned NumToSkip = MatcherTable[MatcherIndex++];
3747  if (NumToSkip & 128)
3748  NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
3749 
3750  // If we have another child in this scope to match, update FailIndex and
3751  // try it.
3752  if (NumToSkip != 0) {
3753  LastScope.FailIndex = MatcherIndex+NumToSkip;
3754  break;
3755  }
3756 
3757  // End of this scope, pop it and try the next child in the containing
3758  // scope.
3759  MatchScopes.pop_back();
3760  }
3761  }
3762 }
3763 
3765  assert(N->getOpcode() == ISD::OR && "Unexpected opcode");
3766  auto *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
3767  if (!C)
3768  return false;
3769 
3770  // Detect when "or" is used to add an offset to a stack object.
3771  if (auto *FN = dyn_cast<FrameIndexSDNode>(N->getOperand(0))) {
3772  MachineFrameInfo &MFI = MF->getFrameInfo();
3773  unsigned A = MFI.getObjectAlignment(FN->getIndex());
3774  assert(isPowerOf2_32(A) && "Unexpected alignment");
3775  int32_t Off = C->getSExtValue();
3776  // If the alleged offset fits in the zero bits guaranteed by
3777  // the alignment, then this or is really an add.
3778  return (Off >= 0) && (((A - 1) & Off) == unsigned(Off));
3779  }
3780  return false;
3781 }
3782 
3783 void SelectionDAGISel::CannotYetSelect(SDNode *N) {
3784  std::string msg;
3785  raw_string_ostream Msg(msg);
3786  Msg << "Cannot select: ";
3787 
3788  if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&
3790  N->getOpcode() != ISD::INTRINSIC_VOID) {
3791  N->printrFull(Msg, CurDAG);
3792  Msg << "\nIn function: " << MF->getName();
3793  } else {
3794  bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other;
3795  unsigned iid =
3796  cast<ConstantSDNode>(N->getOperand(HasInputChain))->getZExtValue();
3797  if (iid < Intrinsic::num_intrinsics)
3798  Msg << "intrinsic %" << Intrinsic::getName((Intrinsic::ID)iid, None);
3799  else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo())
3800  Msg << "target intrinsic %" << TII->getName(iid);
3801  else
3802  Msg << "unknown intrinsic #" << iid;
3803  }
3804  report_fatal_error(Msg.str());
3805 }
3806 
3807 char SelectionDAGISel::ID = 0;
ANNOTATION_LABEL - Represents a mid basic block label used by annotations.
Definition: ISDOpcodes.h:646
SDNode * MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs, ArrayRef< SDValue > Ops)
This mutates the specified node to have the specified return type, opcode, and operands.
uint64_t CallInst * C
Return a value (possibly void), from a function.
std::vector< BitTestBlock > BitTestCases
BitTestCases - Vector of BitTestBlock structures used to communicate SwitchInst code generation infor...
Diagnostic information for ISel fallback path.
SelectionDAGBuilder * SDB
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const SelectionDAGISel &SDISel)
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:109
mop_iterator operands_end()
Definition: MachineInstr.h:330
EVT getValueType() const
Return the ValueType of the referenced return value.
static SDNode * findGlueUse(SDNode *N)
findGlueUse - Return use of MVT::Glue value produced by the specified SDNode.
void EmitLiveInCopies(MachineBasicBlock *EntryMBB, const TargetRegisterInfo &TRI, const TargetInstrInfo &TII)
EmitLiveInCopies - Emit copies to initialize livein virtual registers into the given entry block...
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N)
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setVariableDbgInfo(const DILocalVariable *Var, const DIExpression *Expr, unsigned Slot, const DILocation *Loc)
Collect information used to emit debugging information of a variable.
bool hasPostISelHook(QueryType Type=IgnoreBundle) const
Return true if this instruction requires adjustment after instruction selection by calling a target h...
Definition: MachineInstr.h:708
Diagnostic information for missed-optimization remarks.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1542
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
static int getNumFixedFromVariadicInfo(unsigned Flags)
getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the number of fixed arity values ...
This class represents an incoming formal argument to a Function.
Definition: Argument.h:30
LLVM_NODISCARD std::string str() const
str - Get the contents as an std::string.
Definition: StringRef.h:228
bool LegalizeTypes()
This transforms the SelectionDAG into a SelectionDAG that only uses types natively supported by the t...
DiagnosticInfoOptimizationBase::Argument NV
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:329
GCFunctionInfo * GFI
const TargetRegisterClass * getRegClass(unsigned Reg) const
Return the register class of the specified virtual register.
virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const
IsProfitableToFold - Returns true if it&#39;s profitable to fold the specific operand node N of U during ...
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const TargetLowering *TLI, const DataLayout &DL)
DELETED_NODE - This is an illegal value that is used to catch errors.
Definition: ISDOpcodes.h:42
MDNODE_SDNODE - This is a node that holdes an MDNode*, which is used to reference metadata in the IR...
Definition: ISDOpcodes.h:704
static unsigned virtReg2Index(unsigned Reg)
Convert a virtual register number to a 0-based index.
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:115
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Various leaf nodes.
Definition: ISDOpcodes.h:60
MCSymbol * addLandingPad(MachineBasicBlock *LandingPad)
Add a new panding pad. Returns the label ID for the landing pad entry.
static cl::opt< bool > ViewISelDAGs("view-isel-dags", cl::Hidden, cl::desc("Pop up a window to show isel dags as they are selected"))
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:42
unsigned getCatchPadExceptionPointerVReg(const Value *CPI, const TargetRegisterClass *RC)
DenseMap< MachineBasicBlock *, SmallVector< unsigned, 4 > > LPadToCallSiteMap
LPadToCallSiteMap - Map a landing pad to the call site indexes.
unsigned EnableFastISel
EnableFastISel - This flag enables fast-path instruction selection which trades away generated code q...
static void propagateSwiftErrorVRegs(FunctionLoweringInfo *FuncInfo)
Propagate swifterror values through the machine function CFG.
static ChainResult WalkChainUsers(const SDNode *ChainedNode, SmallVectorImpl< SDNode *> &ChainedNodesInPattern, DenseMap< const SDNode *, ChainResult > &TokenFactorResult, SmallVectorImpl< SDNode *> &InteriorChainedNodes)
WalkChainUsers - Walk down the users of the specified chained node that is part of the pattern we&#39;re ...
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
void ReplaceUses(SDValue F, SDValue T)
ReplaceUses - replace all uses of the old node F with the use of the new node T.
unsigned createVirtualRegister(const TargetRegisterClass *RegClass)
createVirtualRegister - Create and return a new virtual register in the function with the specified r...
std::error_code remove(const Twine &path, bool IgnoreNonExisting=true)
Remove path.
Sched::Preference getSchedulingPreference() const
Return target scheduling preference.
bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS, int64_t DesiredMaskS) const
CheckAndMask - The isel is trying to match something like (and X, 255).
const MachineFunctionProperties & getProperties() const
Get the function properties.
virtual unsigned getRegisterByName(const char *RegName, EVT VT, SelectionDAG &DAG) const
Return the register ID of the name passed in.
SelectionDAGBuilder - This is the common target-independent lowering implementation that is parameter...
EVT getValueType(unsigned ResNo) const
Return the type of a specified result.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:271
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
static unsigned getFlagWord(unsigned Kind, unsigned NumOps)
Definition: InlineAsm.h:269
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:163
void initializeTargetLibraryInfoWrapperPassPass(PassRegistry &)
Clients of various APIs that cause global effects on the DAG can optionally implement this interface...
Definition: SelectionDAG.h:263
unsigned getReg() const
getReg - Returns the register number.
friend struct DAGUpdateListener
DAGUpdateListener is a friend so it can manipulate the listener stack.
Definition: SelectionDAG.h:305
static bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
bool LegalizeVectors()
This transforms the SelectionDAG into a SelectionDAG that only uses vector math operations supported ...
This file contains the declarations for metadata subclasses.
virtual const TargetLowering * getTargetLowering() const
iterator_range< IterTy > args() const
Definition: CallSite.h:215
bool mayWriteToMemory() const
Return true if this instruction may modify memory.
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
Definition: APInt.h:1308
iterator insertAfter(iterator I, MachineInstr *MI)
Insert MI into the instruction list after I.
unsigned getResNo() const
Convenience function for get().getResNo().
void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH, MachineBasicBlock *SwitchBB)
visitJumpTableHeader - This function emits necessary code to produce index in the JumpTable from swit...
bool NewNodesMustHaveLegalTypes
When true, additional steps are taken to ensure that getConstant() and similar functions return DAG n...
Definition: SelectionDAG.h:301
TargetGlobalAddress - Like GlobalAddress, but the DAG does no folding or anything else with this node...
Definition: ISDOpcodes.h:131
static const MCPhysReg VRegs[32]
void getLocation(StringRef *Filename, unsigned *Line, unsigned *Column) const
Return location information for this diagnostic in three parts: the source file name, line number and column.
unsigned second
arg_iterator arg_end()
Definition: Function.h:612
virtual const TargetRegisterClass * getRegClassFor(MVT VT) const
Return the register class that should be used for the specified value type.
STATISTIC(NumFunctions, "Total number of functions")
A debug info location.
Definition: DebugLoc.h:34
Metadata node.
Definition: Metadata.h:862
bool isInteger() const
Return true if this is an integer or a vector integer type.
Definition: ValueTypes.h:141
F(f)
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1067
An instruction for reading from memory.
Definition: Instructions.h:164
RegisterPassParser class - Handle the addition of new machine passes.
void setNodeId(int Id)
Set unique node id.
SDNode * getNode() const
get the SDNode which holds the desired result
static MachineBasicBlock::iterator FindSplitPointForStackProtector(MachineBasicBlock *BB)
Find the split point at which to splice the end of BB into its success stack protector check machine ...
SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, ArrayRef< SDUse > Ops)
Gets or creates the specified node.
const SDValue & setRoot(SDValue N)
Set the current root tag of the SelectionDAG.
Definition: SelectionDAG.h:452
bool mayLoad() const
Return true if this instruction could possibly read memory.
Definition: MCInstrDesc.h:387
bool isPHI() const
Definition: MachineInstr.h:829
void viewGraph(const std::string &Title)
Pop up a GraphViz/gv window with the DAG rendered using &#39;dot&#39;.
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckChildType(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const TargetLowering *TLI, const DataLayout &DL, unsigned ChildNo)
unsigned getValueSizeInBits() const
Returns the size of the value in bits.
EntryToken - This is the marker used to indicate the start of a region.
Definition: ISDOpcodes.h:45
void setCurrentSwiftErrorVReg(const MachineBasicBlock *MBB, const Value *, unsigned)
Set the swifterror virtual register in the SwiftErrorVRegDefMap for this basic block.
static bool isUseOperandTiedToDef(unsigned Flag, unsigned &Idx)
isUseOperandTiedToDef - Return true if the flag of the inline asm operand indicates it is an use oper...
Definition: InlineAsm.h:342
bool isReturn() const
Return true if the instruction is a return.
Definition: MCInstrDesc.h:245
bool hasOneUse() const
Return true if there is exactly one node using value ResNo of Node.
MachineFunction * MF
ScheduleDAGSDNodes * createHybridListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level)
createHybridListDAGScheduler - This creates a bottom up register pressure aware list scheduler that m...
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckChildSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const SmallVectorImpl< std::pair< SDValue, SDNode *>> &RecordedNodes, unsigned ChildNo)
CheckChildSame - Implements OP_CheckChildXSame.
const TargetLibraryInfo * LibInfo
void set(const Function &Fn, MachineFunction &MF, SelectionDAG *DAG)
set - Initialize this FunctionLoweringInfo with the given Function and its associated MachineFunction...
bool isGCRelocate(ImmutableCallSite CS)
Definition: Statepoint.cpp:43
static void setupSwiftErrorVals(const Function &Fn, const TargetLowering *TLI, FunctionLoweringInfo *FuncInfo)
Set up SwiftErrorVals by going through the function.
RESULT,OUTCHAIN = INTRINSIC_W_CHAIN(INCHAIN, INTRINSICID, arg1, ...) This node represents a target in...
Definition: ISDOpcodes.h:159
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:344
bool selectInstruction(const Instruction *I)
Do "fast" instruction selection for the given LLVM IR instruction and append the generated machine in...
Definition: FastISel.cpp:1381
static bool isFoldedOrDeadInstruction(const Instruction *I, FunctionLoweringInfo *FuncInfo)
isFoldedOrDeadInstruction - Return true if the specified instruction is side-effect free and is eithe...
StackProtectorDescriptor SPDescriptor
A StackProtectorDescriptor structure used to communicate stack protector information in between Selec...
std::pair< unsigned, bool > getOrCreateSwiftErrorVRegDefAt(const Instruction *)
Get or create the swifterror value virtual register for a def of a swifterror by an instruction...
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:191
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const SmallVectorImpl< std::pair< SDValue, SDNode *>> &RecordedNodes)
CheckSame - Implements OP_CheckSame.
void visitSPDescriptorParent(StackProtectorDescriptor &SPD, MachineBasicBlock *ParentBB)
Codegen a new tail for a stack protector check ParentMBB which has had its tail spliced into a stack ...
SDValue getRoot()
Return the current virtual root of the Selection DAG, flushing any PendingLoad items.
void clear()
Clear state and free memory necessary to make this SelectionDAG ready to process a new block...
AnalysisUsage & addRequired()
void setLastLocalValue(MachineInstr *I)
Update the position of the last instruction emitted for materializing constants for use in the curren...
Definition: FastISel.h:238
A description of a memory reference used in the backend.
void resetTargetOptions(const Function &F) const
Reset the target options based on the function&#39;s attributes.
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
Definition: Function.cpp:590
void visitSwitchCase(CaseBlock &CB, MachineBasicBlock *SwitchBB)
visitSwitchCase - Emits the necessary code to represent a single node in the binary search tree resul...
Option class for critical edge splitting.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
virtual bool ComplexPatternFuncMutatesDAG() const
Return true if complex patterns for this target can mutate the DAG.
static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root, CodeGenOpt::Level OptLevel, bool IgnoreChains=false)
IsLegalToFold - Returns true if the specific operand node N of U can be folded during instruction sel...
This class is basically a combination of TimeRegion and Timer.
Definition: Timer.h:160
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
const Value * SwiftErrorArg
The swifterror argument of the current function.
MachineSDNode * getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT)
These are used for target selectors to create a new node with specified return type(s), MachineInstr opcode, and operands.
void visitJumpTable(JumpTable &JT)
visitJumpTable - Emit JumpTable node in the current MBB
DenseMap< const Value *, unsigned > ValueMap
ValueMap - Since we emit code for the function a basic block at a time, we must remember which virtua...
const TargetLowering * TLI
#define LLVM_ATTRIBUTE_ALWAYS_INLINE
LLVM_ATTRIBUTE_ALWAYS_INLINE - On compilers where we have a directive to do so, mark a method "always...
Definition: Compiler.h:198
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
CopyToReg - This node has three operands: a chain, a register number to set to this value...
Definition: ISDOpcodes.h:170
const MDNode * getMD() const
virtual bool enableMachineSchedDefaultSched() const
True if the machine scheduler should disable the TLI preference for preRA scheduling with the source ...
op_iterator op_end() const
static MachinePassRegistry Registry
RegisterScheduler class - Track the registration of instruction schedulers.
Reg
All possible values of the reg field in the ModR/M byte.
virtual void Select(SDNode *N)=0
Main hook for targets to transform nodes into machine nodes.
ScheduleDAGSDNodes *(*)(SelectionDAGISel *, CodeGenOpt::Level) FunctionPassCtor
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
SDValue getEntryNode() const
Return the token chain corresponding to the entry of the function.
Definition: SelectionDAG.h:446
const DataLayout & getDataLayout() const
Definition: SelectionDAG.h:388
An analysis pass which caches information about the entire Module.
Definition: GCMetadata.h:154
SDVTList getVTList(EVT VT)
Return an SDVTList that represents the list of values specified.
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDNode *N)
virtual unsigned getFrameRegister(const MachineFunction &MF) const =0
Debug information queries.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
This file implements a class to represent arbitrary precision integral constant values and operations...
INLINEASM - Represents an inline asm block.
Definition: ISDOpcodes.h:635
This represents a list of ValueType&#39;s that has been intern&#39;d by a SelectionDAG.
unsigned DAGSize
DAGSize - Size of DAG being instruction selected.
void initializeAAResultsWrapperPassPass(PassRegistry &)
MachineInstr * getVRegDef(unsigned Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
defusechain_iterator - This class provides iterator support for machine operands in the function that...
unsigned AssignTopologicalOrder()
Topological-sort the AllNodes list and a assign a unique node id for each node in the DAG based on th...
int getArgumentFrameIndex(const Argument *A)
getArgumentFrameIndex - Get frame index for the byval argument.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
int64_t getSExtValue() const
Key
PAL metadata keys.
virtual StringRef getPatternForIndex(unsigned index)
getPatternForIndex - Patterns selected by tablegen during ISEL
static bool hasExceptionPointerOrCodeUser(const CatchPadInst *CPI)
This is a fast-path instruction selection class that generates poor code and doesn&#39;t support illegal ...
Definition: FastISel.h:67
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:862
unsigned getSizeInBits() const
Return the size of the specified value type in bits.
Definition: ValueTypes.h:292
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
bool getBoolValue() const
Convert APInt to a boolean value.
Definition: APInt.h:471
bool canTrap() const
Return true if evaluation of this constant could trap.
Definition: Constants.cpp:370
void clearKillFlags(unsigned Reg) const
clearKillFlags - Iterate over all the uses of the given register and clear the kill flag from the Mac...
virtual bool supportSwiftError() const
Return true if the target supports swifterror attribute.
bool isSwiftError() const
Return true if this value is a swifterror value.
Definition: Value.cpp:749
SDNode * mutateStrictFPToFP(SDNode *Node)
Mutate the specified strict FP node to its non-strict equivalent, unlinking the node from its chain a...
#define T
ScheduleDAGSDNodes * createBURRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createBURRListDAGScheduler - This creates a bottom up register usage reduction list scheduler...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
static unsigned IsPredicateKnownToFail(const unsigned char *Table, unsigned Index, SDValue N, bool &Result, const SelectionDAGISel &SDISel, SmallVectorImpl< std::pair< SDValue, SDNode *>> &RecordedNodes)
IsPredicateKnownToFail - If we know how and can do so without pushing a scope, evaluate the current n...
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:205
An instruction for storing to memory.
Definition: Instructions.h:306
CondCode
ISD::CondCode enum - These are ordered carefully to make the bitfields below work out...
Definition: ISDOpcodes.h:917
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
op_iterator op_begin() const
MachinePassRegistry - Track the registration of machine passes.
void init(GCFunctionInfo *gfi, AliasAnalysis *AA, const TargetLibraryInfo *li)
virtual const TargetInstrInfo * getInstrInfo() const
TargetConstant* - Like Constant*, but the DAG does not do any folding, simplification, or lowering of the constant.
Definition: ISDOpcodes.h:125
SDValue getTargetConstant(uint64_t Val, const SDLoc &DL, EVT VT, bool isOpaque=false)
Definition: SelectionDAG.h:558
static LLVM_ATTRIBUTE_ALWAYS_INLINE uint64_t GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx)
GetVBR - decode a vbr encoding whose top bit is set.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:140
RESULT = INTRINSIC_WO_CHAIN(INTRINSICID, arg1, arg2, ...) This node represents a target intrinsic fun...
Definition: ISDOpcodes.h:151
SDValue getTargetConstantFP(double Val, const SDLoc &DL, EVT VT)
Definition: SelectionDAG.h:586
const TargetRegisterClass * constrainRegClass(unsigned Reg, const TargetRegisterClass *RC, unsigned MinNumRegs=0)
constrainRegClass - Constrain the register class of the specified virtual register to be a common sub...
Legacy analysis pass which computes BranchProbabilityInfo.
const DataLayout & getDataLayout() const
Return the DataLayout attached to the Module associated to this MF.
auto count(R &&Range, const E &Element) -> typename std::iterator_traits< decltype(adl_begin(Range))>::difference_type
Wrapper function around std::count to count the number of times an element Element occurs in the give...
Definition: STLExtras.h:874
void printrFull(raw_ostream &O, const SelectionDAG *G=nullptr) const
Print a SelectionDAG node and all children down to the leaves.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
static cl::opt< bool > EnableFastISelFallbackReport("fast-isel-report-on-fallback", cl::Hidden, cl::desc("Emit a diagnostic when \ast\instruction selection " "falls back to SelectionDAG."))
UNDEF - An undefined node.
Definition: ISDOpcodes.h:178
static cl::opt< bool > ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden, cl::desc("Pop up a window to show dags before the post legalize types" " dag combine pass"))
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
TargetInstrInfo - Interface to description of machine instruction set.
This corresponds to the llvm.lifetime.
Definition: ISDOpcodes.h:802
MachineRegisterInfo * RegInfo
void clear()
clear - Clear out all the function-specific state.
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:146
unsigned ComputeNumSignBits(SDValue Op, unsigned Depth=0) const
Return the number of times the sign bit of the register is replicated into the other bits...
void init(MachineFunction &NewMF, OptimizationRemarkEmitter &NewORE, Pass *PassPtr)
Prepare this SelectionDAG to process code in the given MachineFunction.
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:141
const BasicBlock & getEntryBlock() const
Definition: Function.h:572
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
bool hasAttrSomewhere(Attribute::AttrKind Kind, unsigned *Index=nullptr) const
Return true if the specified attribute is set for at least one parameter or for the return value...
static SDValue HandleMergeInputChains(SmallVectorImpl< SDNode *> &ChainNodesMatched, SelectionDAG *CurDAG)
HandleMergeInputChains - This implements the OPC_EmitMergeInputChains operation for when the pattern ...
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
BasicBlock * SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
If this edge is a critical edge, insert a new node to split the critical edge.
unsigned getObjectAlignment(int ObjectIdx) const
Return the alignment of the specified stack object.
CriticalEdgeSplittingOptions & setMergeIdenticalEdges()
virtual bool CheckPatternPredicate(unsigned PredNo) const
CheckPatternPredicate - This function is generated by tblgen in the target.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
SmallPtrSet< const Instruction *, 4 > ElidedArgCopyInstrs
void initializeBranchProbabilityInfoWrapperPassPass(PassRegistry &)
OUTCHAIN = INTRINSIC_VOID(INCHAIN, INTRINSICID, arg1, arg2, ...) This node represents a target intrin...
Definition: ISDOpcodes.h:166
CodeGenOpt::Level OptLevel
void addLiveIn(MCPhysReg PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:171
READ_REGISTER, WRITE_REGISTER - This node represents llvm.register on the DAG, which implements the n...
Definition: ISDOpcodes.h:85
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
std::vector< std::pair< MachineInstr *, unsigned > > PHINodesToUpdate
PHINodesToUpdate - A list of phi instructions whose operand list will be updated after processing the...
unsigned const MachineRegisterInfo * MRI
ScheduleDAGSDNodes * createVLIWDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createVLIWDAGScheduler - Scheduler for VLIW targets.
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
bool HasTailCall
HasTailCall - This is set to true if a call in the current block has been translated as a tail call...
MVT getPointerTy(const DataLayout &DL, uint32_t AS=0) const
Return the pointer type for the given address space, defaults to the pointer type from the data layou...
static void preassignSwiftErrorRegs(const TargetLowering *TLI, FunctionLoweringInfo *FuncInfo, BasicBlock::const_iterator Begin, BasicBlock::const_iterator End)
void Legalize()
This transforms the SelectionDAG into a SelectionDAG that is compatible with the target instruction s...
virtual unsigned getExceptionPointerRegister(const Constant *PersonalityFn) const
If a physical register, this returns the register that receives the exception address on entry to an ...
ScheduleDAGSDNodes * createDefaultScheduler(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createDefaultScheduler - This creates an instruction scheduler appropriate for the target...
use_iterator use_begin() const
Provide iteration support to walk over all uses of an SDNode.
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:421
Machine Value Type.
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1497
Value * getAddress() const
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
std::pair< unsigned, bool > getOrCreateSwiftErrorVRegUseAt(const Instruction *, const MachineBasicBlock *, const Value *)
MachineInstrBuilder & UseMI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
void removeDeadCode(MachineBasicBlock::iterator I, MachineBasicBlock::iterator E)
Remove all dead instructions between the I and E.
Definition: FastISel.cpp:375
iterator_range< value_op_iterator > op_values() const
LLVM_ATTRIBUTE_ALWAYS_INLINE iterator begin()
Definition: SmallVector.h:116
const SDValue & getOperand(unsigned Num) const
ScheduleDAGSDNodes * createILPListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level)
createILPListDAGScheduler - This creates a bottom up register pressure aware list scheduler that trie...
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:36
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool succ_empty(const BasicBlock *BB)
Definition: CFG.h:140
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:264
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Definition: Interval.h:113
virtual unsigned getExceptionSelectorRegister(const Constant *PersonalityFn) const
If a physical register, this returns the register that receives the exception typeid on entry to a la...
static unsigned getNumOperandRegisters(unsigned Flag)
getNumOperandRegisters - Extract the number of registers field from the inline asm operand flag...
Definition: InlineAsm.h:336
void RemoveDeadNodes()
This method deletes all unreachable nodes in the SelectionDAG.
Represent the analysis usage information of a pass.
void Combine(CombineLevel Level, AliasAnalysis *AA, CodeGenOpt::Level OptLevel)
This iterates over the nodes in the SelectionDAG, folding certain types of nodes together, or eliminating superfluous nodes.
This class provides iterator support for SDUse operands that use a specific SDNode.
DILocalVariable * getVariable() const
Definition: IntrinsicInst.h:80
use_instr_iterator use_instr_begin(unsigned RegNo) const
bool tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst)
We&#39;re checking to see if we can fold LI into FoldInst.
Definition: FastISel.cpp:2097
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, unsigned ChildNo)
static unsigned getMemoryConstraintID(unsigned Flag)
Definition: InlineAsm.h:329
bool lowerArguments()
Do "fast" instruction selection for function arguments and append the machine instructions to the cur...
Definition: FastISel.cpp:136
static const unsigned End
static cl::opt< bool > UseMBPI("use-mbpi", cl::desc("use Machine Branch Probability Info"), cl::init(true), cl::Hidden)
const APInt & getAPIntValue() const
DIExpression * getExpression() const
Definition: IntrinsicInst.h:84
Interval::pred_iterator pred_end(Interval *I)
Definition: Interval.h:116
AssertSext, AssertZext - These nodes record if a register contains a value that has already been zero...
Definition: ISDOpcodes.h:57
arg_iterator arg_begin()
Definition: Function.h:603
void setHasInlineAsm(bool B)
Set a flag that indicates that the function contains inline assembly.
virtual void PostprocessISelDAG()
PostprocessISelDAG() - This hook allows the target to hack on the graph right after selection...
void RemoveDeadNode(SDNode *N)
Remove the specified node from the system.
self_iterator getIterator()
Definition: ilist_node.h:82
void AddLiveOutRegInfo(unsigned Reg, unsigned NumSignBits, const KnownBits &Known)
AddLiveOutRegInfo - Adds LiveOutInfo for a register.
virtual MachineBasicBlock * EmitInstrWithCustomInserter(MachineInstr &MI, MachineBasicBlock *MBB) const
This method should be implemented by targets that mark instructions with the &#39;usesCustomInserter&#39; fla...
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn&#39;t already there.
Definition: SmallSet.h:81
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:841
static unsigned getFlagWordForMem(unsigned InputFlag, unsigned Constraint)
Augment an existing flag word returned by getFlagWord with the constraint code for a memory constrain...
Definition: InlineAsm.h:312
static cl::opt< int > EnableFastISelAbort("fast-isel-abort", cl::Hidden, cl::desc("Enable abort calls when \ast\instruction selection " "fails to lower an instruction: 0 disable the abort, 1 will " "abort but for args, calls and terminators, 2 will also " "abort for argument lowering, and 3 will never fallback " "to SelectionDAG."))
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:193
unsigned ExceptionPointerVirtReg
If the current MBB is a landing pad, the exception pointer and exception selector registers are copie...
SmallPtrSet< const BasicBlock *, 4 > VisitedBBs
VisitedBBs - The set of basic blocks visited thus far by instruction selection.
static void reportFastISelFailure(MachineFunction &MF, OptimizationRemarkEmitter &ORE, OptimizationRemarkMissed &R, bool ShouldAbort)
static bool isMemKind(unsigned Flag)
Definition: InlineAsm.h:277
bool isCopy() const
Definition: MachineInstr.h:860
Extended Value Type.
Definition: ValueTypes.h:34
bool isImplicitDef() const
Definition: MachineInstr.h:834
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const SelectionDAGISel &SDISel)
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
const MachineBasicBlock & front() const
StringRef getName(unsigned Opcode) const
Returns the name for the instructions with the given opcode.
Definition: MCInstrInfo.h:51
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
void ComputePHILiveOutRegInfo(const PHINode *)
ComputePHILiveOutRegInfo - Compute LiveOutInfo for a PHI&#39;s destination register based on the LiveOutI...
bool isMachineOpcode() const
Test if this node has a post-isel opcode, directly corresponding to a MachineInstr opcode...
static void SplitCriticalSideEffectEdges(Function &Fn, DominatorTree *DT, LoopInfo *LI)
SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that may trap on it...
unsigned getNumOperands() const
Return the number of values used by this operation.
std::string & str()
Flushes the stream contents to the target string and returns the string&#39;s reference.
Definition: raw_ostream.h:478
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
HANDLENODE node - Used as a handle for various purposes.
Definition: ISDOpcodes.h:718
const DIExpression * getDebugExpression() const
Return the complex address expression referenced by this DBG_VALUE instruction.
MachineBasicBlock * MBB
MBB - The current block.
virtual bool enableMachineScheduler() const
True if the subtarget should run MachineScheduler after aggressive coalescing.
EH_LABEL - Represents a label in mid basic block used to track locations needed for debug and excepti...
Definition: ISDOpcodes.h:640
unsigned first
bool isOrEquivalentToAdd(const SDNode *N) const
TargetIntrinsicInfo - Interface to description of machine instruction set.
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N)
void recomputeInsertPt()
Reset InsertPt to prepare for inserting instructions into the current block.
Definition: FastISel.cpp:361
bool use_empty() const
Return true if there are no uses of this node.
bool SplitCSR
True if part of the CSRs will be handled via explicit copies.
bool isLandingPad() const
Return true if this basic block is a landing pad.
Definition: BasicBlock.cpp:442
TokenFactor - This node takes multiple tokens as input and produces a single token result...
Definition: ISDOpcodes.h:50
void dump() const
Dump this node, for debugging.
void visitSPDescriptorFailure(StackProtectorDescriptor &SPD)
Codegen the failure basic block for a stack protector check.
ScheduleDAGSDNodes * createSourceListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createBURRListDAGScheduler - This creates a bottom up list scheduler that schedules nodes in source c...
Iterator for intrusive lists based on ilist_node.
virtual bool supportSplitCSR(MachineFunction *MF) const
Return true if the target supports that a subset of CSRs for the given machine function is handled ex...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
virtual void initializeSplitCSR(MachineBasicBlock *Entry) const
Perform necessary initialization to handle a subset of CSRs explicitly via copies.
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file. ...
virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N, unsigned PatternNo, SmallVectorImpl< std::pair< SDValue, SDNode *> > &Result)
DenseMap< std::pair< const MachineBasicBlock *, const Value * >, unsigned > SwiftErrorVRegDefMap
A map from swifterror value in a basic block to the virtual register it is currently represented by...
DenseMap< unsigned, unsigned > RegFixups
RegFixups - Registers which need to be replaced after isel is done.
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:209
SDNode * SelectNodeTo(SDNode *N, unsigned TargetOpc, EVT VT)
These are used for target selectors to mutate the specified node to have the specified return type...
bool isDebugValue() const
Definition: MachineInstr.h:819
MachineOperand class - Representation of each machine instruction operand.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
SmallVector< MachineInstr *, 8 > ArgDbgValues
ArgDbgValues - A list of DBG_VALUE instructions created during isel for function arguments that are i...
void clear()
Clear out the current SelectionDAG and the associated state and prepare this SelectionDAGBuilder obje...
void setFastISel(bool Enable)
static void createSwiftErrorEntriesInEntryBlock(FunctionLoweringInfo *FuncInfo, FastISel *FastIS, const TargetLowering *TLI, const TargetInstrInfo *TII, SelectionDAGBuilder *SDB)
SelectionDAGISel(TargetMachine &tm, CodeGenOpt::Level OL=CodeGenOpt::Default)
void visit(const Instruction &I)
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:385
static void processDbgDeclares(FunctionLoweringInfo *FuncInfo)
Collect llvm.dbg.declare information.
DenseMap< std::pair< const MachineBasicBlock *, const Value * >, unsigned > SwiftErrorVRegUpwardsUse
A list of upward exposed vreg uses that need to be satisfied by either a copy def or a phi node at th...
Wrapper class for IR location info (IR ordering and DebugLoc) to be passed into SDNode creation funct...
Represents one node in the SelectionDAG.
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
void UpdateSplitBlock(MachineBasicBlock *First, MachineBasicBlock *Last)
UpdateSplitBlock - When an MBB was split during scheduling, update the references that need to refer ...
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static cl::opt< bool > ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden, cl::desc("Pop up a window to show dags before legalize types"))
allnodes_const_iterator allnodes_begin() const
Definition: SelectionDAG.h:423
int64_t getImm() const
virtual void AdjustInstrPostInstrSelection(MachineInstr &MI, SDNode *Node) const
This method should be implemented by targets that mark instructions with the &#39;hasPostISelHook&#39; flag...
SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, unsigned Reg, SDValue N)
Definition: SelectionDAG.h:657
DWARF expression.
const Function & getFunction() const
Return the LLVM function that this machine code represents.
unsigned CreateRegs(Type *Ty)
CreateRegs - Allocate the appropriate number of virtual registers of the correctly promoted or expand...