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