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