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