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