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