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