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