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