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