LLVM 19.0.0git
SelectionDAGISel.cpp
Go to the documentation of this file.
1//===- SelectionDAGISel.cpp - Implement the SelectionDAGISel class --------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This implements the SelectionDAGISel class.
10//
11//===----------------------------------------------------------------------===//
12
14#include "ScheduleDAGSDNodes.h"
15#include "SelectionDAGBuilder.h"
16#include "llvm/ADT/APInt.h"
17#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/STLExtras.h"
22#include "llvm/ADT/Statistic.h"
23#include "llvm/ADT/StringRef.h"
27#include "llvm/Analysis/CFG.h"
64#include "llvm/IR/BasicBlock.h"
65#include "llvm/IR/Constants.h"
66#include "llvm/IR/DataLayout.h"
67#include "llvm/IR/DebugInfo.h"
69#include "llvm/IR/DebugLoc.h"
72#include "llvm/IR/Function.h"
73#include "llvm/IR/InlineAsm.h"
75#include "llvm/IR/Instruction.h"
78#include "llvm/IR/Intrinsics.h"
79#include "llvm/IR/IntrinsicsWebAssembly.h"
80#include "llvm/IR/Metadata.h"
81#include "llvm/IR/PrintPasses.h"
82#include "llvm/IR/Statepoint.h"
83#include "llvm/IR/Type.h"
84#include "llvm/IR/User.h"
85#include "llvm/IR/Value.h"
87#include "llvm/MC/MCInstrDesc.h"
88#include "llvm/Pass.h"
94#include "llvm/Support/Debug.h"
97#include "llvm/Support/Timer.h"
103#include <algorithm>
104#include <cassert>
105#include <cstdint>
106#include <iterator>
107#include <limits>
108#include <memory>
109#include <optional>
110#include <string>
111#include <utility>
112#include <vector>
113
114using namespace llvm;
115
116#define DEBUG_TYPE "isel"
117#define ISEL_DUMP_DEBUG_TYPE DEBUG_TYPE "-dump"
118
119STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on");
120STATISTIC(NumFastIselSuccess, "Number of instructions fast isel selected");
121STATISTIC(NumFastIselBlocks, "Number of blocks selected entirely by fast isel");
122STATISTIC(NumDAGBlocks, "Number of blocks selected using DAG");
123STATISTIC(NumDAGIselRetries,"Number of times dag isel has to try another path");
124STATISTIC(NumEntryBlocks, "Number of entry blocks encountered");
125STATISTIC(NumFastIselFailLowerArguments,
126 "Number of entry blocks where fast isel failed to lower arguments");
127
129 "fast-isel-abort", cl::Hidden,
130 cl::desc("Enable abort calls when \"fast\" instruction selection "
131 "fails to lower an instruction: 0 disable the abort, 1 will "
132 "abort but for args, calls and terminators, 2 will also "
133 "abort for argument lowering, and 3 will never fallback "
134 "to SelectionDAG."));
135
137 "fast-isel-report-on-fallback", cl::Hidden,
138 cl::desc("Emit a diagnostic when \"fast\" instruction selection "
139 "falls back to SelectionDAG."));
140
141static cl::opt<bool>
142UseMBPI("use-mbpi",
143 cl::desc("use Machine Branch Probability Info"),
144 cl::init(true), cl::Hidden);
145
146#ifndef NDEBUG
149 cl::desc("Only display the basic block whose name "
150 "matches this for all view-*-dags options"));
151static cl::opt<bool>
152ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
153 cl::desc("Pop up a window to show dags before the first "
154 "dag combine pass"));
155static cl::opt<bool>
156ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden,
157 cl::desc("Pop up a window to show dags before legalize types"));
158static cl::opt<bool>
159 ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden,
160 cl::desc("Pop up a window to show dags before the post "
161 "legalize types dag combine pass"));
162static cl::opt<bool>
163 ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
164 cl::desc("Pop up a window to show dags before legalize"));
165static cl::opt<bool>
166ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
167 cl::desc("Pop up a window to show dags before the second "
168 "dag combine pass"));
169static cl::opt<bool>
170ViewISelDAGs("view-isel-dags", cl::Hidden,
171 cl::desc("Pop up a window to show isel dags as they are selected"));
172static cl::opt<bool>
173ViewSchedDAGs("view-sched-dags", cl::Hidden,
174 cl::desc("Pop up a window to show sched dags as they are processed"));
175static cl::opt<bool>
176ViewSUnitDAGs("view-sunit-dags", cl::Hidden,
177 cl::desc("Pop up a window to show SUnit dags after they are processed"));
178#else
179static const bool ViewDAGCombine1 = false, ViewLegalizeTypesDAGs = false,
180 ViewDAGCombineLT = false, ViewLegalizeDAGs = false,
181 ViewDAGCombine2 = false, ViewISelDAGs = false,
182 ViewSchedDAGs = false, ViewSUnitDAGs = false;
183#endif
184
185#ifndef NDEBUG
186#define ISEL_DUMP(X) \
187 do { \
188 if (llvm::DebugFlag && \
189 (isCurrentDebugType(DEBUG_TYPE) || \
190 (isCurrentDebugType(ISEL_DUMP_DEBUG_TYPE) && MatchFilterFuncName))) { \
191 X; \
192 } \
193 } while (false)
194#else
195#define ISEL_DUMP(X) do { } while (false)
196#endif
197
198//===---------------------------------------------------------------------===//
199///
200/// RegisterScheduler class - Track the registration of instruction schedulers.
201///
202//===---------------------------------------------------------------------===//
205
206//===---------------------------------------------------------------------===//
207///
208/// ISHeuristic command line option for instruction schedulers.
209///
210//===---------------------------------------------------------------------===//
213ISHeuristic("pre-RA-sched",
215 cl::desc("Instruction schedulers available (before register"
216 " allocation):"));
217
219defaultListDAGScheduler("default", "Best scheduler for the target",
221
222static bool dontUseFastISelFor(const Function &Fn) {
223 // Don't enable FastISel for functions with swiftasync Arguments.
224 // Debug info on those is reliant on good Argument lowering, and FastISel is
225 // not capable of lowering the entire function. Mixing the two selectors tend
226 // to result in poor lowering of Arguments.
227 return any_of(Fn.args(), [](const Argument &Arg) {
228 return Arg.hasAttribute(Attribute::AttrKind::SwiftAsync);
229 });
230}
231
232namespace llvm {
233
234 //===--------------------------------------------------------------------===//
235 /// This class is used by SelectionDAGISel to temporarily override
236 /// the optimization level on a per-function basis.
239 CodeGenOptLevel SavedOptLevel;
240 bool SavedFastISel;
241
242 public:
244 : IS(ISel) {
245 SavedOptLevel = IS.OptLevel;
246 SavedFastISel = IS.TM.Options.EnableFastISel;
247 if (NewOptLevel != SavedOptLevel) {
248 IS.OptLevel = NewOptLevel;
249 IS.TM.setOptLevel(NewOptLevel);
250 LLVM_DEBUG(dbgs() << "\nChanging optimization level for Function "
251 << IS.MF->getFunction().getName() << "\n");
252 LLVM_DEBUG(dbgs() << "\tBefore: -O" << static_cast<int>(SavedOptLevel)
253 << " ; After: -O" << static_cast<int>(NewOptLevel)
254 << "\n");
255 if (NewOptLevel == CodeGenOptLevel::None)
257 }
259 IS.TM.setFastISel(false);
261 dbgs() << "\tFastISel is "
262 << (IS.TM.Options.EnableFastISel ? "enabled" : "disabled")
263 << "\n");
264 }
265
267 if (IS.OptLevel == SavedOptLevel)
268 return;
269 LLVM_DEBUG(dbgs() << "\nRestoring optimization level for Function "
270 << IS.MF->getFunction().getName() << "\n");
271 LLVM_DEBUG(dbgs() << "\tBefore: -O" << static_cast<int>(IS.OptLevel)
272 << " ; After: -O" << static_cast<int>(SavedOptLevel) << "\n");
273 IS.OptLevel = SavedOptLevel;
274 IS.TM.setOptLevel(SavedOptLevel);
275 IS.TM.setFastISel(SavedFastISel);
276 }
277 };
278
279 //===--------------------------------------------------------------------===//
280 /// createDefaultScheduler - This creates an instruction scheduler appropriate
281 /// for the target.
283 CodeGenOptLevel OptLevel) {
284 const TargetLowering *TLI = IS->TLI;
285 const TargetSubtargetInfo &ST = IS->MF->getSubtarget();
286
287 // Try first to see if the Target has its own way of selecting a scheduler
288 if (auto *SchedulerCtor = ST.getDAGScheduler(OptLevel)) {
289 return SchedulerCtor(IS, OptLevel);
290 }
291
292 if (OptLevel == CodeGenOptLevel::None ||
293 (ST.enableMachineScheduler() && ST.enableMachineSchedDefaultSched()) ||
295 return createSourceListDAGScheduler(IS, OptLevel);
297 return createBURRListDAGScheduler(IS, OptLevel);
299 return createHybridListDAGScheduler(IS, OptLevel);
301 return createVLIWDAGScheduler(IS, OptLevel);
303 return createFastDAGScheduler(IS, OptLevel);
305 return createDAGLinearizer(IS, OptLevel);
307 "Unknown sched type!");
308 return createILPListDAGScheduler(IS, OptLevel);
309 }
310
311} // end namespace llvm
312
313// EmitInstrWithCustomInserter - This method should be implemented by targets
314// that mark instructions with the 'usesCustomInserter' flag. These
315// instructions are special in various ways, which require special support to
316// insert. The specified MachineInstr is created but not inserted into any
317// basic blocks, and this method is called to expand it into a sequence of
318// instructions, potentially also creating new basic blocks and control flow.
319// When new basic blocks are inserted and the edges from MBB to its successors
320// are modified, the method should insert pairs of <OldSucc, NewSucc> into the
321// DenseMap.
324 MachineBasicBlock *MBB) const {
325#ifndef NDEBUG
326 dbgs() << "If a target marks an instruction with "
327 "'usesCustomInserter', it must implement "
328 "TargetLowering::EmitInstrWithCustomInserter!\n";
329#endif
330 llvm_unreachable(nullptr);
331}
332
334 SDNode *Node) const {
335 assert(!MI.hasPostISelHook() &&
336 "If a target marks an instruction with 'hasPostISelHook', "
337 "it must implement TargetLowering::AdjustInstrPostInstrSelection!");
338}
339
340//===----------------------------------------------------------------------===//
341// SelectionDAGISel code
342//===----------------------------------------------------------------------===//
343
345 char &ID, std::unique_ptr<SelectionDAGISel> S)
346 : MachineFunctionPass(ID), Selector(std::move(S)) {
352}
353
355 // If we already selected that function, we do not need to run SDISel.
356 if (MF.getProperties().hasProperty(
358 return false;
359
360 // Do some sanity-checking on the command-line options.
361 if (EnableFastISelAbort && !Selector->TM.Options.EnableFastISel)
362 report_fatal_error("-fast-isel-abort > 0 requires -fast-isel");
363
364 // Decide what flavour of variable location debug-info will be used, before
365 // we change the optimisation level.
367
368 // Reset the target options before resetting the optimization
369 // level below.
370 // FIXME: This is a horrible hack and should be processed via
371 // codegen looking at the optimization level explicitly when
372 // it wants to look at it.
373 Selector->TM.resetTargetOptions(MF.getFunction());
374 // Reset OptLevel to None for optnone functions.
375 CodeGenOptLevel NewOptLevel = skipFunction(MF.getFunction())
377 : Selector->OptLevel;
378
379 Selector->MF = &MF;
380 OptLevelChanger OLC(*Selector, NewOptLevel);
381 Selector->initializeAnalysisResults(*this);
382 return Selector->runOnMachineFunction(MF);
383}
384
386 : TM(tm), FuncInfo(new FunctionLoweringInfo()),
387 SwiftError(new SwiftErrorValueTracking()),
388 CurDAG(new SelectionDAG(tm, OL)),
389 SDB(std::make_unique<SelectionDAGBuilder>(*CurDAG, *FuncInfo, *SwiftError,
390 OL)),
391 OptLevel(OL) {
397}
398
400 delete CurDAG;
401 delete SwiftError;
402}
403
405 CodeGenOptLevel OptLevel = Selector->OptLevel;
406 if (OptLevel != CodeGenOptLevel::None)
412#ifndef NDEBUG
414#endif
416 if (UseMBPI && OptLevel != CodeGenOptLevel::None)
419 // AssignmentTrackingAnalysis only runs if assignment tracking is enabled for
420 // the module.
423 if (OptLevel != CodeGenOptLevel::None)
426}
427
428static void computeUsesMSVCFloatingPoint(const Triple &TT, const Function &F,
429 MachineModuleInfo &MMI) {
430 // Only needed for MSVC
431 if (!TT.isWindowsMSVCEnvironment())
432 return;
433
434 // If it's already set, nothing to do.
435 if (MMI.usesMSVCFloatingPoint())
436 return;
437
438 for (const Instruction &I : instructions(F)) {
439 if (I.getType()->isFPOrFPVectorTy()) {
440 MMI.setUsesMSVCFloatingPoint(true);
441 return;
442 }
443 for (const auto &Op : I.operands()) {
444 if (Op->getType()->isFPOrFPVectorTy()) {
445 MMI.setUsesMSVCFloatingPoint(true);
446 return;
447 }
448 }
449 }
450}
451
455 // If we already selected that function, we do not need to run SDISel.
456 if (MF.getProperties().hasProperty(
458 return PreservedAnalyses::all();
459
460 // Do some sanity-checking on the command-line options.
461 if (EnableFastISelAbort && !Selector->TM.Options.EnableFastISel)
462 report_fatal_error("-fast-isel-abort > 0 requires -fast-isel");
463
464 // Decide what flavour of variable location debug-info will be used, before
465 // we change the optimisation level.
467
468 // Reset the target options before resetting the optimization
469 // level below.
470 // FIXME: This is a horrible hack and should be processed via
471 // codegen looking at the optimization level explicitly when
472 // it wants to look at it.
473 Selector->TM.resetTargetOptions(MF.getFunction());
474 // Reset OptLevel to None for optnone functions.
475 // TODO: Add a function analysis to handle this.
476 Selector->MF = &MF;
477 // Reset OptLevel to None for optnone functions.
478 CodeGenOptLevel NewOptLevel = MF.getFunction().hasOptNone()
480 : Selector->OptLevel;
481
482 OptLevelChanger OLC(*Selector, NewOptLevel);
483 Selector->initializeAnalysisResults(MFAM);
484 Selector->runOnMachineFunction(MF);
485
487}
488
492 .getManager();
494 Function &Fn = MF->getFunction();
495#ifndef NDEBUG
496 FuncName = Fn.getName();
498#else
500#endif
501
504 RegInfo = &MF->getRegInfo();
506 GFI = Fn.hasGC() ? &FAM.getResult<GCFunctionAnalysis>(Fn) : nullptr;
507 ORE = std::make_unique<OptimizationRemarkEmitter>(&Fn);
509 auto *PSI = MAMP.getCachedResult<ProfileSummaryAnalysis>(*Fn.getParent());
510 BlockFrequencyInfo *BFI = nullptr;
512 if (PSI && PSI->hasProfileSummary() && OptLevel != CodeGenOptLevel::None)
514
515 FunctionVarLocs const *FnVarLocs = nullptr;
518
520 CurDAG->init(*MF, *ORE, MFAM, LibInfo, UA, PSI, BFI, FnVarLocs);
521
522 // Now get the optional analyzes if we want to.
523 // This is based on the possibly changed OptLevel (after optnone is taken
524 // into account). That's unfortunate but OK because it just means we won't
525 // ask for passes that have been required anyway.
526
529 else
530 FuncInfo->BPI = nullptr;
531
533 AA = &FAM.getResult<AAManager>(Fn);
534 else
535 AA = nullptr;
536
538
539#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
541#endif
542}
543
545 Function &Fn = MF->getFunction();
546#ifndef NDEBUG
547 FuncName = Fn.getName();
549#else
551#endif
552
555 RegInfo = &MF->getRegInfo();
557 GFI = Fn.hasGC() ? &MFP.getAnalysis<GCModuleInfo>().getFunctionInfo(Fn)
558 : nullptr;
559 ORE = std::make_unique<OptimizationRemarkEmitter>(&Fn);
560 AC = &MFP.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(Fn);
561 auto *PSI = &MFP.getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
562 BlockFrequencyInfo *BFI = nullptr;
563 if (PSI && PSI->hasProfileSummary() && OptLevel != CodeGenOptLevel::None)
564 BFI = &MFP.getAnalysis<LazyBlockFrequencyInfoPass>().getBFI();
565
566 FunctionVarLocs const *FnVarLocs = nullptr;
568 FnVarLocs = MFP.getAnalysis<AssignmentTrackingAnalysis>().getResults();
569
570 UniformityInfo *UA = nullptr;
571 if (auto *UAPass = MFP.getAnalysisIfAvailable<UniformityInfoWrapperPass>())
572 UA = &UAPass->getUniformityInfo();
573 CurDAG->init(*MF, *ORE, &MFP, LibInfo, UA, PSI, BFI, FnVarLocs);
574
575 // Now get the optional analyzes if we want to.
576 // This is based on the possibly changed OptLevel (after optnone is taken
577 // into account). That's unfortunate but OK because it just means we won't
578 // ask for passes that have been required anyway.
579
581 FuncInfo->BPI =
583 else
584 FuncInfo->BPI = nullptr;
585
587 AA = &MFP.getAnalysis<AAResultsWrapperPass>().getAAResults();
588 else
589 AA = nullptr;
590
591 SP = &MFP.getAnalysis<StackProtector>().getLayoutInfo();
592
593#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
595#endif
596}
597
600 const Function &Fn = mf.getFunction();
601
602 bool InstrRef = mf.shouldUseDebugInstrRef();
603
604 FuncInfo->set(MF->getFunction(), *MF, CurDAG);
605
606 ISEL_DUMP(dbgs() << "\n\n\n=== " << FuncName << '\n');
607
608 SDB->init(GFI, AA, AC, LibInfo);
609
610 MF->setHasInlineAsm(false);
611
612 FuncInfo->SplitCSR = false;
613
614 // We split CSR if the target supports it for the given function
615 // and the function has only return exits.
617 FuncInfo->SplitCSR = true;
618
619 // Collect all the return blocks.
620 for (const BasicBlock &BB : Fn) {
621 if (!succ_empty(&BB))
622 continue;
623
624 const Instruction *Term = BB.getTerminator();
625 if (isa<UnreachableInst>(Term) || isa<ReturnInst>(Term))
626 continue;
627
628 // Bail out if the exit block is not Return nor Unreachable.
629 FuncInfo->SplitCSR = false;
630 break;
631 }
632 }
633
634 MachineBasicBlock *EntryMBB = &MF->front();
635 if (FuncInfo->SplitCSR)
636 // This performs initialization so lowering for SplitCSR will be correct.
637 TLI->initializeSplitCSR(EntryMBB);
638
639 SelectAllBasicBlocks(Fn);
641 DiagnosticInfoISelFallback DiagFallback(Fn);
642 Fn.getContext().diagnose(DiagFallback);
643 }
644
645 // Replace forward-declared registers with the registers containing
646 // the desired value.
647 // Note: it is important that this happens **before** the call to
648 // EmitLiveInCopies, since implementations can skip copies of unused
649 // registers. If we don't apply the reg fixups before, some registers may
650 // appear as unused and will be skipped, resulting in bad MI.
652 for (DenseMap<Register, Register>::iterator I = FuncInfo->RegFixups.begin(),
653 E = FuncInfo->RegFixups.end();
654 I != E; ++I) {
655 Register From = I->first;
656 Register To = I->second;
657 // If To is also scheduled to be replaced, find what its ultimate
658 // replacement is.
659 while (true) {
660 DenseMap<Register, Register>::iterator J = FuncInfo->RegFixups.find(To);
661 if (J == E)
662 break;
663 To = J->second;
664 }
665 // Make sure the new register has a sufficiently constrained register class.
666 if (From.isVirtual() && To.isVirtual())
667 MRI.constrainRegClass(To, MRI.getRegClass(From));
668 // Replace it.
669
670 // Replacing one register with another won't touch the kill flags.
671 // We need to conservatively clear the kill flags as a kill on the old
672 // register might dominate existing uses of the new register.
673 if (!MRI.use_empty(To))
674 MRI.clearKillFlags(From);
675 MRI.replaceRegWith(From, To);
676 }
677
678 // If the first basic block in the function has live ins that need to be
679 // copied into vregs, emit the copies into the top of the block before
680 // emitting the code for the block.
682 RegInfo->EmitLiveInCopies(EntryMBB, TRI, *TII);
683
684 // Insert copies in the entry block and the return blocks.
685 if (FuncInfo->SplitCSR) {
687 // Collect all the return blocks.
688 for (MachineBasicBlock &MBB : mf) {
689 if (!MBB.succ_empty())
690 continue;
691
693 if (Term != MBB.end() && Term->isReturn()) {
694 Returns.push_back(&MBB);
695 continue;
696 }
697 }
698 TLI->insertCopiesSplitCSR(EntryMBB, Returns);
699 }
700
702 if (!FuncInfo->ArgDbgValues.empty())
703 for (std::pair<unsigned, unsigned> LI : RegInfo->liveins())
704 if (LI.second)
705 LiveInMap.insert(LI);
706
707 // Insert DBG_VALUE instructions for function arguments to the entry block.
708 for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; ++i) {
709 MachineInstr *MI = FuncInfo->ArgDbgValues[e - i - 1];
710 assert(MI->getOpcode() != TargetOpcode::DBG_VALUE_LIST &&
711 "Function parameters should not be described by DBG_VALUE_LIST.");
712 bool hasFI = MI->getDebugOperand(0).isFI();
713 Register Reg =
714 hasFI ? TRI.getFrameRegister(*MF) : MI->getDebugOperand(0).getReg();
715 if (Reg.isPhysical())
716 EntryMBB->insert(EntryMBB->begin(), MI);
717 else {
718 MachineInstr *Def = RegInfo->getVRegDef(Reg);
719 if (Def) {
720 MachineBasicBlock::iterator InsertPos = Def;
721 // FIXME: VR def may not be in entry block.
722 Def->getParent()->insert(std::next(InsertPos), MI);
723 } else
724 LLVM_DEBUG(dbgs() << "Dropping debug info for dead vreg"
725 << Register::virtReg2Index(Reg) << "\n");
726 }
727
728 // Don't try and extend through copies in instruction referencing mode.
729 if (InstrRef)
730 continue;
731
732 // If Reg is live-in then update debug info to track its copy in a vreg.
733 DenseMap<unsigned, unsigned>::iterator LDI = LiveInMap.find(Reg);
734 if (LDI != LiveInMap.end()) {
735 assert(!hasFI && "There's no handling of frame pointer updating here yet "
736 "- add if needed");
737 MachineInstr *Def = RegInfo->getVRegDef(LDI->second);
738 MachineBasicBlock::iterator InsertPos = Def;
739 const MDNode *Variable = MI->getDebugVariable();
740 const MDNode *Expr = MI->getDebugExpression();
741 DebugLoc DL = MI->getDebugLoc();
742 bool IsIndirect = MI->isIndirectDebugValue();
743 if (IsIndirect)
744 assert(MI->getDebugOffset().getImm() == 0 &&
745 "DBG_VALUE with nonzero offset");
746 assert(cast<DILocalVariable>(Variable)->isValidLocationForIntrinsic(DL) &&
747 "Expected inlined-at fields to agree");
748 assert(MI->getOpcode() != TargetOpcode::DBG_VALUE_LIST &&
749 "Didn't expect to see a DBG_VALUE_LIST here");
750 // Def is never a terminator here, so it is ok to increment InsertPos.
751 BuildMI(*EntryMBB, ++InsertPos, DL, TII->get(TargetOpcode::DBG_VALUE),
752 IsIndirect, LDI->second, Variable, Expr);
753
754 // If this vreg is directly copied into an exported register then
755 // that COPY instructions also need DBG_VALUE, if it is the only
756 // user of LDI->second.
757 MachineInstr *CopyUseMI = nullptr;
759 UI = RegInfo->use_instr_begin(LDI->second),
760 E = RegInfo->use_instr_end(); UI != E; ) {
761 MachineInstr *UseMI = &*(UI++);
762 if (UseMI->isDebugValue()) continue;
763 if (UseMI->isCopy() && !CopyUseMI && UseMI->getParent() == EntryMBB) {
764 CopyUseMI = UseMI; continue;
765 }
766 // Otherwise this is another use or second copy use.
767 CopyUseMI = nullptr; break;
768 }
769 if (CopyUseMI &&
770 TRI.getRegSizeInBits(LDI->second, MRI) ==
771 TRI.getRegSizeInBits(CopyUseMI->getOperand(0).getReg(), MRI)) {
772 // Use MI's debug location, which describes where Variable was
773 // declared, rather than whatever is attached to CopyUseMI.
774 MachineInstr *NewMI =
775 BuildMI(*MF, DL, TII->get(TargetOpcode::DBG_VALUE), IsIndirect,
776 CopyUseMI->getOperand(0).getReg(), Variable, Expr);
777 MachineBasicBlock::iterator Pos = CopyUseMI;
778 EntryMBB->insertAfter(Pos, NewMI);
779 }
780 }
781 }
782
783 // For debug-info, in instruction referencing mode, we need to perform some
784 // post-isel maintenence.
785 if (MF->useDebugInstrRef())
787
788 // Determine if there are any calls in this machine function.
790 for (const auto &MBB : *MF) {
791 if (MFI.hasCalls() && MF->hasInlineAsm())
792 break;
793
794 for (const auto &MI : MBB) {
795 const MCInstrDesc &MCID = TII->get(MI.getOpcode());
796 if ((MCID.isCall() && !MCID.isReturn()) ||
797 MI.isStackAligningInlineAsm()) {
798 MFI.setHasCalls(true);
799 }
800 if (MI.isInlineAsm()) {
801 MF->setHasInlineAsm(true);
802 }
803 }
804 }
805
806 // Determine if floating point is used for msvc
808
809 // Release function-specific state. SDB and CurDAG are already cleared
810 // at this point.
811 FuncInfo->clear();
812
813 ISEL_DUMP(dbgs() << "*** MachineFunction at end of ISel ***\n");
814 ISEL_DUMP(MF->print(dbgs()));
815
816 return true;
817}
818
822 bool ShouldAbort) {
823 // Print the function name explicitly if we don't have a debug location (which
824 // makes the diagnostic less useful) or if we're going to emit a raw error.
825 if (!R.getLocation().isValid() || ShouldAbort)
826 R << (" (in function: " + MF.getName() + ")").str();
827
828 if (ShouldAbort)
829 report_fatal_error(Twine(R.getMsg()));
830
831 ORE.emit(R);
832 LLVM_DEBUG(dbgs() << R.getMsg() << "\n");
833}
834
835void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,
837 bool &HadTailCall) {
838 // Allow creating illegal types during DAG building for the basic block.
840
841 // Lower the instructions. If a call is emitted as a tail call, cease emitting
842 // nodes for this block. If an instruction is elided, don't emit it, but do
843 // handle any debug-info attached to it.
844 for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I) {
845 if (!ElidedArgCopyInstrs.count(&*I))
846 SDB->visit(*I);
847 else
848 SDB->visitDbgInfo(*I);
849 }
850
851 // Make sure the root of the DAG is up-to-date.
852 CurDAG->setRoot(SDB->getControlRoot());
853 HadTailCall = SDB->HasTailCall;
854 SDB->resolveOrClearDbgInfo();
855 SDB->clear();
856
857 // Final step, emit the lowered DAG as machine code.
858 CodeGenAndEmitDAG();
859}
860
861void SelectionDAGISel::ComputeLiveOutVRegInfo() {
864
865 Worklist.push_back(CurDAG->getRoot().getNode());
866 Added.insert(CurDAG->getRoot().getNode());
867
868 KnownBits Known;
869
870 do {
871 SDNode *N = Worklist.pop_back_val();
872
873 // Otherwise, add all chain operands to the worklist.
874 for (const SDValue &Op : N->op_values())
875 if (Op.getValueType() == MVT::Other && Added.insert(Op.getNode()).second)
876 Worklist.push_back(Op.getNode());
877
878 // If this is a CopyToReg with a vreg dest, process it.
879 if (N->getOpcode() != ISD::CopyToReg)
880 continue;
881
882 unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();
883 if (!Register::isVirtualRegister(DestReg))
884 continue;
885
886 // Ignore non-integer values.
887 SDValue Src = N->getOperand(2);
888 EVT SrcVT = Src.getValueType();
889 if (!SrcVT.isInteger())
890 continue;
891
892 unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);
893 Known = CurDAG->computeKnownBits(Src);
894 FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, Known);
895 } while (!Worklist.empty());
896}
897
898void SelectionDAGISel::CodeGenAndEmitDAG() {
899 StringRef GroupName = "sdag";
900 StringRef GroupDescription = "Instruction Selection and Scheduling";
901 std::string BlockName;
902 bool MatchFilterBB = false;
903 (void)MatchFilterBB;
904
905 // Pre-type legalization allow creation of any node types.
907
908#ifndef NDEBUG
909 MatchFilterBB = (FilterDAGBasicBlockName.empty() ||
911 FuncInfo->MBB->getBasicBlock()->getName());
912#endif
913#ifdef NDEBUG
917#endif
918 {
919 BlockName =
920 (MF->getName() + ":" + FuncInfo->MBB->getBasicBlock()->getName()).str();
921 }
922 ISEL_DUMP(dbgs() << "\nInitial selection DAG: "
923 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
924 << "'\n";
925 CurDAG->dump());
926
927#if LLVM_ENABLE_ABI_BREAKING_CHECKS
930#endif
931
932 if (ViewDAGCombine1 && MatchFilterBB)
933 CurDAG->viewGraph("dag-combine1 input for " + BlockName);
934
935 // Run the DAG combiner in pre-legalize mode.
936 {
937 NamedRegionTimer T("combine1", "DAG Combining 1", GroupName,
938 GroupDescription, TimePassesIsEnabled);
940 }
941
942 ISEL_DUMP(dbgs() << "\nOptimized lowered selection DAG: "
943 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
944 << "'\n";
945 CurDAG->dump());
946
947#if LLVM_ENABLE_ABI_BREAKING_CHECKS
950#endif
951
952 // Second step, hack on the DAG until it only uses operations and types that
953 // the target supports.
954 if (ViewLegalizeTypesDAGs && MatchFilterBB)
955 CurDAG->viewGraph("legalize-types input for " + BlockName);
956
957 bool Changed;
958 {
959 NamedRegionTimer T("legalize_types", "Type Legalization", GroupName,
960 GroupDescription, TimePassesIsEnabled);
961 Changed = CurDAG->LegalizeTypes();
962 }
963
964 ISEL_DUMP(dbgs() << "\nType-legalized selection DAG: "
965 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
966 << "'\n";
967 CurDAG->dump());
968
969#if LLVM_ENABLE_ABI_BREAKING_CHECKS
972#endif
973
974 // Only allow creation of legal node types.
976
977 if (Changed) {
978 if (ViewDAGCombineLT && MatchFilterBB)
979 CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
980
981 // Run the DAG combiner in post-type-legalize mode.
982 {
983 NamedRegionTimer T("combine_lt", "DAG Combining after legalize types",
984 GroupName, GroupDescription, TimePassesIsEnabled);
986 }
987
988 ISEL_DUMP(dbgs() << "\nOptimized type-legalized selection DAG: "
989 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
990 << "'\n";
991 CurDAG->dump());
992
993#if LLVM_ENABLE_ABI_BREAKING_CHECKS
996#endif
997 }
998
999 {
1000 NamedRegionTimer T("legalize_vec", "Vector Legalization", GroupName,
1001 GroupDescription, TimePassesIsEnabled);
1002 Changed = CurDAG->LegalizeVectors();
1003 }
1004
1005 if (Changed) {
1006 ISEL_DUMP(dbgs() << "\nVector-legalized selection DAG: "
1007 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
1008 << "'\n";
1009 CurDAG->dump());
1010
1011#if LLVM_ENABLE_ABI_BREAKING_CHECKS
1012 if (TTI->hasBranchDivergence())
1014#endif
1015
1016 {
1017 NamedRegionTimer T("legalize_types2", "Type Legalization 2", GroupName,
1018 GroupDescription, TimePassesIsEnabled);
1020 }
1021
1022 ISEL_DUMP(dbgs() << "\nVector/type-legalized selection DAG: "
1023 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
1024 << "'\n";
1025 CurDAG->dump());
1026
1027#if LLVM_ENABLE_ABI_BREAKING_CHECKS
1028 if (TTI->hasBranchDivergence())
1030#endif
1031
1032 if (ViewDAGCombineLT && MatchFilterBB)
1033 CurDAG->viewGraph("dag-combine-lv input for " + BlockName);
1034
1035 // Run the DAG combiner in post-type-legalize mode.
1036 {
1037 NamedRegionTimer T("combine_lv", "DAG Combining after legalize vectors",
1038 GroupName, GroupDescription, TimePassesIsEnabled);
1040 }
1041
1042 ISEL_DUMP(dbgs() << "\nOptimized vector-legalized selection DAG: "
1043 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
1044 << "'\n";
1045 CurDAG->dump());
1046
1047#if LLVM_ENABLE_ABI_BREAKING_CHECKS
1048 if (TTI->hasBranchDivergence())
1050#endif
1051 }
1052
1053 if (ViewLegalizeDAGs && MatchFilterBB)
1054 CurDAG->viewGraph("legalize input for " + BlockName);
1055
1056 {
1057 NamedRegionTimer T("legalize", "DAG Legalization", GroupName,
1058 GroupDescription, TimePassesIsEnabled);
1059 CurDAG->Legalize();
1060 }
1061
1062 ISEL_DUMP(dbgs() << "\nLegalized selection DAG: "
1063 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
1064 << "'\n";
1065 CurDAG->dump());
1066
1067#if LLVM_ENABLE_ABI_BREAKING_CHECKS
1068 if (TTI->hasBranchDivergence())
1070#endif
1071
1072 if (ViewDAGCombine2 && MatchFilterBB)
1073 CurDAG->viewGraph("dag-combine2 input for " + BlockName);
1074
1075 // Run the DAG combiner in post-legalize mode.
1076 {
1077 NamedRegionTimer T("combine2", "DAG Combining 2", GroupName,
1078 GroupDescription, TimePassesIsEnabled);
1080 }
1081
1082 ISEL_DUMP(dbgs() << "\nOptimized legalized selection DAG: "
1083 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
1084 << "'\n";
1085 CurDAG->dump());
1086
1087#if LLVM_ENABLE_ABI_BREAKING_CHECKS
1088 if (TTI->hasBranchDivergence())
1090#endif
1091
1093 ComputeLiveOutVRegInfo();
1094
1095 if (ViewISelDAGs && MatchFilterBB)
1096 CurDAG->viewGraph("isel input for " + BlockName);
1097
1098 // Third, instruction select all of the operations to machine code, adding the
1099 // code to the MachineBasicBlock.
1100 {
1101 NamedRegionTimer T("isel", "Instruction Selection", GroupName,
1102 GroupDescription, TimePassesIsEnabled);
1103 DoInstructionSelection();
1104 }
1105
1106 ISEL_DUMP(dbgs() << "\nSelected selection DAG: "
1107 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
1108 << "'\n";
1109 CurDAG->dump());
1110
1111 if (ViewSchedDAGs && MatchFilterBB)
1112 CurDAG->viewGraph("scheduler input for " + BlockName);
1113
1114 // Schedule machine code.
1115 ScheduleDAGSDNodes *Scheduler = CreateScheduler();
1116 {
1117 NamedRegionTimer T("sched", "Instruction Scheduling", GroupName,
1118 GroupDescription, TimePassesIsEnabled);
1119 Scheduler->Run(CurDAG, FuncInfo->MBB);
1120 }
1121
1122 if (ViewSUnitDAGs && MatchFilterBB)
1123 Scheduler->viewGraph();
1124
1125 // Emit machine code to BB. This can change 'BB' to the last block being
1126 // inserted into.
1127 MachineBasicBlock *FirstMBB = FuncInfo->MBB, *LastMBB;
1128 {
1129 NamedRegionTimer T("emit", "Instruction Creation", GroupName,
1130 GroupDescription, TimePassesIsEnabled);
1131
1132 // FuncInfo->InsertPt is passed by reference and set to the end of the
1133 // scheduled instructions.
1134 LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(FuncInfo->InsertPt);
1135 }
1136
1137 // If the block was split, make sure we update any references that are used to
1138 // update PHI nodes later on.
1139 if (FirstMBB != LastMBB)
1140 SDB->UpdateSplitBlock(FirstMBB, LastMBB);
1141
1142 // Free the scheduler state.
1143 {
1144 NamedRegionTimer T("cleanup", "Instruction Scheduling Cleanup", GroupName,
1145 GroupDescription, TimePassesIsEnabled);
1146 delete Scheduler;
1147 }
1148
1149 // Free the SelectionDAG state, now that we're finished with it.
1150 CurDAG->clear();
1151}
1152
1153namespace {
1154
1155/// ISelUpdater - helper class to handle updates of the instruction selection
1156/// graph.
1157class ISelUpdater : public SelectionDAG::DAGUpdateListener {
1158 SelectionDAG::allnodes_iterator &ISelPosition;
1159
1160public:
1161 ISelUpdater(SelectionDAG &DAG, SelectionDAG::allnodes_iterator &isp)
1162 : SelectionDAG::DAGUpdateListener(DAG), ISelPosition(isp) {}
1163
1164 /// NodeDeleted - Handle nodes deleted from the graph. If the node being
1165 /// deleted is the current ISelPosition node, update ISelPosition.
1166 ///
1167 void NodeDeleted(SDNode *N, SDNode *E) override {
1168 if (ISelPosition == SelectionDAG::allnodes_iterator(N))
1169 ++ISelPosition;
1170 }
1171
1172 /// NodeInserted - Handle new nodes inserted into the graph: propagate
1173 /// metadata from root nodes that also applies to new nodes, in case the root
1174 /// is later deleted.
1175 void NodeInserted(SDNode *N) override {
1176 SDNode *CurNode = &*ISelPosition;
1177 if (MDNode *MD = DAG.getPCSections(CurNode))
1178 DAG.addPCSections(N, MD);
1179 if (MDNode *MMRA = DAG.getMMRAMetadata(CurNode))
1180 DAG.addMMRAMetadata(N, MMRA);
1181 }
1182};
1183
1184} // end anonymous namespace
1185
1186// This function is used to enforce the topological node id property
1187// leveraged during instruction selection. Before the selection process all
1188// nodes are given a non-negative id such that all nodes have a greater id than
1189// their operands. As this holds transitively we can prune checks that a node N
1190// is a predecessor of M another by not recursively checking through M's
1191// operands if N's ID is larger than M's ID. This significantly improves
1192// performance of various legality checks (e.g. IsLegalToFold / UpdateChains).
1193
1194// However, when we fuse multiple nodes into a single node during the
1195// selection we may induce a predecessor relationship between inputs and
1196// outputs of distinct nodes being merged, violating the topological property.
1197// Should a fused node have a successor which has yet to be selected,
1198// our legality checks would be incorrect. To avoid this we mark all unselected
1199// successor nodes, i.e. id != -1, as invalid for pruning by bit-negating (x =>
1200// (-(x+1))) the ids and modify our pruning check to ignore negative Ids of M.
1201// We use bit-negation to more clearly enforce that node id -1 can only be
1202// achieved by selected nodes. As the conversion is reversable to the original
1203// Id, topological pruning can still be leveraged when looking for unselected
1204// nodes. This method is called internally in all ISel replacement related
1205// functions.
1208 Nodes.push_back(Node);
1209
1210 while (!Nodes.empty()) {
1211 SDNode *N = Nodes.pop_back_val();
1212 for (auto *U : N->uses()) {
1213 auto UId = U->getNodeId();
1214 if (UId > 0) {
1216 Nodes.push_back(U);
1217 }
1218 }
1219 }
1220}
1221
1222// InvalidateNodeId - As explained in EnforceNodeIdInvariant, mark a
1223// NodeId with the equivalent node id which is invalid for topological
1224// pruning.
1226 int InvalidId = -(N->getNodeId() + 1);
1227 N->setNodeId(InvalidId);
1228}
1229
1230// getUninvalidatedNodeId - get original uninvalidated node id.
1232 int Id = N->getNodeId();
1233 if (Id < -1)
1234 return -(Id + 1);
1235 return Id;
1236}
1237
1238void SelectionDAGISel::DoInstructionSelection() {
1239 LLVM_DEBUG(dbgs() << "===== Instruction selection begins: "
1240 << printMBBReference(*FuncInfo->MBB) << " '"
1241 << FuncInfo->MBB->getName() << "'\n");
1242
1244
1245 // Select target instructions for the DAG.
1246 {
1247 // Number all nodes with a topological order and set DAGSize.
1249
1250 // Create a dummy node (which is not added to allnodes), that adds
1251 // a reference to the root node, preventing it from being deleted,
1252 // and tracking any changes of the root.
1253 HandleSDNode Dummy(CurDAG->getRoot());
1255 ++ISelPosition;
1256
1257 // Make sure that ISelPosition gets properly updated when nodes are deleted
1258 // in calls made from this function. New nodes inherit relevant metadata.
1259 ISelUpdater ISU(*CurDAG, ISelPosition);
1260
1261 // The AllNodes list is now topological-sorted. Visit the
1262 // nodes by starting at the end of the list (the root of the
1263 // graph) and preceding back toward the beginning (the entry
1264 // node).
1265 while (ISelPosition != CurDAG->allnodes_begin()) {
1266 SDNode *Node = &*--ISelPosition;
1267 // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
1268 // but there are currently some corner cases that it misses. Also, this
1269 // makes it theoretically possible to disable the DAGCombiner.
1270 if (Node->use_empty())
1271 continue;
1272
1273#ifndef NDEBUG
1275 Nodes.push_back(Node);
1276
1277 while (!Nodes.empty()) {
1278 auto N = Nodes.pop_back_val();
1279 if (N->getOpcode() == ISD::TokenFactor || N->getNodeId() < 0)
1280 continue;
1281 for (const SDValue &Op : N->op_values()) {
1282 if (Op->getOpcode() == ISD::TokenFactor)
1283 Nodes.push_back(Op.getNode());
1284 else {
1285 // We rely on topological ordering of node ids for checking for
1286 // cycles when fusing nodes during selection. All unselected nodes
1287 // successors of an already selected node should have a negative id.
1288 // This assertion will catch such cases. If this assertion triggers
1289 // it is likely you using DAG-level Value/Node replacement functions
1290 // (versus equivalent ISEL replacement) in backend-specific
1291 // selections. See comment in EnforceNodeIdInvariant for more
1292 // details.
1293 assert(Op->getNodeId() != -1 &&
1294 "Node has already selected predecessor node");
1295 }
1296 }
1297 }
1298#endif
1299
1300 // When we are using non-default rounding modes or FP exception behavior
1301 // FP operations are represented by StrictFP pseudo-operations. For
1302 // targets that do not (yet) understand strict FP operations directly,
1303 // we convert them to normal FP opcodes instead at this point. This
1304 // will allow them to be handled by existing target-specific instruction
1305 // selectors.
1306 if (!TLI->isStrictFPEnabled() && Node->isStrictFPOpcode()) {
1307 // For some opcodes, we need to call TLI->getOperationAction using
1308 // the first operand type instead of the result type. Note that this
1309 // must match what SelectionDAGLegalize::LegalizeOp is doing.
1310 EVT ActionVT;
1311 switch (Node->getOpcode()) {
1314 case ISD::STRICT_LRINT:
1315 case ISD::STRICT_LLRINT:
1316 case ISD::STRICT_LROUND:
1318 case ISD::STRICT_FSETCC:
1320 ActionVT = Node->getOperand(1).getValueType();
1321 break;
1322 default:
1323 ActionVT = Node->getValueType(0);
1324 break;
1325 }
1326 if (TLI->getOperationAction(Node->getOpcode(), ActionVT)
1329 }
1330
1331 LLVM_DEBUG(dbgs() << "\nISEL: Starting selection on root node: ";
1332 Node->dump(CurDAG));
1333
1334 Select(Node);
1335 }
1336
1337 CurDAG->setRoot(Dummy.getValue());
1338 }
1339
1340 LLVM_DEBUG(dbgs() << "\n===== Instruction selection ends:\n");
1341
1343}
1344
1346 for (const User *U : CPI->users()) {
1347 if (const IntrinsicInst *EHPtrCall = dyn_cast<IntrinsicInst>(U)) {
1348 Intrinsic::ID IID = EHPtrCall->getIntrinsicID();
1349 if (IID == Intrinsic::eh_exceptionpointer ||
1350 IID == Intrinsic::eh_exceptioncode)
1351 return true;
1352 }
1353 }
1354 return false;
1355}
1356
1357// wasm.landingpad.index intrinsic is for associating a landing pad index number
1358// with a catchpad instruction. Retrieve the landing pad index in the intrinsic
1359// and store the mapping in the function.
1361 const CatchPadInst *CPI) {
1362 MachineFunction *MF = MBB->getParent();
1363 // In case of single catch (...), we don't emit LSDA, so we don't need
1364 // this information.
1365 bool IsSingleCatchAllClause =
1366 CPI->arg_size() == 1 &&
1367 cast<Constant>(CPI->getArgOperand(0))->isNullValue();
1368 // cathchpads for longjmp use an empty type list, e.g. catchpad within %0 []
1369 // and they don't need LSDA info
1370 bool IsCatchLongjmp = CPI->arg_size() == 0;
1371 if (!IsSingleCatchAllClause && !IsCatchLongjmp) {
1372 // Create a mapping from landing pad label to landing pad index.
1373 bool IntrFound = false;
1374 for (const User *U : CPI->users()) {
1375 if (const auto *Call = dyn_cast<IntrinsicInst>(U)) {
1376 Intrinsic::ID IID = Call->getIntrinsicID();
1377 if (IID == Intrinsic::wasm_landingpad_index) {
1378 Value *IndexArg = Call->getArgOperand(1);
1379 int Index = cast<ConstantInt>(IndexArg)->getZExtValue();
1381 IntrFound = true;
1382 break;
1383 }
1384 }
1385 }
1386 assert(IntrFound && "wasm.landingpad.index intrinsic not found!");
1387 (void)IntrFound;
1388 }
1389}
1390
1391/// PrepareEHLandingPad - Emit an EH_LABEL, set up live-in registers, and
1392/// do other setup for EH landing-pad blocks.
1393bool SelectionDAGISel::PrepareEHLandingPad() {
1395 const Constant *PersonalityFn = FuncInfo->Fn->getPersonalityFn();
1396 const BasicBlock *LLVMBB = MBB->getBasicBlock();
1397 const TargetRegisterClass *PtrRC =
1399
1400 auto Pers = classifyEHPersonality(PersonalityFn);
1401
1402 // Catchpads have one live-in register, which typically holds the exception
1403 // pointer or code.
1404 if (isFuncletEHPersonality(Pers)) {
1405 if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHI())) {
1407 // Get or create the virtual register to hold the pointer or code. Mark
1408 // the live in physreg and copy into the vreg.
1409 MCPhysReg EHPhysReg = TLI->getExceptionPointerRegister(PersonalityFn);
1410 assert(EHPhysReg && "target lacks exception pointer register");
1411 MBB->addLiveIn(EHPhysReg);
1412 unsigned VReg = FuncInfo->getCatchPadExceptionPointerVReg(CPI, PtrRC);
1413 BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(),
1414 TII->get(TargetOpcode::COPY), VReg)
1415 .addReg(EHPhysReg, RegState::Kill);
1416 }
1417 }
1418 return true;
1419 }
1420
1421 // Add a label to mark the beginning of the landing pad. Deletion of the
1422 // landing pad can thus be detected via the MachineModuleInfo.
1424
1425 const MCInstrDesc &II = TII->get(TargetOpcode::EH_LABEL);
1426 BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II)
1427 .addSym(Label);
1428
1429 // If the unwinder does not preserve all registers, ensure that the
1430 // function marks the clobbered registers as used.
1432 if (auto *RegMask = TRI.getCustomEHPadPreservedMask(*MF))
1434
1435 if (Pers == EHPersonality::Wasm_CXX) {
1436 if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHI()))
1438 } else {
1439 // Assign the call site to the landing pad's begin label.
1440 MF->setCallSiteLandingPad(Label, SDB->LPadToCallSiteMap[MBB]);
1441 // Mark exception register as live in.
1442 if (unsigned Reg = TLI->getExceptionPointerRegister(PersonalityFn))
1443 FuncInfo->ExceptionPointerVirtReg = MBB->addLiveIn(Reg, PtrRC);
1444 // Mark exception selector register as live in.
1445 if (unsigned Reg = TLI->getExceptionSelectorRegister(PersonalityFn))
1446 FuncInfo->ExceptionSelectorVirtReg = MBB->addLiveIn(Reg, PtrRC);
1447 }
1448
1449 return true;
1450}
1451
1452// Mark and Report IPToState for each Block under IsEHa
1453void SelectionDAGISel::reportIPToStateForBlocks(MachineFunction *MF) {
1454 MachineModuleInfo &MMI = MF->getMMI();
1456 if (!EHInfo)
1457 return;
1458 for (auto MBBI = MF->begin(), E = MF->end(); MBBI != E; ++MBBI) {
1460 const BasicBlock *BB = MBB->getBasicBlock();
1461 int State = EHInfo->BlockToStateMap[BB];
1462 if (BB->getFirstMayFaultInst()) {
1463 // Report IP range only for blocks with Faulty inst
1464 auto MBBb = MBB->getFirstNonPHI();
1465 MachineInstr *MIb = &*MBBb;
1466 if (MIb->isTerminator())
1467 continue;
1468
1469 // Insert EH Labels
1470 MCSymbol *BeginLabel = MMI.getContext().createTempSymbol();
1471 MCSymbol *EndLabel = MMI.getContext().createTempSymbol();
1472 EHInfo->addIPToStateRange(State, BeginLabel, EndLabel);
1473 BuildMI(*MBB, MBBb, SDB->getCurDebugLoc(),
1474 TII->get(TargetOpcode::EH_LABEL))
1475 .addSym(BeginLabel);
1476 auto MBBe = MBB->instr_end();
1477 MachineInstr *MIe = &*(--MBBe);
1478 // insert before (possible multiple) terminators
1479 while (MIe->isTerminator())
1480 MIe = &*(--MBBe);
1481 ++MBBe;
1482 BuildMI(*MBB, MBBe, SDB->getCurDebugLoc(),
1483 TII->get(TargetOpcode::EH_LABEL))
1484 .addSym(EndLabel);
1485 }
1486 }
1487}
1488
1489/// isFoldedOrDeadInstruction - Return true if the specified instruction is
1490/// side-effect free and is either dead or folded into a generated instruction.
1491/// Return false if it needs to be emitted.
1493 const FunctionLoweringInfo &FuncInfo) {
1494 return !I->mayWriteToMemory() && // Side-effecting instructions aren't folded.
1495 !I->isTerminator() && // Terminators aren't folded.
1496 !isa<DbgInfoIntrinsic>(I) && // Debug instructions aren't folded.
1497 !I->isEHPad() && // EH pad instructions aren't folded.
1498 !FuncInfo.isExportedInst(I); // Exported instrs must be computed.
1499}
1500
1502 const Value *Arg, DIExpression *Expr,
1503 DILocalVariable *Var,
1504 DebugLoc DbgLoc) {
1505 if (!Expr->isEntryValue() || !isa<Argument>(Arg))
1506 return false;
1507
1508 auto ArgIt = FuncInfo.ValueMap.find(Arg);
1509 if (ArgIt == FuncInfo.ValueMap.end())
1510 return false;
1511 Register ArgVReg = ArgIt->getSecond();
1512
1513 // Find the corresponding livein physical register to this argument.
1514 for (auto [PhysReg, VirtReg] : FuncInfo.RegInfo->liveins())
1515 if (VirtReg == ArgVReg) {
1516 // Append an op deref to account for the fact that this is a dbg_declare.
1517 Expr = DIExpression::append(Expr, dwarf::DW_OP_deref);
1518 FuncInfo.MF->setVariableDbgInfo(Var, Expr, PhysReg, DbgLoc);
1519 LLVM_DEBUG(dbgs() << "processDbgDeclare: setVariableDbgInfo Var=" << *Var
1520 << ", Expr=" << *Expr << ", MCRegister=" << PhysReg
1521 << ", DbgLoc=" << DbgLoc << "\n");
1522 return true;
1523 }
1524 return false;
1525}
1526
1528 const Value *Address, DIExpression *Expr,
1529 DILocalVariable *Var, DebugLoc DbgLoc) {
1530 if (!Address) {
1531 LLVM_DEBUG(dbgs() << "processDbgDeclares skipping " << *Var
1532 << " (bad address)\n");
1533 return false;
1534 }
1535
1536 if (processIfEntryValueDbgDeclare(FuncInfo, Address, Expr, Var, DbgLoc))
1537 return true;
1538
1539 MachineFunction *MF = FuncInfo.MF;
1540 const DataLayout &DL = MF->getDataLayout();
1541
1542 assert(Var && "Missing variable");
1543 assert(DbgLoc && "Missing location");
1544
1545 // Look through casts and constant offset GEPs. These mostly come from
1546 // inalloca.
1547 APInt Offset(DL.getTypeSizeInBits(Address->getType()), 0);
1548 Address = Address->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
1549
1550 // Check if the variable is a static alloca or a byval or inalloca
1551 // argument passed in memory. If it is not, then we will ignore this
1552 // intrinsic and handle this during isel like dbg.value.
1553 int FI = std::numeric_limits<int>::max();
1554 if (const auto *AI = dyn_cast<AllocaInst>(Address)) {
1555 auto SI = FuncInfo.StaticAllocaMap.find(AI);
1556 if (SI != FuncInfo.StaticAllocaMap.end())
1557 FI = SI->second;
1558 } else if (const auto *Arg = dyn_cast<Argument>(Address))
1559 FI = FuncInfo.getArgumentFrameIndex(Arg);
1560
1561 if (FI == std::numeric_limits<int>::max())
1562 return false;
1563
1564 if (Offset.getBoolValue())
1566 Offset.getZExtValue());
1567
1568 LLVM_DEBUG(dbgs() << "processDbgDeclare: setVariableDbgInfo Var=" << *Var
1569 << ", Expr=" << *Expr << ", FI=" << FI
1570 << ", DbgLoc=" << DbgLoc << "\n");
1571 MF->setVariableDbgInfo(Var, Expr, FI, DbgLoc);
1572 return true;
1573}
1574
1575/// Collect llvm.dbg.declare information. This is done after argument lowering
1576/// in case the declarations refer to arguments.
1578 for (const auto &I : instructions(*FuncInfo.Fn)) {
1579 const auto *DI = dyn_cast<DbgDeclareInst>(&I);
1580 if (DI && processDbgDeclare(FuncInfo, DI->getAddress(), DI->getExpression(),
1581 DI->getVariable(), DI->getDebugLoc()))
1582 FuncInfo.PreprocessedDbgDeclares.insert(DI);
1583 for (const DbgVariableRecord &DVR : filterDbgVars(I.getDbgRecordRange())) {
1585 processDbgDeclare(FuncInfo, DVR.getVariableLocationOp(0),
1586 DVR.getExpression(), DVR.getVariable(),
1587 DVR.getDebugLoc()))
1588 FuncInfo.PreprocessedDVRDeclares.insert(&DVR);
1589 }
1590 }
1591}
1592
1593/// Collect single location variable information generated with assignment
1594/// tracking. This is done after argument lowering in case the declarations
1595/// refer to arguments.
1597 FunctionVarLocs const *FnVarLocs) {
1598 for (auto It = FnVarLocs->single_locs_begin(),
1599 End = FnVarLocs->single_locs_end();
1600 It != End; ++It) {
1601 assert(!It->Values.hasArgList() && "Single loc variadic ops not supported");
1602 processDbgDeclare(FuncInfo, It->Values.getVariableLocationOp(0), It->Expr,
1603 FnVarLocs->getDILocalVariable(It->VariableID), It->DL);
1604 }
1605}
1606
1607void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) {
1608 FastISelFailed = false;
1609 // Initialize the Fast-ISel state, if needed.
1610 FastISel *FastIS = nullptr;
1612 LLVM_DEBUG(dbgs() << "Enabling fast-isel\n");
1613 FastIS = TLI->createFastISel(*FuncInfo, LibInfo);
1614 }
1615
1617
1618 // Lower arguments up front. An RPO iteration always visits the entry block
1619 // first.
1620 assert(*RPOT.begin() == &Fn.getEntryBlock());
1621 ++NumEntryBlocks;
1622
1623 // Set up FuncInfo for ISel. Entry blocks never have PHIs.
1624 FuncInfo->MBB = FuncInfo->MBBMap[&Fn.getEntryBlock()];
1625 FuncInfo->InsertPt = FuncInfo->MBB->begin();
1626
1628
1629 if (!FastIS) {
1630 LowerArguments(Fn);
1631 } else {
1632 // See if fast isel can lower the arguments.
1633 FastIS->startNewBlock();
1634 if (!FastIS->lowerArguments()) {
1635 FastISelFailed = true;
1636 // Fast isel failed to lower these arguments
1637 ++NumFastIselFailLowerArguments;
1638
1639 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1640 Fn.getSubprogram(),
1641 &Fn.getEntryBlock());
1642 R << "FastISel didn't lower all arguments: "
1643 << ore::NV("Prototype", Fn.getFunctionType());
1645
1646 // Use SelectionDAG argument lowering
1647 LowerArguments(Fn);
1648 CurDAG->setRoot(SDB->getControlRoot());
1649 SDB->clear();
1650 CodeGenAndEmitDAG();
1651 }
1652
1653 // If we inserted any instructions at the beginning, make a note of
1654 // where they are, so we can be sure to emit subsequent instructions
1655 // after them.
1656 if (FuncInfo->InsertPt != FuncInfo->MBB->begin())
1657 FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
1658 else
1659 FastIS->setLastLocalValue(nullptr);
1660 }
1661
1662 bool Inserted = SwiftError->createEntriesInEntryBlock(SDB->getCurDebugLoc());
1663
1664 if (FastIS && Inserted)
1665 FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
1666
1669 "expected AssignmentTrackingAnalysis pass results");
1671 } else {
1673 }
1674
1675 // Iterate over all basic blocks in the function.
1676 for (const BasicBlock *LLVMBB : RPOT) {
1678 bool AllPredsVisited = true;
1679 for (const BasicBlock *Pred : predecessors(LLVMBB)) {
1680 if (!FuncInfo->VisitedBBs.count(Pred)) {
1681 AllPredsVisited = false;
1682 break;
1683 }
1684 }
1685
1686 if (AllPredsVisited) {
1687 for (const PHINode &PN : LLVMBB->phis())
1688 FuncInfo->ComputePHILiveOutRegInfo(&PN);
1689 } else {
1690 for (const PHINode &PN : LLVMBB->phis())
1691 FuncInfo->InvalidatePHILiveOutRegInfo(&PN);
1692 }
1693
1694 FuncInfo->VisitedBBs.insert(LLVMBB);
1695 }
1696
1697 BasicBlock::const_iterator const Begin =
1698 LLVMBB->getFirstNonPHI()->getIterator();
1699 BasicBlock::const_iterator const End = LLVMBB->end();
1701
1702 FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB];
1703 if (!FuncInfo->MBB)
1704 continue; // Some blocks like catchpads have no code or MBB.
1705
1706 // Insert new instructions after any phi or argument setup code.
1707 FuncInfo->InsertPt = FuncInfo->MBB->end();
1708
1709 // Setup an EH landing-pad block.
1710 FuncInfo->ExceptionPointerVirtReg = 0;
1711 FuncInfo->ExceptionSelectorVirtReg = 0;
1712 if (LLVMBB->isEHPad())
1713 if (!PrepareEHLandingPad())
1714 continue;
1715
1716 // Before doing SelectionDAG ISel, see if FastISel has been requested.
1717 if (FastIS) {
1718 if (LLVMBB != &Fn.getEntryBlock())
1719 FastIS->startNewBlock();
1720
1721 unsigned NumFastIselRemaining = std::distance(Begin, End);
1722
1723 // Pre-assign swifterror vregs.
1724 SwiftError->preassignVRegs(FuncInfo->MBB, Begin, End);
1725
1726 // Do FastISel on as many instructions as possible.
1727 for (; BI != Begin; --BI) {
1728 const Instruction *Inst = &*std::prev(BI);
1729
1730 // If we no longer require this instruction, skip it.
1731 if (isFoldedOrDeadInstruction(Inst, *FuncInfo) ||
1732 ElidedArgCopyInstrs.count(Inst)) {
1733 --NumFastIselRemaining;
1734 FastIS->handleDbgInfo(Inst);
1735 continue;
1736 }
1737
1738 // Bottom-up: reset the insert pos at the top, after any local-value
1739 // instructions.
1740 FastIS->recomputeInsertPt();
1741
1742 // Try to select the instruction with FastISel.
1743 if (FastIS->selectInstruction(Inst)) {
1744 --NumFastIselRemaining;
1745 ++NumFastIselSuccess;
1746
1747 FastIS->handleDbgInfo(Inst);
1748 // If fast isel succeeded, skip over all the folded instructions, and
1749 // then see if there is a load right before the selected instructions.
1750 // Try to fold the load if so.
1751 const Instruction *BeforeInst = Inst;
1752 while (BeforeInst != &*Begin) {
1753 BeforeInst = &*std::prev(BasicBlock::const_iterator(BeforeInst));
1754 if (!isFoldedOrDeadInstruction(BeforeInst, *FuncInfo))
1755 break;
1756 }
1757 if (BeforeInst != Inst && isa<LoadInst>(BeforeInst) &&
1758 BeforeInst->hasOneUse() &&
1759 FastIS->tryToFoldLoad(cast<LoadInst>(BeforeInst), Inst)) {
1760 // If we succeeded, don't re-select the load.
1762 << "FastISel folded load: " << *BeforeInst << "\n");
1763 FastIS->handleDbgInfo(BeforeInst);
1764 BI = std::next(BasicBlock::const_iterator(BeforeInst));
1765 --NumFastIselRemaining;
1766 ++NumFastIselSuccess;
1767 }
1768 continue;
1769 }
1770
1771 FastISelFailed = true;
1772
1773 // Then handle certain instructions as single-LLVM-Instruction blocks.
1774 // We cannot separate out GCrelocates to their own blocks since we need
1775 // to keep track of gc-relocates for a particular gc-statepoint. This is
1776 // done by SelectionDAGBuilder::LowerAsSTATEPOINT, called before
1777 // visitGCRelocate.
1778 if (isa<CallInst>(Inst) && !isa<GCStatepointInst>(Inst) &&
1779 !isa<GCRelocateInst>(Inst) && !isa<GCResultInst>(Inst)) {
1780 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1781 Inst->getDebugLoc(), LLVMBB);
1782
1783 R << "FastISel missed call";
1784
1785 if (R.isEnabled() || EnableFastISelAbort) {
1786 std::string InstStrStorage;
1787 raw_string_ostream InstStr(InstStrStorage);
1788 InstStr << *Inst;
1789
1790 R << ": " << InstStr.str();
1791 }
1792
1794
1795 if (!Inst->getType()->isVoidTy() && !Inst->getType()->isTokenTy() &&
1796 !Inst->use_empty()) {
1797 Register &R = FuncInfo->ValueMap[Inst];
1798 if (!R)
1799 R = FuncInfo->CreateRegs(Inst);
1800 }
1801
1802 bool HadTailCall = false;
1803 MachineBasicBlock::iterator SavedInsertPt = FuncInfo->InsertPt;
1804 SelectBasicBlock(Inst->getIterator(), BI, HadTailCall);
1805
1806 // If the call was emitted as a tail call, we're done with the block.
1807 // We also need to delete any previously emitted instructions.
1808 if (HadTailCall) {
1809 FastIS->removeDeadCode(SavedInsertPt, FuncInfo->MBB->end());
1810 --BI;
1811 break;
1812 }
1813
1814 // Recompute NumFastIselRemaining as Selection DAG instruction
1815 // selection may have handled the call, input args, etc.
1816 unsigned RemainingNow = std::distance(Begin, BI);
1817 NumFastIselFailures += NumFastIselRemaining - RemainingNow;
1818 NumFastIselRemaining = RemainingNow;
1819 continue;
1820 }
1821
1822 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1823 Inst->getDebugLoc(), LLVMBB);
1824
1825 bool ShouldAbort = EnableFastISelAbort;
1826 if (Inst->isTerminator()) {
1827 // Use a different message for terminator misses.
1828 R << "FastISel missed terminator";
1829 // Don't abort for terminator unless the level is really high
1830 ShouldAbort = (EnableFastISelAbort > 2);
1831 } else {
1832 R << "FastISel missed";
1833 }
1834
1835 if (R.isEnabled() || EnableFastISelAbort) {
1836 std::string InstStrStorage;
1837 raw_string_ostream InstStr(InstStrStorage);
1838 InstStr << *Inst;
1839 R << ": " << InstStr.str();
1840 }
1841
1842 reportFastISelFailure(*MF, *ORE, R, ShouldAbort);
1843
1844 NumFastIselFailures += NumFastIselRemaining;
1845 break;
1846 }
1847
1848 FastIS->recomputeInsertPt();
1849 }
1850
1851 if (SP->shouldEmitSDCheck(*LLVMBB)) {
1852 bool FunctionBasedInstrumentation =
1854 SDB->SPDescriptor.initialize(LLVMBB, FuncInfo->MBBMap[LLVMBB],
1855 FunctionBasedInstrumentation);
1856 }
1857
1858 if (Begin != BI)
1859 ++NumDAGBlocks;
1860 else
1861 ++NumFastIselBlocks;
1862
1863 if (Begin != BI) {
1864 // Run SelectionDAG instruction selection on the remainder of the block
1865 // not handled by FastISel. If FastISel is not run, this is the entire
1866 // block.
1867 bool HadTailCall;
1868 SelectBasicBlock(Begin, BI, HadTailCall);
1869
1870 // But if FastISel was run, we already selected some of the block.
1871 // If we emitted a tail-call, we need to delete any previously emitted
1872 // instruction that follows it.
1873 if (FastIS && HadTailCall && FuncInfo->InsertPt != FuncInfo->MBB->end())
1874 FastIS->removeDeadCode(FuncInfo->InsertPt, FuncInfo->MBB->end());
1875 }
1876
1877 if (FastIS)
1878 FastIS->finishBasicBlock();
1879 FinishBasicBlock();
1880 FuncInfo->PHINodesToUpdate.clear();
1881 ElidedArgCopyInstrs.clear();
1882 }
1883
1884 // AsynchEH: Report Block State under -AsynchEH
1885 if (Fn.getParent()->getModuleFlag("eh-asynch"))
1886 reportIPToStateForBlocks(MF);
1887
1889
1891
1892 delete FastIS;
1893 SDB->clearDanglingDebugInfo();
1894 SDB->SPDescriptor.resetPerFunctionState();
1895}
1896
1897void
1898SelectionDAGISel::FinishBasicBlock() {
1899 LLVM_DEBUG(dbgs() << "Total amount of phi nodes to update: "
1900 << FuncInfo->PHINodesToUpdate.size() << "\n";
1901 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e;
1902 ++i) dbgs()
1903 << "Node " << i << " : (" << FuncInfo->PHINodesToUpdate[i].first
1904 << ", " << FuncInfo->PHINodesToUpdate[i].second << ")\n");
1905
1906 // Next, now that we know what the last MBB the LLVM BB expanded is, update
1907 // PHI nodes in successors.
1908 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) {
1909 MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[i].first);
1910 assert(PHI->isPHI() &&
1911 "This is not a machine PHI node that we are updating!");
1912 if (!FuncInfo->MBB->isSuccessor(PHI->getParent()))
1913 continue;
1914 PHI.addReg(FuncInfo->PHINodesToUpdate[i].second).addMBB(FuncInfo->MBB);
1915 }
1916
1917 // Handle stack protector.
1918 if (SDB->SPDescriptor.shouldEmitFunctionBasedCheckStackProtector()) {
1919 // The target provides a guard check function. There is no need to
1920 // generate error handling code or to split current basic block.
1921 MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
1922
1923 // Add load and check to the basicblock.
1924 FuncInfo->MBB = ParentMBB;
1925 FuncInfo->InsertPt =
1927 SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
1928 CurDAG->setRoot(SDB->getRoot());
1929 SDB->clear();
1930 CodeGenAndEmitDAG();
1931
1932 // Clear the Per-BB State.
1933 SDB->SPDescriptor.resetPerBBState();
1934 } else if (SDB->SPDescriptor.shouldEmitStackProtector()) {
1935 MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
1936 MachineBasicBlock *SuccessMBB = SDB->SPDescriptor.getSuccessMBB();
1937
1938 // Find the split point to split the parent mbb. At the same time copy all
1939 // physical registers used in the tail of parent mbb into virtual registers
1940 // before the split point and back into physical registers after the split
1941 // point. This prevents us needing to deal with Live-ins and many other
1942 // register allocation issues caused by us splitting the parent mbb. The
1943 // register allocator will clean up said virtual copies later on.
1944 MachineBasicBlock::iterator SplitPoint =
1946
1947 // Splice the terminator of ParentMBB into SuccessMBB.
1948 SuccessMBB->splice(SuccessMBB->end(), ParentMBB,
1949 SplitPoint,
1950 ParentMBB->end());
1951
1952 // Add compare/jump on neq/jump to the parent BB.
1953 FuncInfo->MBB = ParentMBB;
1954 FuncInfo->InsertPt = ParentMBB->end();
1955 SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
1956 CurDAG->setRoot(SDB->getRoot());
1957 SDB->clear();
1958 CodeGenAndEmitDAG();
1959
1960 // CodeGen Failure MBB if we have not codegened it yet.
1961 MachineBasicBlock *FailureMBB = SDB->SPDescriptor.getFailureMBB();
1962 if (FailureMBB->empty()) {
1963 FuncInfo->MBB = FailureMBB;
1964 FuncInfo->InsertPt = FailureMBB->end();
1965 SDB->visitSPDescriptorFailure(SDB->SPDescriptor);
1966 CurDAG->setRoot(SDB->getRoot());
1967 SDB->clear();
1968 CodeGenAndEmitDAG();
1969 }
1970
1971 // Clear the Per-BB State.
1972 SDB->SPDescriptor.resetPerBBState();
1973 }
1974
1975 // Lower each BitTestBlock.
1976 for (auto &BTB : SDB->SL->BitTestCases) {
1977 // Lower header first, if it wasn't already lowered
1978 if (!BTB.Emitted) {
1979 // Set the current basic block to the mbb we wish to insert the code into
1980 FuncInfo->MBB = BTB.Parent;
1981 FuncInfo->InsertPt = FuncInfo->MBB->end();
1982 // Emit the code
1983 SDB->visitBitTestHeader(BTB, FuncInfo->MBB);
1984 CurDAG->setRoot(SDB->getRoot());
1985 SDB->clear();
1986 CodeGenAndEmitDAG();
1987 }
1988
1989 BranchProbability UnhandledProb = BTB.Prob;
1990 for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; ++j) {
1991 UnhandledProb -= BTB.Cases[j].ExtraProb;
1992 // Set the current basic block to the mbb we wish to insert the code into
1993 FuncInfo->MBB = BTB.Cases[j].ThisBB;
1994 FuncInfo->InsertPt = FuncInfo->MBB->end();
1995 // Emit the code
1996
1997 // If all cases cover a contiguous range, it is not necessary to jump to
1998 // the default block after the last bit test fails. This is because the
1999 // range check during bit test header creation has guaranteed that every
2000 // case here doesn't go outside the range. In this case, there is no need
2001 // to perform the last bit test, as it will always be true. Instead, make
2002 // the second-to-last bit-test fall through to the target of the last bit
2003 // test, and delete the last bit test.
2004
2005 MachineBasicBlock *NextMBB;
2006 if ((BTB.ContiguousRange || BTB.FallthroughUnreachable) && j + 2 == ej) {
2007 // Second-to-last bit-test with contiguous range or omitted range
2008 // check: fall through to the target of the final bit test.
2009 NextMBB = BTB.Cases[j + 1].TargetBB;
2010 } else if (j + 1 == ej) {
2011 // For the last bit test, fall through to Default.
2012 NextMBB = BTB.Default;
2013 } else {
2014 // Otherwise, fall through to the next bit test.
2015 NextMBB = BTB.Cases[j + 1].ThisBB;
2016 }
2017
2018 SDB->visitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j],
2019 FuncInfo->MBB);
2020
2021 CurDAG->setRoot(SDB->getRoot());
2022 SDB->clear();
2023 CodeGenAndEmitDAG();
2024
2025 if ((BTB.ContiguousRange || BTB.FallthroughUnreachable) && j + 2 == ej) {
2026 // Since we're not going to use the final bit test, remove it.
2027 BTB.Cases.pop_back();
2028 break;
2029 }
2030 }
2031
2032 // Update PHI Nodes
2033 for (const std::pair<MachineInstr *, unsigned> &P :
2034 FuncInfo->PHINodesToUpdate) {
2035 MachineInstrBuilder PHI(*MF, P.first);
2036 MachineBasicBlock *PHIBB = PHI->getParent();
2037 assert(PHI->isPHI() &&
2038 "This is not a machine PHI node that we are updating!");
2039 // This is "default" BB. We have two jumps to it. From "header" BB and
2040 // from last "case" BB, unless the latter was skipped.
2041 if (PHIBB == BTB.Default) {
2042 PHI.addReg(P.second).addMBB(BTB.Parent);
2043 if (!BTB.ContiguousRange) {
2044 PHI.addReg(P.second).addMBB(BTB.Cases.back().ThisBB);
2045 }
2046 }
2047 // One of "cases" BB.
2048 for (const SwitchCG::BitTestCase &BT : BTB.Cases) {
2049 MachineBasicBlock* cBB = BT.ThisBB;
2050 if (cBB->isSuccessor(PHIBB))
2051 PHI.addReg(P.second).addMBB(cBB);
2052 }
2053 }
2054 }
2055 SDB->SL->BitTestCases.clear();
2056
2057 // If the JumpTable record is filled in, then we need to emit a jump table.
2058 // Updating the PHI nodes is tricky in this case, since we need to determine
2059 // whether the PHI is a successor of the range check MBB or the jump table MBB
2060 for (unsigned i = 0, e = SDB->SL->JTCases.size(); i != e; ++i) {
2061 // Lower header first, if it wasn't already lowered
2062 if (!SDB->SL->JTCases[i].first.Emitted) {
2063 // Set the current basic block to the mbb we wish to insert the code into
2064 FuncInfo->MBB = SDB->SL->JTCases[i].first.HeaderBB;
2065 FuncInfo->InsertPt = FuncInfo->MBB->end();
2066 // Emit the code
2067 SDB->visitJumpTableHeader(SDB->SL->JTCases[i].second,
2068 SDB->SL->JTCases[i].first, FuncInfo->MBB);
2069 CurDAG->setRoot(SDB->getRoot());
2070 SDB->clear();
2071 CodeGenAndEmitDAG();
2072 }
2073
2074 // Set the current basic block to the mbb we wish to insert the code into
2075 FuncInfo->MBB = SDB->SL->JTCases[i].second.MBB;
2076 FuncInfo->InsertPt = FuncInfo->MBB->end();
2077 // Emit the code
2078 SDB->visitJumpTable(SDB->SL->JTCases[i].second);
2079 CurDAG->setRoot(SDB->getRoot());
2080 SDB->clear();
2081 CodeGenAndEmitDAG();
2082
2083 // Update PHI Nodes
2084 for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
2085 pi != pe; ++pi) {
2086 MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
2087 MachineBasicBlock *PHIBB = PHI->getParent();
2088 assert(PHI->isPHI() &&
2089 "This is not a machine PHI node that we are updating!");
2090 // "default" BB. We can go there only from header BB.
2091 if (PHIBB == SDB->SL->JTCases[i].second.Default)
2092 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)
2093 .addMBB(SDB->SL->JTCases[i].first.HeaderBB);
2094 // JT BB. Just iterate over successors here
2095 if (FuncInfo->MBB->isSuccessor(PHIBB))
2096 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(FuncInfo->MBB);
2097 }
2098 }
2099 SDB->SL->JTCases.clear();
2100
2101 // If we generated any switch lowering information, build and codegen any
2102 // additional DAGs necessary.
2103 for (unsigned i = 0, e = SDB->SL->SwitchCases.size(); i != e; ++i) {
2104 // Set the current basic block to the mbb we wish to insert the code into
2105 FuncInfo->MBB = SDB->SL->SwitchCases[i].ThisBB;
2106 FuncInfo->InsertPt = FuncInfo->MBB->end();
2107
2108 // Determine the unique successors.
2110 Succs.push_back(SDB->SL->SwitchCases[i].TrueBB);
2111 if (SDB->SL->SwitchCases[i].TrueBB != SDB->SL->SwitchCases[i].FalseBB)
2112 Succs.push_back(SDB->SL->SwitchCases[i].FalseBB);
2113
2114 // Emit the code. Note that this could result in FuncInfo->MBB being split.
2115 SDB->visitSwitchCase(SDB->SL->SwitchCases[i], FuncInfo->MBB);
2116 CurDAG->setRoot(SDB->getRoot());
2117 SDB->clear();
2118 CodeGenAndEmitDAG();
2119
2120 // Remember the last block, now that any splitting is done, for use in
2121 // populating PHI nodes in successors.
2122 MachineBasicBlock *ThisBB = FuncInfo->MBB;
2123
2124 // Handle any PHI nodes in successors of this chunk, as if we were coming
2125 // from the original BB before switch expansion. Note that PHI nodes can
2126 // occur multiple times in PHINodesToUpdate. We have to be very careful to
2127 // handle them the right number of times.
2128 for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
2129 FuncInfo->MBB = Succs[i];
2130 FuncInfo->InsertPt = FuncInfo->MBB->end();
2131 // FuncInfo->MBB may have been removed from the CFG if a branch was
2132 // constant folded.
2133 if (ThisBB->isSuccessor(FuncInfo->MBB)) {
2135 MBBI = FuncInfo->MBB->begin(), MBBE = FuncInfo->MBB->end();
2136 MBBI != MBBE && MBBI->isPHI(); ++MBBI) {
2138 // This value for this PHI node is recorded in PHINodesToUpdate.
2139 for (unsigned pn = 0; ; ++pn) {
2140 assert(pn != FuncInfo->PHINodesToUpdate.size() &&
2141 "Didn't find PHI entry!");
2142 if (FuncInfo->PHINodesToUpdate[pn].first == PHI) {
2143 PHI.addReg(FuncInfo->PHINodesToUpdate[pn].second).addMBB(ThisBB);
2144 break;
2145 }
2146 }
2147 }
2148 }
2149 }
2150 }
2151 SDB->SL->SwitchCases.clear();
2152}
2153
2154/// Create the scheduler. If a specific scheduler was specified
2155/// via the SchedulerRegistry, use it, otherwise select the
2156/// one preferred by the target.
2157///
2158ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {
2159 return ISHeuristic(this, OptLevel);
2160}
2161
2162//===----------------------------------------------------------------------===//
2163// Helper functions used by the generated instruction selector.
2164//===----------------------------------------------------------------------===//
2165// Calls to these methods are generated by tblgen.
2166
2167/// CheckAndMask - The isel is trying to match something like (and X, 255). If
2168/// the dag combiner simplified the 255, we still want to match. RHS is the
2169/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
2170/// specified in the .td file (e.g. 255).
2172 int64_t DesiredMaskS) const {
2173 const APInt &ActualMask = RHS->getAPIntValue();
2174 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
2175
2176 // If the actual mask exactly matches, success!
2177 if (ActualMask == DesiredMask)
2178 return true;
2179
2180 // If the actual AND mask is allowing unallowed bits, this doesn't match.
2181 if (!ActualMask.isSubsetOf(DesiredMask))
2182 return false;
2183
2184 // Otherwise, the DAG Combiner may have proven that the value coming in is
2185 // either already zero or is not demanded. Check for known zero input bits.
2186 APInt NeededMask = DesiredMask & ~ActualMask;
2187 if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
2188 return true;
2189
2190 // TODO: check to see if missing bits are just not demanded.
2191
2192 // Otherwise, this pattern doesn't match.
2193 return false;
2194}
2195
2196/// CheckOrMask - The isel is trying to match something like (or X, 255). If
2197/// the dag combiner simplified the 255, we still want to match. RHS is the
2198/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
2199/// specified in the .td file (e.g. 255).
2201 int64_t DesiredMaskS) const {
2202 const APInt &ActualMask = RHS->getAPIntValue();
2203 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
2204
2205 // If the actual mask exactly matches, success!
2206 if (ActualMask == DesiredMask)
2207 return true;
2208
2209 // If the actual AND mask is allowing unallowed bits, this doesn't match.
2210 if (!ActualMask.isSubsetOf(DesiredMask))
2211 return false;
2212
2213 // Otherwise, the DAG Combiner may have proven that the value coming in is
2214 // either already zero or is not demanded. Check for known zero input bits.
2215 APInt NeededMask = DesiredMask & ~ActualMask;
2217
2218 // If all the missing bits in the or are already known to be set, match!
2219 if (NeededMask.isSubsetOf(Known.One))
2220 return true;
2221
2222 // TODO: check to see if missing bits are just not demanded.
2223
2224 // Otherwise, this pattern doesn't match.
2225 return false;
2226}
2227
2228/// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
2229/// by tblgen. Others should not call it.
2231 const SDLoc &DL) {
2232 std::vector<SDValue> InOps;
2233 std::swap(InOps, Ops);
2234
2235 Ops.push_back(InOps[InlineAsm::Op_InputChain]); // 0
2236 Ops.push_back(InOps[InlineAsm::Op_AsmString]); // 1
2237 Ops.push_back(InOps[InlineAsm::Op_MDNode]); // 2, !srcloc
2238 Ops.push_back(InOps[InlineAsm::Op_ExtraInfo]); // 3 (SideEffect, AlignStack)
2239
2240 unsigned i = InlineAsm::Op_FirstOperand, e = InOps.size();
2241 if (InOps[e-1].getValueType() == MVT::Glue)
2242 --e; // Don't process a glue operand if it is here.
2243
2244 while (i != e) {
2245 InlineAsm::Flag Flags(InOps[i]->getAsZExtVal());
2246 if (!Flags.isMemKind() && !Flags.isFuncKind()) {
2247 // Just skip over this operand, copying the operands verbatim.
2248 Ops.insert(Ops.end(), InOps.begin() + i,
2249 InOps.begin() + i + Flags.getNumOperandRegisters() + 1);
2250 i += Flags.getNumOperandRegisters() + 1;
2251 } else {
2252 assert(Flags.getNumOperandRegisters() == 1 &&
2253 "Memory operand with multiple values?");
2254
2255 unsigned TiedToOperand;
2256 if (Flags.isUseOperandTiedToDef(TiedToOperand)) {
2257 // We need the constraint ID from the operand this is tied to.
2258 unsigned CurOp = InlineAsm::Op_FirstOperand;
2259 Flags = InlineAsm::Flag(InOps[CurOp]->getAsZExtVal());
2260 for (; TiedToOperand; --TiedToOperand) {
2261 CurOp += Flags.getNumOperandRegisters() + 1;
2262 Flags = InlineAsm::Flag(InOps[CurOp]->getAsZExtVal());
2263 }
2264 }
2265
2266 // Otherwise, this is a memory operand. Ask the target to select it.
2267 std::vector<SDValue> SelOps;
2268 const InlineAsm::ConstraintCode ConstraintID =
2269 Flags.getMemoryConstraintID();
2270 if (SelectInlineAsmMemoryOperand(InOps[i+1], ConstraintID, SelOps))
2271 report_fatal_error("Could not match memory address. Inline asm"
2272 " failure!");
2273
2274 // Add this to the output node.
2275 Flags = InlineAsm::Flag(Flags.isMemKind() ? InlineAsm::Kind::Mem
2277 SelOps.size());
2278 Flags.setMemConstraint(ConstraintID);
2279 Ops.push_back(CurDAG->getTargetConstant(Flags, DL, MVT::i32));
2280 llvm::append_range(Ops, SelOps);
2281 i += 2;
2282 }
2283 }
2284
2285 // Add the glue input back if present.
2286 if (e != InOps.size())
2287 Ops.push_back(InOps.back());
2288}
2289
2290/// findGlueUse - Return use of MVT::Glue value produced by the specified
2291/// SDNode.
2292///
2294 unsigned FlagResNo = N->getNumValues()-1;
2295 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
2296 SDUse &Use = I.getUse();
2297 if (Use.getResNo() == FlagResNo)
2298 return Use.getUser();
2299 }
2300 return nullptr;
2301}
2302
2303/// findNonImmUse - Return true if "Def" is a predecessor of "Root" via a path
2304/// beyond "ImmedUse". We may ignore chains as they are checked separately.
2305static bool findNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse,
2306 bool IgnoreChains) {
2309 // Only check if we have non-immediate uses of Def.
2310 if (ImmedUse->isOnlyUserOf(Def))
2311 return false;
2312
2313 // We don't care about paths to Def that go through ImmedUse so mark it
2314 // visited and mark non-def operands as used.
2315 Visited.insert(ImmedUse);
2316 for (const SDValue &Op : ImmedUse->op_values()) {
2317 SDNode *N = Op.getNode();
2318 // Ignore chain deps (they are validated by
2319 // HandleMergeInputChains) and immediate uses
2320 if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)
2321 continue;
2322 if (!Visited.insert(N).second)
2323 continue;
2324 WorkList.push_back(N);
2325 }
2326
2327 // Initialize worklist to operands of Root.
2328 if (Root != ImmedUse) {
2329 for (const SDValue &Op : Root->op_values()) {
2330 SDNode *N = Op.getNode();
2331 // Ignore chains (they are validated by HandleMergeInputChains)
2332 if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)
2333 continue;
2334 if (!Visited.insert(N).second)
2335 continue;
2336 WorkList.push_back(N);
2337 }
2338 }
2339
2340 return SDNode::hasPredecessorHelper(Def, Visited, WorkList, 0, true);
2341}
2342
2343/// IsProfitableToFold - Returns true if it's profitable to fold the specific
2344/// operand node N of U during instruction selection that starts at Root.
2346 SDNode *Root) const {
2348 return false;
2349 return N.hasOneUse();
2350}
2351
2352/// IsLegalToFold - Returns true if the specific operand node N of
2353/// U can be folded during instruction selection that starts at Root.
2355 CodeGenOptLevel OptLevel,
2356 bool IgnoreChains) {
2358 return false;
2359
2360 // If Root use can somehow reach N through a path that doesn't contain
2361 // U then folding N would create a cycle. e.g. In the following
2362 // diagram, Root can reach N through X. If N is folded into Root, then
2363 // X is both a predecessor and a successor of U.
2364 //
2365 // [N*] //
2366 // ^ ^ //
2367 // / \ //
2368 // [U*] [X]? //
2369 // ^ ^ //
2370 // \ / //
2371 // \ / //
2372 // [Root*] //
2373 //
2374 // * indicates nodes to be folded together.
2375 //
2376 // If Root produces glue, then it gets (even more) interesting. Since it
2377 // will be "glued" together with its glue use in the scheduler, we need to
2378 // check if it might reach N.
2379 //
2380 // [N*] //
2381 // ^ ^ //
2382 // / \ //
2383 // [U*] [X]? //
2384 // ^ ^ //
2385 // \ \ //
2386 // \ | //
2387 // [Root*] | //
2388 // ^ | //
2389 // f | //
2390 // | / //
2391 // [Y] / //
2392 // ^ / //
2393 // f / //
2394 // | / //
2395 // [GU] //
2396 //
2397 // If GU (glue use) indirectly reaches N (the load), and Root folds N
2398 // (call it Fold), then X is a predecessor of GU and a successor of
2399 // Fold. But since Fold and GU are glued together, this will create
2400 // a cycle in the scheduling graph.
2401
2402 // If the node has glue, walk down the graph to the "lowest" node in the
2403 // glueged set.
2404 EVT VT = Root->getValueType(Root->getNumValues()-1);
2405 while (VT == MVT::Glue) {
2406 SDNode *GU = findGlueUse(Root);
2407 if (!GU)
2408 break;
2409 Root = GU;
2410 VT = Root->getValueType(Root->getNumValues()-1);
2411
2412 // If our query node has a glue result with a use, we've walked up it. If
2413 // the user (which has already been selected) has a chain or indirectly uses
2414 // the chain, HandleMergeInputChains will not consider it. Because of
2415 // this, we cannot ignore chains in this predicate.
2416 IgnoreChains = false;
2417 }
2418
2419 return !findNonImmUse(Root, N.getNode(), U, IgnoreChains);
2420}
2421
2422void SelectionDAGISel::Select_INLINEASM(SDNode *N) {
2423 SDLoc DL(N);
2424
2425 std::vector<SDValue> Ops(N->op_begin(), N->op_end());
2427
2428 const EVT VTs[] = {MVT::Other, MVT::Glue};
2429 SDValue New = CurDAG->getNode(N->getOpcode(), DL, VTs, Ops);
2430 New->setNodeId(-1);
2431 ReplaceUses(N, New.getNode());
2433}
2434
2435void SelectionDAGISel::Select_READ_REGISTER(SDNode *Op) {
2436 SDLoc dl(Op);
2437 MDNodeSDNode *MD = cast<MDNodeSDNode>(Op->getOperand(1));
2438 const MDString *RegStr = cast<MDString>(MD->getMD()->getOperand(0));
2439
2440 EVT VT = Op->getValueType(0);
2441 LLT Ty = VT.isSimple() ? getLLTForMVT(VT.getSimpleVT()) : LLT();
2442 Register Reg =
2443 TLI->getRegisterByName(RegStr->getString().data(), Ty,
2446 Op->getOperand(0), dl, Reg, Op->getValueType(0));
2447 New->setNodeId(-1);
2448 ReplaceUses(Op, New.getNode());
2450}
2451
2452void SelectionDAGISel::Select_WRITE_REGISTER(SDNode *Op) {
2453 SDLoc dl(Op);
2454 MDNodeSDNode *MD = cast<MDNodeSDNode>(Op->getOperand(1));
2455 const MDString *RegStr = cast<MDString>(MD->getMD()->getOperand(0));
2456
2457 EVT VT = Op->getOperand(2).getValueType();
2458 LLT Ty = VT.isSimple() ? getLLTForMVT(VT.getSimpleVT()) : LLT();
2459
2460 Register Reg = TLI->getRegisterByName(RegStr->getString().data(), Ty,
2463 Op->getOperand(0), dl, Reg, Op->getOperand(2));
2464 New->setNodeId(-1);
2465 ReplaceUses(Op, New.getNode());
2467}
2468
2469void SelectionDAGISel::Select_UNDEF(SDNode *N) {
2470 CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF, N->getValueType(0));
2471}
2472
2473void SelectionDAGISel::Select_FREEZE(SDNode *N) {
2474 // TODO: We don't have FREEZE pseudo-instruction in MachineInstr-level now.
2475 // If FREEZE instruction is added later, the code below must be changed as
2476 // well.
2477 CurDAG->SelectNodeTo(N, TargetOpcode::COPY, N->getValueType(0),
2478 N->getOperand(0));
2479}
2480
2481void SelectionDAGISel::Select_ARITH_FENCE(SDNode *N) {
2482 CurDAG->SelectNodeTo(N, TargetOpcode::ARITH_FENCE, N->getValueType(0),
2483 N->getOperand(0));
2484}
2485
2486void SelectionDAGISel::Select_MEMBARRIER(SDNode *N) {
2487 CurDAG->SelectNodeTo(N, TargetOpcode::MEMBARRIER, N->getValueType(0),
2488 N->getOperand(0));
2489}
2490
2491void SelectionDAGISel::Select_CONVERGENCECTRL_ANCHOR(SDNode *N) {
2492 CurDAG->SelectNodeTo(N, TargetOpcode::CONVERGENCECTRL_ANCHOR,
2493 N->getValueType(0));
2494}
2495
2496void SelectionDAGISel::Select_CONVERGENCECTRL_ENTRY(SDNode *N) {
2497 CurDAG->SelectNodeTo(N, TargetOpcode::CONVERGENCECTRL_ENTRY,
2498 N->getValueType(0));
2499}
2500
2501void SelectionDAGISel::Select_CONVERGENCECTRL_LOOP(SDNode *N) {
2502 CurDAG->SelectNodeTo(N, TargetOpcode::CONVERGENCECTRL_LOOP,
2503 N->getValueType(0), N->getOperand(0));
2504}
2505
2506void SelectionDAGISel::pushStackMapLiveVariable(SmallVectorImpl<SDValue> &Ops,
2507 SDValue OpVal, SDLoc DL) {
2508 SDNode *OpNode = OpVal.getNode();
2509
2510 // FrameIndex nodes should have been directly emitted to TargetFrameIndex
2511 // nodes at DAG-construction time.
2512 assert(OpNode->getOpcode() != ISD::FrameIndex);
2513
2514 if (OpNode->getOpcode() == ISD::Constant) {
2515 Ops.push_back(
2516 CurDAG->getTargetConstant(StackMaps::ConstantOp, DL, MVT::i64));
2518 OpVal.getValueType()));
2519 } else {
2520 Ops.push_back(OpVal);
2521 }
2522}
2523
2524void SelectionDAGISel::Select_STACKMAP(SDNode *N) {
2526 auto *It = N->op_begin();
2527 SDLoc DL(N);
2528
2529 // Stash the chain and glue operands so we can move them to the end.
2530 SDValue Chain = *It++;
2531 SDValue InGlue = *It++;
2532
2533 // <id> operand.
2534 SDValue ID = *It++;
2535 assert(ID.getValueType() == MVT::i64);
2536 Ops.push_back(ID);
2537
2538 // <numShadowBytes> operand.
2539 SDValue Shad = *It++;
2540 assert(Shad.getValueType() == MVT::i32);
2541 Ops.push_back(Shad);
2542
2543 // Live variable operands.
2544 for (; It != N->op_end(); It++)
2545 pushStackMapLiveVariable(Ops, *It, DL);
2546
2547 Ops.push_back(Chain);
2548 Ops.push_back(InGlue);
2549
2550 SDVTList NodeTys = CurDAG->getVTList(MVT::Other, MVT::Glue);
2551 CurDAG->SelectNodeTo(N, TargetOpcode::STACKMAP, NodeTys, Ops);
2552}
2553
2554void SelectionDAGISel::Select_PATCHPOINT(SDNode *N) {
2556 auto *It = N->op_begin();
2557 SDLoc DL(N);
2558
2559 // Cache arguments that will be moved to the end in the target node.
2560 SDValue Chain = *It++;
2561 std::optional<SDValue> Glue;
2562 if (It->getValueType() == MVT::Glue)
2563 Glue = *It++;
2564 SDValue RegMask = *It++;
2565
2566 // <id> operand.
2567 SDValue ID = *It++;
2568 assert(ID.getValueType() == MVT::i64);
2569 Ops.push_back(ID);
2570
2571 // <numShadowBytes> operand.
2572 SDValue Shad = *It++;
2573 assert(Shad.getValueType() == MVT::i32);
2574 Ops.push_back(Shad);
2575
2576 // Add the callee.
2577 Ops.push_back(*It++);
2578
2579 // Add <numArgs>.
2580 SDValue NumArgs = *It++;
2581 assert(NumArgs.getValueType() == MVT::i32);
2582 Ops.push_back(NumArgs);
2583
2584 // Calling convention.
2585 Ops.push_back(*It++);
2586
2587 // Push the args for the call.
2588 for (uint64_t I = NumArgs->getAsZExtVal(); I != 0; I--)
2589 Ops.push_back(*It++);
2590
2591 // Now push the live variables.
2592 for (; It != N->op_end(); It++)
2593 pushStackMapLiveVariable(Ops, *It, DL);
2594
2595 // Finally, the regmask, chain and (if present) glue are moved to the end.
2596 Ops.push_back(RegMask);
2597 Ops.push_back(Chain);
2598 if (Glue.has_value())
2599 Ops.push_back(*Glue);
2600
2601 SDVTList NodeTys = N->getVTList();
2602 CurDAG->SelectNodeTo(N, TargetOpcode::PATCHPOINT, NodeTys, Ops);
2603}
2604
2605/// GetVBR - decode a vbr encoding whose top bit is set.
2607GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {
2608 assert(Val >= 128 && "Not a VBR");
2609 Val &= 127; // Remove first vbr bit.
2610
2611 unsigned Shift = 7;
2612 uint64_t NextBits;
2613 do {
2614 NextBits = MatcherTable[Idx++];
2615 Val |= (NextBits&127) << Shift;
2616 Shift += 7;
2617 } while (NextBits & 128);
2618
2619 return Val;
2620}
2621
2622void SelectionDAGISel::Select_JUMP_TABLE_DEBUG_INFO(SDNode *N) {
2623 SDLoc dl(N);
2624 CurDAG->SelectNodeTo(N, TargetOpcode::JUMP_TABLE_DEBUG_INFO, MVT::Glue,
2625 CurDAG->getTargetConstant(N->getConstantOperandVal(1),
2626 dl, MVT::i64, true));
2627}
2628
2629/// When a match is complete, this method updates uses of interior chain results
2630/// to use the new results.
2631void SelectionDAGISel::UpdateChains(
2632 SDNode *NodeToMatch, SDValue InputChain,
2633 SmallVectorImpl<SDNode *> &ChainNodesMatched, bool isMorphNodeTo) {
2634 SmallVector<SDNode*, 4> NowDeadNodes;
2635
2636 // Now that all the normal results are replaced, we replace the chain and
2637 // glue results if present.
2638 if (!ChainNodesMatched.empty()) {
2639 assert(InputChain.getNode() &&
2640 "Matched input chains but didn't produce a chain");
2641 // Loop over all of the nodes we matched that produced a chain result.
2642 // Replace all the chain results with the final chain we ended up with.
2643 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2644 SDNode *ChainNode = ChainNodesMatched[i];
2645 // If ChainNode is null, it's because we replaced it on a previous
2646 // iteration and we cleared it out of the map. Just skip it.
2647 if (!ChainNode)
2648 continue;
2649
2650 assert(ChainNode->getOpcode() != ISD::DELETED_NODE &&
2651 "Deleted node left in chain");
2652
2653 // Don't replace the results of the root node if we're doing a
2654 // MorphNodeTo.
2655 if (ChainNode == NodeToMatch && isMorphNodeTo)
2656 continue;
2657
2658 SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);
2659 if (ChainVal.getValueType() == MVT::Glue)
2660 ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
2661 assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
2663 *CurDAG, [&](SDNode *N, SDNode *E) {
2664 std::replace(ChainNodesMatched.begin(), ChainNodesMatched.end(), N,
2665 static_cast<SDNode *>(nullptr));
2666 });
2667 if (ChainNode->getOpcode() != ISD::TokenFactor)
2668 ReplaceUses(ChainVal, InputChain);
2669
2670 // If the node became dead and we haven't already seen it, delete it.
2671 if (ChainNode != NodeToMatch && ChainNode->use_empty() &&
2672 !llvm::is_contained(NowDeadNodes, ChainNode))
2673 NowDeadNodes.push_back(ChainNode);
2674 }
2675 }
2676
2677 if (!NowDeadNodes.empty())
2678 CurDAG->RemoveDeadNodes(NowDeadNodes);
2679
2680 LLVM_DEBUG(dbgs() << "ISEL: Match complete!\n");
2681}
2682
2683/// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
2684/// operation for when the pattern matched at least one node with a chains. The
2685/// input vector contains a list of all of the chained nodes that we match. We
2686/// must determine if this is a valid thing to cover (i.e. matching it won't
2687/// induce cycles in the DAG) and if so, creating a TokenFactor node. that will
2688/// be used as the input node chain for the generated nodes.
2689static SDValue
2691 SelectionDAG *CurDAG) {
2692
2695 SmallVector<SDValue, 3> InputChains;
2696 unsigned int Max = 8192;
2697
2698 // Quick exit on trivial merge.
2699 if (ChainNodesMatched.size() == 1)
2700 return ChainNodesMatched[0]->getOperand(0);
2701
2702 // Add chains that aren't already added (internal). Peek through
2703 // token factors.
2704 std::function<void(const SDValue)> AddChains = [&](const SDValue V) {
2705 if (V.getValueType() != MVT::Other)
2706 return;
2707 if (V->getOpcode() == ISD::EntryToken)
2708 return;
2709 if (!Visited.insert(V.getNode()).second)
2710 return;
2711 if (V->getOpcode() == ISD::TokenFactor) {
2712 for (const SDValue &Op : V->op_values())
2713 AddChains(Op);
2714 } else
2715 InputChains.push_back(V);
2716 };
2717
2718 for (auto *N : ChainNodesMatched) {
2719 Worklist.push_back(N);
2720 Visited.insert(N);
2721 }
2722
2723 while (!Worklist.empty())
2724 AddChains(Worklist.pop_back_val()->getOperand(0));
2725
2726 // Skip the search if there are no chain dependencies.
2727 if (InputChains.size() == 0)
2728 return CurDAG->getEntryNode();
2729
2730 // If one of these chains is a successor of input, we must have a
2731 // node that is both the predecessor and successor of the
2732 // to-be-merged nodes. Fail.
2733 Visited.clear();
2734 for (SDValue V : InputChains)
2735 Worklist.push_back(V.getNode());
2736
2737 for (auto *N : ChainNodesMatched)
2738 if (SDNode::hasPredecessorHelper(N, Visited, Worklist, Max, true))
2739 return SDValue();
2740
2741 // Return merged chain.
2742 if (InputChains.size() == 1)
2743 return InputChains[0];
2744 return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]),
2745 MVT::Other, InputChains);
2746}
2747
2748/// MorphNode - Handle morphing a node in place for the selector.
2749SDNode *SelectionDAGISel::
2750MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
2751 ArrayRef<SDValue> Ops, unsigned EmitNodeInfo) {
2752 // It is possible we're using MorphNodeTo to replace a node with no
2753 // normal results with one that has a normal result (or we could be
2754 // adding a chain) and the input could have glue and chains as well.
2755 // In this case we need to shift the operands down.
2756 // FIXME: This is a horrible hack and broken in obscure cases, no worse
2757 // than the old isel though.
2758 int OldGlueResultNo = -1, OldChainResultNo = -1;
2759
2760 unsigned NTMNumResults = Node->getNumValues();
2761 if (Node->getValueType(NTMNumResults-1) == MVT::Glue) {
2762 OldGlueResultNo = NTMNumResults-1;
2763 if (NTMNumResults != 1 &&
2764 Node->getValueType(NTMNumResults-2) == MVT::Other)
2765 OldChainResultNo = NTMNumResults-2;
2766 } else if (Node->getValueType(NTMNumResults-1) == MVT::Other)
2767 OldChainResultNo = NTMNumResults-1;
2768
2769 // Call the underlying SelectionDAG routine to do the transmogrification. Note
2770 // that this deletes operands of the old node that become dead.
2771 SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops);
2772
2773 // MorphNodeTo can operate in two ways: if an existing node with the
2774 // specified operands exists, it can just return it. Otherwise, it
2775 // updates the node in place to have the requested operands.
2776 if (Res == Node) {
2777 // If we updated the node in place, reset the node ID. To the isel,
2778 // this should be just like a newly allocated machine node.
2779 Res->setNodeId(-1);
2780 }
2781
2782 unsigned ResNumResults = Res->getNumValues();
2783 // Move the glue if needed.
2784 if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 &&
2785 static_cast<unsigned>(OldGlueResultNo) != ResNumResults - 1)
2786 ReplaceUses(SDValue(Node, OldGlueResultNo),
2787 SDValue(Res, ResNumResults - 1));
2788
2789 if ((EmitNodeInfo & OPFL_GlueOutput) != 0)
2790 --ResNumResults;
2791
2792 // Move the chain reference if needed.
2793 if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
2794 static_cast<unsigned>(OldChainResultNo) != ResNumResults - 1)
2795 ReplaceUses(SDValue(Node, OldChainResultNo),
2796 SDValue(Res, ResNumResults - 1));
2797
2798 // Otherwise, no replacement happened because the node already exists. Replace
2799 // Uses of the old node with the new one.
2800 if (Res != Node) {
2801 ReplaceNode(Node, Res);
2802 } else {
2804 }
2805
2806 return Res;
2807}
2808
2809/// CheckSame - Implements OP_CheckSame.
2811CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2812 const SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes) {
2813 // Accept if it is exactly the same as a previously recorded node.
2814 unsigned RecNo = MatcherTable[MatcherIndex++];
2815 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2816 return N == RecordedNodes[RecNo].first;
2817}
2818
2819/// CheckChildSame - Implements OP_CheckChildXSame.
2821 const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2822 const SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes,
2823 unsigned ChildNo) {
2824 if (ChildNo >= N.getNumOperands())
2825 return false; // Match fails if out of range child #.
2826 return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo),
2827 RecordedNodes);
2828}
2829
2830/// CheckPatternPredicate - Implements OP_CheckPatternPredicate.
2832CheckPatternPredicate(unsigned Opcode, const unsigned char *MatcherTable,
2833 unsigned &MatcherIndex, const SelectionDAGISel &SDISel) {
2834 bool TwoBytePredNo =
2836 unsigned PredNo =
2837 TwoBytePredNo || Opcode == SelectionDAGISel::OPC_CheckPatternPredicate
2838 ? MatcherTable[MatcherIndex++]
2840 if (TwoBytePredNo)
2841 PredNo |= MatcherTable[MatcherIndex++] << 8;
2842 return SDISel.CheckPatternPredicate(PredNo);
2843}
2844
2845/// CheckNodePredicate - Implements OP_CheckNodePredicate.
2847CheckNodePredicate(unsigned Opcode, const unsigned char *MatcherTable,
2848 unsigned &MatcherIndex, const SelectionDAGISel &SDISel,
2849 SDNode *N) {
2850 unsigned PredNo = Opcode == SelectionDAGISel::OPC_CheckPredicate
2851 ? MatcherTable[MatcherIndex++]
2853 return SDISel.CheckNodePredicate(N, PredNo);
2854}
2855
2857CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2858 SDNode *N) {
2859 uint16_t Opc = MatcherTable[MatcherIndex++];
2860 Opc |= static_cast<uint16_t>(MatcherTable[MatcherIndex++]) << 8;
2861 return N->getOpcode() == Opc;
2862}
2863
2865 SDValue N,
2866 const TargetLowering *TLI,
2867 const DataLayout &DL) {
2868 if (N.getValueType() == VT)
2869 return true;
2870
2871 // Handle the case when VT is iPTR.
2872 return VT == MVT::iPTR && N.getValueType() == TLI->getPointerTy(DL);
2873}
2874
2877 const DataLayout &DL, unsigned ChildNo) {
2878 if (ChildNo >= N.getNumOperands())
2879 return false; // Match fails if out of range child #.
2880 return ::CheckType(VT, N.getOperand(ChildNo), TLI, DL);
2881}
2882
2884CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2885 SDValue N) {
2886 return cast<CondCodeSDNode>(N)->get() ==
2887 static_cast<ISD::CondCode>(MatcherTable[MatcherIndex++]);
2888}
2889
2891CheckChild2CondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2892 SDValue N) {
2893 if (2 >= N.getNumOperands())
2894 return false;
2895 return ::CheckCondCode(MatcherTable, MatcherIndex, N.getOperand(2));
2896}
2897
2899CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2900 SDValue N, const TargetLowering *TLI, const DataLayout &DL) {
2902 static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
2903 if (cast<VTSDNode>(N)->getVT() == VT)
2904 return true;
2905
2906 // Handle the case when VT is iPTR.
2907 return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI->getPointerTy(DL);
2908}
2909
2910// Bit 0 stores the sign of the immediate. The upper bits contain the magnitude
2911// shifted left by 1.
2913 if ((V & 1) == 0)
2914 return V >> 1;
2915 if (V != 1)
2916 return -(V >> 1);
2917 // There is no such thing as -0 with integers. "-0" really means MININT.
2918 return 1ULL << 63;
2919}
2920
2922CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2923 SDValue N) {
2924 int64_t Val = MatcherTable[MatcherIndex++];
2925 if (Val & 128)
2926 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2927
2928 Val = decodeSignRotatedValue(Val);
2929
2930 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N);
2931 return C && C->getAPIntValue().trySExtValue() == Val;
2932}
2933
2935CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2936 SDValue N, unsigned ChildNo) {
2937 if (ChildNo >= N.getNumOperands())
2938 return false; // Match fails if out of range child #.
2939 return ::CheckInteger(MatcherTable, MatcherIndex, N.getOperand(ChildNo));
2940}
2941
2943CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2944 SDValue N, const SelectionDAGISel &SDISel) {
2945 int64_t Val = MatcherTable[MatcherIndex++];
2946 if (Val & 128)
2947 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2948
2949 if (N->getOpcode() != ISD::AND) return false;
2950
2951 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
2952 return C && SDISel.CheckAndMask(N.getOperand(0), C, Val);
2953}
2954
2956CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2957 const SelectionDAGISel &SDISel) {
2958 int64_t Val = MatcherTable[MatcherIndex++];
2959 if (Val & 128)
2960 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2961
2962 if (N->getOpcode() != ISD::OR) return false;
2963
2964 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
2965 return C && SDISel.CheckOrMask(N.getOperand(0), C, Val);
2966}
2967
2968/// IsPredicateKnownToFail - If we know how and can do so without pushing a
2969/// scope, evaluate the current node. If the current predicate is known to
2970/// fail, set Result=true and return anything. If the current predicate is
2971/// known to pass, set Result=false and return the MatcherIndex to continue
2972/// with. If the current predicate is unknown, set Result=false and return the
2973/// MatcherIndex to continue with.
2974static unsigned IsPredicateKnownToFail(const unsigned char *Table,
2975 unsigned Index, SDValue N,
2976 bool &Result,
2977 const SelectionDAGISel &SDISel,
2978 SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) {
2979 unsigned Opcode = Table[Index++];
2980 switch (Opcode) {
2981 default:
2982 Result = false;
2983 return Index-1; // Could not evaluate this predicate.
2985 Result = !::CheckSame(Table, Index, N, RecordedNodes);
2986 return Index;
2991 Result = !::CheckChildSame(Table, Index, N, RecordedNodes,
2993 return Index;
3004 Result = !::CheckPatternPredicate(Opcode, Table, Index, SDISel);
3005 return Index;
3015 Result = !::CheckNodePredicate(Opcode, Table, Index, SDISel, N.getNode());
3016 return Index;
3018 Result = !::CheckOpcode(Table, Index, N.getNode());
3019 return Index;
3024 switch (Opcode) {
3026 VT = MVT::i32;
3027 break;
3029 VT = MVT::i64;
3030 break;
3031 default:
3032 VT = static_cast<MVT::SimpleValueType>(Table[Index++]);
3033 break;
3034 }
3035 Result = !::CheckType(VT, N, SDISel.TLI, SDISel.CurDAG->getDataLayout());
3036 return Index;
3037 }
3039 unsigned Res = Table[Index++];
3040 Result = !::CheckType(static_cast<MVT::SimpleValueType>(Table[Index++]),
3041 N.getValue(Res), SDISel.TLI,
3042 SDISel.CurDAG->getDataLayout());
3043 return Index;
3044 }
3070 unsigned ChildNo;
3073 VT = MVT::i32;
3075 } else if (Opcode >= SelectionDAGISel::OPC_CheckChild0TypeI64 &&
3077 VT = MVT::i64;
3079 } else {
3080 VT = static_cast<MVT::SimpleValueType>(Table[Index++]);
3081 ChildNo = Opcode - SelectionDAGISel::OPC_CheckChild0Type;
3082 }
3083 Result = !::CheckChildType(VT, N, SDISel.TLI,
3084 SDISel.CurDAG->getDataLayout(), ChildNo);
3085 return Index;
3086 }
3088 Result = !::CheckCondCode(Table, Index, N);
3089 return Index;
3091 Result = !::CheckChild2CondCode(Table, Index, N);
3092 return Index;
3094 Result = !::CheckValueType(Table, Index, N, SDISel.TLI,
3095 SDISel.CurDAG->getDataLayout());
3096 return Index;
3098 Result = !::CheckInteger(Table, Index, N);
3099 return Index;
3105 Result = !::CheckChildInteger(Table, Index, N,
3107 return Index;
3109 Result = !::CheckAndImm(Table, Index, N, SDISel);
3110 return Index;
3112 Result = !::CheckOrImm(Table, Index, N, SDISel);
3113 return Index;
3114 }
3115}
3116
3117namespace {
3118
3119struct MatchScope {
3120 /// FailIndex - If this match fails, this is the index to continue with.
3121 unsigned FailIndex;
3122
3123 /// NodeStack - The node stack when the scope was formed.
3124 SmallVector<SDValue, 4> NodeStack;
3125
3126 /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
3127 unsigned NumRecordedNodes;
3128
3129 /// NumMatchedMemRefs - The number of matched memref entries.
3130 unsigned NumMatchedMemRefs;
3131
3132 /// InputChain/InputGlue - The current chain/glue
3133 SDValue InputChain, InputGlue;
3134
3135 /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.
3136 bool HasChainNodesMatched;
3137};
3138
3139/// \A DAG update listener to keep the matching state
3140/// (i.e. RecordedNodes and MatchScope) uptodate if the target is allowed to
3141/// change the DAG while matching. X86 addressing mode matcher is an example
3142/// for this.
3143class MatchStateUpdater : public SelectionDAG::DAGUpdateListener
3144{
3145 SDNode **NodeToMatch;
3147 SmallVectorImpl<MatchScope> &MatchScopes;
3148
3149public:
3150 MatchStateUpdater(SelectionDAG &DAG, SDNode **NodeToMatch,
3151 SmallVectorImpl<std::pair<SDValue, SDNode *>> &RN,
3153 : SelectionDAG::DAGUpdateListener(DAG), NodeToMatch(NodeToMatch),
3154 RecordedNodes(RN), MatchScopes(MS) {}
3155
3156 void NodeDeleted(SDNode *N, SDNode *E) override {
3157 // Some early-returns here to avoid the search if we deleted the node or
3158 // if the update comes from MorphNodeTo (MorphNodeTo is the last thing we
3159 // do, so it's unnecessary to update matching state at that point).
3160 // Neither of these can occur currently because we only install this
3161 // update listener during matching a complex patterns.
3162 if (!E || E->isMachineOpcode())
3163 return;
3164 // Check if NodeToMatch was updated.
3165 if (N == *NodeToMatch)
3166 *NodeToMatch = E;
3167 // Performing linear search here does not matter because we almost never
3168 // run this code. You'd have to have a CSE during complex pattern
3169 // matching.
3170 for (auto &I : RecordedNodes)
3171 if (I.first.getNode() == N)
3172 I.first.setNode(E);
3173
3174 for (auto &I : MatchScopes)
3175 for (auto &J : I.NodeStack)
3176 if (J.getNode() == N)
3177 J.setNode(E);
3178 }
3179};
3180
3181} // end anonymous namespace
3182
3184 const unsigned char *MatcherTable,
3185 unsigned TableSize) {
3186 // FIXME: Should these even be selected? Handle these cases in the caller?
3187 switch (NodeToMatch->getOpcode()) {
3188 default:
3189 break;
3190 case ISD::EntryToken: // These nodes remain the same.
3191 case ISD::BasicBlock:
3192 case ISD::Register:
3193 case ISD::RegisterMask:
3194 case ISD::HANDLENODE:
3195 case ISD::MDNODE_SDNODE:
3201 case ISD::MCSymbol:
3206 case ISD::TokenFactor:
3207 case ISD::CopyFromReg:
3208 case ISD::CopyToReg:
3209 case ISD::EH_LABEL:
3212 case ISD::LIFETIME_END:
3213 case ISD::PSEUDO_PROBE:
3214 NodeToMatch->setNodeId(-1); // Mark selected.
3215 return;
3216 case ISD::AssertSext:
3217 case ISD::AssertZext:
3218 case ISD::AssertAlign:
3219 ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
3220 CurDAG->RemoveDeadNode(NodeToMatch);
3221 return;
3222 case ISD::INLINEASM:
3223 case ISD::INLINEASM_BR:
3224 Select_INLINEASM(NodeToMatch);
3225 return;
3226 case ISD::READ_REGISTER:
3227 Select_READ_REGISTER(NodeToMatch);
3228 return;
3230 Select_WRITE_REGISTER(NodeToMatch);
3231 return;
3232 case ISD::UNDEF:
3233 Select_UNDEF(NodeToMatch);
3234 return;
3235 case ISD::FREEZE:
3236 Select_FREEZE(NodeToMatch);
3237 return;
3238 case ISD::ARITH_FENCE:
3239 Select_ARITH_FENCE(NodeToMatch);
3240 return;
3241 case ISD::MEMBARRIER:
3242 Select_MEMBARRIER(NodeToMatch);
3243 return;
3244 case ISD::STACKMAP:
3245 Select_STACKMAP(NodeToMatch);
3246 return;
3247 case ISD::PATCHPOINT:
3248 Select_PATCHPOINT(NodeToMatch);
3249 return;
3251 Select_JUMP_TABLE_DEBUG_INFO(NodeToMatch);
3252 return;
3254 Select_CONVERGENCECTRL_ANCHOR(NodeToMatch);
3255 return;
3257 Select_CONVERGENCECTRL_ENTRY(NodeToMatch);
3258 return;
3260 Select_CONVERGENCECTRL_LOOP(NodeToMatch);
3261 return;
3262 }
3263
3264 assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
3265
3266 // Set up the node stack with NodeToMatch as the only node on the stack.
3267 SmallVector<SDValue, 8> NodeStack;
3268 SDValue N = SDValue(NodeToMatch, 0);
3269 NodeStack.push_back(N);
3270
3271 // MatchScopes - Scopes used when matching, if a match failure happens, this
3272 // indicates where to continue checking.
3273 SmallVector<MatchScope, 8> MatchScopes;
3274
3275 // RecordedNodes - This is the set of nodes that have been recorded by the
3276 // state machine. The second value is the parent of the node, or null if the
3277 // root is recorded.
3279
3280 // MatchedMemRefs - This is the set of MemRef's we've seen in the input
3281 // pattern.
3283
3284 // These are the current input chain and glue for use when generating nodes.
3285 // Various Emit operations change these. For example, emitting a copytoreg
3286 // uses and updates these.
3287 SDValue InputChain, InputGlue;
3288
3289 // ChainNodesMatched - If a pattern matches nodes that have input/output
3290 // chains, the OPC_EmitMergeInputChains operation is emitted which indicates
3291 // which ones they are. The result is captured into this list so that we can
3292 // update the chain results when the pattern is complete.
3293 SmallVector<SDNode*, 3> ChainNodesMatched;
3294
3295 LLVM_DEBUG(dbgs() << "ISEL: Starting pattern match\n");
3296
3297 // Determine where to start the interpreter. Normally we start at opcode #0,
3298 // but if the state machine starts with an OPC_SwitchOpcode, then we
3299 // accelerate the first lookup (which is guaranteed to be hot) with the
3300 // OpcodeOffset table.
3301 unsigned MatcherIndex = 0;
3302
3303 if (!OpcodeOffset.empty()) {
3304 // Already computed the OpcodeOffset table, just index into it.
3305 if (N.getOpcode() < OpcodeOffset.size())
3306 MatcherIndex = OpcodeOffset[N.getOpcode()];
3307 LLVM_DEBUG(dbgs() << " Initial Opcode index to " << MatcherIndex << "\n");
3308
3309 } else if (MatcherTable[0] == OPC_SwitchOpcode) {
3310 // Otherwise, the table isn't computed, but the state machine does start
3311 // with an OPC_SwitchOpcode instruction. Populate the table now, since this
3312 // is the first time we're selecting an instruction.
3313 unsigned Idx = 1;
3314 while (true) {
3315 // Get the size of this case.
3316 unsigned CaseSize = MatcherTable[Idx++];
3317 if (CaseSize & 128)
3318 CaseSize = GetVBR(CaseSize, MatcherTable, Idx);
3319 if (CaseSize == 0) break;
3320
3321 // Get the opcode, add the index to the table.
3322 uint16_t Opc = MatcherTable[Idx++];
3323 Opc |= static_cast<uint16_t>(MatcherTable[Idx++]) << 8;
3324 if (Opc >= OpcodeOffset.size())
3325 OpcodeOffset.resize((Opc+1)*2);
3326 OpcodeOffset[Opc] = Idx;
3327 Idx += CaseSize;
3328 }
3329
3330 // Okay, do the lookup for the first opcode.
3331 if (N.getOpcode() < OpcodeOffset.size())
3332 MatcherIndex = OpcodeOffset[N.getOpcode()];
3333 }
3334
3335 while (true) {
3336 assert(MatcherIndex < TableSize && "Invalid index");
3337#ifndef NDEBUG
3338 unsigned CurrentOpcodeIndex = MatcherIndex;
3339#endif
3340 BuiltinOpcodes Opcode =
3341 static_cast<BuiltinOpcodes>(MatcherTable[MatcherIndex++]);
3342 switch (Opcode) {
3343 case OPC_Scope: {
3344 // Okay, the semantics of this operation are that we should push a scope
3345 // then evaluate the first child. However, pushing a scope only to have
3346 // the first check fail (which then pops it) is inefficient. If we can
3347 // determine immediately that the first check (or first several) will
3348 // immediately fail, don't even bother pushing a scope for them.
3349 unsigned FailIndex;
3350
3351 while (true) {
3352 unsigned NumToSkip = MatcherTable[MatcherIndex++];
3353 if (NumToSkip & 128)
3354 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
3355 // Found the end of the scope with no match.
3356 if (NumToSkip == 0) {
3357 FailIndex = 0;
3358 break;
3359 }
3360
3361 FailIndex = MatcherIndex+NumToSkip;
3362
3363 unsigned MatcherIndexOfPredicate = MatcherIndex;
3364 (void)MatcherIndexOfPredicate; // silence warning.
3365
3366 // If we can't evaluate this predicate without pushing a scope (e.g. if
3367 // it is a 'MoveParent') or if the predicate succeeds on this node, we
3368 // push the scope and evaluate the full predicate chain.
3369 bool Result;
3370 MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,
3371 Result, *this, RecordedNodes);
3372 if (!Result)
3373 break;
3374
3375 LLVM_DEBUG(
3376 dbgs() << " Skipped scope entry (due to false predicate) at "
3377 << "index " << MatcherIndexOfPredicate << ", continuing at "
3378 << FailIndex << "\n");
3379 ++NumDAGIselRetries;
3380
3381 // Otherwise, we know that this case of the Scope is guaranteed to fail,
3382 // move to the next case.
3383 MatcherIndex = FailIndex;
3384 }
3385
3386 // If the whole scope failed to match, bail.
3387 if (FailIndex == 0) break;
3388
3389 // Push a MatchScope which indicates where to go if the first child fails
3390 // to match.
3391 MatchScope NewEntry;
3392 NewEntry.FailIndex = FailIndex;
3393 NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
3394 NewEntry.NumRecordedNodes = RecordedNodes.size();
3395 NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
3396 NewEntry.InputChain = InputChain;
3397 NewEntry.InputGlue = InputGlue;
3398 NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
3399 MatchScopes.push_back(NewEntry);
3400 continue;
3401 }
3402 case OPC_RecordNode: {
3403 // Remember this node, it may end up being an operand in the pattern.
3404 SDNode *Parent = nullptr;
3405 if (NodeStack.size() > 1)
3406 Parent = NodeStack[NodeStack.size()-2].getNode();
3407 RecordedNodes.push_back(std::make_pair(N, Parent));
3408 continue;
3409 }
3410
3415 unsigned ChildNo = Opcode-OPC_RecordChild0;
3416 if (ChildNo >= N.getNumOperands())
3417 break; // Match fails if out of range child #.
3418
3419 RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo),
3420 N.getNode()));
3421 continue;
3422 }
3423 case OPC_RecordMemRef:
3424 if (auto *MN = dyn_cast<MemSDNode>(N))
3425 MatchedMemRefs.push_back(MN->getMemOperand());
3426 else {
3427 LLVM_DEBUG(dbgs() << "Expected MemSDNode "; N->dump(CurDAG);
3428 dbgs() << '\n');
3429 }
3430
3431 continue;
3432
3434 // If the current node has an input glue, capture it in InputGlue.
3435 if (N->getNumOperands() != 0 &&
3436 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue)
3437 InputGlue = N->getOperand(N->getNumOperands()-1);
3438 continue;
3439
3440 case OPC_MoveChild: {
3441 unsigned ChildNo = MatcherTable[MatcherIndex++];
3442 if (ChildNo >= N.getNumOperands())
3443 break; // Match fails if out of range child #.
3444 N = N.getOperand(ChildNo);
3445 NodeStack.push_back(N);
3446 continue;
3447 }
3448
3449 case OPC_MoveChild0: case OPC_MoveChild1:
3450 case OPC_MoveChild2: case OPC_MoveChild3:
3451 case OPC_MoveChild4: case OPC_MoveChild5:
3452 case OPC_MoveChild6: case OPC_MoveChild7: {
3453 unsigned ChildNo = Opcode-OPC_MoveChild0;
3454 if (ChildNo >= N.getNumOperands())
3455 break; // Match fails if out of range child #.
3456 N = N.getOperand(ChildNo);
3457 NodeStack.push_back(N);
3458 continue;
3459 }
3460
3461 case OPC_MoveSibling:
3462 case OPC_MoveSibling0:
3463 case OPC_MoveSibling1:
3464 case OPC_MoveSibling2:
3465 case OPC_MoveSibling3:
3466 case OPC_MoveSibling4:
3467 case OPC_MoveSibling5:
3468 case OPC_MoveSibling6:
3469 case OPC_MoveSibling7: {
3470 // Pop the current node off the NodeStack.
3471 NodeStack.pop_back();
3472 assert(!NodeStack.empty() && "Node stack imbalance!");
3473 N = NodeStack.back();
3474
3475 unsigned SiblingNo = Opcode == OPC_MoveSibling
3476 ? MatcherTable[MatcherIndex++]
3477 : Opcode - OPC_MoveSibling0;
3478 if (SiblingNo >= N.getNumOperands())
3479 break; // Match fails if out of range sibling #.
3480 N = N.getOperand(SiblingNo);
3481 NodeStack.push_back(N);
3482 continue;
3483 }
3484 case OPC_MoveParent:
3485 // Pop the current node off the NodeStack.
3486 NodeStack.pop_back();
3487 assert(!NodeStack.empty() && "Node stack imbalance!");
3488 N = NodeStack.back();
3489 continue;
3490
3491 case OPC_CheckSame:
3492 if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break;
3493 continue;
3494
3497 if (!::CheckChildSame(MatcherTable, MatcherIndex, N, RecordedNodes,
3498 Opcode-OPC_CheckChild0Same))
3499 break;
3500 continue;
3501
3512 if (!::CheckPatternPredicate(Opcode, MatcherTable, MatcherIndex, *this))
3513 break;
3514 continue;
3523 case OPC_CheckPredicate:
3524 if (!::CheckNodePredicate(Opcode, MatcherTable, MatcherIndex, *this,
3525 N.getNode()))
3526 break;
3527 continue;
3529 unsigned OpNum = MatcherTable[MatcherIndex++];
3531
3532 for (unsigned i = 0; i < OpNum; ++i)
3533 Operands.push_back(RecordedNodes[MatcherTable[MatcherIndex++]].first);
3534
3535 unsigned PredNo = MatcherTable[MatcherIndex++];
3536 if (!CheckNodePredicateWithOperands(N.getNode(), PredNo, Operands))
3537 break;
3538 continue;
3539 }
3548 case OPC_CheckComplexPat7: {
3549 unsigned CPNum = Opcode == OPC_CheckComplexPat
3550 ? MatcherTable[MatcherIndex++]
3551 : Opcode - OPC_CheckComplexPat0;
3552 unsigned RecNo = MatcherTable[MatcherIndex++];
3553 assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat");
3554
3555 // If target can modify DAG during matching, keep the matching state
3556 // consistent.
3557 std::unique_ptr<MatchStateUpdater> MSU;
3559 MSU.reset(new MatchStateUpdater(*CurDAG, &NodeToMatch, RecordedNodes,
3560 MatchScopes));
3561
3562 if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second,
3563 RecordedNodes[RecNo].first, CPNum,
3564 RecordedNodes))
3565 break;
3566 continue;
3567 }
3568 case OPC_CheckOpcode:
3569 if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break;
3570 continue;
3571
3572 case OPC_CheckType:
3573 case OPC_CheckTypeI32:
3574 case OPC_CheckTypeI64:
3576 switch (Opcode) {
3577 case OPC_CheckTypeI32:
3578 VT = MVT::i32;
3579 break;
3580 case OPC_CheckTypeI64:
3581 VT = MVT::i64;
3582 break;
3583 default:
3584 VT = static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
3585 break;
3586 }
3587 if (!::CheckType(VT, N, TLI, CurDAG->getDataLayout()))
3588 break;
3589 continue;
3590
3591 case OPC_CheckTypeRes: {
3592 unsigned Res = MatcherTable[MatcherIndex++];
3593 if (!::CheckType(
3594 static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]),
3595 N.getValue(Res), TLI, CurDAG->getDataLayout()))
3596 break;
3597 continue;
3598 }
3599
3600 case OPC_SwitchOpcode: {
3601 unsigned CurNodeOpcode = N.getOpcode();
3602 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3603 unsigned CaseSize;
3604 while (true) {
3605 // Get the size of this case.
3606 CaseSize = MatcherTable[MatcherIndex++];
3607 if (CaseSize & 128)
3608 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3609 if (CaseSize == 0) break;
3610
3611 uint16_t Opc = MatcherTable[MatcherIndex++];
3612 Opc |= static_cast<uint16_t>(MatcherTable[MatcherIndex++]) << 8;
3613
3614 // If the opcode matches, then we will execute this case.
3615 if (CurNodeOpcode == Opc)
3616 break;
3617
3618 // Otherwise, skip over this case.
3619 MatcherIndex += CaseSize;
3620 }
3621
3622 // If no cases matched, bail out.
3623 if (CaseSize == 0) break;
3624
3625 // Otherwise, execute the case we found.
3626 LLVM_DEBUG(dbgs() << " OpcodeSwitch from " << SwitchStart << " to "
3627 << MatcherIndex << "\n");
3628 continue;
3629 }
3630
3631 case OPC_SwitchType: {
3632 MVT CurNodeVT = N.getSimpleValueType();
3633 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3634 unsigned CaseSize;
3635 while (true) {
3636 // Get the size of this case.
3637 CaseSize = MatcherTable[MatcherIndex++];
3638 if (CaseSize & 128)
3639 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3640 if (CaseSize == 0) break;
3641
3642 MVT CaseVT =
3643 static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
3644 if (CaseVT == MVT::iPTR)
3645 CaseVT = TLI->getPointerTy(CurDAG->getDataLayout());
3646
3647 // If the VT matches, then we will execute this case.
3648 if (CurNodeVT == CaseVT)
3649 break;
3650
3651 // Otherwise, skip over this case.
3652 MatcherIndex += CaseSize;
3653 }
3654
3655 // If no cases matched, bail out.
3656 if (CaseSize == 0) break;
3657
3658 // Otherwise, execute the case we found.
3659 LLVM_DEBUG(dbgs() << " TypeSwitch[" << CurNodeVT
3660 << "] from " << SwitchStart << " to " << MatcherIndex
3661 << '\n');
3662 continue;
3663 }
3689 unsigned ChildNo;
3692 VT = MVT::i32;
3694 } else if (Opcode >= SelectionDAGISel::OPC_CheckChild0TypeI64 &&
3696 VT = MVT::i64;
3698 } else {
3699 VT = static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
3700 ChildNo = Opcode - SelectionDAGISel::OPC_CheckChild0Type;
3701 }
3702 if (!::CheckChildType(VT, N, TLI, CurDAG->getDataLayout(), ChildNo))
3703 break;
3704 continue;
3705 }
3706 case OPC_CheckCondCode:
3707 if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break;
3708 continue;
3710 if (!::CheckChild2CondCode(MatcherTable, MatcherIndex, N)) break;
3711 continue;
3712 case OPC_CheckValueType:
3713 if (!::CheckValueType(MatcherTable, MatcherIndex, N, TLI,
3715 break;
3716 continue;
3717 case OPC_CheckInteger:
3718 if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break;
3719 continue;
3723 if (!::CheckChildInteger(MatcherTable, MatcherIndex, N,
3724 Opcode-OPC_CheckChild0Integer)) break;
3725 continue;
3726 case OPC_CheckAndImm:
3727 if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break;
3728 continue;
3729 case OPC_CheckOrImm:
3730 if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break;
3731 continue;
3733 if (!ISD::isConstantSplatVectorAllOnes(N.getNode()))
3734 break;
3735 continue;
3737 if (!ISD::isConstantSplatVectorAllZeros(N.getNode()))
3738 break;
3739 continue;
3740
3742 assert(NodeStack.size() != 1 && "No parent node");
3743 // Verify that all intermediate nodes between the root and this one have
3744 // a single use (ignoring chains, which are handled in UpdateChains).
3745 bool HasMultipleUses = false;
3746 for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i) {
3747 unsigned NNonChainUses = 0;
3748 SDNode *NS = NodeStack[i].getNode();
3749 for (auto UI = NS->use_begin(), UE = NS->use_end(); UI != UE; ++UI)
3750 if (UI.getUse().getValueType() != MVT::Other)
3751 if (++NNonChainUses > 1) {
3752 HasMultipleUses = true;
3753 break;
3754 }
3755 if (HasMultipleUses) break;
3756 }
3757 if (HasMultipleUses) break;
3758
3759 // Check to see that the target thinks this is profitable to fold and that
3760 // we can fold it without inducing cycles in the graph.
3761 if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3762 NodeToMatch) ||
3763 !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3764 NodeToMatch, OptLevel,
3765 true/*We validate our own chains*/))
3766 break;
3767
3768 continue;
3769 }
3770 case OPC_EmitInteger:
3771 case OPC_EmitInteger8:
3772 case OPC_EmitInteger16:
3773 case OPC_EmitInteger32:
3774 case OPC_EmitInteger64:
3778 switch (Opcode) {
3779 case OPC_EmitInteger8:
3780 VT = MVT::i8;
3781 break;
3782 case OPC_EmitInteger16:
3783 VT = MVT::i16;
3784 break;
3785 case OPC_EmitInteger32:
3787 VT = MVT::i32;
3788 break;
3789 case OPC_EmitInteger64:
3790 VT = MVT::i64;
3791 break;
3792 default:
3793 VT = static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
3794 break;
3795 }
3796 int64_t Val = MatcherTable[MatcherIndex++];
3797 if (Val & 128)
3798 Val = GetVBR(Val, MatcherTable, MatcherIndex);
3799 if (Opcode >= OPC_EmitInteger && Opcode <= OPC_EmitInteger64)
3800 Val = decodeSignRotatedValue(Val);
3801 RecordedNodes.push_back(std::pair<SDValue, SDNode *>(
3802 CurDAG->getTargetConstant(Val, SDLoc(NodeToMatch), VT), nullptr));
3803 continue;
3804 }
3805 case OPC_EmitRegister:
3807 case OPC_EmitRegisterI64: {
3809 switch (Opcode) {
3811 VT = MVT::i32;
3812 break;
3814 VT = MVT::i64;
3815 break;
3816 default:
3817 VT = static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
3818 break;
3819 }
3820 unsigned RegNo = MatcherTable[MatcherIndex++];
3821 RecordedNodes.push_back(std::pair<SDValue, SDNode *>(
3822 CurDAG->getRegister(RegNo, VT), nullptr));
3823 continue;
3824 }
3825 case OPC_EmitRegister2: {
3826 // For targets w/ more than 256 register names, the register enum
3827 // values are stored in two bytes in the matcher table (just like
3828 // opcodes).
3830 static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
3831 unsigned RegNo = MatcherTable[MatcherIndex++];
3832 RegNo |= MatcherTable[MatcherIndex++] << 8;
3833 RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3834 CurDAG->getRegister(RegNo, VT), nullptr));
3835 continue;
3836 }
3837
3847 // Convert from IMM/FPIMM to target version.
3848 unsigned RecNo = Opcode == OPC_EmitConvertToTarget
3849 ? MatcherTable[MatcherIndex++]
3850 : Opcode - OPC_EmitConvertToTarget0;
3851 assert(RecNo < RecordedNodes.size() && "Invalid EmitConvertToTarget");
3852 SDValue Imm = RecordedNodes[RecNo].first;
3853
3854 if (Imm->getOpcode() == ISD::Constant) {
3855 const ConstantInt *Val=cast<ConstantSDNode>(Imm)->getConstantIntValue();
3856 Imm = CurDAG->getTargetConstant(*Val, SDLoc(NodeToMatch),
3857 Imm.getValueType());
3858 } else if (Imm->getOpcode() == ISD::ConstantFP) {
3859 const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
3860 Imm = CurDAG->getTargetConstantFP(*Val, SDLoc(NodeToMatch),
3861 Imm.getValueType());
3862 }
3863
3864 RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second));
3865 continue;
3866 }
3867
3868 case OPC_EmitMergeInputChains1_0: // OPC_EmitMergeInputChains, 1, 0
3869 case OPC_EmitMergeInputChains1_1: // OPC_EmitMergeInputChains, 1, 1
3870 case OPC_EmitMergeInputChains1_2: { // OPC_EmitMergeInputChains, 1, 2
3871 // These are space-optimized forms of OPC_EmitMergeInputChains.
3872 assert(!InputChain.getNode() &&
3873 "EmitMergeInputChains should be the first chain producing node");
3874 assert(ChainNodesMatched.empty() &&
3875 "Should only have one EmitMergeInputChains per match");
3876
3877 // Read all of the chained nodes.
3878 unsigned RecNo = Opcode - OPC_EmitMergeInputChains1_0;
3879 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3880 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3881
3882 // If the chained node is not the root, we can't fold it if it has
3883 // multiple uses.
3884 // FIXME: What if other value results of the node have uses not matched
3885 // by this pattern?
3886 if (ChainNodesMatched.back() != NodeToMatch &&
3887 !RecordedNodes[RecNo].first.hasOneUse()) {
3888 ChainNodesMatched.clear();
3889 break;
3890 }
3891
3892 // Merge the input chains if they are not intra-pattern references.
3893 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3894
3895 if (!InputChain.getNode())
3896 break; // Failed to merge.
3897 continue;
3898 }
3899
3901 assert(!InputChain.getNode() &&
3902 "EmitMergeInputChains should be the first chain producing node");
3903 // This node gets a list of nodes we matched in the input that have
3904 // chains. We want to token factor all of the input chains to these nodes
3905 // together. However, if any of the input chains is actually one of the
3906 // nodes matched in this pattern, then we have an intra-match reference.
3907 // Ignore these because the newly token factored chain should not refer to
3908 // the old nodes.
3909 unsigned NumChains = MatcherTable[MatcherIndex++];
3910 assert(NumChains != 0 && "Can't TF zero chains");
3911
3912 assert(ChainNodesMatched.empty() &&
3913 "Should only have one EmitMergeInputChains per match");
3914
3915 // Read all of the chained nodes.
3916 for (unsigned i = 0; i != NumChains; ++i) {
3917 unsigned RecNo = MatcherTable[MatcherIndex++];
3918 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3919 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3920
3921 // If the chained node is not the root, we can't fold it if it has
3922 // multiple uses.
3923 // FIXME: What if other value results of the node have uses not matched
3924 // by this pattern?
3925 if (ChainNodesMatched.back() != NodeToMatch &&
3926 !RecordedNodes[RecNo].first.hasOneUse()) {
3927 ChainNodesMatched.clear();
3928 break;
3929 }
3930 }
3931
3932 // If the inner loop broke out, the match fails.
3933 if (ChainNodesMatched.empty())
3934 break;
3935
3936 // Merge the input chains if they are not intra-pattern references.
3937 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3938
3939 if (!InputChain.getNode())
3940 break; // Failed to merge.
3941
3942 continue;
3943 }
3944
3945 case OPC_EmitCopyToReg:
3946 case OPC_EmitCopyToReg0:
3947 case OPC_EmitCopyToReg1:
3948 case OPC_EmitCopyToReg2:
3949 case OPC_EmitCopyToReg3:
3950 case OPC_EmitCopyToReg4:
3951 case OPC_EmitCopyToReg5:
3952 case OPC_EmitCopyToReg6:
3953 case OPC_EmitCopyToReg7:
3955 unsigned RecNo =
3956 Opcode >= OPC_EmitCopyToReg0 && Opcode <= OPC_EmitCopyToReg7
3957 ? Opcode - OPC_EmitCopyToReg0
3958 : MatcherTable[MatcherIndex++];
3959 assert(RecNo < RecordedNodes.size() && "Invalid EmitCopyToReg");
3960 unsigned DestPhysReg = MatcherTable[MatcherIndex++];
3961 if (Opcode == OPC_EmitCopyToRegTwoByte)
3962 DestPhysReg |= MatcherTable[MatcherIndex++] << 8;
3963
3964 if (!InputChain.getNode())
3965 InputChain = CurDAG->getEntryNode();
3966
3967 InputChain = CurDAG->getCopyToReg(InputChain, SDLoc(NodeToMatch),
3968 DestPhysReg, RecordedNodes[RecNo].first,
3969 InputGlue);
3970
3971 InputGlue = InputChain.getValue(1);
3972 continue;
3973 }
3974
3975 case OPC_EmitNodeXForm: {
3976 unsigned XFormNo = MatcherTable[MatcherIndex++];
3977 unsigned RecNo = MatcherTable[MatcherIndex++];
3978 assert(RecNo < RecordedNodes.size() && "Invalid EmitNodeXForm");
3979 SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo);
3980 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, nullptr));
3981 continue;
3982 }
3983 case OPC_Coverage: {
3984 // This is emitted right before MorphNode/EmitNode.
3985 // So it should be safe to assume that this node has been selected
3986 unsigned index = MatcherTable[MatcherIndex++];
3987 index |= (MatcherTable[MatcherIndex++] << 8);
3988 dbgs() << "COVERED: " << getPatternForIndex(index) << "\n";
3989 dbgs() << "INCLUDED: " << getIncludePathForIndex(index) << "\n";
3990 continue;
3991 }
3992
3993 case OPC_EmitNode:
3994 case OPC_EmitNode0:
3995 case OPC_EmitNode1:
3996 case OPC_EmitNode2:
3997 case OPC_EmitNode0None:
3998 case OPC_EmitNode1None:
3999 case OPC_EmitNode2None:
4000 case OPC_EmitNode0Chain:
4001 case OPC_EmitNode1Chain:
4002 case OPC_EmitNode2Chain:
4003 case OPC_MorphNodeTo:
4004 case OPC_MorphNodeTo0:
4005 case OPC_MorphNodeTo1:
4006 case OPC_MorphNodeTo2:
4019 uint16_t TargetOpc = MatcherTable[MatcherIndex++];
4020 TargetOpc |= static_cast<uint16_t>(MatcherTable[MatcherIndex++]) << 8;
4021 unsigned EmitNodeInfo;
4022 if (Opcode >= OPC_EmitNode0None && Opcode <= OPC_EmitNode2Chain) {
4023 if (Opcode >= OPC_EmitNode0Chain && Opcode <= OPC_EmitNode2Chain)
4024 EmitNodeInfo = OPFL_Chain;
4025 else
4026 EmitNodeInfo = OPFL_None;
4027 } else if (Opcode >= OPC_MorphNodeTo0None &&
4028 Opcode <= OPC_MorphNodeTo2GlueOutput) {
4029 if (Opcode >= OPC_MorphNodeTo0Chain && Opcode <= OPC_MorphNodeTo2Chain)
4030 EmitNodeInfo = OPFL_Chain;
4031 else if (Opcode >= OPC_MorphNodeTo0GlueInput &&
4032 Opcode <= OPC_MorphNodeTo2GlueInput)
4033 EmitNodeInfo = OPFL_GlueInput;
4034 else if (Opcode >= OPC_MorphNodeTo0GlueOutput &&
4036 EmitNodeInfo = OPFL_GlueOutput;
4037 else
4038 EmitNodeInfo = OPFL_None;
4039 } else
4040 EmitNodeInfo = MatcherTable[MatcherIndex++];
4041 // Get the result VT list.
4042 unsigned NumVTs;
4043 // If this is one of the compressed forms, get the number of VTs based
4044 // on the Opcode. Otherwise read the next byte from the table.
4045 if (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2)
4046 NumVTs = Opcode - OPC_MorphNodeTo0;
4047 else if (Opcode >= OPC_MorphNodeTo0None && Opcode <= OPC_MorphNodeTo2None)
4048 NumVTs = Opcode - OPC_MorphNodeTo0None;
4049 else if (Opcode >= OPC_MorphNodeTo0Chain &&
4050 Opcode <= OPC_MorphNodeTo2Chain)
4051 NumVTs = Opcode - OPC_MorphNodeTo0Chain;
4052 else if (Opcode >= OPC_MorphNodeTo0GlueInput &&
4053 Opcode <= OPC_MorphNodeTo2GlueInput)
4054 NumVTs = Opcode - OPC_MorphNodeTo0GlueInput;
4055 else if (Opcode >= OPC_MorphNodeTo0GlueOutput &&
4057 NumVTs = Opcode - OPC_MorphNodeTo0GlueOutput;
4058 else if (Opcode >= OPC_EmitNode0 && Opcode <= OPC_EmitNode2)
4059 NumVTs = Opcode - OPC_EmitNode0;
4060 else if (Opcode >= OPC_EmitNode0None && Opcode <= OPC_EmitNode2None)
4061 NumVTs = Opcode - OPC_EmitNode0None;
4062 else if (Opcode >= OPC_EmitNode0Chain && Opcode <= OPC_EmitNode2Chain)
4063 NumVTs = Opcode - OPC_EmitNode0Chain;
4064 else
4065 NumVTs = MatcherTable[MatcherIndex++];
4067 for (unsigned i = 0; i != NumVTs; ++i) {
4069 static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
4070 if (VT == MVT::iPTR)
4071 VT = TLI->getPointerTy(CurDAG->getDataLayout()).SimpleTy;
4072 VTs.push_back(VT);
4073 }
4074
4075 if (EmitNodeInfo & OPFL_Chain)
4076 VTs.push_back(MVT::Other);
4077 if (EmitNodeInfo & OPFL_GlueOutput)
4078 VTs.push_back(MVT::Glue);
4079
4080 // This is hot code, so optimize the two most common cases of 1 and 2
4081 // results.
4082 SDVTList VTList;
4083 if (VTs.size() == 1)
4084 VTList = CurDAG->getVTList(VTs[0]);
4085 else if (VTs.size() == 2)
4086 VTList = CurDAG->getVTList(VTs[0], VTs[1]);
4087 else
4088 VTList = CurDAG->getVTList(VTs);
4089
4090 // Get the operand list.
4091 unsigned NumOps = MatcherTable[MatcherIndex++];
4093 for (unsigned i = 0; i != NumOps; ++i) {
4094 unsigned RecNo = MatcherTable[MatcherIndex++];
4095 if (RecNo & 128)
4096 RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
4097
4098 assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");
4099 Ops.push_back(RecordedNodes[RecNo].first);
4100 }
4101
4102 // If there are variadic operands to add, handle them now.
4103 if (EmitNodeInfo & OPFL_VariadicInfo) {
4104 // Determine the start index to copy from.
4105 unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
4106 FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
4107 assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
4108 "Invalid variadic node");
4109 // Copy all of the variadic operands, not including a potential glue
4110 // input.
4111 for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
4112 i != e; ++i) {
4113 SDValue V = NodeToMatch->getOperand(i);
4114 if (V.getValueType() == MVT::Glue) break;
4115 Ops.push_back(V);
4116 }
4117 }
4118
4119 // If this has chain/glue inputs, add them.
4120 if (EmitNodeInfo & OPFL_Chain)
4121 Ops.push_back(InputChain);
4122 if ((EmitNodeInfo & OPFL_GlueInput) && InputGlue.getNode() != nullptr)
4123 Ops.push_back(InputGlue);
4124
4125 // Check whether any matched node could raise an FP exception. Since all
4126 // such nodes must have a chain, it suffices to check ChainNodesMatched.
4127 // We need to perform this check before potentially modifying one of the
4128 // nodes via MorphNode.
4129 bool MayRaiseFPException =
4130 llvm::any_of(ChainNodesMatched, [this](SDNode *N) {
4131 return mayRaiseFPException(N) && !N->getFlags().hasNoFPExcept();
4132 });
4133
4134 // Create the node.
4135 MachineSDNode *Res = nullptr;
4136 bool IsMorphNodeTo =
4137 Opcode == OPC_MorphNodeTo ||
4138 (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2GlueOutput);
4139 if (!IsMorphNodeTo) {
4140 // If this is a normal EmitNode command, just create the new node and
4141 // add the results to the RecordedNodes list.
4142 Res = CurDAG->getMachineNode(TargetOpc, SDLoc(NodeToMatch),
4143 VTList, Ops);
4144
4145 // Add all the non-glue/non-chain results to the RecordedNodes list.
4146 for (unsigned i = 0, e = VTs.size(); i != e; ++i) {
4147 if (VTs[i] == MVT::Other || VTs[i] == MVT::Glue) break;
4148 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i),
4149 nullptr));
4150 }
4151 } else {
4152 assert(NodeToMatch->getOpcode() != ISD::DELETED_NODE &&
4153 "NodeToMatch was removed partway through selection");
4155 SDNode *E) {
4157 auto &Chain = ChainNodesMatched;
4158 assert((!E || !is_contained(Chain, N)) &&
4159 "Chain node replaced during MorphNode");
4160 llvm::erase(Chain, N);
4161 });
4162 Res = cast<MachineSDNode>(MorphNode(NodeToMatch, TargetOpc, VTList,
4163 Ops, EmitNodeInfo));
4164 }
4165
4166 // Set the NoFPExcept flag when no original matched node could
4167 // raise an FP exception, but the new node potentially might.
4168 if (!MayRaiseFPException && mayRaiseFPException(Res)) {
4169 SDNodeFlags Flags = Res->getFlags();
4170 Flags.setNoFPExcept(true);
4171 Res->setFlags(Flags);
4172 }
4173
4174 // If the node had chain/glue results, update our notion of the current
4175 // chain and glue.
4176 if (EmitNodeInfo & OPFL_GlueOutput) {
4177 InputGlue = SDValue(Res, VTs.size()-1);
4178 if (EmitNodeInfo & OPFL_Chain)
4179 InputChain = SDValue(Res, VTs.size()-2);
4180 } else if (EmitNodeInfo & OPFL_Chain)
4181 InputChain = SDValue(Res, VTs.size()-1);
4182
4183 // If the OPFL_MemRefs glue is set on this node, slap all of the
4184 // accumulated memrefs onto it.
4185 //
4186 // FIXME: This is vastly incorrect for patterns with multiple outputs
4187 // instructions that access memory and for ComplexPatterns that match
4188 // loads.
4189 if (EmitNodeInfo & OPFL_MemRefs) {
4190 // Only attach load or store memory operands if the generated
4191 // instruction may load or store.
4192 const MCInstrDesc &MCID = TII->get(TargetOpc);
4193 bool mayLoad = MCID.mayLoad();
4194 bool mayStore = MCID.mayStore();
4195
4196 // We expect to have relatively few of these so just filter them into a
4197 // temporary buffer so that we can easily add them to the instruction.
4199 for (MachineMemOperand *MMO : MatchedMemRefs) {
4200 if (MMO->isLoad()) {
4201 if (mayLoad)
4202 FilteredMemRefs.push_back(MMO);
4203 } else if (MMO->isStore()) {
4204 if (mayStore)
4205 FilteredMemRefs.push_back(MMO);
4206 } else {
4207 FilteredMemRefs.push_back(MMO);
4208 }
4209 }
4210
4211 CurDAG->setNodeMemRefs(Res, FilteredMemRefs);
4212 }
4213
4214 LLVM_DEBUG(if (!MatchedMemRefs.empty() && Res->memoperands_empty()) dbgs()
4215 << " Dropping mem operands\n";
4216 dbgs() << " " << (IsMorphNodeTo ? "Morphed" : "Created")
4217 << " node: ";
4218 Res->dump(CurDAG););
4219
4220 // If this was a MorphNodeTo then we're completely done!
4221 if (IsMorphNodeTo) {
4222 // Update chain uses.
4223 UpdateChains(Res, InputChain, ChainNodesMatched, true);
4224 return;
4225 }
4226 continue;
4227 }
4228
4229 case OPC_CompleteMatch: {
4230 // The match has been completed, and any new nodes (if any) have been
4231 // created. Patch up references to the matched dag to use the newly
4232 // created nodes.
4233 unsigned NumResults = MatcherTable[MatcherIndex++];
4234
4235 for (unsigned i = 0; i != NumResults; ++i) {
4236 unsigned ResSlot = MatcherTable[MatcherIndex++];
4237 if (ResSlot & 128)
4238 ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);
4239
4240 assert(ResSlot < RecordedNodes.size() && "Invalid CompleteMatch");
4241 SDValue Res = RecordedNodes[ResSlot].first;
4242
4243 assert(i < NodeToMatch->getNumValues() &&
4244 NodeToMatch->getValueType(i) != MVT::Other &&
4245 NodeToMatch->getValueType(i) != MVT::Glue &&
4246 "Invalid number of results to complete!");
4247 assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
4248 NodeToMatch->getValueType(i) == MVT::iPTR ||
4249 Res.getValueType() == MVT::iPTR ||
4250 NodeToMatch->getValueType(i).getSizeInBits() ==
4251 Res.getValueSizeInBits()) &&
4252 "invalid replacement");
4253 ReplaceUses(SDValue(NodeToMatch, i), Res);
4254 }
4255
4256 // Update chain uses.
4257 UpdateChains(NodeToMatch, InputChain, ChainNodesMatched, false);
4258
4259 // If the root node defines glue, we need to update it to the glue result.
4260 // TODO: This never happens in our tests and I think it can be removed /
4261 // replaced with an assert, but if we do it this the way the change is
4262 // NFC.
4263 if (NodeToMatch->getValueType(NodeToMatch->getNumValues() - 1) ==
4264 MVT::Glue &&
4265 InputGlue.getNode())
4266 ReplaceUses(SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1),
4267 InputGlue);
4268
4269 assert(NodeToMatch->use_empty() &&
4270 "Didn't replace all uses of the node?");
4271 CurDAG->RemoveDeadNode(NodeToMatch);
4272
4273 return;
4274 }
4275 }
4276
4277 // If the code reached this point, then the match failed. See if there is
4278 // another child to try in the current 'Scope', otherwise pop it until we
4279 // find a case to check.
4280 LLVM_DEBUG(dbgs() << " Match failed at index " << CurrentOpcodeIndex
4281 << "\n");
4282 ++NumDAGIselRetries;
4283 while (true) {
4284 if (MatchScopes.empty()) {
4285 CannotYetSelect(NodeToMatch);
4286 return;
4287 }
4288
4289 // Restore the interpreter state back to the point where the scope was
4290 // formed.
4291 MatchScope &LastScope = MatchScopes.back();
4292 RecordedNodes.resize(LastScope.NumRecordedNodes);
4293 NodeStack.clear();
4294 NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());
4295 N = NodeStack.back();
4296
4297 if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
4298 MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
4299 MatcherIndex = LastScope.FailIndex;
4300
4301 LLVM_DEBUG(dbgs() << " Continuing at " << MatcherIndex << "\n");
4302
4303 InputChain = LastScope.InputChain;
4304 InputGlue = LastScope.InputGlue;
4305 if (!LastScope.HasChainNodesMatched)
4306 ChainNodesMatched.clear();
4307
4308 // Check to see what the offset is at the new MatcherIndex. If it is zero
4309 // we have reached the end of this scope, otherwise we have another child
4310 // in the current scope to try.
4311 unsigned NumToSkip = MatcherTable[MatcherIndex++];
4312 if (NumToSkip & 128)
4313 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
4314
4315 // If we have another child in this scope to match, update FailIndex and
4316 // try it.
4317 if (NumToSkip != 0) {
4318 LastScope.FailIndex = MatcherIndex+NumToSkip;
4319 break;
4320 }
4321
4322 // End of this scope, pop it and try the next child in the containing
4323 // scope.
4324 MatchScopes.pop_back();
4325 }
4326 }
4327}
4328
4329/// Return whether the node may raise an FP exception.
4331 // For machine opcodes, consult the MCID flag.
4332 if (N->isMachineOpcode()) {
4333 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
4334 return MCID.mayRaiseFPException();
4335 }
4336
4337 // For ISD opcodes, only StrictFP opcodes may raise an FP
4338 // exception.
4339 if (N->isTargetOpcode())
4340 return N->isTargetStrictFPOpcode();
4341 return N->isStrictFPOpcode();
4342}
4343
4345 assert(N->getOpcode() == ISD::OR && "Unexpected opcode");
4346 auto *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
4347 if (!C)
4348 return false;
4349
4350 // Detect when "or" is used to add an offset to a stack object.
4351 if (auto *FN = dyn_cast<FrameIndexSDNode>(N->getOperand(0))) {
4353 Align A = MFI.getObjectAlign(FN->getIndex());
4354 int32_t Off = C->getSExtValue();
4355 // If the alleged offset fits in the zero bits guaranteed by
4356 // the alignment, then this or is really an add.
4357 return (Off >= 0) && (((A.value() - 1) & Off) == unsigned(Off));
4358 }
4359 return false;
4360}
4361
4362void SelectionDAGISel::CannotYetSelect(SDNode *N) {
4363 std::string msg;
4364 raw_string_ostream Msg(msg);
4365 Msg << "Cannot select: ";
4366
4367 if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&
4368 N->getOpcode() != ISD::INTRINSIC_WO_CHAIN &&
4369 N->getOpcode() != ISD::INTRINSIC_VOID) {
4370 N->printrFull(Msg, CurDAG);
4371 Msg << "\nIn function: " << MF->getName();
4372 } else {
4373 bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other;
4374 unsigned iid = N->getConstantOperandVal(HasInputChain);
4375 if (iid < Intrinsic::num_intrinsics)
4376 Msg << "intrinsic %" << Intrinsic::getBaseName((Intrinsic::ID)iid);
4377 else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo())
4378 Msg << "target intrinsic %" << TII->getName(iid);
4379 else
4380 Msg << "unknown intrinsic #" << iid;
4381 }
4382 report_fatal_error(Twine(Msg.str()));
4383}
unsigned const MachineRegisterInfo * MRI
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineInstrBuilder & UseMI
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
MachineBasicBlock MachineBasicBlock::iterator MBBI
amdgpu AMDGPU Register Bank Select
Rewrite undef for PHI
This file implements a class to represent arbitrary precision integral constant values and operations...
Expand Atomic instructions
BlockVerifier::State From
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_ATTRIBUTE_ALWAYS_INLINE
LLVM_ATTRIBUTE_ALWAYS_INLINE - On compilers where we have a directive to do so, mark a method "always...
Definition: Compiler.h:261
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
bool End
Definition: ELF_riscv.cpp:480
This file defines the FastISel class.
IRTranslator LLVM IR MI
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
mir Rename Register Operands
Machine Instruction Scheduler
unsigned const TargetRegisterInfo * TRI
This file contains the declarations for metadata subclasses.
uint64_t IntrinsicInst * II
#define P(N)
FunctionAnalysisManager FAM
const char LLVMTargetMachineRef TM
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const TargetLowering *TLI, const DataLayout &DL)
static cl::opt< bool > ViewSUnitDAGs("view-sunit-dags", cl::Hidden, cl::desc("Pop up a window to show SUnit dags after they are processed"))
static cl::opt< bool > ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden, cl::desc("Pop up a window to show dags before the post " "legalize types dag combine pass"))
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckPatternPredicate(unsigned Opcode, const unsigned char *MatcherTable, unsigned &MatcherIndex, const SelectionDAGISel &SDISel)
CheckPatternPredicate - Implements OP_CheckPatternPredicate.
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckChildSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const SmallVectorImpl< std::pair< SDValue, SDNode * > > &RecordedNodes, unsigned ChildNo)
CheckChildSame - Implements OP_CheckChildXSame.
static uint64_t decodeSignRotatedValue(uint64_t V)
Decode a signed value stored with the sign bit in the LSB for dense VBR encoding.
static cl::opt< bool > ViewISelDAGs("view-isel-dags", cl::Hidden, cl::desc("Pop up a window to show isel dags as they are selected"))
static LLVM_ATTRIBUTE_ALWAYS_INLINE uint64_t GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx)
GetVBR - decode a vbr encoding whose top bit is set.
static void computeUsesMSVCFloatingPoint(const Triple &TT, const Function &F, MachineModuleInfo &MMI)
static void reportFastISelFailure(MachineFunction &MF, OptimizationRemarkEmitter &ORE, OptimizationRemarkMissed &R, bool ShouldAbort)
static cl::opt< bool > ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden, cl::desc("Pop up a window to show dags before the second " "dag combine pass"))
static RegisterScheduler defaultListDAGScheduler("default", "Best scheduler for the target", createDefaultScheduler)
static unsigned IsPredicateKnownToFail(const unsigned char *Table, unsigned Index, SDValue N, bool &Result, const SelectionDAGISel &SDISel, SmallVectorImpl< std::pair< SDValue, SDNode * > > &RecordedNodes)
IsPredicateKnownToFail - If we know how and can do so without pushing a scope, evaluate the current n...
static cl::opt< int > EnableFastISelAbort("fast-isel-abort", cl::Hidden, cl::desc("Enable abort calls when \"fast\" instruction selection " "fails to lower an instruction: 0 disable the abort, 1 will " "abort but for args, calls and terminators, 2 will also " "abort for argument lowering, and 3 will never fallback " "to SelectionDAG."))
static void mapWasmLandingPadIndex(MachineBasicBlock *MBB, const CatchPadInst *CPI)
#define ISEL_DUMP(X)
static void processSingleLocVars(FunctionLoweringInfo &FuncInfo, FunctionVarLocs const *FnVarLocs)
Collect single location variable information generated with assignment tracking.
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N)
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const SelectionDAGISel &SDISel)
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const SelectionDAGISel &SDISel)
static cl::opt< bool > UseMBPI("use-mbpi", cl::desc("use Machine Branch Probability Info"), cl::init(true), cl::Hidden)
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckChildType(MVT::SimpleValueType VT, SDValue N, const TargetLowering *TLI, const DataLayout &DL, unsigned ChildNo)
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const SmallVectorImpl< std::pair< SDValue, SDNode * > > &RecordedNodes)
CheckSame - Implements OP_CheckSame.
static bool dontUseFastISelFor(const Function &Fn)
static bool findNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse, bool IgnoreChains)
findNonImmUse - Return true if "Def" is a predecessor of "Root" via a path beyond "ImmedUse".
static cl::opt< bool > ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden, cl::desc("Pop up a window to show dags before the first " "dag combine pass"))
static bool processIfEntryValueDbgDeclare(FunctionLoweringInfo &FuncInfo, const Value *Arg, DIExpression *Expr, DILocalVariable *Var, DebugLoc DbgLoc)
static cl::opt< bool > ViewSchedDAGs("view-sched-dags", cl::Hidden, cl::desc("Pop up a window to show sched dags as they are processed"))
static void processDbgDeclares(FunctionLoweringInfo &FuncInfo)
Collect llvm.dbg.declare information.
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckType(MVT::SimpleValueType VT, SDValue N, const TargetLowering *TLI, const DataLayout &DL)
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N)
static bool hasExceptionPointerOrCodeUser(const CatchPadInst *CPI)
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckChild2CondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N)
static cl::opt< bool > ViewLegalizeDAGs("view-legalize-dags", cl::Hidden, cl::desc("Pop up a window to show dags before legalize"))
static cl::opt< bool > ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden, cl::desc("Pop up a window to show dags before legalize types"))
static SDNode * findGlueUse(SDNode *N)
findGlueUse - Return use of MVT::Glue value produced by the specified SDNode.