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