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