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