1 //===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the SelectionDAGISel class.
12 //===----------------------------------------------------------------------===//
14 #include "ScheduleDAGSDNodes.h"
15 #include "SelectionDAGBuilder.h"
16 #include "llvm/ADT/APInt.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/None.h"
19 #include "llvm/ADT/PostOrderIterator.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/SmallSet.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include "llvm/ADT/StringRef.h"
26 #include "llvm/Analysis/AliasAnalysis.h"
27 #include "llvm/Analysis/BranchProbabilityInfo.h"
28 #include "llvm/Analysis/CFG.h"
29 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
30 #include "llvm/Analysis/TargetLibraryInfo.h"
31 #include "llvm/CodeGen/FastISel.h"
32 #include "llvm/CodeGen/FunctionLoweringInfo.h"
33 #include "llvm/CodeGen/GCMetadata.h"
34 #include "llvm/CodeGen/MachineBasicBlock.h"
35 #include "llvm/CodeGen/MachineFrameInfo.h"
36 #include "llvm/CodeGen/MachineFunction.h"
37 #include "llvm/CodeGen/MachineFunctionPass.h"
38 #include "llvm/CodeGen/MachineInstr.h"
39 #include "llvm/CodeGen/MachineInstrBuilder.h"
40 #include "llvm/CodeGen/MachineMemOperand.h"
41 #include "llvm/CodeGen/MachineOperand.h"
42 #include "llvm/CodeGen/MachinePassRegistry.h"
43 #include "llvm/CodeGen/MachineRegisterInfo.h"
44 #include "llvm/CodeGen/MachineValueType.h"
45 #include "llvm/CodeGen/SchedulerRegistry.h"
46 #include "llvm/CodeGen/SelectionDAG.h"
47 #include "llvm/CodeGen/SelectionDAGISel.h"
48 #include "llvm/CodeGen/SelectionDAGNodes.h"
49 #include "llvm/CodeGen/StackProtector.h"
50 #include "llvm/CodeGen/ValueTypes.h"
51 #include "llvm/IR/BasicBlock.h"
52 #include "llvm/IR/Constants.h"
53 #include "llvm/IR/DebugInfoMetadata.h"
54 #include "llvm/IR/DebugLoc.h"
55 #include "llvm/IR/DiagnosticInfo.h"
56 #include "llvm/IR/Function.h"
57 #include "llvm/IR/InlineAsm.h"
58 #include "llvm/IR/InstrTypes.h"
59 #include "llvm/IR/Instruction.h"
60 #include "llvm/IR/Instructions.h"
61 #include "llvm/IR/IntrinsicInst.h"
62 #include "llvm/IR/Intrinsics.h"
63 #include "llvm/IR/Metadata.h"
64 #include "llvm/IR/Type.h"
65 #include "llvm/IR/User.h"
66 #include "llvm/MC/MCInstrDesc.h"
67 #include "llvm/MC/MCRegisterInfo.h"
68 #include "llvm/Pass.h"
69 #include "llvm/Support/BranchProbability.h"
70 #include "llvm/Support/Casting.h"
71 #include "llvm/Support/CodeGen.h"
72 #include "llvm/Support/CommandLine.h"
73 #include "llvm/Support/Compiler.h"
74 #include "llvm/Support/Debug.h"
75 #include "llvm/Support/ErrorHandling.h"
76 #include "llvm/Support/KnownBits.h"
77 #include "llvm/Support/Timer.h"
78 #include "llvm/Support/raw_ostream.h"
79 #include "llvm/Target/TargetInstrInfo.h"
80 #include "llvm/Target/TargetIntrinsicInfo.h"
81 #include "llvm/Target/TargetLowering.h"
82 #include "llvm/Target/TargetMachine.h"
83 #include "llvm/Target/TargetOptions.h"
84 #include "llvm/Target/TargetRegisterInfo.h"
85 #include "llvm/Target/TargetSubtargetInfo.h"
86 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
98 #define DEBUG_TYPE "isel"
100 STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on");
101 STATISTIC(NumFastIselSuccess, "Number of instructions fast isel selected");
102 STATISTIC(NumFastIselBlocks, "Number of blocks selected entirely by fast isel");
103 STATISTIC(NumDAGBlocks, "Number of blocks selected using DAG");
104 STATISTIC(NumDAGIselRetries,"Number of times dag isel has to try another path");
105 STATISTIC(NumEntryBlocks, "Number of entry blocks encountered");
106 STATISTIC(NumFastIselFailLowerArguments,
107 "Number of entry blocks where fast isel failed to lower arguments");
109 static cl::opt<int> EnableFastISelAbort(
110 "fast-isel-abort", cl::Hidden,
111 cl::desc("Enable abort calls when \"fast\" instruction selection "
112 "fails to lower an instruction: 0 disable the abort, 1 will "
113 "abort but for args, calls and terminators, 2 will also "
114 "abort for argument lowering, and 3 will never fallback "
115 "to SelectionDAG."));
117 static cl::opt<bool> EnableFastISelFallbackReport(
118 "fast-isel-report-on-fallback", cl::Hidden,
119 cl::desc("Emit a diagnostic when \"fast\" instruction selection "
120 "falls back to SelectionDAG."));
124 cl::desc("use Machine Branch Probability Info"),
125 cl::init(true), cl::Hidden);
128 static cl::opt<std::string>
129 FilterDAGBasicBlockName("filter-view-dags", cl::Hidden,
130 cl::desc("Only display the basic block whose name "
131 "matches this for all view-*-dags options"));
133 ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
134 cl::desc("Pop up a window to show dags before the first "
135 "dag combine pass"));
137 ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden,
138 cl::desc("Pop up a window to show dags before legalize types"));
140 ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
141 cl::desc("Pop up a window to show dags before legalize"));
143 ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
144 cl::desc("Pop up a window to show dags before the second "
145 "dag combine pass"));
147 ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden,
148 cl::desc("Pop up a window to show dags before the post legalize types"
149 " dag combine pass"));
151 ViewISelDAGs("view-isel-dags", cl::Hidden,
152 cl::desc("Pop up a window to show isel dags as they are selected"));
154 ViewSchedDAGs("view-sched-dags", cl::Hidden,
155 cl::desc("Pop up a window to show sched dags as they are processed"));
157 ViewSUnitDAGs("view-sunit-dags", cl::Hidden,
158 cl::desc("Pop up a window to show SUnit dags after they are processed"));
160 static const bool ViewDAGCombine1 = false,
161 ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false,
162 ViewDAGCombine2 = false,
163 ViewDAGCombineLT = false,
164 ViewISelDAGs = false, ViewSchedDAGs = false,
165 ViewSUnitDAGs = false;
168 //===---------------------------------------------------------------------===//
170 /// RegisterScheduler class - Track the registration of instruction schedulers.
172 //===---------------------------------------------------------------------===//
173 MachinePassRegistry RegisterScheduler::Registry;
175 //===---------------------------------------------------------------------===//
177 /// ISHeuristic command line option for instruction schedulers.
179 //===---------------------------------------------------------------------===//
180 static cl::opt<RegisterScheduler::FunctionPassCtor, false,
181 RegisterPassParser<RegisterScheduler>>
182 ISHeuristic("pre-RA-sched",
183 cl::init(&createDefaultScheduler), cl::Hidden,
184 cl::desc("Instruction schedulers available (before register"
187 static RegisterScheduler
188 defaultListDAGScheduler("default", "Best scheduler for the target",
189 createDefaultScheduler);
193 //===--------------------------------------------------------------------===//
194 /// \brief This class is used by SelectionDAGISel to temporarily override
195 /// the optimization level on a per-function basis.
196 class OptLevelChanger {
197 SelectionDAGISel &IS;
198 CodeGenOpt::Level SavedOptLevel;
202 OptLevelChanger(SelectionDAGISel &ISel,
203 CodeGenOpt::Level NewOptLevel) : IS(ISel) {
204 SavedOptLevel = IS.OptLevel;
205 if (NewOptLevel == SavedOptLevel)
207 IS.OptLevel = NewOptLevel;
208 IS.TM.setOptLevel(NewOptLevel);
209 DEBUG(dbgs() << "\nChanging optimization level for Function "
210 << IS.MF->getFunction()->getName() << "\n");
211 DEBUG(dbgs() << "\tBefore: -O" << SavedOptLevel
212 << " ; After: -O" << NewOptLevel << "\n");
213 SavedFastISel = IS.TM.Options.EnableFastISel;
214 if (NewOptLevel == CodeGenOpt::None) {
215 IS.TM.setFastISel(IS.TM.getO0WantsFastISel());
216 DEBUG(dbgs() << "\tFastISel is "
217 << (IS.TM.Options.EnableFastISel ? "enabled" : "disabled")
223 if (IS.OptLevel == SavedOptLevel)
225 DEBUG(dbgs() << "\nRestoring optimization level for Function "
226 << IS.MF->getFunction()->getName() << "\n");
227 DEBUG(dbgs() << "\tBefore: -O" << IS.OptLevel
228 << " ; After: -O" << SavedOptLevel << "\n");
229 IS.OptLevel = SavedOptLevel;
230 IS.TM.setOptLevel(SavedOptLevel);
231 IS.TM.setFastISel(SavedFastISel);
235 //===--------------------------------------------------------------------===//
236 /// createDefaultScheduler - This creates an instruction scheduler appropriate
238 ScheduleDAGSDNodes* createDefaultScheduler(SelectionDAGISel *IS,
239 CodeGenOpt::Level OptLevel) {
240 const TargetLowering *TLI = IS->TLI;
241 const TargetSubtargetInfo &ST = IS->MF->getSubtarget();
243 // Try first to see if the Target has its own way of selecting a scheduler
244 if (auto *SchedulerCtor = ST.getDAGScheduler(OptLevel)) {
245 return SchedulerCtor(IS, OptLevel);
248 if (OptLevel == CodeGenOpt::None ||
249 (ST.enableMachineScheduler() && ST.enableMachineSchedDefaultSched()) ||
250 TLI->getSchedulingPreference() == Sched::Source)
251 return createSourceListDAGScheduler(IS, OptLevel);
252 if (TLI->getSchedulingPreference() == Sched::RegPressure)
253 return createBURRListDAGScheduler(IS, OptLevel);
254 if (TLI->getSchedulingPreference() == Sched::Hybrid)
255 return createHybridListDAGScheduler(IS, OptLevel);
256 if (TLI->getSchedulingPreference() == Sched::VLIW)
257 return createVLIWDAGScheduler(IS, OptLevel);
258 assert(TLI->getSchedulingPreference() == Sched::ILP &&
259 "Unknown sched type!");
260 return createILPListDAGScheduler(IS, OptLevel);
263 } // end namespace llvm
265 // EmitInstrWithCustomInserter - This method should be implemented by targets
266 // that mark instructions with the 'usesCustomInserter' flag. These
267 // instructions are special in various ways, which require special support to
268 // insert. The specified MachineInstr is created but not inserted into any
269 // basic blocks, and this method is called to expand it into a sequence of
270 // instructions, potentially also creating new basic blocks and control flow.
271 // When new basic blocks are inserted and the edges from MBB to its successors
272 // are modified, the method should insert pairs of <OldSucc, NewSucc> into the
275 TargetLowering::EmitInstrWithCustomInserter(MachineInstr &MI,
276 MachineBasicBlock *MBB) const {
278 dbgs() << "If a target marks an instruction with "
279 "'usesCustomInserter', it must implement "
280 "TargetLowering::EmitInstrWithCustomInserter!";
282 llvm_unreachable(nullptr);
285 void TargetLowering::AdjustInstrPostInstrSelection(MachineInstr &MI,
286 SDNode *Node) const {
287 assert(!MI.hasPostISelHook() &&
288 "If a target marks an instruction with 'hasPostISelHook', "
289 "it must implement TargetLowering::AdjustInstrPostInstrSelection!");
292 //===----------------------------------------------------------------------===//
293 // SelectionDAGISel code
294 //===----------------------------------------------------------------------===//
296 SelectionDAGISel::SelectionDAGISel(TargetMachine &tm,
297 CodeGenOpt::Level OL) :
298 MachineFunctionPass(ID), TM(tm),
299 FuncInfo(new FunctionLoweringInfo()),
300 CurDAG(new SelectionDAG(tm, OL)),
301 SDB(new SelectionDAGBuilder(*CurDAG, *FuncInfo, OL)),
305 initializeGCModuleInfoPass(*PassRegistry::getPassRegistry());
306 initializeBranchProbabilityInfoWrapperPassPass(
307 *PassRegistry::getPassRegistry());
308 initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
309 initializeTargetLibraryInfoWrapperPassPass(
310 *PassRegistry::getPassRegistry());
313 SelectionDAGISel::~SelectionDAGISel() {
319 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
320 AU.addRequired<AAResultsWrapperPass>();
321 AU.addRequired<GCModuleInfo>();
322 AU.addRequired<StackProtector>();
323 AU.addPreserved<StackProtector>();
324 AU.addPreserved<GCModuleInfo>();
325 AU.addRequired<TargetLibraryInfoWrapperPass>();
326 if (UseMBPI && OptLevel != CodeGenOpt::None)
327 AU.addRequired<BranchProbabilityInfoWrapperPass>();
328 MachineFunctionPass::getAnalysisUsage(AU);
331 /// SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that
332 /// may trap on it. In this case we have to split the edge so that the path
333 /// through the predecessor block that doesn't go to the phi block doesn't
334 /// execute the possibly trapping instruction.
336 /// This is required for correctness, so it must be done at -O0.
338 static void SplitCriticalSideEffectEdges(Function &Fn) {
339 // Loop for blocks with phi nodes.
340 for (BasicBlock &BB : Fn) {
341 PHINode *PN = dyn_cast<PHINode>(BB.begin());
345 // For each block with a PHI node, check to see if any of the input values
346 // are potentially trapping constant expressions. Constant expressions are
347 // the only potentially trapping value that can occur as the argument to a
349 for (BasicBlock::iterator I = BB.begin(); (PN = dyn_cast<PHINode>(I)); ++I)
350 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
351 ConstantExpr *CE = dyn_cast<ConstantExpr>(PN->getIncomingValue(i));
352 if (!CE || !CE->canTrap()) continue;
354 // The only case we have to worry about is when the edge is critical.
355 // Since this block has a PHI Node, we assume it has multiple input
356 // edges: check to see if the pred has multiple successors.
357 BasicBlock *Pred = PN->getIncomingBlock(i);
358 if (Pred->getTerminator()->getNumSuccessors() == 1)
361 // Okay, we have to split this edge.
363 Pred->getTerminator(), GetSuccessorNumber(Pred, &BB),
364 CriticalEdgeSplittingOptions().setMergeIdenticalEdges());
370 bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
371 // If we already selected that function, we do not need to run SDISel.
372 if (mf.getProperties().hasProperty(
373 MachineFunctionProperties::Property::Selected))
375 // Do some sanity-checking on the command-line options.
376 assert((!EnableFastISelAbort || TM.Options.EnableFastISel) &&
377 "-fast-isel-abort > 0 requires -fast-isel");
379 const Function &Fn = *mf.getFunction();
382 // Reset the target options before resetting the optimization
384 // FIXME: This is a horrible hack and should be processed via
385 // codegen looking at the optimization level explicitly when
386 // it wants to look at it.
387 TM.resetTargetOptions(Fn);
388 // Reset OptLevel to None for optnone functions.
389 CodeGenOpt::Level NewOptLevel = OptLevel;
390 if (OptLevel != CodeGenOpt::None && skipFunction(Fn))
391 NewOptLevel = CodeGenOpt::None;
392 OptLevelChanger OLC(*this, NewOptLevel);
394 TII = MF->getSubtarget().getInstrInfo();
395 TLI = MF->getSubtarget().getTargetLowering();
396 RegInfo = &MF->getRegInfo();
397 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
398 LibInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
399 GFI = Fn.hasGC() ? &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn) : nullptr;
400 ORE = make_unique<OptimizationRemarkEmitter>(&Fn);
402 DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n");
404 SplitCriticalSideEffectEdges(const_cast<Function &>(Fn));
406 CurDAG->init(*MF, *ORE);
407 FuncInfo->set(Fn, *MF, CurDAG);
409 if (UseMBPI && OptLevel != CodeGenOpt::None)
410 FuncInfo->BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
412 FuncInfo->BPI = nullptr;
414 SDB->init(GFI, *AA, LibInfo);
416 MF->setHasInlineAsm(false);
418 FuncInfo->SplitCSR = false;
420 // We split CSR if the target supports it for the given function
421 // and the function has only return exits.
422 if (OptLevel != CodeGenOpt::None && TLI->supportSplitCSR(MF)) {
423 FuncInfo->SplitCSR = true;
425 // Collect all the return blocks.
426 for (const BasicBlock &BB : Fn) {
427 if (!succ_empty(&BB))
430 const TerminatorInst *Term = BB.getTerminator();
431 if (isa<UnreachableInst>(Term) || isa<ReturnInst>(Term))
434 // Bail out if the exit block is not Return nor Unreachable.
435 FuncInfo->SplitCSR = false;
440 MachineBasicBlock *EntryMBB = &MF->front();
441 if (FuncInfo->SplitCSR)
442 // This performs initialization so lowering for SplitCSR will be correct.
443 TLI->initializeSplitCSR(EntryMBB);
445 SelectAllBasicBlocks(Fn);
446 if (FastISelFailed && EnableFastISelFallbackReport) {
447 DiagnosticInfoISelFallback DiagFallback(Fn);
448 Fn.getContext().diagnose(DiagFallback);
451 // If the first basic block in the function has live ins that need to be
452 // copied into vregs, emit the copies into the top of the block before
453 // emitting the code for the block.
454 const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();
455 RegInfo->EmitLiveInCopies(EntryMBB, TRI, *TII);
457 // Insert copies in the entry block and the return blocks.
458 if (FuncInfo->SplitCSR) {
459 SmallVector<MachineBasicBlock*, 4> Returns;
460 // Collect all the return blocks.
461 for (MachineBasicBlock &MBB : mf) {
462 if (!MBB.succ_empty())
465 MachineBasicBlock::iterator Term = MBB.getFirstTerminator();
466 if (Term != MBB.end() && Term->isReturn()) {
467 Returns.push_back(&MBB);
471 TLI->insertCopiesSplitCSR(EntryMBB, Returns);
474 DenseMap<unsigned, unsigned> LiveInMap;
475 if (!FuncInfo->ArgDbgValues.empty())
476 for (MachineRegisterInfo::livein_iterator LI = RegInfo->livein_begin(),
477 E = RegInfo->livein_end(); LI != E; ++LI)
479 LiveInMap.insert(std::make_pair(LI->first, LI->second));
481 // Insert DBG_VALUE instructions for function arguments to the entry block.
482 for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; ++i) {
483 MachineInstr *MI = FuncInfo->ArgDbgValues[e-i-1];
484 bool hasFI = MI->getOperand(0).isFI();
486 hasFI ? TRI.getFrameRegister(*MF) : MI->getOperand(0).getReg();
487 if (TargetRegisterInfo::isPhysicalRegister(Reg))
488 EntryMBB->insert(EntryMBB->begin(), MI);
490 MachineInstr *Def = RegInfo->getVRegDef(Reg);
492 MachineBasicBlock::iterator InsertPos = Def;
493 // FIXME: VR def may not be in entry block.
494 Def->getParent()->insert(std::next(InsertPos), MI);
496 DEBUG(dbgs() << "Dropping debug info for dead vreg"
497 << TargetRegisterInfo::virtReg2Index(Reg) << "\n");
500 // If Reg is live-in then update debug info to track its copy in a vreg.
501 DenseMap<unsigned, unsigned>::iterator LDI = LiveInMap.find(Reg);
502 if (LDI != LiveInMap.end()) {
503 assert(!hasFI && "There's no handling of frame pointer updating here yet "
505 MachineInstr *Def = RegInfo->getVRegDef(LDI->second);
506 MachineBasicBlock::iterator InsertPos = Def;
507 const MDNode *Variable = MI->getDebugVariable();
508 const MDNode *Expr = MI->getDebugExpression();
509 DebugLoc DL = MI->getDebugLoc();
510 bool IsIndirect = MI->isIndirectDebugValue();
511 unsigned Offset = IsIndirect ? MI->getOperand(1).getImm() : 0;
512 assert(cast<DILocalVariable>(Variable)->isValidLocationForIntrinsic(DL) &&
513 "Expected inlined-at fields to agree");
514 // Def is never a terminator here, so it is ok to increment InsertPos.
515 BuildMI(*EntryMBB, ++InsertPos, DL, TII->get(TargetOpcode::DBG_VALUE),
516 IsIndirect, LDI->second, Offset, Variable, Expr);
518 // If this vreg is directly copied into an exported register then
519 // that COPY instructions also need DBG_VALUE, if it is the only
520 // user of LDI->second.
521 MachineInstr *CopyUseMI = nullptr;
522 for (MachineRegisterInfo::use_instr_iterator
523 UI = RegInfo->use_instr_begin(LDI->second),
524 E = RegInfo->use_instr_end(); UI != E; ) {
525 MachineInstr *UseMI = &*(UI++);
526 if (UseMI->isDebugValue()) continue;
527 if (UseMI->isCopy() && !CopyUseMI && UseMI->getParent() == EntryMBB) {
528 CopyUseMI = UseMI; continue;
530 // Otherwise this is another use or second copy use.
531 CopyUseMI = nullptr; break;
534 // Use MI's debug location, which describes where Variable was
535 // declared, rather than whatever is attached to CopyUseMI.
536 MachineInstr *NewMI =
537 BuildMI(*MF, DL, TII->get(TargetOpcode::DBG_VALUE), IsIndirect,
538 CopyUseMI->getOperand(0).getReg(), Offset, Variable, Expr);
539 MachineBasicBlock::iterator Pos = CopyUseMI;
540 EntryMBB->insertAfter(Pos, NewMI);
545 // Determine if there are any calls in this machine function.
546 MachineFrameInfo &MFI = MF->getFrameInfo();
547 for (const auto &MBB : *MF) {
548 if (MFI.hasCalls() && MF->hasInlineAsm())
551 for (const auto &MI : MBB) {
552 const MCInstrDesc &MCID = TII->get(MI.getOpcode());
553 if ((MCID.isCall() && !MCID.isReturn()) ||
554 MI.isStackAligningInlineAsm()) {
555 MFI.setHasCalls(true);
557 if (MI.isInlineAsm()) {
558 MF->setHasInlineAsm(true);
563 // Determine if there is a call to setjmp in the machine function.
564 MF->setExposesReturnsTwice(Fn.callsFunctionThatReturnsTwice());
566 // Replace forward-declared registers with the registers containing
567 // the desired value.
568 MachineRegisterInfo &MRI = MF->getRegInfo();
569 for (DenseMap<unsigned, unsigned>::iterator
570 I = FuncInfo->RegFixups.begin(), E = FuncInfo->RegFixups.end();
572 unsigned From = I->first;
573 unsigned To = I->second;
574 // If To is also scheduled to be replaced, find what its ultimate
577 DenseMap<unsigned, unsigned>::iterator J = FuncInfo->RegFixups.find(To);
581 // Make sure the new register has a sufficiently constrained register class.
582 if (TargetRegisterInfo::isVirtualRegister(From) &&
583 TargetRegisterInfo::isVirtualRegister(To))
584 MRI.constrainRegClass(To, MRI.getRegClass(From));
588 // Replacing one register with another won't touch the kill flags.
589 // We need to conservatively clear the kill flags as a kill on the old
590 // register might dominate existing uses of the new register.
591 if (!MRI.use_empty(To))
592 MRI.clearKillFlags(From);
593 MRI.replaceRegWith(From, To);
596 TLI->finalizeLowering(*MF);
598 // Release function-specific state. SDB and CurDAG are already cleared
602 DEBUG(dbgs() << "*** MachineFunction at end of ISel ***\n");
603 DEBUG(MF->print(dbgs()));
608 static void reportFastISelFailure(MachineFunction &MF,
609 OptimizationRemarkEmitter &ORE,
610 OptimizationRemarkMissed &R,
612 // Print the function name explicitly if we don't have a debug location (which
613 // makes the diagnostic less useful) or if we're going to emit a raw error.
614 if (!R.getLocation().isValid() || ShouldAbort)
615 R << (" (in function: " + MF.getName() + ")").str();
618 report_fatal_error(R.getMsg());
623 void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,
624 BasicBlock::const_iterator End,
626 // Lower the instructions. If a call is emitted as a tail call, cease emitting
627 // nodes for this block.
628 for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I) {
629 if (!ElidedArgCopyInstrs.count(&*I))
633 // Make sure the root of the DAG is up-to-date.
634 CurDAG->setRoot(SDB->getControlRoot());
635 HadTailCall = SDB->HasTailCall;
638 // Final step, emit the lowered DAG as machine code.
642 void SelectionDAGISel::ComputeLiveOutVRegInfo() {
643 SmallPtrSet<SDNode*, 16> VisitedNodes;
644 SmallVector<SDNode*, 128> Worklist;
646 Worklist.push_back(CurDAG->getRoot().getNode());
651 SDNode *N = Worklist.pop_back_val();
653 // If we've already seen this node, ignore it.
654 if (!VisitedNodes.insert(N).second)
657 // Otherwise, add all chain operands to the worklist.
658 for (const SDValue &Op : N->op_values())
659 if (Op.getValueType() == MVT::Other)
660 Worklist.push_back(Op.getNode());
662 // If this is a CopyToReg with a vreg dest, process it.
663 if (N->getOpcode() != ISD::CopyToReg)
666 unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();
667 if (!TargetRegisterInfo::isVirtualRegister(DestReg))
670 // Ignore non-scalar or non-integer values.
671 SDValue Src = N->getOperand(2);
672 EVT SrcVT = Src.getValueType();
673 if (!SrcVT.isInteger() || SrcVT.isVector())
676 unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);
677 CurDAG->computeKnownBits(Src, Known);
678 FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, Known);
679 } while (!Worklist.empty());
682 void SelectionDAGISel::CodeGenAndEmitDAG() {
683 StringRef GroupName = "sdag";
684 StringRef GroupDescription = "Instruction Selection and Scheduling";
685 std::string BlockName;
686 int BlockNumber = -1;
688 bool MatchFilterBB = false; (void)MatchFilterBB;
690 // Pre-type legalization allow creation of any node types.
691 CurDAG->NewNodesMustHaveLegalTypes = false;
694 MatchFilterBB = (FilterDAGBasicBlockName.empty() ||
695 FilterDAGBasicBlockName ==
696 FuncInfo->MBB->getBasicBlock()->getName().str());
699 if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs ||
700 ViewDAGCombine2 || ViewDAGCombineLT || ViewISelDAGs || ViewSchedDAGs ||
704 BlockNumber = FuncInfo->MBB->getNumber();
706 (MF->getName() + ":" + FuncInfo->MBB->getBasicBlock()->getName()).str();
708 DEBUG(dbgs() << "Initial selection DAG: BB#" << BlockNumber
709 << " '" << BlockName << "'\n"; CurDAG->dump());
711 if (ViewDAGCombine1 && MatchFilterBB)
712 CurDAG->viewGraph("dag-combine1 input for " + BlockName);
714 // Run the DAG combiner in pre-legalize mode.
716 NamedRegionTimer T("combine1", "DAG Combining 1", GroupName,
717 GroupDescription, TimePassesIsEnabled);
718 CurDAG->Combine(BeforeLegalizeTypes, *AA, OptLevel);
721 DEBUG(dbgs() << "Optimized lowered selection DAG: BB#" << BlockNumber
722 << " '" << BlockName << "'\n"; CurDAG->dump());
724 // Second step, hack on the DAG until it only uses operations and types that
725 // the target supports.
726 if (ViewLegalizeTypesDAGs && MatchFilterBB)
727 CurDAG->viewGraph("legalize-types input for " + BlockName);
731 NamedRegionTimer T("legalize_types", "Type Legalization", GroupName,
732 GroupDescription, TimePassesIsEnabled);
733 Changed = CurDAG->LegalizeTypes();
736 DEBUG(dbgs() << "Type-legalized selection DAG: BB#" << BlockNumber
737 << " '" << BlockName << "'\n"; CurDAG->dump());
739 // Only allow creation of legal node types.
740 CurDAG->NewNodesMustHaveLegalTypes = true;
743 if (ViewDAGCombineLT && MatchFilterBB)
744 CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
746 // Run the DAG combiner in post-type-legalize mode.
748 NamedRegionTimer T("combine_lt", "DAG Combining after legalize types",
749 GroupName, GroupDescription, TimePassesIsEnabled);
750 CurDAG->Combine(AfterLegalizeTypes, *AA, OptLevel);
753 DEBUG(dbgs() << "Optimized type-legalized selection DAG: BB#" << BlockNumber
754 << " '" << BlockName << "'\n"; CurDAG->dump());
759 NamedRegionTimer T("legalize_vec", "Vector Legalization", GroupName,
760 GroupDescription, TimePassesIsEnabled);
761 Changed = CurDAG->LegalizeVectors();
765 DEBUG(dbgs() << "Vector-legalized selection DAG: BB#" << BlockNumber
766 << " '" << BlockName << "'\n"; CurDAG->dump());
769 NamedRegionTimer T("legalize_types2", "Type Legalization 2", GroupName,
770 GroupDescription, TimePassesIsEnabled);
771 CurDAG->LegalizeTypes();
774 DEBUG(dbgs() << "Vector/type-legalized selection DAG: BB#" << BlockNumber
775 << " '" << BlockName << "'\n"; CurDAG->dump());
777 if (ViewDAGCombineLT && MatchFilterBB)
778 CurDAG->viewGraph("dag-combine-lv input for " + BlockName);
780 // Run the DAG combiner in post-type-legalize mode.
782 NamedRegionTimer T("combine_lv", "DAG Combining after legalize vectors",
783 GroupName, GroupDescription, TimePassesIsEnabled);
784 CurDAG->Combine(AfterLegalizeVectorOps, *AA, OptLevel);
787 DEBUG(dbgs() << "Optimized vector-legalized selection DAG: BB#"
788 << BlockNumber << " '" << BlockName << "'\n"; CurDAG->dump());
791 if (ViewLegalizeDAGs && MatchFilterBB)
792 CurDAG->viewGraph("legalize input for " + BlockName);
795 NamedRegionTimer T("legalize", "DAG Legalization", GroupName,
796 GroupDescription, TimePassesIsEnabled);
800 DEBUG(dbgs() << "Legalized selection DAG: BB#" << BlockNumber
801 << " '" << BlockName << "'\n"; CurDAG->dump());
803 if (ViewDAGCombine2 && MatchFilterBB)
804 CurDAG->viewGraph("dag-combine2 input for " + BlockName);
806 // Run the DAG combiner in post-legalize mode.
808 NamedRegionTimer T("combine2", "DAG Combining 2", GroupName,
809 GroupDescription, TimePassesIsEnabled);
810 CurDAG->Combine(AfterLegalizeDAG, *AA, OptLevel);
813 DEBUG(dbgs() << "Optimized legalized selection DAG: BB#" << BlockNumber
814 << " '" << BlockName << "'\n"; CurDAG->dump());
816 if (OptLevel != CodeGenOpt::None)
817 ComputeLiveOutVRegInfo();
819 if (ViewISelDAGs && MatchFilterBB)
820 CurDAG->viewGraph("isel input for " + BlockName);
822 // Third, instruction select all of the operations to machine code, adding the
823 // code to the MachineBasicBlock.
825 NamedRegionTimer T("isel", "Instruction Selection", GroupName,
826 GroupDescription, TimePassesIsEnabled);
827 DoInstructionSelection();
830 DEBUG(dbgs() << "Selected selection DAG: BB#" << BlockNumber
831 << " '" << BlockName << "'\n"; CurDAG->dump());
833 if (ViewSchedDAGs && MatchFilterBB)
834 CurDAG->viewGraph("scheduler input for " + BlockName);
836 // Schedule machine code.
837 ScheduleDAGSDNodes *Scheduler = CreateScheduler();
839 NamedRegionTimer T("sched", "Instruction Scheduling", GroupName,
840 GroupDescription, TimePassesIsEnabled);
841 Scheduler->Run(CurDAG, FuncInfo->MBB);
844 if (ViewSUnitDAGs && MatchFilterBB)
845 Scheduler->viewGraph();
847 // Emit machine code to BB. This can change 'BB' to the last block being
849 MachineBasicBlock *FirstMBB = FuncInfo->MBB, *LastMBB;
851 NamedRegionTimer T("emit", "Instruction Creation", GroupName,
852 GroupDescription, TimePassesIsEnabled);
854 // FuncInfo->InsertPt is passed by reference and set to the end of the
855 // scheduled instructions.
856 LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(FuncInfo->InsertPt);
859 // If the block was split, make sure we update any references that are used to
860 // update PHI nodes later on.
861 if (FirstMBB != LastMBB)
862 SDB->UpdateSplitBlock(FirstMBB, LastMBB);
864 // Free the scheduler state.
866 NamedRegionTimer T("cleanup", "Instruction Scheduling Cleanup", GroupName,
867 GroupDescription, TimePassesIsEnabled);
871 // Free the SelectionDAG state, now that we're finished with it.
877 /// ISelUpdater - helper class to handle updates of the instruction selection
879 class ISelUpdater : public SelectionDAG::DAGUpdateListener {
880 SelectionDAG::allnodes_iterator &ISelPosition;
883 ISelUpdater(SelectionDAG &DAG, SelectionDAG::allnodes_iterator &isp)
884 : SelectionDAG::DAGUpdateListener(DAG), ISelPosition(isp) {}
886 /// NodeDeleted - Handle nodes deleted from the graph. If the node being
887 /// deleted is the current ISelPosition node, update ISelPosition.
889 void NodeDeleted(SDNode *N, SDNode *E) override {
890 if (ISelPosition == SelectionDAG::allnodes_iterator(N))
895 } // end anonymous namespace
897 static bool isStrictFPOp(SDNode *Node, unsigned &NewOpc) {
898 unsigned OrigOpc = Node->getOpcode();
900 case ISD::STRICT_FADD: NewOpc = ISD::FADD; return true;
901 case ISD::STRICT_FSUB: NewOpc = ISD::FSUB; return true;
902 case ISD::STRICT_FMUL: NewOpc = ISD::FMUL; return true;
903 case ISD::STRICT_FDIV: NewOpc = ISD::FDIV; return true;
904 case ISD::STRICT_FREM: NewOpc = ISD::FREM; return true;
905 default: return false;
909 SDNode* SelectionDAGISel::MutateStrictFPToFP(SDNode *Node, unsigned NewOpc) {
910 assert(((Node->getOpcode() == ISD::STRICT_FADD && NewOpc == ISD::FADD) ||
911 (Node->getOpcode() == ISD::STRICT_FSUB && NewOpc == ISD::FSUB) ||
912 (Node->getOpcode() == ISD::STRICT_FMUL && NewOpc == ISD::FMUL) ||
913 (Node->getOpcode() == ISD::STRICT_FDIV && NewOpc == ISD::FDIV) ||
914 (Node->getOpcode() == ISD::STRICT_FREM && NewOpc == ISD::FREM)) &&
915 "Unexpected StrictFP opcode!");
917 // We're taking this node out of the chain, so we need to re-link things.
918 SDValue InputChain = Node->getOperand(0);
919 SDValue OutputChain = SDValue(Node, 1);
920 CurDAG->ReplaceAllUsesOfValueWith(OutputChain, InputChain);
922 SDVTList VTs = CurDAG->getVTList(Node->getOperand(1).getValueType());
923 SDValue Ops[2] = { Node->getOperand(1), Node->getOperand(2) };
924 SDNode *Res = CurDAG->MorphNodeTo(Node, NewOpc, VTs, Ops);
926 // MorphNodeTo can operate in two ways: if an existing node with the
927 // specified operands exists, it can just return it. Otherwise, it
928 // updates the node in place to have the requested operands.
930 // If we updated the node in place, reset the node ID. To the isel,
931 // this should be just like a newly allocated machine node.
934 CurDAG->ReplaceAllUsesWith(Node, Res);
935 CurDAG->RemoveDeadNode(Node);
941 void SelectionDAGISel::DoInstructionSelection() {
942 DEBUG(dbgs() << "===== Instruction selection begins: BB#"
943 << FuncInfo->MBB->getNumber()
944 << " '" << FuncInfo->MBB->getName() << "'\n");
948 // Select target instructions for the DAG.
950 // Number all nodes with a topological order and set DAGSize.
951 DAGSize = CurDAG->AssignTopologicalOrder();
953 // Create a dummy node (which is not added to allnodes), that adds
954 // a reference to the root node, preventing it from being deleted,
955 // and tracking any changes of the root.
956 HandleSDNode Dummy(CurDAG->getRoot());
957 SelectionDAG::allnodes_iterator ISelPosition (CurDAG->getRoot().getNode());
960 // Make sure that ISelPosition gets properly updated when nodes are deleted
961 // in calls made from this function.
962 ISelUpdater ISU(*CurDAG, ISelPosition);
964 // The AllNodes list is now topological-sorted. Visit the
965 // nodes by starting at the end of the list (the root of the
966 // graph) and preceding back toward the beginning (the entry
968 while (ISelPosition != CurDAG->allnodes_begin()) {
969 SDNode *Node = &*--ISelPosition;
970 // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
971 // but there are currently some corner cases that it misses. Also, this
972 // makes it theoretically possible to disable the DAGCombiner.
973 if (Node->use_empty())
976 // When we are using non-default rounding modes or FP exception behavior
977 // FP operations are represented by StrictFP pseudo-operations. They
978 // need to be simplified here so that the target-specific instruction
979 // selectors know how to handle them.
981 // If the current node is a strict FP pseudo-op, the isStrictFPOp()
982 // function will provide the corresponding normal FP opcode to which the
983 // node should be mutated.
984 unsigned NormalFPOpc = ISD::UNDEF;
985 bool IsStrictFPOp = isStrictFPOp(Node, NormalFPOpc);
987 Node = MutateStrictFPToFP(Node, NormalFPOpc);
991 // FIXME: Add code here to attach an implicit def and use of
992 // target-specific FP environment registers.
995 CurDAG->setRoot(Dummy.getValue());
998 DEBUG(dbgs() << "===== Instruction selection ends:\n");
1000 PostprocessISelDAG();
1003 static bool hasExceptionPointerOrCodeUser(const CatchPadInst *CPI) {
1004 for (const User *U : CPI->users()) {
1005 if (const IntrinsicInst *EHPtrCall = dyn_cast<IntrinsicInst>(U)) {
1006 Intrinsic::ID IID = EHPtrCall->getIntrinsicID();
1007 if (IID == Intrinsic::eh_exceptionpointer ||
1008 IID == Intrinsic::eh_exceptioncode)
1015 /// PrepareEHLandingPad - Emit an EH_LABEL, set up live-in registers, and
1016 /// do other setup for EH landing-pad blocks.
1017 bool SelectionDAGISel::PrepareEHLandingPad() {
1018 MachineBasicBlock *MBB = FuncInfo->MBB;
1019 const Constant *PersonalityFn = FuncInfo->Fn->getPersonalityFn();
1020 const BasicBlock *LLVMBB = MBB->getBasicBlock();
1021 const TargetRegisterClass *PtrRC =
1022 TLI->getRegClassFor(TLI->getPointerTy(CurDAG->getDataLayout()));
1024 // Catchpads have one live-in register, which typically holds the exception
1026 if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHI())) {
1027 if (hasExceptionPointerOrCodeUser(CPI)) {
1028 // Get or create the virtual register to hold the pointer or code. Mark
1029 // the live in physreg and copy into the vreg.
1030 MCPhysReg EHPhysReg = TLI->getExceptionPointerRegister(PersonalityFn);
1031 assert(EHPhysReg && "target lacks exception pointer register");
1032 MBB->addLiveIn(EHPhysReg);
1033 unsigned VReg = FuncInfo->getCatchPadExceptionPointerVReg(CPI, PtrRC);
1034 BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(),
1035 TII->get(TargetOpcode::COPY), VReg)
1036 .addReg(EHPhysReg, RegState::Kill);
1041 if (!LLVMBB->isLandingPad())
1044 // Add a label to mark the beginning of the landing pad. Deletion of the
1045 // landing pad can thus be detected via the MachineModuleInfo.
1046 MCSymbol *Label = MF->addLandingPad(MBB);
1048 // Assign the call site to the landing pad's begin label.
1049 MF->setCallSiteLandingPad(Label, SDB->LPadToCallSiteMap[MBB]);
1051 const MCInstrDesc &II = TII->get(TargetOpcode::EH_LABEL);
1052 BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II)
1055 // Mark exception register as live in.
1056 if (unsigned Reg = TLI->getExceptionPointerRegister(PersonalityFn))
1057 FuncInfo->ExceptionPointerVirtReg = MBB->addLiveIn(Reg, PtrRC);
1059 // Mark exception selector register as live in.
1060 if (unsigned Reg = TLI->getExceptionSelectorRegister(PersonalityFn))
1061 FuncInfo->ExceptionSelectorVirtReg = MBB->addLiveIn(Reg, PtrRC);
1066 /// isFoldedOrDeadInstruction - Return true if the specified instruction is
1067 /// side-effect free and is either dead or folded into a generated instruction.
1068 /// Return false if it needs to be emitted.
1069 static bool isFoldedOrDeadInstruction(const Instruction *I,
1070 FunctionLoweringInfo *FuncInfo) {
1071 return !I->mayWriteToMemory() && // Side-effecting instructions aren't folded.
1072 !isa<TerminatorInst>(I) && // Terminators aren't folded.
1073 !isa<DbgInfoIntrinsic>(I) && // Debug instructions aren't folded.
1074 !I->isEHPad() && // EH pad instructions aren't folded.
1075 !FuncInfo->isExportedInst(I); // Exported instrs must be computed.
1078 /// Set up SwiftErrorVals by going through the function. If the function has
1079 /// swifterror argument, it will be the first entry.
1080 static void setupSwiftErrorVals(const Function &Fn, const TargetLowering *TLI,
1081 FunctionLoweringInfo *FuncInfo) {
1082 if (!TLI->supportSwiftError())
1085 FuncInfo->SwiftErrorVals.clear();
1086 FuncInfo->SwiftErrorVRegDefMap.clear();
1087 FuncInfo->SwiftErrorVRegUpwardsUse.clear();
1088 FuncInfo->SwiftErrorArg = nullptr;
1090 // Check if function has a swifterror argument.
1091 bool HaveSeenSwiftErrorArg = false;
1092 for (Function::const_arg_iterator AI = Fn.arg_begin(), AE = Fn.arg_end();
1094 if (AI->hasSwiftErrorAttr()) {
1095 assert(!HaveSeenSwiftErrorArg &&
1096 "Must have only one swifterror parameter");
1097 (void)HaveSeenSwiftErrorArg; // silence warning.
1098 HaveSeenSwiftErrorArg = true;
1099 FuncInfo->SwiftErrorArg = &*AI;
1100 FuncInfo->SwiftErrorVals.push_back(&*AI);
1103 for (const auto &LLVMBB : Fn)
1104 for (const auto &Inst : LLVMBB) {
1105 if (const AllocaInst *Alloca = dyn_cast<AllocaInst>(&Inst))
1106 if (Alloca->isSwiftError())
1107 FuncInfo->SwiftErrorVals.push_back(Alloca);
1111 static void createSwiftErrorEntriesInEntryBlock(FunctionLoweringInfo *FuncInfo,
1113 const TargetLowering *TLI,
1114 const TargetInstrInfo *TII,
1115 SelectionDAGBuilder *SDB) {
1116 if (!TLI->supportSwiftError())
1119 // We only need to do this when we have swifterror parameter or swifterror
1121 if (FuncInfo->SwiftErrorVals.empty())
1124 assert(FuncInfo->MBB == &*FuncInfo->MF->begin() &&
1125 "expected to insert into entry block");
1126 auto &DL = FuncInfo->MF->getDataLayout();
1127 auto const *RC = TLI->getRegClassFor(TLI->getPointerTy(DL));
1128 for (const auto *SwiftErrorVal : FuncInfo->SwiftErrorVals) {
1129 // We will always generate a copy from the argument. It is always used at
1130 // least by the 'return' of the swifterror.
1131 if (FuncInfo->SwiftErrorArg && FuncInfo->SwiftErrorArg == SwiftErrorVal)
1133 unsigned VReg = FuncInfo->MF->getRegInfo().createVirtualRegister(RC);
1134 // Assign Undef to Vreg. We construct MI directly to make sure it works
1136 BuildMI(*FuncInfo->MBB, FuncInfo->MBB->getFirstNonPHI(),
1137 SDB->getCurDebugLoc(), TII->get(TargetOpcode::IMPLICIT_DEF),
1140 // Keep FastIS informed about the value we just inserted.
1142 FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
1144 FuncInfo->setCurrentSwiftErrorVReg(FuncInfo->MBB, SwiftErrorVal, VReg);
1148 /// Propagate swifterror values through the machine function CFG.
1149 static void propagateSwiftErrorVRegs(FunctionLoweringInfo *FuncInfo) {
1150 auto *TLI = FuncInfo->TLI;
1151 if (!TLI->supportSwiftError())
1154 // We only need to do this when we have swifterror parameter or swifterror
1156 if (FuncInfo->SwiftErrorVals.empty())
1159 // For each machine basic block in reverse post order.
1160 ReversePostOrderTraversal<MachineFunction *> RPOT(FuncInfo->MF);
1161 for (ReversePostOrderTraversal<MachineFunction *>::rpo_iterator
1165 MachineBasicBlock *MBB = *It;
1167 // For each swifterror value in the function.
1168 for(const auto *SwiftErrorVal : FuncInfo->SwiftErrorVals) {
1169 auto Key = std::make_pair(MBB, SwiftErrorVal);
1170 auto UUseIt = FuncInfo->SwiftErrorVRegUpwardsUse.find(Key);
1171 auto VRegDefIt = FuncInfo->SwiftErrorVRegDefMap.find(Key);
1172 bool UpwardsUse = UUseIt != FuncInfo->SwiftErrorVRegUpwardsUse.end();
1173 unsigned UUseVReg = UpwardsUse ? UUseIt->second : 0;
1174 bool DownwardDef = VRegDefIt != FuncInfo->SwiftErrorVRegDefMap.end();
1175 assert(!(UpwardsUse && !DownwardDef) &&
1176 "We can't have an upwards use but no downwards def");
1178 // If there is no upwards exposed use and an entry for the swifterror in
1179 // the def map for this value we don't need to do anything: We already
1180 // have a downward def for this basic block.
1181 if (!UpwardsUse && DownwardDef)
1184 // Otherwise we either have an upwards exposed use vreg that we need to
1185 // materialize or need to forward the downward def from predecessors.
1187 // Check whether we have a single vreg def from all predecessors.
1188 // Otherwise we need a phi.
1189 SmallVector<std::pair<MachineBasicBlock *, unsigned>, 4> VRegs;
1190 SmallSet<const MachineBasicBlock*, 8> Visited;
1191 for (auto *Pred : MBB->predecessors()) {
1192 if (!Visited.insert(Pred).second)
1194 VRegs.push_back(std::make_pair(
1195 Pred, FuncInfo->getOrCreateSwiftErrorVReg(Pred, SwiftErrorVal)));
1198 // We have a self-edge.
1199 // If there was no upwards use in this basic block there is now one: the
1200 // phi needs to use it self.
1203 UUseIt = FuncInfo->SwiftErrorVRegUpwardsUse.find(Key);
1204 assert(UUseIt != FuncInfo->SwiftErrorVRegUpwardsUse.end());
1205 UUseVReg = UUseIt->second;
1209 // We need a phi node if we have more than one predecessor with different
1212 VRegs.size() >= 1 &&
1214 VRegs.begin(), VRegs.end(),
1215 [&](const std::pair<const MachineBasicBlock *, unsigned> &V)
1216 -> bool { return V.second != VRegs[0].second; }) !=
1219 // If there is no upwards exposed used and we don't need a phi just
1220 // forward the swifterror vreg from the predecessor(s).
1221 if (!UpwardsUse && !needPHI) {
1222 assert(!VRegs.empty() &&
1223 "No predecessors? The entry block should bail out earlier");
1224 // Just forward the swifterror vreg from the predecessor(s).
1225 FuncInfo->setCurrentSwiftErrorVReg(MBB, SwiftErrorVal, VRegs[0].second);
1229 auto DLoc = isa<Instruction>(SwiftErrorVal)
1230 ? dyn_cast<Instruction>(SwiftErrorVal)->getDebugLoc()
1232 const auto *TII = FuncInfo->MF->getSubtarget().getInstrInfo();
1234 // If we don't need a phi create a copy to the upward exposed vreg.
1237 unsigned DestReg = UUseVReg;
1238 BuildMI(*MBB, MBB->getFirstNonPHI(), DLoc, TII->get(TargetOpcode::COPY),
1240 .addReg(VRegs[0].second);
1244 // We need a phi: if there is an upwards exposed use we already have a
1245 // destination virtual register number otherwise we generate a new one.
1246 auto &DL = FuncInfo->MF->getDataLayout();
1247 auto const *RC = TLI->getRegClassFor(TLI->getPointerTy(DL));
1249 UpwardsUse ? UUseVReg
1250 : FuncInfo->MF->getRegInfo().createVirtualRegister(RC);
1251 MachineInstrBuilder SwiftErrorPHI =
1252 BuildMI(*MBB, MBB->getFirstNonPHI(), DLoc,
1253 TII->get(TargetOpcode::PHI), PHIVReg);
1254 for (auto BBRegPair : VRegs) {
1255 SwiftErrorPHI.addReg(BBRegPair.second).addMBB(BBRegPair.first);
1258 // We did not have a definition in this block before: store the phi's vreg
1259 // as this block downward exposed def.
1261 FuncInfo->setCurrentSwiftErrorVReg(MBB, SwiftErrorVal, PHIVReg);
1266 void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) {
1267 FastISelFailed = false;
1268 // Initialize the Fast-ISel state, if needed.
1269 FastISel *FastIS = nullptr;
1270 if (TM.Options.EnableFastISel)
1271 FastIS = TLI->createFastISel(*FuncInfo, LibInfo);
1273 setupSwiftErrorVals(Fn, TLI, FuncInfo);
1275 ReversePostOrderTraversal<const Function*> RPOT(&Fn);
1277 // Lower arguments up front. An RPO iteration always visits the entry block
1279 assert(*RPOT.begin() == &Fn.getEntryBlock());
1282 // Set up FuncInfo for ISel. Entry blocks never have PHIs.
1283 FuncInfo->MBB = FuncInfo->MBBMap[&Fn.getEntryBlock()];
1284 FuncInfo->InsertPt = FuncInfo->MBB->begin();
1289 // See if fast isel can lower the arguments.
1290 FastIS->startNewBlock();
1291 if (!FastIS->lowerArguments()) {
1292 FastISelFailed = true;
1293 // Fast isel failed to lower these arguments
1294 ++NumFastIselFailLowerArguments;
1296 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1298 &Fn.getEntryBlock());
1299 R << "FastISel didn't lower all arguments: "
1300 << ore::NV("Prototype", Fn.getType());
1301 reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 1);
1303 // Use SelectionDAG argument lowering
1305 CurDAG->setRoot(SDB->getControlRoot());
1307 CodeGenAndEmitDAG();
1310 // If we inserted any instructions at the beginning, make a note of
1311 // where they are, so we can be sure to emit subsequent instructions
1313 if (FuncInfo->InsertPt != FuncInfo->MBB->begin())
1314 FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
1316 FastIS->setLastLocalValue(nullptr);
1318 createSwiftErrorEntriesInEntryBlock(FuncInfo, FastIS, TLI, TII, SDB);
1320 // Iterate over all basic blocks in the function.
1321 for (const BasicBlock *LLVMBB : RPOT) {
1322 if (OptLevel != CodeGenOpt::None) {
1323 bool AllPredsVisited = true;
1324 for (const_pred_iterator PI = pred_begin(LLVMBB), PE = pred_end(LLVMBB);
1326 if (!FuncInfo->VisitedBBs.count(*PI)) {
1327 AllPredsVisited = false;
1332 if (AllPredsVisited) {
1333 for (BasicBlock::const_iterator I = LLVMBB->begin();
1334 const PHINode *PN = dyn_cast<PHINode>(I); ++I)
1335 FuncInfo->ComputePHILiveOutRegInfo(PN);
1337 for (BasicBlock::const_iterator I = LLVMBB->begin();
1338 const PHINode *PN = dyn_cast<PHINode>(I); ++I)
1339 FuncInfo->InvalidatePHILiveOutRegInfo(PN);
1342 FuncInfo->VisitedBBs.insert(LLVMBB);
1345 BasicBlock::const_iterator const Begin =
1346 LLVMBB->getFirstNonPHI()->getIterator();
1347 BasicBlock::const_iterator const End = LLVMBB->end();
1348 BasicBlock::const_iterator BI = End;
1350 FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB];
1352 continue; // Some blocks like catchpads have no code or MBB.
1354 // Insert new instructions after any phi or argument setup code.
1355 FuncInfo->InsertPt = FuncInfo->MBB->end();
1357 // Setup an EH landing-pad block.
1358 FuncInfo->ExceptionPointerVirtReg = 0;
1359 FuncInfo->ExceptionSelectorVirtReg = 0;
1360 if (LLVMBB->isEHPad())
1361 if (!PrepareEHLandingPad())
1364 // Before doing SelectionDAG ISel, see if FastISel has been requested.
1366 if (LLVMBB != &Fn.getEntryBlock())
1367 FastIS->startNewBlock();
1369 unsigned NumFastIselRemaining = std::distance(Begin, End);
1370 // Do FastISel on as many instructions as possible.
1371 for (; BI != Begin; --BI) {
1372 const Instruction *Inst = &*std::prev(BI);
1374 // If we no longer require this instruction, skip it.
1375 if (isFoldedOrDeadInstruction(Inst, FuncInfo) ||
1376 ElidedArgCopyInstrs.count(Inst)) {
1377 --NumFastIselRemaining;
1381 // Bottom-up: reset the insert pos at the top, after any local-value
1383 FastIS->recomputeInsertPt();
1385 // Try to select the instruction with FastISel.
1386 if (FastIS->selectInstruction(Inst)) {
1387 FastISelFailed = true;
1388 --NumFastIselRemaining;
1389 ++NumFastIselSuccess;
1390 // If fast isel succeeded, skip over all the folded instructions, and
1391 // then see if there is a load right before the selected instructions.
1392 // Try to fold the load if so.
1393 const Instruction *BeforeInst = Inst;
1394 while (BeforeInst != &*Begin) {
1395 BeforeInst = &*std::prev(BasicBlock::const_iterator(BeforeInst));
1396 if (!isFoldedOrDeadInstruction(BeforeInst, FuncInfo))
1399 if (BeforeInst != Inst && isa<LoadInst>(BeforeInst) &&
1400 BeforeInst->hasOneUse() &&
1401 FastIS->tryToFoldLoad(cast<LoadInst>(BeforeInst), Inst)) {
1402 // If we succeeded, don't re-select the load.
1403 BI = std::next(BasicBlock::const_iterator(BeforeInst));
1404 --NumFastIselRemaining;
1405 ++NumFastIselSuccess;
1410 // Then handle certain instructions as single-LLVM-Instruction blocks.
1411 if (isa<CallInst>(Inst)) {
1412 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1413 Inst->getDebugLoc(), LLVMBB);
1415 R << "FastISel missed call";
1417 if (R.isEnabled() || EnableFastISelAbort) {
1418 std::string InstStrStorage;
1419 raw_string_ostream InstStr(InstStrStorage);
1422 R << ": " << InstStr.str();
1425 reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 2);
1427 if (!Inst->getType()->isVoidTy() && !Inst->getType()->isTokenTy() &&
1428 !Inst->use_empty()) {
1429 unsigned &R = FuncInfo->ValueMap[Inst];
1431 R = FuncInfo->CreateRegs(Inst->getType());
1434 bool HadTailCall = false;
1435 MachineBasicBlock::iterator SavedInsertPt = FuncInfo->InsertPt;
1436 SelectBasicBlock(Inst->getIterator(), BI, HadTailCall);
1438 // If the call was emitted as a tail call, we're done with the block.
1439 // We also need to delete any previously emitted instructions.
1441 FastIS->removeDeadCode(SavedInsertPt, FuncInfo->MBB->end());
1446 // Recompute NumFastIselRemaining as Selection DAG instruction
1447 // selection may have handled the call, input args, etc.
1448 unsigned RemainingNow = std::distance(Begin, BI);
1449 NumFastIselFailures += NumFastIselRemaining - RemainingNow;
1450 NumFastIselRemaining = RemainingNow;
1454 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1455 Inst->getDebugLoc(), LLVMBB);
1457 bool ShouldAbort = EnableFastISelAbort;
1458 if (isa<TerminatorInst>(Inst)) {
1459 // Use a different message for terminator misses.
1460 R << "FastISel missed terminator";
1461 // Don't abort for terminator unless the level is really high
1462 ShouldAbort = (EnableFastISelAbort > 2);
1464 R << "FastISel missed";
1467 if (R.isEnabled() || EnableFastISelAbort) {
1468 std::string InstStrStorage;
1469 raw_string_ostream InstStr(InstStrStorage);
1471 R << ": " << InstStr.str();
1474 reportFastISelFailure(*MF, *ORE, R, ShouldAbort);
1476 NumFastIselFailures += NumFastIselRemaining;
1480 FastIS->recomputeInsertPt();
1483 if (getAnalysis<StackProtector>().shouldEmitSDCheck(*LLVMBB)) {
1484 bool FunctionBasedInstrumentation =
1485 TLI->getSSPStackGuardCheck(*Fn.getParent());
1486 SDB->SPDescriptor.initialize(LLVMBB, FuncInfo->MBBMap[LLVMBB],
1487 FunctionBasedInstrumentation);
1493 ++NumFastIselBlocks;
1496 // Run SelectionDAG instruction selection on the remainder of the block
1497 // not handled by FastISel. If FastISel is not run, this is the entire
1500 SelectBasicBlock(Begin, BI, HadTailCall);
1502 // But if FastISel was run, we already selected some of the block.
1503 // If we emitted a tail-call, we need to delete any previously emitted
1504 // instruction that follows it.
1505 if (HadTailCall && FuncInfo->InsertPt != FuncInfo->MBB->end())
1506 FastIS->removeDeadCode(FuncInfo->InsertPt, FuncInfo->MBB->end());
1510 FuncInfo->PHINodesToUpdate.clear();
1511 ElidedArgCopyInstrs.clear();
1514 propagateSwiftErrorVRegs(FuncInfo);
1517 SDB->clearDanglingDebugInfo();
1518 SDB->SPDescriptor.resetPerFunctionState();
1521 /// Given that the input MI is before a partial terminator sequence TSeq, return
1522 /// true if M + TSeq also a partial terminator sequence.
1524 /// A Terminator sequence is a sequence of MachineInstrs which at this point in
1525 /// lowering copy vregs into physical registers, which are then passed into
1526 /// terminator instructors so we can satisfy ABI constraints. A partial
1527 /// terminator sequence is an improper subset of a terminator sequence (i.e. it
1528 /// may be the whole terminator sequence).
1529 static bool MIIsInTerminatorSequence(const MachineInstr &MI) {
1530 // If we do not have a copy or an implicit def, we return true if and only if
1531 // MI is a debug value.
1532 if (!MI.isCopy() && !MI.isImplicitDef())
1533 // Sometimes DBG_VALUE MI sneak in between the copies from the vregs to the
1534 // physical registers if there is debug info associated with the terminator
1535 // of our mbb. We want to include said debug info in our terminator
1536 // sequence, so we return true in that case.
1537 return MI.isDebugValue();
1539 // We have left the terminator sequence if we are not doing one of the
1542 // 1. Copying a vreg into a physical register.
1543 // 2. Copying a vreg into a vreg.
1544 // 3. Defining a register via an implicit def.
1546 // OPI should always be a register definition...
1547 MachineInstr::const_mop_iterator OPI = MI.operands_begin();
1548 if (!OPI->isReg() || !OPI->isDef())
1551 // Defining any register via an implicit def is always ok.
1552 if (MI.isImplicitDef())
1555 // Grab the copy source...
1556 MachineInstr::const_mop_iterator OPI2 = OPI;
1558 assert(OPI2 != MI.operands_end()
1559 && "Should have a copy implying we should have 2 arguments.");
1561 // Make sure that the copy dest is not a vreg when the copy source is a
1562 // physical register.
1563 if (!OPI2->isReg() ||
1564 (!TargetRegisterInfo::isPhysicalRegister(OPI->getReg()) &&
1565 TargetRegisterInfo::isPhysicalRegister(OPI2->getReg())))
1571 /// Find the split point at which to splice the end of BB into its success stack
1572 /// protector check machine basic block.
1574 /// On many platforms, due to ABI constraints, terminators, even before register
1575 /// allocation, use physical registers. This creates an issue for us since
1576 /// physical registers at this point can not travel across basic
1577 /// blocks. Luckily, selectiondag always moves physical registers into vregs
1578 /// when they enter functions and moves them through a sequence of copies back
1579 /// into the physical registers right before the terminator creating a
1580 /// ``Terminator Sequence''. This function is searching for the beginning of the
1581 /// terminator sequence so that we can ensure that we splice off not just the
1582 /// terminator, but additionally the copies that move the vregs into the
1583 /// physical registers.
1584 static MachineBasicBlock::iterator
1585 FindSplitPointForStackProtector(MachineBasicBlock *BB) {
1586 MachineBasicBlock::iterator SplitPoint = BB->getFirstTerminator();
1588 if (SplitPoint == BB->begin())
1591 MachineBasicBlock::iterator Start = BB->begin();
1592 MachineBasicBlock::iterator Previous = SplitPoint;
1595 while (MIIsInTerminatorSequence(*Previous)) {
1596 SplitPoint = Previous;
1597 if (Previous == Start)
1606 SelectionDAGISel::FinishBasicBlock() {
1607 DEBUG(dbgs() << "Total amount of phi nodes to update: "
1608 << FuncInfo->PHINodesToUpdate.size() << "\n";
1609 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i)
1610 dbgs() << "Node " << i << " : ("
1611 << FuncInfo->PHINodesToUpdate[i].first
1612 << ", " << FuncInfo->PHINodesToUpdate[i].second << ")\n");
1614 // Next, now that we know what the last MBB the LLVM BB expanded is, update
1615 // PHI nodes in successors.
1616 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) {
1617 MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[i].first);
1618 assert(PHI->isPHI() &&
1619 "This is not a machine PHI node that we are updating!");
1620 if (!FuncInfo->MBB->isSuccessor(PHI->getParent()))
1622 PHI.addReg(FuncInfo->PHINodesToUpdate[i].second).addMBB(FuncInfo->MBB);
1625 // Handle stack protector.
1626 if (SDB->SPDescriptor.shouldEmitFunctionBasedCheckStackProtector()) {
1627 // The target provides a guard check function. There is no need to
1628 // generate error handling code or to split current basic block.
1629 MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
1631 // Add load and check to the basicblock.
1632 FuncInfo->MBB = ParentMBB;
1633 FuncInfo->InsertPt =
1634 FindSplitPointForStackProtector(ParentMBB);
1635 SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
1636 CurDAG->setRoot(SDB->getRoot());
1638 CodeGenAndEmitDAG();
1640 // Clear the Per-BB State.
1641 SDB->SPDescriptor.resetPerBBState();
1642 } else if (SDB->SPDescriptor.shouldEmitStackProtector()) {
1643 MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
1644 MachineBasicBlock *SuccessMBB = SDB->SPDescriptor.getSuccessMBB();
1646 // Find the split point to split the parent mbb. At the same time copy all
1647 // physical registers used in the tail of parent mbb into virtual registers
1648 // before the split point and back into physical registers after the split
1649 // point. This prevents us needing to deal with Live-ins and many other
1650 // register allocation issues caused by us splitting the parent mbb. The
1651 // register allocator will clean up said virtual copies later on.
1652 MachineBasicBlock::iterator SplitPoint =
1653 FindSplitPointForStackProtector(ParentMBB);
1655 // Splice the terminator of ParentMBB into SuccessMBB.
1656 SuccessMBB->splice(SuccessMBB->end(), ParentMBB,
1660 // Add compare/jump on neq/jump to the parent BB.
1661 FuncInfo->MBB = ParentMBB;
1662 FuncInfo->InsertPt = ParentMBB->end();
1663 SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
1664 CurDAG->setRoot(SDB->getRoot());
1666 CodeGenAndEmitDAG();
1668 // CodeGen Failure MBB if we have not codegened it yet.
1669 MachineBasicBlock *FailureMBB = SDB->SPDescriptor.getFailureMBB();
1670 if (FailureMBB->empty()) {
1671 FuncInfo->MBB = FailureMBB;
1672 FuncInfo->InsertPt = FailureMBB->end();
1673 SDB->visitSPDescriptorFailure(SDB->SPDescriptor);
1674 CurDAG->setRoot(SDB->getRoot());
1676 CodeGenAndEmitDAG();
1679 // Clear the Per-BB State.
1680 SDB->SPDescriptor.resetPerBBState();
1683 // Lower each BitTestBlock.
1684 for (auto &BTB : SDB->BitTestCases) {
1685 // Lower header first, if it wasn't already lowered
1687 // Set the current basic block to the mbb we wish to insert the code into
1688 FuncInfo->MBB = BTB.Parent;
1689 FuncInfo->InsertPt = FuncInfo->MBB->end();
1691 SDB->visitBitTestHeader(BTB, FuncInfo->MBB);
1692 CurDAG->setRoot(SDB->getRoot());
1694 CodeGenAndEmitDAG();
1697 BranchProbability UnhandledProb = BTB.Prob;
1698 for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; ++j) {
1699 UnhandledProb -= BTB.Cases[j].ExtraProb;
1700 // Set the current basic block to the mbb we wish to insert the code into
1701 FuncInfo->MBB = BTB.Cases[j].ThisBB;
1702 FuncInfo->InsertPt = FuncInfo->MBB->end();
1705 // If all cases cover a contiguous range, it is not necessary to jump to
1706 // the default block after the last bit test fails. This is because the
1707 // range check during bit test header creation has guaranteed that every
1708 // case here doesn't go outside the range. In this case, there is no need
1709 // to perform the last bit test, as it will always be true. Instead, make
1710 // the second-to-last bit-test fall through to the target of the last bit
1711 // test, and delete the last bit test.
1713 MachineBasicBlock *NextMBB;
1714 if (BTB.ContiguousRange && j + 2 == ej) {
1715 // Second-to-last bit-test with contiguous range: fall through to the
1716 // target of the final bit test.
1717 NextMBB = BTB.Cases[j + 1].TargetBB;
1718 } else if (j + 1 == ej) {
1719 // For the last bit test, fall through to Default.
1720 NextMBB = BTB.Default;
1722 // Otherwise, fall through to the next bit test.
1723 NextMBB = BTB.Cases[j + 1].ThisBB;
1726 SDB->visitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j],
1729 CurDAG->setRoot(SDB->getRoot());
1731 CodeGenAndEmitDAG();
1733 if (BTB.ContiguousRange && j + 2 == ej) {
1734 // Since we're not going to use the final bit test, remove it.
1735 BTB.Cases.pop_back();
1741 for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
1743 MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
1744 MachineBasicBlock *PHIBB = PHI->getParent();
1745 assert(PHI->isPHI() &&
1746 "This is not a machine PHI node that we are updating!");
1747 // This is "default" BB. We have two jumps to it. From "header" BB and
1748 // from last "case" BB, unless the latter was skipped.
1749 if (PHIBB == BTB.Default) {
1750 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(BTB.Parent);
1751 if (!BTB.ContiguousRange) {
1752 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)
1753 .addMBB(BTB.Cases.back().ThisBB);
1756 // One of "cases" BB.
1757 for (unsigned j = 0, ej = BTB.Cases.size();
1759 MachineBasicBlock* cBB = BTB.Cases[j].ThisBB;
1760 if (cBB->isSuccessor(PHIBB))
1761 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(cBB);
1765 SDB->BitTestCases.clear();
1767 // If the JumpTable record is filled in, then we need to emit a jump table.
1768 // Updating the PHI nodes is tricky in this case, since we need to determine
1769 // whether the PHI is a successor of the range check MBB or the jump table MBB
1770 for (unsigned i = 0, e = SDB->JTCases.size(); i != e; ++i) {
1771 // Lower header first, if it wasn't already lowered
1772 if (!SDB->JTCases[i].first.Emitted) {
1773 // Set the current basic block to the mbb we wish to insert the code into
1774 FuncInfo->MBB = SDB->JTCases[i].first.HeaderBB;
1775 FuncInfo->InsertPt = FuncInfo->MBB->end();
1777 SDB->visitJumpTableHeader(SDB->JTCases[i].second, SDB->JTCases[i].first,
1779 CurDAG->setRoot(SDB->getRoot());
1781 CodeGenAndEmitDAG();
1784 // Set the current basic block to the mbb we wish to insert the code into
1785 FuncInfo->MBB = SDB->JTCases[i].second.MBB;
1786 FuncInfo->InsertPt = FuncInfo->MBB->end();
1788 SDB->visitJumpTable(SDB->JTCases[i].second);
1789 CurDAG->setRoot(SDB->getRoot());
1791 CodeGenAndEmitDAG();
1794 for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
1796 MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
1797 MachineBasicBlock *PHIBB = PHI->getParent();
1798 assert(PHI->isPHI() &&
1799 "This is not a machine PHI node that we are updating!");
1800 // "default" BB. We can go there only from header BB.
1801 if (PHIBB == SDB->JTCases[i].second.Default)
1802 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)
1803 .addMBB(SDB->JTCases[i].first.HeaderBB);
1804 // JT BB. Just iterate over successors here
1805 if (FuncInfo->MBB->isSuccessor(PHIBB))
1806 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(FuncInfo->MBB);
1809 SDB->JTCases.clear();
1811 // If we generated any switch lowering information, build and codegen any
1812 // additional DAGs necessary.
1813 for (unsigned i = 0, e = SDB->SwitchCases.size(); i != e; ++i) {
1814 // Set the current basic block to the mbb we wish to insert the code into
1815 FuncInfo->MBB = SDB->SwitchCases[i].ThisBB;
1816 FuncInfo->InsertPt = FuncInfo->MBB->end();
1818 // Determine the unique successors.
1819 SmallVector<MachineBasicBlock *, 2> Succs;
1820 Succs.push_back(SDB->SwitchCases[i].TrueBB);
1821 if (SDB->SwitchCases[i].TrueBB != SDB->SwitchCases[i].FalseBB)
1822 Succs.push_back(SDB->SwitchCases[i].FalseBB);
1824 // Emit the code. Note that this could result in FuncInfo->MBB being split.
1825 SDB->visitSwitchCase(SDB->SwitchCases[i], FuncInfo->MBB);
1826 CurDAG->setRoot(SDB->getRoot());
1828 CodeGenAndEmitDAG();
1830 // Remember the last block, now that any splitting is done, for use in
1831 // populating PHI nodes in successors.
1832 MachineBasicBlock *ThisBB = FuncInfo->MBB;
1834 // Handle any PHI nodes in successors of this chunk, as if we were coming
1835 // from the original BB before switch expansion. Note that PHI nodes can
1836 // occur multiple times in PHINodesToUpdate. We have to be very careful to
1837 // handle them the right number of times.
1838 for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1839 FuncInfo->MBB = Succs[i];
1840 FuncInfo->InsertPt = FuncInfo->MBB->end();
1841 // FuncInfo->MBB may have been removed from the CFG if a branch was
1843 if (ThisBB->isSuccessor(FuncInfo->MBB)) {
1844 for (MachineBasicBlock::iterator
1845 MBBI = FuncInfo->MBB->begin(), MBBE = FuncInfo->MBB->end();
1846 MBBI != MBBE && MBBI->isPHI(); ++MBBI) {
1847 MachineInstrBuilder PHI(*MF, MBBI);
1848 // This value for this PHI node is recorded in PHINodesToUpdate.
1849 for (unsigned pn = 0; ; ++pn) {
1850 assert(pn != FuncInfo->PHINodesToUpdate.size() &&
1851 "Didn't find PHI entry!");
1852 if (FuncInfo->PHINodesToUpdate[pn].first == PHI) {
1853 PHI.addReg(FuncInfo->PHINodesToUpdate[pn].second).addMBB(ThisBB);
1861 SDB->SwitchCases.clear();
1864 /// Create the scheduler. If a specific scheduler was specified
1865 /// via the SchedulerRegistry, use it, otherwise select the
1866 /// one preferred by the target.
1868 ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {
1869 return ISHeuristic(this, OptLevel);
1872 //===----------------------------------------------------------------------===//
1873 // Helper functions used by the generated instruction selector.
1874 //===----------------------------------------------------------------------===//
1875 // Calls to these methods are generated by tblgen.
1877 /// CheckAndMask - The isel is trying to match something like (and X, 255). If
1878 /// the dag combiner simplified the 255, we still want to match. RHS is the
1879 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
1880 /// specified in the .td file (e.g. 255).
1881 bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
1882 int64_t DesiredMaskS) const {
1883 const APInt &ActualMask = RHS->getAPIntValue();
1884 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
1886 // If the actual mask exactly matches, success!
1887 if (ActualMask == DesiredMask)
1890 // If the actual AND mask is allowing unallowed bits, this doesn't match.
1891 if (ActualMask.intersects(~DesiredMask))
1894 // Otherwise, the DAG Combiner may have proven that the value coming in is
1895 // either already zero or is not demanded. Check for known zero input bits.
1896 APInt NeededMask = DesiredMask & ~ActualMask;
1897 if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
1900 // TODO: check to see if missing bits are just not demanded.
1902 // Otherwise, this pattern doesn't match.
1906 /// CheckOrMask - The isel is trying to match something like (or X, 255). If
1907 /// the dag combiner simplified the 255, we still want to match. RHS is the
1908 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
1909 /// specified in the .td file (e.g. 255).
1910 bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
1911 int64_t DesiredMaskS) const {
1912 const APInt &ActualMask = RHS->getAPIntValue();
1913 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
1915 // If the actual mask exactly matches, success!
1916 if (ActualMask == DesiredMask)
1919 // If the actual AND mask is allowing unallowed bits, this doesn't match.
1920 if (ActualMask.intersects(~DesiredMask))
1923 // Otherwise, the DAG Combiner may have proven that the value coming in is
1924 // either already zero or is not demanded. Check for known zero input bits.
1925 APInt NeededMask = DesiredMask & ~ActualMask;
1928 CurDAG->computeKnownBits(LHS, Known);
1930 // If all the missing bits in the or are already known to be set, match!
1931 if (NeededMask.isSubsetOf(Known.One))
1934 // TODO: check to see if missing bits are just not demanded.
1936 // Otherwise, this pattern doesn't match.
1940 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
1941 /// by tblgen. Others should not call it.
1942 void SelectionDAGISel::SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
1944 std::vector<SDValue> InOps;
1945 std::swap(InOps, Ops);
1947 Ops.push_back(InOps[InlineAsm::Op_InputChain]); // 0
1948 Ops.push_back(InOps[InlineAsm::Op_AsmString]); // 1
1949 Ops.push_back(InOps[InlineAsm::Op_MDNode]); // 2, !srcloc
1950 Ops.push_back(InOps[InlineAsm::Op_ExtraInfo]); // 3 (SideEffect, AlignStack)
1952 unsigned i = InlineAsm::Op_FirstOperand, e = InOps.size();
1953 if (InOps[e-1].getValueType() == MVT::Glue)
1954 --e; // Don't process a glue operand if it is here.
1957 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue();
1958 if (!InlineAsm::isMemKind(Flags)) {
1959 // Just skip over this operand, copying the operands verbatim.
1960 Ops.insert(Ops.end(), InOps.begin()+i,
1961 InOps.begin()+i+InlineAsm::getNumOperandRegisters(Flags) + 1);
1962 i += InlineAsm::getNumOperandRegisters(Flags) + 1;
1964 assert(InlineAsm::getNumOperandRegisters(Flags) == 1 &&
1965 "Memory operand with multiple values?");
1967 unsigned TiedToOperand;
1968 if (InlineAsm::isUseOperandTiedToDef(Flags, TiedToOperand)) {
1969 // We need the constraint ID from the operand this is tied to.
1970 unsigned CurOp = InlineAsm::Op_FirstOperand;
1971 Flags = cast<ConstantSDNode>(InOps[CurOp])->getZExtValue();
1972 for (; TiedToOperand; --TiedToOperand) {
1973 CurOp += InlineAsm::getNumOperandRegisters(Flags)+1;
1974 Flags = cast<ConstantSDNode>(InOps[CurOp])->getZExtValue();
1978 // Otherwise, this is a memory operand. Ask the target to select it.
1979 std::vector<SDValue> SelOps;
1980 unsigned ConstraintID = InlineAsm::getMemoryConstraintID(Flags);
1981 if (SelectInlineAsmMemoryOperand(InOps[i+1], ConstraintID, SelOps))
1982 report_fatal_error("Could not match memory address. Inline asm"
1985 // Add this to the output node.
1987 InlineAsm::getFlagWord(InlineAsm::Kind_Mem, SelOps.size());
1988 NewFlags = InlineAsm::getFlagWordForMem(NewFlags, ConstraintID);
1989 Ops.push_back(CurDAG->getTargetConstant(NewFlags, DL, MVT::i32));
1990 Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
1995 // Add the glue input back if present.
1996 if (e != InOps.size())
1997 Ops.push_back(InOps.back());
2000 /// findGlueUse - Return use of MVT::Glue value produced by the specified
2003 static SDNode *findGlueUse(SDNode *N) {
2004 unsigned FlagResNo = N->getNumValues()-1;
2005 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
2006 SDUse &Use = I.getUse();
2007 if (Use.getResNo() == FlagResNo)
2008 return Use.getUser();
2013 /// findNonImmUse - Return true if "Use" is a non-immediate use of "Def".
2014 /// This function recursively traverses up the operand chain, ignoring
2016 static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse,
2017 SDNode *Root, SmallPtrSetImpl<SDNode*> &Visited,
2018 bool IgnoreChains) {
2019 // The NodeID's are given uniques ID's where a node ID is guaranteed to be
2020 // greater than all of its (recursive) operands. If we scan to a point where
2021 // 'use' is smaller than the node we're scanning for, then we know we will
2024 // The Use may be -1 (unassigned) if it is a newly allocated node. This can
2025 // happen because we scan down to newly selected nodes in the case of glue
2027 if ((Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1))
2030 // Don't revisit nodes if we already scanned it and didn't fail, we know we
2031 // won't fail if we scan it again.
2032 if (!Visited.insert(Use).second)
2035 for (const SDValue &Op : Use->op_values()) {
2036 // Ignore chain uses, they are validated by HandleMergeInputChains.
2037 if (Op.getValueType() == MVT::Other && IgnoreChains)
2040 SDNode *N = Op.getNode();
2042 if (Use == ImmedUse || Use == Root)
2043 continue; // We are not looking for immediate use.
2048 // Traverse up the operand chain.
2049 if (findNonImmUse(N, Def, ImmedUse, Root, Visited, IgnoreChains))
2055 /// IsProfitableToFold - Returns true if it's profitable to fold the specific
2056 /// operand node N of U during instruction selection that starts at Root.
2057 bool SelectionDAGISel::IsProfitableToFold(SDValue N, SDNode *U,
2058 SDNode *Root) const {
2059 if (OptLevel == CodeGenOpt::None) return false;
2060 return N.hasOneUse();
2063 /// IsLegalToFold - Returns true if the specific operand node N of
2064 /// U can be folded during instruction selection that starts at Root.
2065 bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
2066 CodeGenOpt::Level OptLevel,
2067 bool IgnoreChains) {
2068 if (OptLevel == CodeGenOpt::None) return false;
2070 // If Root use can somehow reach N through a path that that doesn't contain
2071 // U then folding N would create a cycle. e.g. In the following
2072 // diagram, Root can reach N through X. If N is folded into into Root, then
2073 // X is both a predecessor and a successor of U.
2084 // * indicates nodes to be folded together.
2086 // If Root produces glue, then it gets (even more) interesting. Since it
2087 // will be "glued" together with its glue use in the scheduler, we need to
2088 // check if it might reach N.
2107 // If GU (glue use) indirectly reaches N (the load), and Root folds N
2108 // (call it Fold), then X is a predecessor of GU and a successor of
2109 // Fold. But since Fold and GU are glued together, this will create
2110 // a cycle in the scheduling graph.
2112 // If the node has glue, walk down the graph to the "lowest" node in the
2114 EVT VT = Root->getValueType(Root->getNumValues()-1);
2115 while (VT == MVT::Glue) {
2116 SDNode *GU = findGlueUse(Root);
2120 VT = Root->getValueType(Root->getNumValues()-1);
2122 // If our query node has a glue result with a use, we've walked up it. If
2123 // the user (which has already been selected) has a chain or indirectly uses
2124 // the chain, our WalkChainUsers predicate will not consider it. Because of
2125 // this, we cannot ignore chains in this predicate.
2126 IgnoreChains = false;
2129 SmallPtrSet<SDNode*, 16> Visited;
2130 return !findNonImmUse(Root, N.getNode(), U, Root, Visited, IgnoreChains);
2133 void SelectionDAGISel::Select_INLINEASM(SDNode *N) {
2136 std::vector<SDValue> Ops(N->op_begin(), N->op_end());
2137 SelectInlineAsmMemoryOperands(Ops, DL);
2139 const EVT VTs[] = {MVT::Other, MVT::Glue};
2140 SDValue New = CurDAG->getNode(ISD::INLINEASM, DL, VTs, Ops);
2142 ReplaceUses(N, New.getNode());
2143 CurDAG->RemoveDeadNode(N);
2146 void SelectionDAGISel::Select_READ_REGISTER(SDNode *Op) {
2148 MDNodeSDNode *MD = dyn_cast<MDNodeSDNode>(Op->getOperand(1));
2149 const MDString *RegStr = dyn_cast<MDString>(MD->getMD()->getOperand(0));
2151 TLI->getRegisterByName(RegStr->getString().data(), Op->getValueType(0),
2153 SDValue New = CurDAG->getCopyFromReg(
2154 Op->getOperand(0), dl, Reg, Op->getValueType(0));
2156 ReplaceUses(Op, New.getNode());
2157 CurDAG->RemoveDeadNode(Op);
2160 void SelectionDAGISel::Select_WRITE_REGISTER(SDNode *Op) {
2162 MDNodeSDNode *MD = dyn_cast<MDNodeSDNode>(Op->getOperand(1));
2163 const MDString *RegStr = dyn_cast<MDString>(MD->getMD()->getOperand(0));
2164 unsigned Reg = TLI->getRegisterByName(RegStr->getString().data(),
2165 Op->getOperand(2).getValueType(),
2167 SDValue New = CurDAG->getCopyToReg(
2168 Op->getOperand(0), dl, Reg, Op->getOperand(2));
2170 ReplaceUses(Op, New.getNode());
2171 CurDAG->RemoveDeadNode(Op);
2174 void SelectionDAGISel::Select_UNDEF(SDNode *N) {
2175 CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF, N->getValueType(0));
2178 /// GetVBR - decode a vbr encoding whose top bit is set.
2179 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline uint64_t
2180 GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {
2181 assert(Val >= 128 && "Not a VBR");
2182 Val &= 127; // Remove first vbr bit.
2187 NextBits = MatcherTable[Idx++];
2188 Val |= (NextBits&127) << Shift;
2190 } while (NextBits & 128);
2195 /// When a match is complete, this method updates uses of interior chain results
2196 /// to use the new results.
2197 void SelectionDAGISel::UpdateChains(
2198 SDNode *NodeToMatch, SDValue InputChain,
2199 SmallVectorImpl<SDNode *> &ChainNodesMatched, bool isMorphNodeTo) {
2200 SmallVector<SDNode*, 4> NowDeadNodes;
2202 // Now that all the normal results are replaced, we replace the chain and
2203 // glue results if present.
2204 if (!ChainNodesMatched.empty()) {
2205 assert(InputChain.getNode() &&
2206 "Matched input chains but didn't produce a chain");
2207 // Loop over all of the nodes we matched that produced a chain result.
2208 // Replace all the chain results with the final chain we ended up with.
2209 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2210 SDNode *ChainNode = ChainNodesMatched[i];
2211 // If ChainNode is null, it's because we replaced it on a previous
2212 // iteration and we cleared it out of the map. Just skip it.
2216 assert(ChainNode->getOpcode() != ISD::DELETED_NODE &&
2217 "Deleted node left in chain");
2219 // Don't replace the results of the root node if we're doing a
2221 if (ChainNode == NodeToMatch && isMorphNodeTo)
2224 SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);
2225 if (ChainVal.getValueType() == MVT::Glue)
2226 ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
2227 assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
2228 SelectionDAG::DAGNodeDeletedListener NDL(
2229 *CurDAG, [&](SDNode *N, SDNode *E) {
2230 std::replace(ChainNodesMatched.begin(), ChainNodesMatched.end(), N,
2231 static_cast<SDNode *>(nullptr));
2233 CurDAG->ReplaceAllUsesOfValueWith(ChainVal, InputChain);
2235 // If the node became dead and we haven't already seen it, delete it.
2236 if (ChainNode != NodeToMatch && ChainNode->use_empty() &&
2237 !std::count(NowDeadNodes.begin(), NowDeadNodes.end(), ChainNode))
2238 NowDeadNodes.push_back(ChainNode);
2242 if (!NowDeadNodes.empty())
2243 CurDAG->RemoveDeadNodes(NowDeadNodes);
2245 DEBUG(dbgs() << "ISEL: Match complete!\n");
2251 CR_LeadsToInteriorNode
2254 /// WalkChainUsers - Walk down the users of the specified chained node that is
2255 /// part of the pattern we're matching, looking at all of the users we find.
2256 /// This determines whether something is an interior node, whether we have a
2257 /// non-pattern node in between two pattern nodes (which prevent folding because
2258 /// it would induce a cycle) and whether we have a TokenFactor node sandwiched
2259 /// between pattern nodes (in which case the TF becomes part of the pattern).
2261 /// The walk we do here is guaranteed to be small because we quickly get down to
2262 /// already selected nodes "below" us.
2264 WalkChainUsers(const SDNode *ChainedNode,
2265 SmallVectorImpl<SDNode *> &ChainedNodesInPattern,
2266 DenseMap<const SDNode *, ChainResult> &TokenFactorResult,
2267 SmallVectorImpl<SDNode *> &InteriorChainedNodes) {
2268 ChainResult Result = CR_Simple;
2270 for (SDNode::use_iterator UI = ChainedNode->use_begin(),
2271 E = ChainedNode->use_end(); UI != E; ++UI) {
2272 // Make sure the use is of the chain, not some other value we produce.
2273 if (UI.getUse().getValueType() != MVT::Other) continue;
2277 if (User->getOpcode() == ISD::HANDLENODE) // Root of the graph.
2280 // If we see an already-selected machine node, then we've gone beyond the
2281 // pattern that we're selecting down into the already selected chunk of the
2283 unsigned UserOpcode = User->getOpcode();
2284 if (User->isMachineOpcode() ||
2285 UserOpcode == ISD::CopyToReg ||
2286 UserOpcode == ISD::CopyFromReg ||
2287 UserOpcode == ISD::INLINEASM ||
2288 UserOpcode == ISD::EH_LABEL ||
2289 UserOpcode == ISD::LIFETIME_START ||
2290 UserOpcode == ISD::LIFETIME_END) {
2291 // If their node ID got reset to -1 then they've already been selected.
2292 // Treat them like a MachineOpcode.
2293 if (User->getNodeId() == -1)
2297 // If we have a TokenFactor, we handle it specially.
2298 if (User->getOpcode() != ISD::TokenFactor) {
2299 // If the node isn't a token factor and isn't part of our pattern, then it
2300 // must be a random chained node in between two nodes we're selecting.
2301 // This happens when we have something like:
2306 // Because we structurally match the load/store as a read/modify/write,
2307 // but the call is chained between them. We cannot fold in this case
2308 // because it would induce a cycle in the graph.
2309 if (!std::count(ChainedNodesInPattern.begin(),
2310 ChainedNodesInPattern.end(), User))
2311 return CR_InducesCycle;
2313 // Otherwise we found a node that is part of our pattern. For example in:
2317 // This would happen when we're scanning down from the load and see the
2318 // store as a user. Record that there is a use of ChainedNode that is
2319 // part of the pattern and keep scanning uses.
2320 Result = CR_LeadsToInteriorNode;
2321 InteriorChainedNodes.push_back(User);
2325 // If we found a TokenFactor, there are two cases to consider: first if the
2326 // TokenFactor is just hanging "below" the pattern we're matching (i.e. no
2327 // uses of the TF are in our pattern) we just want to ignore it. Second,
2328 // the TokenFactor can be sandwiched in between two chained nodes, like so:
2334 // | \ DAG's like cheese
2337 // [TokenFactor] [Op]
2344 // In this case, the TokenFactor becomes part of our match and we rewrite it
2345 // as a new TokenFactor.
2347 // To distinguish these two cases, do a recursive walk down the uses.
2348 auto MemoizeResult = TokenFactorResult.find(User);
2349 bool Visited = MemoizeResult != TokenFactorResult.end();
2350 // Recursively walk chain users only if the result is not memoized.
2352 auto Res = WalkChainUsers(User, ChainedNodesInPattern, TokenFactorResult,
2353 InteriorChainedNodes);
2354 MemoizeResult = TokenFactorResult.insert(std::make_pair(User, Res)).first;
2356 switch (MemoizeResult->second) {
2358 // If the uses of the TokenFactor are just already-selected nodes, ignore
2359 // it, it is "below" our pattern.
2361 case CR_InducesCycle:
2362 // If the uses of the TokenFactor lead to nodes that are not part of our
2363 // pattern that are not selected, folding would turn this into a cycle,
2365 return CR_InducesCycle;
2366 case CR_LeadsToInteriorNode:
2367 break; // Otherwise, keep processing.
2370 // Okay, we know we're in the interesting interior case. The TokenFactor
2371 // is now going to be considered part of the pattern so that we rewrite its
2372 // uses (it may have uses that are not part of the pattern) with the
2373 // ultimate chain result of the generated code. We will also add its chain
2374 // inputs as inputs to the ultimate TokenFactor we create.
2375 Result = CR_LeadsToInteriorNode;
2377 ChainedNodesInPattern.push_back(User);
2378 InteriorChainedNodes.push_back(User);
2385 /// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
2386 /// operation for when the pattern matched at least one node with a chains. The
2387 /// input vector contains a list of all of the chained nodes that we match. We
2388 /// must determine if this is a valid thing to cover (i.e. matching it won't
2389 /// induce cycles in the DAG) and if so, creating a TokenFactor node. that will
2390 /// be used as the input node chain for the generated nodes.
2392 HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched,
2393 SelectionDAG *CurDAG) {
2394 // Used for memoization. Without it WalkChainUsers could take exponential
2396 DenseMap<const SDNode *, ChainResult> TokenFactorResult;
2397 // Walk all of the chained nodes we've matched, recursively scanning down the
2398 // users of the chain result. This adds any TokenFactor nodes that are caught
2399 // in between chained nodes to the chained and interior nodes list.
2400 SmallVector<SDNode*, 3> InteriorChainedNodes;
2401 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2402 if (WalkChainUsers(ChainNodesMatched[i], ChainNodesMatched,
2404 InteriorChainedNodes) == CR_InducesCycle)
2405 return SDValue(); // Would induce a cycle.
2408 // Okay, we have walked all the matched nodes and collected TokenFactor nodes
2409 // that we are interested in. Form our input TokenFactor node.
2410 SmallVector<SDValue, 3> InputChains;
2411 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2412 // Add the input chain of this node to the InputChains list (which will be
2413 // the operands of the generated TokenFactor) if it's not an interior node.
2414 SDNode *N = ChainNodesMatched[i];
2415 if (N->getOpcode() != ISD::TokenFactor) {
2416 if (std::count(InteriorChainedNodes.begin(),InteriorChainedNodes.end(),N))
2419 // Otherwise, add the input chain.
2420 SDValue InChain = ChainNodesMatched[i]->getOperand(0);
2421 assert(InChain.getValueType() == MVT::Other && "Not a chain");
2422 InputChains.push_back(InChain);
2426 // If we have a token factor, we want to add all inputs of the token factor
2427 // that are not part of the pattern we're matching.
2428 for (const SDValue &Op : N->op_values()) {
2429 if (!std::count(ChainNodesMatched.begin(), ChainNodesMatched.end(),
2431 InputChains.push_back(Op);
2435 if (InputChains.size() == 1)
2436 return InputChains[0];
2437 return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]),
2438 MVT::Other, InputChains);
2441 /// MorphNode - Handle morphing a node in place for the selector.
2442 SDNode *SelectionDAGISel::
2443 MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
2444 ArrayRef<SDValue> Ops, unsigned EmitNodeInfo) {
2445 // It is possible we're using MorphNodeTo to replace a node with no
2446 // normal results with one that has a normal result (or we could be
2447 // adding a chain) and the input could have glue and chains as well.
2448 // In this case we need to shift the operands down.
2449 // FIXME: This is a horrible hack and broken in obscure cases, no worse
2450 // than the old isel though.
2451 int OldGlueResultNo = -1, OldChainResultNo = -1;
2453 unsigned NTMNumResults = Node->getNumValues();
2454 if (Node->getValueType(NTMNumResults-1) == MVT::Glue) {
2455 OldGlueResultNo = NTMNumResults-1;
2456 if (NTMNumResults != 1 &&
2457 Node->getValueType(NTMNumResults-2) == MVT::Other)
2458 OldChainResultNo = NTMNumResults-2;
2459 } else if (Node->getValueType(NTMNumResults-1) == MVT::Other)
2460 OldChainResultNo = NTMNumResults-1;
2462 // Call the underlying SelectionDAG routine to do the transmogrification. Note
2463 // that this deletes operands of the old node that become dead.
2464 SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops);
2466 // MorphNodeTo can operate in two ways: if an existing node with the
2467 // specified operands exists, it can just return it. Otherwise, it
2468 // updates the node in place to have the requested operands.
2470 // If we updated the node in place, reset the node ID. To the isel,
2471 // this should be just like a newly allocated machine node.
2475 unsigned ResNumResults = Res->getNumValues();
2476 // Move the glue if needed.
2477 if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 &&
2478 (unsigned)OldGlueResultNo != ResNumResults-1)
2479 CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldGlueResultNo),
2480 SDValue(Res, ResNumResults-1));
2482 if ((EmitNodeInfo & OPFL_GlueOutput) != 0)
2485 // Move the chain reference if needed.
2486 if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
2487 (unsigned)OldChainResultNo != ResNumResults-1)
2488 CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldChainResultNo),
2489 SDValue(Res, ResNumResults-1));
2491 // Otherwise, no replacement happened because the node already exists. Replace
2492 // Uses of the old node with the new one.
2494 CurDAG->ReplaceAllUsesWith(Node, Res);
2495 CurDAG->RemoveDeadNode(Node);
2501 /// CheckSame - Implements OP_CheckSame.
2502 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2503 CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2505 const SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) {
2506 // Accept if it is exactly the same as a previously recorded node.
2507 unsigned RecNo = MatcherTable[MatcherIndex++];
2508 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2509 return N == RecordedNodes[RecNo].first;
2512 /// CheckChildSame - Implements OP_CheckChildXSame.
2513 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2514 CheckChildSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2516 const SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes,
2518 if (ChildNo >= N.getNumOperands())
2519 return false; // Match fails if out of range child #.
2520 return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo),
2524 /// CheckPatternPredicate - Implements OP_CheckPatternPredicate.
2525 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2526 CheckPatternPredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2527 const SelectionDAGISel &SDISel) {
2528 return SDISel.CheckPatternPredicate(MatcherTable[MatcherIndex++]);
2531 /// CheckNodePredicate - Implements OP_CheckNodePredicate.
2532 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2533 CheckNodePredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2534 const SelectionDAGISel &SDISel, SDNode *N) {
2535 return SDISel.CheckNodePredicate(N, MatcherTable[MatcherIndex++]);
2538 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2539 CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2541 uint16_t Opc = MatcherTable[MatcherIndex++];
2542 Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
2543 return N->getOpcode() == Opc;
2546 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2547 CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2548 const TargetLowering *TLI, const DataLayout &DL) {
2549 MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2550 if (N.getValueType() == VT) return true;
2552 // Handle the case when VT is iPTR.
2553 return VT == MVT::iPTR && N.getValueType() == TLI->getPointerTy(DL);
2556 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2557 CheckChildType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2558 SDValue N, const TargetLowering *TLI, const DataLayout &DL,
2560 if (ChildNo >= N.getNumOperands())
2561 return false; // Match fails if out of range child #.
2562 return ::CheckType(MatcherTable, MatcherIndex, N.getOperand(ChildNo), TLI,
2566 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2567 CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2569 return cast<CondCodeSDNode>(N)->get() ==
2570 (ISD::CondCode)MatcherTable[MatcherIndex++];
2573 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2574 CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2575 SDValue N, const TargetLowering *TLI, const DataLayout &DL) {
2576 MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2577 if (cast<VTSDNode>(N)->getVT() == VT)
2580 // Handle the case when VT is iPTR.
2581 return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI->getPointerTy(DL);
2584 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2585 CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2587 int64_t Val = MatcherTable[MatcherIndex++];
2589 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2591 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N);
2592 return C && C->getSExtValue() == Val;
2595 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2596 CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2597 SDValue N, unsigned ChildNo) {
2598 if (ChildNo >= N.getNumOperands())
2599 return false; // Match fails if out of range child #.
2600 return ::CheckInteger(MatcherTable, MatcherIndex, N.getOperand(ChildNo));
2603 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2604 CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2605 SDValue N, const SelectionDAGISel &SDISel) {
2606 int64_t Val = MatcherTable[MatcherIndex++];
2608 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2610 if (N->getOpcode() != ISD::AND) return false;
2612 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
2613 return C && SDISel.CheckAndMask(N.getOperand(0), C, Val);
2616 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2617 CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2618 SDValue N, const SelectionDAGISel &SDISel) {
2619 int64_t Val = MatcherTable[MatcherIndex++];
2621 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2623 if (N->getOpcode() != ISD::OR) return false;
2625 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
2626 return C && SDISel.CheckOrMask(N.getOperand(0), C, Val);
2629 /// IsPredicateKnownToFail - If we know how and can do so without pushing a
2630 /// scope, evaluate the current node. If the current predicate is known to
2631 /// fail, set Result=true and return anything. If the current predicate is
2632 /// known to pass, set Result=false and return the MatcherIndex to continue
2633 /// with. If the current predicate is unknown, set Result=false and return the
2634 /// MatcherIndex to continue with.
2635 static unsigned IsPredicateKnownToFail(const unsigned char *Table,
2636 unsigned Index, SDValue N,
2638 const SelectionDAGISel &SDISel,
2639 SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) {
2640 switch (Table[Index++]) {
2643 return Index-1; // Could not evaluate this predicate.
2644 case SelectionDAGISel::OPC_CheckSame:
2645 Result = !::CheckSame(Table, Index, N, RecordedNodes);
2647 case SelectionDAGISel::OPC_CheckChild0Same:
2648 case SelectionDAGISel::OPC_CheckChild1Same:
2649 case SelectionDAGISel::OPC_CheckChild2Same:
2650 case SelectionDAGISel::OPC_CheckChild3Same:
2651 Result = !::CheckChildSame(Table, Index, N, RecordedNodes,
2652 Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Same);
2654 case SelectionDAGISel::OPC_CheckPatternPredicate:
2655 Result = !::CheckPatternPredicate(Table, Index, SDISel);
2657 case SelectionDAGISel::OPC_CheckPredicate:
2658 Result = !::CheckNodePredicate(Table, Index, SDISel, N.getNode());
2660 case SelectionDAGISel::OPC_CheckOpcode:
2661 Result = !::CheckOpcode(Table, Index, N.getNode());
2663 case SelectionDAGISel::OPC_CheckType:
2664 Result = !::CheckType(Table, Index, N, SDISel.TLI,
2665 SDISel.CurDAG->getDataLayout());
2667 case SelectionDAGISel::OPC_CheckChild0Type:
2668 case SelectionDAGISel::OPC_CheckChild1Type:
2669 case SelectionDAGISel::OPC_CheckChild2Type:
2670 case SelectionDAGISel::OPC_CheckChild3Type:
2671 case SelectionDAGISel::OPC_CheckChild4Type:
2672 case SelectionDAGISel::OPC_CheckChild5Type:
2673 case SelectionDAGISel::OPC_CheckChild6Type:
2674 case SelectionDAGISel::OPC_CheckChild7Type:
2675 Result = !::CheckChildType(
2676 Table, Index, N, SDISel.TLI, SDISel.CurDAG->getDataLayout(),
2677 Table[Index - 1] - SelectionDAGISel::OPC_CheckChild0Type);
2679 case SelectionDAGISel::OPC_CheckCondCode:
2680 Result = !::CheckCondCode(Table, Index, N);
2682 case SelectionDAGISel::OPC_CheckValueType:
2683 Result = !::CheckValueType(Table, Index, N, SDISel.TLI,
2684 SDISel.CurDAG->getDataLayout());
2686 case SelectionDAGISel::OPC_CheckInteger:
2687 Result = !::CheckInteger(Table, Index, N);
2689 case SelectionDAGISel::OPC_CheckChild0Integer:
2690 case SelectionDAGISel::OPC_CheckChild1Integer:
2691 case SelectionDAGISel::OPC_CheckChild2Integer:
2692 case SelectionDAGISel::OPC_CheckChild3Integer:
2693 case SelectionDAGISel::OPC_CheckChild4Integer:
2694 Result = !::CheckChildInteger(Table, Index, N,
2695 Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Integer);
2697 case SelectionDAGISel::OPC_CheckAndImm:
2698 Result = !::CheckAndImm(Table, Index, N, SDISel);
2700 case SelectionDAGISel::OPC_CheckOrImm:
2701 Result = !::CheckOrImm(Table, Index, N, SDISel);
2709 /// FailIndex - If this match fails, this is the index to continue with.
2712 /// NodeStack - The node stack when the scope was formed.
2713 SmallVector<SDValue, 4> NodeStack;
2715 /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
2716 unsigned NumRecordedNodes;
2718 /// NumMatchedMemRefs - The number of matched memref entries.
2719 unsigned NumMatchedMemRefs;
2721 /// InputChain/InputGlue - The current chain/glue
2722 SDValue InputChain, InputGlue;
2724 /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.
2725 bool HasChainNodesMatched;
2728 /// \\brief A DAG update listener to keep the matching state
2729 /// (i.e. RecordedNodes and MatchScope) uptodate if the target is allowed to
2730 /// change the DAG while matching. X86 addressing mode matcher is an example
2732 class MatchStateUpdater : public SelectionDAG::DAGUpdateListener
2734 SDNode **NodeToMatch;
2735 SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes;
2736 SmallVectorImpl<MatchScope> &MatchScopes;
2739 MatchStateUpdater(SelectionDAG &DAG, SDNode **NodeToMatch,
2740 SmallVectorImpl<std::pair<SDValue, SDNode *>> &RN,
2741 SmallVectorImpl<MatchScope> &MS)
2742 : SelectionDAG::DAGUpdateListener(DAG), NodeToMatch(NodeToMatch),
2743 RecordedNodes(RN), MatchScopes(MS) {}
2745 void NodeDeleted(SDNode *N, SDNode *E) override {
2746 // Some early-returns here to avoid the search if we deleted the node or
2747 // if the update comes from MorphNodeTo (MorphNodeTo is the last thing we
2748 // do, so it's unnecessary to update matching state at that point).
2749 // Neither of these can occur currently because we only install this
2750 // update listener during matching a complex patterns.
2751 if (!E || E->isMachineOpcode())
2753 // Check if NodeToMatch was updated.
2754 if (N == *NodeToMatch)
2756 // Performing linear search here does not matter because we almost never
2757 // run this code. You'd have to have a CSE during complex pattern
2759 for (auto &I : RecordedNodes)
2760 if (I.first.getNode() == N)
2763 for (auto &I : MatchScopes)
2764 for (auto &J : I.NodeStack)
2765 if (J.getNode() == N)
2770 } // end anonymous namespace
2772 void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch,
2773 const unsigned char *MatcherTable,
2774 unsigned TableSize) {
2775 // FIXME: Should these even be selected? Handle these cases in the caller?
2776 switch (NodeToMatch->getOpcode()) {
2779 case ISD::EntryToken: // These nodes remain the same.
2780 case ISD::BasicBlock:
2782 case ISD::RegisterMask:
2783 case ISD::HANDLENODE:
2784 case ISD::MDNODE_SDNODE:
2785 case ISD::TargetConstant:
2786 case ISD::TargetConstantFP:
2787 case ISD::TargetConstantPool:
2788 case ISD::TargetFrameIndex:
2789 case ISD::TargetExternalSymbol:
2791 case ISD::TargetBlockAddress:
2792 case ISD::TargetJumpTable:
2793 case ISD::TargetGlobalTLSAddress:
2794 case ISD::TargetGlobalAddress:
2795 case ISD::TokenFactor:
2796 case ISD::CopyFromReg:
2797 case ISD::CopyToReg:
2799 case ISD::LIFETIME_START:
2800 case ISD::LIFETIME_END:
2801 NodeToMatch->setNodeId(-1); // Mark selected.
2803 case ISD::AssertSext:
2804 case ISD::AssertZext:
2805 CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, 0),
2806 NodeToMatch->getOperand(0));
2807 CurDAG->RemoveDeadNode(NodeToMatch);
2809 case ISD::INLINEASM:
2810 Select_INLINEASM(NodeToMatch);
2812 case ISD::READ_REGISTER:
2813 Select_READ_REGISTER(NodeToMatch);
2815 case ISD::WRITE_REGISTER:
2816 Select_WRITE_REGISTER(NodeToMatch);
2819 Select_UNDEF(NodeToMatch);
2823 assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
2825 // Set up the node stack with NodeToMatch as the only node on the stack.
2826 SmallVector<SDValue, 8> NodeStack;
2827 SDValue N = SDValue(NodeToMatch, 0);
2828 NodeStack.push_back(N);
2830 // MatchScopes - Scopes used when matching, if a match failure happens, this
2831 // indicates where to continue checking.
2832 SmallVector<MatchScope, 8> MatchScopes;
2834 // RecordedNodes - This is the set of nodes that have been recorded by the
2835 // state machine. The second value is the parent of the node, or null if the
2836 // root is recorded.
2837 SmallVector<std::pair<SDValue, SDNode*>, 8> RecordedNodes;
2839 // MatchedMemRefs - This is the set of MemRef's we've seen in the input
2841 SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
2843 // These are the current input chain and glue for use when generating nodes.
2844 // Various Emit operations change these. For example, emitting a copytoreg
2845 // uses and updates these.
2846 SDValue InputChain, InputGlue;
2848 // ChainNodesMatched - If a pattern matches nodes that have input/output
2849 // chains, the OPC_EmitMergeInputChains operation is emitted which indicates
2850 // which ones they are. The result is captured into this list so that we can
2851 // update the chain results when the pattern is complete.
2852 SmallVector<SDNode*, 3> ChainNodesMatched;
2854 DEBUG(dbgs() << "ISEL: Starting pattern match on root node: ";
2855 NodeToMatch->dump(CurDAG);
2858 // Determine where to start the interpreter. Normally we start at opcode #0,
2859 // but if the state machine starts with an OPC_SwitchOpcode, then we
2860 // accelerate the first lookup (which is guaranteed to be hot) with the
2861 // OpcodeOffset table.
2862 unsigned MatcherIndex = 0;
2864 if (!OpcodeOffset.empty()) {
2865 // Already computed the OpcodeOffset table, just index into it.
2866 if (N.getOpcode() < OpcodeOffset.size())
2867 MatcherIndex = OpcodeOffset[N.getOpcode()];
2868 DEBUG(dbgs() << " Initial Opcode index to " << MatcherIndex << "\n");
2870 } else if (MatcherTable[0] == OPC_SwitchOpcode) {
2871 // Otherwise, the table isn't computed, but the state machine does start
2872 // with an OPC_SwitchOpcode instruction. Populate the table now, since this
2873 // is the first time we're selecting an instruction.
2876 // Get the size of this case.
2877 unsigned CaseSize = MatcherTable[Idx++];
2879 CaseSize = GetVBR(CaseSize, MatcherTable, Idx);
2880 if (CaseSize == 0) break;
2882 // Get the opcode, add the index to the table.
2883 uint16_t Opc = MatcherTable[Idx++];
2884 Opc |= (unsigned short)MatcherTable[Idx++] << 8;
2885 if (Opc >= OpcodeOffset.size())
2886 OpcodeOffset.resize((Opc+1)*2);
2887 OpcodeOffset[Opc] = Idx;
2891 // Okay, do the lookup for the first opcode.
2892 if (N.getOpcode() < OpcodeOffset.size())
2893 MatcherIndex = OpcodeOffset[N.getOpcode()];
2897 assert(MatcherIndex < TableSize && "Invalid index");
2899 unsigned CurrentOpcodeIndex = MatcherIndex;
2901 BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++];
2904 // Okay, the semantics of this operation are that we should push a scope
2905 // then evaluate the first child. However, pushing a scope only to have
2906 // the first check fail (which then pops it) is inefficient. If we can
2907 // determine immediately that the first check (or first several) will
2908 // immediately fail, don't even bother pushing a scope for them.
2912 unsigned NumToSkip = MatcherTable[MatcherIndex++];
2913 if (NumToSkip & 128)
2914 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
2915 // Found the end of the scope with no match.
2916 if (NumToSkip == 0) {
2921 FailIndex = MatcherIndex+NumToSkip;
2923 unsigned MatcherIndexOfPredicate = MatcherIndex;
2924 (void)MatcherIndexOfPredicate; // silence warning.
2926 // If we can't evaluate this predicate without pushing a scope (e.g. if
2927 // it is a 'MoveParent') or if the predicate succeeds on this node, we
2928 // push the scope and evaluate the full predicate chain.
2930 MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,
2931 Result, *this, RecordedNodes);
2935 DEBUG(dbgs() << " Skipped scope entry (due to false predicate) at "
2936 << "index " << MatcherIndexOfPredicate
2937 << ", continuing at " << FailIndex << "\n");
2938 ++NumDAGIselRetries;
2940 // Otherwise, we know that this case of the Scope is guaranteed to fail,
2941 // move to the next case.
2942 MatcherIndex = FailIndex;
2945 // If the whole scope failed to match, bail.
2946 if (FailIndex == 0) break;
2948 // Push a MatchScope which indicates where to go if the first child fails
2950 MatchScope NewEntry;
2951 NewEntry.FailIndex = FailIndex;
2952 NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
2953 NewEntry.NumRecordedNodes = RecordedNodes.size();
2954 NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
2955 NewEntry.InputChain = InputChain;
2956 NewEntry.InputGlue = InputGlue;
2957 NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
2958 MatchScopes.push_back(NewEntry);
2961 case OPC_RecordNode: {
2962 // Remember this node, it may end up being an operand in the pattern.
2963 SDNode *Parent = nullptr;
2964 if (NodeStack.size() > 1)
2965 Parent = NodeStack[NodeStack.size()-2].getNode();
2966 RecordedNodes.push_back(std::make_pair(N, Parent));
2970 case OPC_RecordChild0: case OPC_RecordChild1:
2971 case OPC_RecordChild2: case OPC_RecordChild3:
2972 case OPC_RecordChild4: case OPC_RecordChild5:
2973 case OPC_RecordChild6: case OPC_RecordChild7: {
2974 unsigned ChildNo = Opcode-OPC_RecordChild0;
2975 if (ChildNo >= N.getNumOperands())
2976 break; // Match fails if out of range child #.
2978 RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo),
2982 case OPC_RecordMemRef:
2983 MatchedMemRefs.push_back(cast<MemSDNode>(N)->getMemOperand());
2986 case OPC_CaptureGlueInput:
2987 // If the current node has an input glue, capture it in InputGlue.
2988 if (N->getNumOperands() != 0 &&
2989 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue)
2990 InputGlue = N->getOperand(N->getNumOperands()-1);
2993 case OPC_MoveChild: {
2994 unsigned ChildNo = MatcherTable[MatcherIndex++];
2995 if (ChildNo >= N.getNumOperands())
2996 break; // Match fails if out of range child #.
2997 N = N.getOperand(ChildNo);
2998 NodeStack.push_back(N);
3002 case OPC_MoveChild0: case OPC_MoveChild1:
3003 case OPC_MoveChild2: case OPC_MoveChild3:
3004 case OPC_MoveChild4: case OPC_MoveChild5:
3005 case OPC_MoveChild6: case OPC_MoveChild7: {
3006 unsigned ChildNo = Opcode-OPC_MoveChild0;
3007 if (ChildNo >= N.getNumOperands())
3008 break; // Match fails if out of range child #.
3009 N = N.getOperand(ChildNo);
3010 NodeStack.push_back(N);
3014 case OPC_MoveParent:
3015 // Pop the current node off the NodeStack.
3016 NodeStack.pop_back();
3017 assert(!NodeStack.empty() && "Node stack imbalance!");
3018 N = NodeStack.back();
3022 if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break;
3025 case OPC_CheckChild0Same: case OPC_CheckChild1Same:
3026 case OPC_CheckChild2Same: case OPC_CheckChild3Same:
3027 if (!::CheckChildSame(MatcherTable, MatcherIndex, N, RecordedNodes,
3028 Opcode-OPC_CheckChild0Same))
3032 case OPC_CheckPatternPredicate:
3033 if (!::CheckPatternPredicate(MatcherTable, MatcherIndex, *this)) break;
3035 case OPC_CheckPredicate:
3036 if (!::CheckNodePredicate(MatcherTable, MatcherIndex, *this,
3040 case OPC_CheckComplexPat: {
3041 unsigned CPNum = MatcherTable[MatcherIndex++];
3042 unsigned RecNo = MatcherTable[MatcherIndex++];
3043 assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat");
3045 // If target can modify DAG during matching, keep the matching state
3047 std::unique_ptr<MatchStateUpdater> MSU;
3048 if (ComplexPatternFuncMutatesDAG())
3049 MSU.reset(new MatchStateUpdater(*CurDAG, &NodeToMatch, RecordedNodes,
3052 if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second,
3053 RecordedNodes[RecNo].first, CPNum,
3058 case OPC_CheckOpcode:
3059 if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break;
3063 if (!::CheckType(MatcherTable, MatcherIndex, N, TLI,
3064 CurDAG->getDataLayout()))
3068 case OPC_SwitchOpcode: {
3069 unsigned CurNodeOpcode = N.getOpcode();
3070 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3073 // Get the size of this case.
3074 CaseSize = MatcherTable[MatcherIndex++];
3076 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3077 if (CaseSize == 0) break;
3079 uint16_t Opc = MatcherTable[MatcherIndex++];
3080 Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
3082 // If the opcode matches, then we will execute this case.
3083 if (CurNodeOpcode == Opc)
3086 // Otherwise, skip over this case.
3087 MatcherIndex += CaseSize;
3090 // If no cases matched, bail out.
3091 if (CaseSize == 0) break;
3093 // Otherwise, execute the case we found.
3094 DEBUG(dbgs() << " OpcodeSwitch from " << SwitchStart
3095 << " to " << MatcherIndex << "\n");
3099 case OPC_SwitchType: {
3100 MVT CurNodeVT = N.getSimpleValueType();
3101 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3104 // Get the size of this case.
3105 CaseSize = MatcherTable[MatcherIndex++];
3107 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3108 if (CaseSize == 0) break;
3110 MVT CaseVT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3111 if (CaseVT == MVT::iPTR)
3112 CaseVT = TLI->getPointerTy(CurDAG->getDataLayout());
3114 // If the VT matches, then we will execute this case.
3115 if (CurNodeVT == CaseVT)
3118 // Otherwise, skip over this case.
3119 MatcherIndex += CaseSize;
3122 // If no cases matched, bail out.
3123 if (CaseSize == 0) break;
3125 // Otherwise, execute the case we found.
3126 DEBUG(dbgs() << " TypeSwitch[" << EVT(CurNodeVT).getEVTString()
3127 << "] from " << SwitchStart << " to " << MatcherIndex<<'\n');
3130 case OPC_CheckChild0Type: case OPC_CheckChild1Type:
3131 case OPC_CheckChild2Type: case OPC_CheckChild3Type:
3132 case OPC_CheckChild4Type: case OPC_CheckChild5Type:
3133 case OPC_CheckChild6Type: case OPC_CheckChild7Type:
3134 if (!::CheckChildType(MatcherTable, MatcherIndex, N, TLI,
3135 CurDAG->getDataLayout(),
3136 Opcode - OPC_CheckChild0Type))
3139 case OPC_CheckCondCode:
3140 if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break;
3142 case OPC_CheckValueType:
3143 if (!::CheckValueType(MatcherTable, MatcherIndex, N, TLI,
3144 CurDAG->getDataLayout()))
3147 case OPC_CheckInteger:
3148 if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break;
3150 case OPC_CheckChild0Integer: case OPC_CheckChild1Integer:
3151 case OPC_CheckChild2Integer: case OPC_CheckChild3Integer:
3152 case OPC_CheckChild4Integer:
3153 if (!::CheckChildInteger(MatcherTable, MatcherIndex, N,
3154 Opcode-OPC_CheckChild0Integer)) break;
3156 case OPC_CheckAndImm:
3157 if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break;
3159 case OPC_CheckOrImm:
3160 if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break;
3163 case OPC_CheckFoldableChainNode: {
3164 assert(NodeStack.size() != 1 && "No parent node");
3165 // Verify that all intermediate nodes between the root and this one have
3167 bool HasMultipleUses = false;
3168 for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i)
3169 if (!NodeStack[i].getNode()->hasOneUse()) {
3170 HasMultipleUses = true;
3173 if (HasMultipleUses) break;
3175 // Check to see that the target thinks this is profitable to fold and that
3176 // we can fold it without inducing cycles in the graph.
3177 if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3179 !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3180 NodeToMatch, OptLevel,
3181 true/*We validate our own chains*/))
3186 case OPC_EmitInteger: {
3187 MVT::SimpleValueType VT =
3188 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3189 int64_t Val = MatcherTable[MatcherIndex++];
3191 Val = GetVBR(Val, MatcherTable, MatcherIndex);
3192 RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3193 CurDAG->getTargetConstant(Val, SDLoc(NodeToMatch),
3197 case OPC_EmitRegister: {
3198 MVT::SimpleValueType VT =
3199 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3200 unsigned RegNo = MatcherTable[MatcherIndex++];
3201 RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3202 CurDAG->getRegister(RegNo, VT), nullptr));
3205 case OPC_EmitRegister2: {
3206 // For targets w/ more than 256 register names, the register enum
3207 // values are stored in two bytes in the matcher table (just like
3209 MVT::SimpleValueType VT =
3210 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3211 unsigned RegNo = MatcherTable[MatcherIndex++];
3212 RegNo |= MatcherTable[MatcherIndex++] << 8;
3213 RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3214 CurDAG->getRegister(RegNo, VT), nullptr));
3218 case OPC_EmitConvertToTarget: {
3219 // Convert from IMM/FPIMM to target version.
3220 unsigned RecNo = MatcherTable[MatcherIndex++];
3221 assert(RecNo < RecordedNodes.size() && "Invalid EmitConvertToTarget");
3222 SDValue Imm = RecordedNodes[RecNo].first;
3224 if (Imm->getOpcode() == ISD::Constant) {
3225 const ConstantInt *Val=cast<ConstantSDNode>(Imm)->getConstantIntValue();
3226 Imm = CurDAG->getTargetConstant(*Val, SDLoc(NodeToMatch),
3227 Imm.getValueType());
3228 } else if (Imm->getOpcode() == ISD::ConstantFP) {
3229 const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
3230 Imm = CurDAG->getTargetConstantFP(*Val, SDLoc(NodeToMatch),
3231 Imm.getValueType());
3234 RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second));
3238 case OPC_EmitMergeInputChains1_0: // OPC_EmitMergeInputChains, 1, 0
3239 case OPC_EmitMergeInputChains1_1: // OPC_EmitMergeInputChains, 1, 1
3240 case OPC_EmitMergeInputChains1_2: { // OPC_EmitMergeInputChains, 1, 2
3241 // These are space-optimized forms of OPC_EmitMergeInputChains.
3242 assert(!InputChain.getNode() &&
3243 "EmitMergeInputChains should be the first chain producing node");
3244 assert(ChainNodesMatched.empty() &&
3245 "Should only have one EmitMergeInputChains per match");
3247 // Read all of the chained nodes.
3248 unsigned RecNo = Opcode - OPC_EmitMergeInputChains1_0;
3249 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3250 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3252 // FIXME: What if other value results of the node have uses not matched
3254 if (ChainNodesMatched.back() != NodeToMatch &&
3255 !RecordedNodes[RecNo].first.hasOneUse()) {
3256 ChainNodesMatched.clear();
3260 // Merge the input chains if they are not intra-pattern references.
3261 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3263 if (!InputChain.getNode())
3264 break; // Failed to merge.
3268 case OPC_EmitMergeInputChains: {
3269 assert(!InputChain.getNode() &&
3270 "EmitMergeInputChains should be the first chain producing node");
3271 // This node gets a list of nodes we matched in the input that have
3272 // chains. We want to token factor all of the input chains to these nodes
3273 // together. However, if any of the input chains is actually one of the
3274 // nodes matched in this pattern, then we have an intra-match reference.
3275 // Ignore these because the newly token factored chain should not refer to
3277 unsigned NumChains = MatcherTable[MatcherIndex++];
3278 assert(NumChains != 0 && "Can't TF zero chains");
3280 assert(ChainNodesMatched.empty() &&
3281 "Should only have one EmitMergeInputChains per match");
3283 // Read all of the chained nodes.
3284 for (unsigned i = 0; i != NumChains; ++i) {
3285 unsigned RecNo = MatcherTable[MatcherIndex++];
3286 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3287 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3289 // FIXME: What if other value results of the node have uses not matched
3291 if (ChainNodesMatched.back() != NodeToMatch &&
3292 !RecordedNodes[RecNo].first.hasOneUse()) {
3293 ChainNodesMatched.clear();
3298 // If the inner loop broke out, the match fails.
3299 if (ChainNodesMatched.empty())
3302 // Merge the input chains if they are not intra-pattern references.
3303 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3305 if (!InputChain.getNode())
3306 break; // Failed to merge.
3311 case OPC_EmitCopyToReg: {
3312 unsigned RecNo = MatcherTable[MatcherIndex++];
3313 assert(RecNo < RecordedNodes.size() && "Invalid EmitCopyToReg");
3314 unsigned DestPhysReg = MatcherTable[MatcherIndex++];
3316 if (!InputChain.getNode())
3317 InputChain = CurDAG->getEntryNode();
3319 InputChain = CurDAG->getCopyToReg(InputChain, SDLoc(NodeToMatch),
3320 DestPhysReg, RecordedNodes[RecNo].first,
3323 InputGlue = InputChain.getValue(1);
3327 case OPC_EmitNodeXForm: {
3328 unsigned XFormNo = MatcherTable[MatcherIndex++];
3329 unsigned RecNo = MatcherTable[MatcherIndex++];
3330 assert(RecNo < RecordedNodes.size() && "Invalid EmitNodeXForm");
3331 SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo);
3332 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, nullptr));
3335 case OPC_Coverage: {
3336 // This is emitted right before MorphNode/EmitNode.
3337 // So it should be safe to assume that this node has been selected
3338 unsigned index = MatcherTable[MatcherIndex++];
3339 index |= (MatcherTable[MatcherIndex++] << 8);
3340 dbgs() << "COVERED: " << getPatternForIndex(index) << "\n";
3341 dbgs() << "INCLUDED: " << getIncludePathForIndex(index) << "\n";
3345 case OPC_EmitNode: case OPC_MorphNodeTo:
3346 case OPC_EmitNode0: case OPC_EmitNode1: case OPC_EmitNode2:
3347 case OPC_MorphNodeTo0: case OPC_MorphNodeTo1: case OPC_MorphNodeTo2: {
3348 uint16_t TargetOpc = MatcherTable[MatcherIndex++];
3349 TargetOpc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
3350 unsigned EmitNodeInfo = MatcherTable[MatcherIndex++];
3351 // Get the result VT list.
3353 // If this is one of the compressed forms, get the number of VTs based
3354 // on the Opcode. Otherwise read the next byte from the table.
3355 if (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2)
3356 NumVTs = Opcode - OPC_MorphNodeTo0;
3357 else if (Opcode >= OPC_EmitNode0 && Opcode <= OPC_EmitNode2)
3358 NumVTs = Opcode - OPC_EmitNode0;
3360 NumVTs = MatcherTable[MatcherIndex++];
3361 SmallVector<EVT, 4> VTs;
3362 for (unsigned i = 0; i != NumVTs; ++i) {
3363 MVT::SimpleValueType VT =
3364 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3365 if (VT == MVT::iPTR)
3366 VT = TLI->getPointerTy(CurDAG->getDataLayout()).SimpleTy;
3370 if (EmitNodeInfo & OPFL_Chain)
3371 VTs.push_back(MVT::Other);
3372 if (EmitNodeInfo & OPFL_GlueOutput)
3373 VTs.push_back(MVT::Glue);
3375 // This is hot code, so optimize the two most common cases of 1 and 2
3378 if (VTs.size() == 1)
3379 VTList = CurDAG->getVTList(VTs[0]);
3380 else if (VTs.size() == 2)
3381 VTList = CurDAG->getVTList(VTs[0], VTs[1]);
3383 VTList = CurDAG->getVTList(VTs);
3385 // Get the operand list.
3386 unsigned NumOps = MatcherTable[MatcherIndex++];
3387 SmallVector<SDValue, 8> Ops;
3388 for (unsigned i = 0; i != NumOps; ++i) {
3389 unsigned RecNo = MatcherTable[MatcherIndex++];
3391 RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
3393 assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");
3394 Ops.push_back(RecordedNodes[RecNo].first);
3397 // If there are variadic operands to add, handle them now.
3398 if (EmitNodeInfo & OPFL_VariadicInfo) {
3399 // Determine the start index to copy from.
3400 unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
3401 FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
3402 assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
3403 "Invalid variadic node");
3404 // Copy all of the variadic operands, not including a potential glue
3406 for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
3408 SDValue V = NodeToMatch->getOperand(i);
3409 if (V.getValueType() == MVT::Glue) break;
3414 // If this has chain/glue inputs, add them.
3415 if (EmitNodeInfo & OPFL_Chain)
3416 Ops.push_back(InputChain);
3417 if ((EmitNodeInfo & OPFL_GlueInput) && InputGlue.getNode() != nullptr)
3418 Ops.push_back(InputGlue);
3421 SDNode *Res = nullptr;
3422 bool IsMorphNodeTo = Opcode == OPC_MorphNodeTo ||
3423 (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2);
3424 if (!IsMorphNodeTo) {
3425 // If this is a normal EmitNode command, just create the new node and
3426 // add the results to the RecordedNodes list.
3427 Res = CurDAG->getMachineNode(TargetOpc, SDLoc(NodeToMatch),
3430 // Add all the non-glue/non-chain results to the RecordedNodes list.
3431 for (unsigned i = 0, e = VTs.size(); i != e; ++i) {
3432 if (VTs[i] == MVT::Other || VTs[i] == MVT::Glue) break;
3433 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i),
3437 assert(NodeToMatch->getOpcode() != ISD::DELETED_NODE &&
3438 "NodeToMatch was removed partway through selection");
3439 SelectionDAG::DAGNodeDeletedListener NDL(*CurDAG, [&](SDNode *N,
3441 auto &Chain = ChainNodesMatched;
3442 assert((!E || !is_contained(Chain, N)) &&
3443 "Chain node replaced during MorphNode");
3444 Chain.erase(std::remove(Chain.begin(), Chain.end(), N), Chain.end());
3446 Res = MorphNode(NodeToMatch, TargetOpc, VTList, Ops, EmitNodeInfo);
3449 // If the node had chain/glue results, update our notion of the current
3451 if (EmitNodeInfo & OPFL_GlueOutput) {
3452 InputGlue = SDValue(Res, VTs.size()-1);
3453 if (EmitNodeInfo & OPFL_Chain)
3454 InputChain = SDValue(Res, VTs.size()-2);
3455 } else if (EmitNodeInfo & OPFL_Chain)
3456 InputChain = SDValue(Res, VTs.size()-1);
3458 // If the OPFL_MemRefs glue is set on this node, slap all of the
3459 // accumulated memrefs onto it.
3461 // FIXME: This is vastly incorrect for patterns with multiple outputs
3462 // instructions that access memory and for ComplexPatterns that match
3464 if (EmitNodeInfo & OPFL_MemRefs) {
3465 // Only attach load or store memory operands if the generated
3466 // instruction may load or store.
3467 const MCInstrDesc &MCID = TII->get(TargetOpc);
3468 bool mayLoad = MCID.mayLoad();
3469 bool mayStore = MCID.mayStore();
3471 unsigned NumMemRefs = 0;
3472 for (SmallVectorImpl<MachineMemOperand *>::const_iterator I =
3473 MatchedMemRefs.begin(), E = MatchedMemRefs.end(); I != E; ++I) {
3474 if ((*I)->isLoad()) {
3477 } else if ((*I)->isStore()) {
3485 MachineSDNode::mmo_iterator MemRefs =
3486 MF->allocateMemRefsArray(NumMemRefs);
3488 MachineSDNode::mmo_iterator MemRefsPos = MemRefs;
3489 for (SmallVectorImpl<MachineMemOperand *>::const_iterator I =
3490 MatchedMemRefs.begin(), E = MatchedMemRefs.end(); I != E; ++I) {
3491 if ((*I)->isLoad()) {
3494 } else if ((*I)->isStore()) {
3502 cast<MachineSDNode>(Res)
3503 ->setMemRefs(MemRefs, MemRefs + NumMemRefs);
3507 << (IsMorphNodeTo ? "Morphed" : "Created")
3508 << " node: "; Res->dump(CurDAG); dbgs() << "\n");
3510 // If this was a MorphNodeTo then we're completely done!
3511 if (IsMorphNodeTo) {
3512 // Update chain uses.
3513 UpdateChains(Res, InputChain, ChainNodesMatched, true);
3519 case OPC_CompleteMatch: {
3520 // The match has been completed, and any new nodes (if any) have been
3521 // created. Patch up references to the matched dag to use the newly
3523 unsigned NumResults = MatcherTable[MatcherIndex++];
3525 for (unsigned i = 0; i != NumResults; ++i) {
3526 unsigned ResSlot = MatcherTable[MatcherIndex++];
3528 ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);
3530 assert(ResSlot < RecordedNodes.size() && "Invalid CompleteMatch");
3531 SDValue Res = RecordedNodes[ResSlot].first;
3533 assert(i < NodeToMatch->getNumValues() &&
3534 NodeToMatch->getValueType(i) != MVT::Other &&
3535 NodeToMatch->getValueType(i) != MVT::Glue &&
3536 "Invalid number of results to complete!");
3537 assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
3538 NodeToMatch->getValueType(i) == MVT::iPTR ||
3539 Res.getValueType() == MVT::iPTR ||
3540 NodeToMatch->getValueType(i).getSizeInBits() ==
3541 Res.getValueSizeInBits()) &&
3542 "invalid replacement");
3543 CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, i), Res);
3546 // Update chain uses.
3547 UpdateChains(NodeToMatch, InputChain, ChainNodesMatched, false);
3549 // If the root node defines glue, we need to update it to the glue result.
3550 // TODO: This never happens in our tests and I think it can be removed /
3551 // replaced with an assert, but if we do it this the way the change is
3553 if (NodeToMatch->getValueType(NodeToMatch->getNumValues() - 1) ==
3555 InputGlue.getNode())
3556 CurDAG->ReplaceAllUsesOfValueWith(
3557 SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1), InputGlue);
3559 assert(NodeToMatch->use_empty() &&
3560 "Didn't replace all uses of the node?");
3561 CurDAG->RemoveDeadNode(NodeToMatch);
3567 // If the code reached this point, then the match failed. See if there is
3568 // another child to try in the current 'Scope', otherwise pop it until we
3569 // find a case to check.
3570 DEBUG(dbgs() << " Match failed at index " << CurrentOpcodeIndex << "\n");
3571 ++NumDAGIselRetries;
3573 if (MatchScopes.empty()) {
3574 CannotYetSelect(NodeToMatch);
3578 // Restore the interpreter state back to the point where the scope was
3580 MatchScope &LastScope = MatchScopes.back();
3581 RecordedNodes.resize(LastScope.NumRecordedNodes);
3583 NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());
3584 N = NodeStack.back();
3586 if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
3587 MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
3588 MatcherIndex = LastScope.FailIndex;
3590 DEBUG(dbgs() << " Continuing at " << MatcherIndex << "\n");
3592 InputChain = LastScope.InputChain;
3593 InputGlue = LastScope.InputGlue;
3594 if (!LastScope.HasChainNodesMatched)
3595 ChainNodesMatched.clear();
3597 // Check to see what the offset is at the new MatcherIndex. If it is zero
3598 // we have reached the end of this scope, otherwise we have another child
3599 // in the current scope to try.
3600 unsigned NumToSkip = MatcherTable[MatcherIndex++];
3601 if (NumToSkip & 128)
3602 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
3604 // If we have another child in this scope to match, update FailIndex and
3606 if (NumToSkip != 0) {
3607 LastScope.FailIndex = MatcherIndex+NumToSkip;
3611 // End of this scope, pop it and try the next child in the containing
3613 MatchScopes.pop_back();
3618 void SelectionDAGISel::CannotYetSelect(SDNode *N) {
3620 raw_string_ostream Msg(msg);
3621 Msg << "Cannot select: ";
3623 if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&
3624 N->getOpcode() != ISD::INTRINSIC_WO_CHAIN &&
3625 N->getOpcode() != ISD::INTRINSIC_VOID) {
3626 N->printrFull(Msg, CurDAG);
3627 Msg << "\nIn function: " << MF->getName();
3629 bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other;
3631 cast<ConstantSDNode>(N->getOperand(HasInputChain))->getZExtValue();
3632 if (iid < Intrinsic::num_intrinsics)
3633 Msg << "intrinsic %" << Intrinsic::getName((Intrinsic::ID)iid, None);
3634 else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo())
3635 Msg << "target intrinsic %" << TII->getName(iid);
3637 Msg << "unknown intrinsic #" << iid;
3639 report_fatal_error(Msg.str());
3642 char SelectionDAGISel::ID = 0;