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