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