LLVM 20.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"
65#include "llvm/IR/BasicBlock.h"
66#include "llvm/IR/Constants.h"
67#include "llvm/IR/DataLayout.h"
68#include "llvm/IR/DebugInfo.h"
70#include "llvm/IR/DebugLoc.h"
73#include "llvm/IR/Function.h"
74#include "llvm/IR/InlineAsm.h"
76#include "llvm/IR/Instruction.h"
79#include "llvm/IR/Intrinsics.h"
80#include "llvm/IR/IntrinsicsWebAssembly.h"
81#include "llvm/IR/Metadata.h"
82#include "llvm/IR/Module.h"
83#include "llvm/IR/PrintPasses.h"
84#include "llvm/IR/Statepoint.h"
85#include "llvm/IR/Type.h"
86#include "llvm/IR/User.h"
87#include "llvm/IR/Value.h"
89#include "llvm/MC/MCInstrDesc.h"
90#include "llvm/Pass.h"
96#include "llvm/Support/Debug.h"
99#include "llvm/Support/Timer.h"
105#include <algorithm>
106#include <cassert>
107#include <cstdint>
108#include <iterator>
109#include <limits>
110#include <memory>
111#include <optional>
112#include <string>
113#include <utility>
114#include <vector>
115
116using namespace llvm;
117
118#define DEBUG_TYPE "isel"
119#define ISEL_DUMP_DEBUG_TYPE DEBUG_TYPE "-dump"
120
121STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on");
122STATISTIC(NumFastIselSuccess, "Number of instructions fast isel selected");
123STATISTIC(NumFastIselBlocks, "Number of blocks selected entirely by fast isel");
124STATISTIC(NumDAGBlocks, "Number of blocks selected using DAG");
125STATISTIC(NumDAGIselRetries,"Number of times dag isel has to try another path");
126STATISTIC(NumEntryBlocks, "Number of entry blocks encountered");
127STATISTIC(NumFastIselFailLowerArguments,
128 "Number of entry blocks where fast isel failed to lower arguments");
129
131 "fast-isel-abort", cl::Hidden,
132 cl::desc("Enable abort calls when \"fast\" instruction selection "
133 "fails to lower an instruction: 0 disable the abort, 1 will "
134 "abort but for args, calls and terminators, 2 will also "
135 "abort for argument lowering, and 3 will never fallback "
136 "to SelectionDAG."));
137
139 "fast-isel-report-on-fallback", cl::Hidden,
140 cl::desc("Emit a diagnostic when \"fast\" instruction selection "
141 "falls back to SelectionDAG."));
142
143static cl::opt<bool>
144UseMBPI("use-mbpi",
145 cl::desc("use Machine Branch Probability Info"),
146 cl::init(true), cl::Hidden);
147
148#ifndef NDEBUG
151 cl::desc("Only display the basic block whose name "
152 "matches this for all view-*-dags options"));
153static cl::opt<bool>
154ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
155 cl::desc("Pop up a window to show dags before the first "
156 "dag combine pass"));
157static cl::opt<bool>
158ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden,
159 cl::desc("Pop up a window to show dags before legalize types"));
160static cl::opt<bool>
161 ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden,
162 cl::desc("Pop up a window to show dags before the post "
163 "legalize types dag combine pass"));
164static cl::opt<bool>
165 ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
166 cl::desc("Pop up a window to show dags before legalize"));
167static cl::opt<bool>
168ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
169 cl::desc("Pop up a window to show dags before the second "
170 "dag combine pass"));
171static cl::opt<bool>
172ViewISelDAGs("view-isel-dags", cl::Hidden,
173 cl::desc("Pop up a window to show isel dags as they are selected"));
174static cl::opt<bool>
175ViewSchedDAGs("view-sched-dags", cl::Hidden,
176 cl::desc("Pop up a window to show sched dags as they are processed"));
177static cl::opt<bool>
178ViewSUnitDAGs("view-sunit-dags", cl::Hidden,
179 cl::desc("Pop up a window to show SUnit dags after they are processed"));
180#else
181static const bool ViewDAGCombine1 = false, ViewLegalizeTypesDAGs = false,
182 ViewDAGCombineLT = false, ViewLegalizeDAGs = false,
183 ViewDAGCombine2 = false, ViewISelDAGs = false,
184 ViewSchedDAGs = false, ViewSUnitDAGs = false;
185#endif
186
187#ifndef NDEBUG
188#define ISEL_DUMP(X) \
189 do { \
190 if (llvm::DebugFlag && \
191 (isCurrentDebugType(DEBUG_TYPE) || \
192 (isCurrentDebugType(ISEL_DUMP_DEBUG_TYPE) && MatchFilterFuncName))) { \
193 X; \
194 } \
195 } while (false)
196#else
197#define ISEL_DUMP(X) do { } while (false)
198#endif
199
200//===---------------------------------------------------------------------===//
201///
202/// RegisterScheduler class - Track the registration of instruction schedulers.
203///
204//===---------------------------------------------------------------------===//
207
208//===---------------------------------------------------------------------===//
209///
210/// ISHeuristic command line option for instruction schedulers.
211///
212//===---------------------------------------------------------------------===//
215ISHeuristic("pre-RA-sched",
217 cl::desc("Instruction schedulers available (before register"
218 " allocation):"));
219
221defaultListDAGScheduler("default", "Best scheduler for the target",
223
224static bool dontUseFastISelFor(const Function &Fn) {
225 // Don't enable FastISel for functions with swiftasync Arguments.
226 // Debug info on those is reliant on good Argument lowering, and FastISel is
227 // not capable of lowering the entire function. Mixing the two selectors tend
228 // to result in poor lowering of Arguments.
229 return any_of(Fn.args(), [](const Argument &Arg) {
230 return Arg.hasAttribute(Attribute::AttrKind::SwiftAsync);
231 });
232}
233
234namespace llvm {
235
236 //===--------------------------------------------------------------------===//
237 /// This class is used by SelectionDAGISel to temporarily override
238 /// the optimization level on a per-function basis.
241 CodeGenOptLevel SavedOptLevel;
242 bool SavedFastISel;
243
244 public:
246 : IS(ISel) {
247 SavedOptLevel = IS.OptLevel;
248 SavedFastISel = IS.TM.Options.EnableFastISel;
249 if (NewOptLevel != SavedOptLevel) {
250 IS.OptLevel = NewOptLevel;
251 IS.TM.setOptLevel(NewOptLevel);
252 LLVM_DEBUG(dbgs() << "\nChanging optimization level for Function "
253 << IS.MF->getFunction().getName() << "\n");
254 LLVM_DEBUG(dbgs() << "\tBefore: -O" << static_cast<int>(SavedOptLevel)
255 << " ; After: -O" << static_cast<int>(NewOptLevel)
256 << "\n");
257 if (NewOptLevel == CodeGenOptLevel::None)
259 }
261 IS.TM.setFastISel(false);
263 dbgs() << "\tFastISel is "
264 << (IS.TM.Options.EnableFastISel ? "enabled" : "disabled")
265 << "\n");
266 }
267
269 if (IS.OptLevel == SavedOptLevel)
270 return;
271 LLVM_DEBUG(dbgs() << "\nRestoring optimization level for Function "
272 << IS.MF->getFunction().getName() << "\n");
273 LLVM_DEBUG(dbgs() << "\tBefore: -O" << static_cast<int>(IS.OptLevel)
274 << " ; After: -O" << static_cast<int>(SavedOptLevel) << "\n");
275 IS.OptLevel = SavedOptLevel;
276 IS.TM.setOptLevel(SavedOptLevel);
277 IS.TM.setFastISel(SavedFastISel);
278 }
279 };
280
281 //===--------------------------------------------------------------------===//
282 /// createDefaultScheduler - This creates an instruction scheduler appropriate
283 /// for the target.
285 CodeGenOptLevel OptLevel) {
286 const TargetLowering *TLI = IS->TLI;
287 const TargetSubtargetInfo &ST = IS->MF->getSubtarget();
288
289 // Try first to see if the Target has its own way of selecting a scheduler
290 if (auto *SchedulerCtor = ST.getDAGScheduler(OptLevel)) {
291 return SchedulerCtor(IS, OptLevel);
292 }
293
294 if (OptLevel == CodeGenOptLevel::None ||
295 (ST.enableMachineScheduler() && ST.enableMachineSchedDefaultSched()) ||
297 return createSourceListDAGScheduler(IS, OptLevel);
299 return createBURRListDAGScheduler(IS, OptLevel);
301 return createHybridListDAGScheduler(IS, OptLevel);
303 return createVLIWDAGScheduler(IS, OptLevel);
305 return createFastDAGScheduler(IS, OptLevel);
307 return createDAGLinearizer(IS, OptLevel);
309 "Unknown sched type!");
310 return createILPListDAGScheduler(IS, OptLevel);
311 }
312
313} // end namespace llvm
314
317 MachineBasicBlock *MBB) const {
318#ifndef NDEBUG
319 dbgs() << "If a target marks an instruction with "
320 "'usesCustomInserter', it must implement "
321 "TargetLowering::EmitInstrWithCustomInserter!\n";
322#endif
323 llvm_unreachable(nullptr);
324}
325
327 SDNode *Node) const {
328 assert(!MI.hasPostISelHook() &&
329 "If a target marks an instruction with 'hasPostISelHook', "
330 "it must implement TargetLowering::AdjustInstrPostInstrSelection!");
331}
332
333//===----------------------------------------------------------------------===//
334// SelectionDAGISel code
335//===----------------------------------------------------------------------===//
336
338 char &ID, std::unique_ptr<SelectionDAGISel> S)
339 : MachineFunctionPass(ID), Selector(std::move(S)) {
345}
346
348 // If we already selected that function, we do not need to run SDISel.
349 if (MF.getProperties().hasProperty(
351 return false;
352
353 // Do some sanity-checking on the command-line options.
354 if (EnableFastISelAbort && !Selector->TM.Options.EnableFastISel)
355 report_fatal_error("-fast-isel-abort > 0 requires -fast-isel");
356
357 // Decide what flavour of variable location debug-info will be used, before
358 // we change the optimisation level.
360
361 // Reset the target options before resetting the optimization
362 // level below.
363 // FIXME: This is a horrible hack and should be processed via
364 // codegen looking at the optimization level explicitly when
365 // it wants to look at it.
366 Selector->TM.resetTargetOptions(MF.getFunction());
367 // Reset OptLevel to None for optnone functions.
368 CodeGenOptLevel NewOptLevel = skipFunction(MF.getFunction())
370 : Selector->OptLevel;
371
372 Selector->MF = &MF;
373 OptLevelChanger OLC(*Selector, NewOptLevel);
374 Selector->initializeAnalysisResults(*this);
375 return Selector->runOnMachineFunction(MF);
376}
377
379 : TM(tm), FuncInfo(new FunctionLoweringInfo()),
380 SwiftError(new SwiftErrorValueTracking()),
381 CurDAG(new SelectionDAG(tm, OL)),
382 SDB(std::make_unique<SelectionDAGBuilder>(*CurDAG, *FuncInfo, *SwiftError,
383 OL)),
384 OptLevel(OL) {
390}
391
393 delete CurDAG;
394 delete SwiftError;
395}
396
398 CodeGenOptLevel OptLevel = Selector->OptLevel;
399 if (OptLevel != CodeGenOptLevel::None)
405#ifndef NDEBUG
407#endif
409 if (UseMBPI && OptLevel != CodeGenOptLevel::None)
412 // AssignmentTrackingAnalysis only runs if assignment tracking is enabled for
413 // the module.
416 if (OptLevel != CodeGenOptLevel::None)
419}
420
424 // If we already selected that function, we do not need to run SDISel.
425 if (MF.getProperties().hasProperty(
427 return PreservedAnalyses::all();
428
429 // Do some sanity-checking on the command-line options.
430 if (EnableFastISelAbort && !Selector->TM.Options.EnableFastISel)
431 report_fatal_error("-fast-isel-abort > 0 requires -fast-isel");
432
433 // Decide what flavour of variable location debug-info will be used, before
434 // we change the optimisation level.
436
437 // Reset the target options before resetting the optimization
438 // level below.
439 // FIXME: This is a horrible hack and should be processed via
440 // codegen looking at the optimization level explicitly when
441 // it wants to look at it.
442 Selector->TM.resetTargetOptions(MF.getFunction());
443 // Reset OptLevel to None for optnone functions.
444 // TODO: Add a function analysis to handle this.
445 Selector->MF = &MF;
446 // Reset OptLevel to None for optnone functions.
447 CodeGenOptLevel NewOptLevel = MF.getFunction().hasOptNone()
449 : Selector->OptLevel;
450
451 OptLevelChanger OLC(*Selector, NewOptLevel);
452 Selector->initializeAnalysisResults(MFAM);
453 Selector->runOnMachineFunction(MF);
454
456}
457
461 .getManager();
463 Function &Fn = MF->getFunction();
464#ifndef NDEBUG
465 FuncName = Fn.getName();
467#else
469#endif
470
473 RegInfo = &MF->getRegInfo();
475 GFI = Fn.hasGC() ? &FAM.getResult<GCFunctionAnalysis>(Fn) : nullptr;
476 ORE = std::make_unique<OptimizationRemarkEmitter>(&Fn);
478 auto *PSI = MAMP.getCachedResult<ProfileSummaryAnalysis>(*Fn.getParent());
479 BlockFrequencyInfo *BFI = nullptr;
481 if (PSI && PSI->hasProfileSummary() && OptLevel != CodeGenOptLevel::None)
483
484 FunctionVarLocs const *FnVarLocs = nullptr;
487
490 MAMP.getCachedResult<MachineModuleAnalysis>(*Fn.getParent())->getMMI();
491
492 CurDAG->init(*MF, *ORE, MFAM, LibInfo, UA, PSI, BFI, MMI, FnVarLocs);
493
494 // Now get the optional analyzes if we want to.
495 // This is based on the possibly changed OptLevel (after optnone is taken
496 // into account). That's unfortunate but OK because it just means we won't
497 // ask for passes that have been required anyway.
498
501 else
502 FuncInfo->BPI = nullptr;
503
505 BatchAA.emplace(FAM.getResult<AAManager>(Fn));
506 else
507 BatchAA = std::nullopt;
508
510
511#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
513#endif
514}
515
517 Function &Fn = MF->getFunction();
518#ifndef NDEBUG
519 FuncName = Fn.getName();
521#else
523#endif
524
527 RegInfo = &MF->getRegInfo();
529 GFI = Fn.hasGC() ? &MFP.getAnalysis<GCModuleInfo>().getFunctionInfo(Fn)
530 : nullptr;
531 ORE = std::make_unique<OptimizationRemarkEmitter>(&Fn);
532 AC = &MFP.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(Fn);
533 auto *PSI = &MFP.getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
534 BlockFrequencyInfo *BFI = nullptr;
535 if (PSI && PSI->hasProfileSummary() && OptLevel != CodeGenOptLevel::None)
536 BFI = &MFP.getAnalysis<LazyBlockFrequencyInfoPass>().getBFI();
537
538 FunctionVarLocs const *FnVarLocs = nullptr;
540 FnVarLocs = MFP.getAnalysis<AssignmentTrackingAnalysis>().getResults();
541
542 UniformityInfo *UA = nullptr;
543 if (auto *UAPass = MFP.getAnalysisIfAvailable<UniformityInfoWrapperPass>())
544 UA = &UAPass->getUniformityInfo();
545
548
549 CurDAG->init(*MF, *ORE, &MFP, LibInfo, UA, PSI, BFI, MMI, FnVarLocs);
550
551 // Now get the optional analyzes if we want to.
552 // This is based on the possibly changed OptLevel (after optnone is taken
553 // into account). That's unfortunate but OK because it just means we won't
554 // ask for passes that have been required anyway.
555
557 FuncInfo->BPI =
559 else
560 FuncInfo->BPI = nullptr;
561
564 else
565 BatchAA = std::nullopt;
566
567 SP = &MFP.getAnalysis<StackProtector>().getLayoutInfo();
568
569#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
571#endif
572}
573
576 const Function &Fn = mf.getFunction();
577
578 bool InstrRef = mf.shouldUseDebugInstrRef();
579
580 FuncInfo->set(MF->getFunction(), *MF, CurDAG);
581
582 ISEL_DUMP(dbgs() << "\n\n\n=== " << FuncName << '\n');
583
584 SDB->init(GFI, getBatchAA(), AC, LibInfo);
585
586 MF->setHasInlineAsm(false);
587
588 FuncInfo->SplitCSR = false;
589
590 // We split CSR if the target supports it for the given function
591 // and the function has only return exits.
593 FuncInfo->SplitCSR = true;
594
595 // Collect all the return blocks.
596 for (const BasicBlock &BB : Fn) {
597 if (!succ_empty(&BB))
598 continue;
599
600 const Instruction *Term = BB.getTerminator();
601 if (isa<UnreachableInst>(Term) || isa<ReturnInst>(Term))
602 continue;
603
604 // Bail out if the exit block is not Return nor Unreachable.
605 FuncInfo->SplitCSR = false;
606 break;
607 }
608 }
609
610 MachineBasicBlock *EntryMBB = &MF->front();
611 if (FuncInfo->SplitCSR)
612 // This performs initialization so lowering for SplitCSR will be correct.
613 TLI->initializeSplitCSR(EntryMBB);
614
615 SelectAllBasicBlocks(Fn);
617 DiagnosticInfoISelFallback DiagFallback(Fn);
618 Fn.getContext().diagnose(DiagFallback);
619 }
620
621 // Replace forward-declared registers with the registers containing
622 // the desired value.
623 // Note: it is important that this happens **before** the call to
624 // EmitLiveInCopies, since implementations can skip copies of unused
625 // registers. If we don't apply the reg fixups before, some registers may
626 // appear as unused and will be skipped, resulting in bad MI.
628 for (DenseMap<Register, Register>::iterator I = FuncInfo->RegFixups.begin(),
629 E = FuncInfo->RegFixups.end();
630 I != E; ++I) {
631 Register From = I->first;
632 Register To = I->second;
633 // If To is also scheduled to be replaced, find what its ultimate
634 // replacement is.
635 while (true) {
636 DenseMap<Register, Register>::iterator J = FuncInfo->RegFixups.find(To);
637 if (J == E)
638 break;
639 To = J->second;
640 }
641 // Make sure the new register has a sufficiently constrained register class.
642 if (From.isVirtual() && To.isVirtual())
643 MRI.constrainRegClass(To, MRI.getRegClass(From));
644 // Replace it.
645
646 // Replacing one register with another won't touch the kill flags.
647 // We need to conservatively clear the kill flags as a kill on the old
648 // register might dominate existing uses of the new register.
649 if (!MRI.use_empty(To))
650 MRI.clearKillFlags(From);
651 MRI.replaceRegWith(From, To);
652 }
653
654 // If the first basic block in the function has live ins that need to be
655 // copied into vregs, emit the copies into the top of the block before
656 // emitting the code for the block.
658 RegInfo->EmitLiveInCopies(EntryMBB, TRI, *TII);
659
660 // Insert copies in the entry block and the return blocks.
661 if (FuncInfo->SplitCSR) {
663 // Collect all the return blocks.
664 for (MachineBasicBlock &MBB : mf) {
665 if (!MBB.succ_empty())
666 continue;
667
669 if (Term != MBB.end() && Term->isReturn()) {
670 Returns.push_back(&MBB);
671 continue;
672 }
673 }
674 TLI->insertCopiesSplitCSR(EntryMBB, Returns);
675 }
676
678 if (!FuncInfo->ArgDbgValues.empty())
679 for (std::pair<MCRegister, Register> LI : RegInfo->liveins())
680 if (LI.second)
681 LiveInMap.insert(LI);
682
683 // Insert DBG_VALUE instructions for function arguments to the entry block.
684 for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; ++i) {
685 MachineInstr *MI = FuncInfo->ArgDbgValues[e - i - 1];
686 assert(MI->getOpcode() != TargetOpcode::DBG_VALUE_LIST &&
687 "Function parameters should not be described by DBG_VALUE_LIST.");
688 bool hasFI = MI->getDebugOperand(0).isFI();
689 Register Reg =
690 hasFI ? TRI.getFrameRegister(*MF) : MI->getDebugOperand(0).getReg();
691 if (Reg.isPhysical())
692 EntryMBB->insert(EntryMBB->begin(), MI);
693 else {
694 MachineInstr *Def = RegInfo->getVRegDef(Reg);
695 if (Def) {
696 MachineBasicBlock::iterator InsertPos = Def;
697 // FIXME: VR def may not be in entry block.
698 Def->getParent()->insert(std::next(InsertPos), MI);
699 } else
700 LLVM_DEBUG(dbgs() << "Dropping debug info for dead vreg"
701 << Register::virtReg2Index(Reg) << "\n");
702 }
703
704 // Don't try and extend through copies in instruction referencing mode.
705 if (InstrRef)
706 continue;
707
708 // If Reg is live-in then update debug info to track its copy in a vreg.
709 if (!Reg.isPhysical())
710 continue;
712 if (LDI != LiveInMap.end()) {
713 assert(!hasFI && "There's no handling of frame pointer updating here yet "
714 "- add if needed");
715 MachineInstr *Def = RegInfo->getVRegDef(LDI->second);
716 MachineBasicBlock::iterator InsertPos = Def;
717 const MDNode *Variable = MI->getDebugVariable();
718 const MDNode *Expr = MI->getDebugExpression();
719 DebugLoc DL = MI->getDebugLoc();
720 bool IsIndirect = MI->isIndirectDebugValue();
721 if (IsIndirect)
722 assert(MI->getDebugOffset().getImm() == 0 &&
723 "DBG_VALUE with nonzero offset");
724 assert(cast<DILocalVariable>(Variable)->isValidLocationForIntrinsic(DL) &&
725 "Expected inlined-at fields to agree");
726 assert(MI->getOpcode() != TargetOpcode::DBG_VALUE_LIST &&
727 "Didn't expect to see a DBG_VALUE_LIST here");
728 // Def is never a terminator here, so it is ok to increment InsertPos.
729 BuildMI(*EntryMBB, ++InsertPos, DL, TII->get(TargetOpcode::DBG_VALUE),
730 IsIndirect, LDI->second, Variable, Expr);
731
732 // If this vreg is directly copied into an exported register then
733 // that COPY instructions also need DBG_VALUE, if it is the only
734 // user of LDI->second.
735 MachineInstr *CopyUseMI = nullptr;
736 for (MachineInstr &UseMI : RegInfo->use_instructions(LDI->second)) {
737 if (UseMI.isDebugValue())
738 continue;
739 if (UseMI.isCopy() && !CopyUseMI && UseMI.getParent() == EntryMBB) {
740 CopyUseMI = &UseMI;
741 continue;
742 }
743 // Otherwise this is another use or second copy use.
744 CopyUseMI = nullptr;
745 break;
746 }
747 if (CopyUseMI &&
748 TRI.getRegSizeInBits(LDI->second, MRI) ==
749 TRI.getRegSizeInBits(CopyUseMI->getOperand(0).getReg(), MRI)) {
750 // Use MI's debug location, which describes where Variable was
751 // declared, rather than whatever is attached to CopyUseMI.
752 MachineInstr *NewMI =
753 BuildMI(*MF, DL, TII->get(TargetOpcode::DBG_VALUE), IsIndirect,
754 CopyUseMI->getOperand(0).getReg(), Variable, Expr);
755 MachineBasicBlock::iterator Pos = CopyUseMI;
756 EntryMBB->insertAfter(Pos, NewMI);
757 }
758 }
759 }
760
761 // For debug-info, in instruction referencing mode, we need to perform some
762 // post-isel maintenence.
763 if (MF->useDebugInstrRef())
765
766 // Determine if there are any calls in this machine function.
768 for (const auto &MBB : *MF) {
769 if (MFI.hasCalls() && MF->hasInlineAsm())
770 break;
771
772 for (const auto &MI : MBB) {
773 const MCInstrDesc &MCID = TII->get(MI.getOpcode());
774 if ((MCID.isCall() && !MCID.isReturn()) ||
775 MI.isStackAligningInlineAsm()) {
776 MFI.setHasCalls(true);
777 }
778 if (MI.isInlineAsm()) {
779 MF->setHasInlineAsm(true);
780 }
781 }
782 }
783
784 // Release function-specific state. SDB and CurDAG are already cleared
785 // at this point.
786 FuncInfo->clear();
787
788 ISEL_DUMP(dbgs() << "*** MachineFunction at end of ISel ***\n");
789 ISEL_DUMP(MF->print(dbgs()));
790
791 return true;
792}
793
797 bool ShouldAbort) {
798 // Print the function name explicitly if we don't have a debug location (which
799 // makes the diagnostic less useful) or if we're going to emit a raw error.
800 if (!R.getLocation().isValid() || ShouldAbort)
801 R << (" (in function: " + MF.getName() + ")").str();
802
803 if (ShouldAbort)
804 report_fatal_error(Twine(R.getMsg()));
805
806 ORE.emit(R);
807 LLVM_DEBUG(dbgs() << R.getMsg() << "\n");
808}
809
810// Detect any fake uses that follow a tail call and move them before the tail
811// call. Ignore fake uses that use values that are def'd by or after the tail
812// call.
816 if (--I == Begin || !isa<ReturnInst>(*I))
817 return;
818 // Detect whether there are any fake uses trailing a (potential) tail call.
819 bool HaveFakeUse = false;
820 bool HaveTailCall = false;
821 do {
822 if (const CallInst *CI = dyn_cast<CallInst>(--I))
823 if (CI->isTailCall()) {
824 HaveTailCall = true;
825 break;
826 }
827 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
828 if (II->getIntrinsicID() == Intrinsic::fake_use)
829 HaveFakeUse = true;
830 } while (I != Begin);
831
832 // If we didn't find any tail calls followed by fake uses, we are done.
833 if (!HaveTailCall || !HaveFakeUse)
834 return;
835
837 // Record the fake uses we found so we can move them to the front of the
838 // tail call. Ignore them if they use a value that is def'd by or after
839 // the tail call.
840 for (BasicBlock::iterator Inst = I; Inst != End; Inst++) {
841 if (IntrinsicInst *FakeUse = dyn_cast<IntrinsicInst>(Inst);
842 FakeUse && FakeUse->getIntrinsicID() == Intrinsic::fake_use) {
843 if (auto UsedDef = dyn_cast<Instruction>(FakeUse->getOperand(0));
844 !UsedDef || UsedDef->getParent() != I->getParent() ||
845 UsedDef->comesBefore(&*I))
846 FakeUses.push_back(FakeUse);
847 }
848 }
849
850 for (auto *Inst : FakeUses)
851 Inst->moveBefore(*Inst->getParent(), I);
852}
853
854void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,
856 bool &HadTailCall) {
857 // Allow creating illegal types during DAG building for the basic block.
859
860 // Lower the instructions. If a call is emitted as a tail call, cease emitting
861 // nodes for this block. If an instruction is elided, don't emit it, but do
862 // handle any debug-info attached to it.
863 for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I) {
864 if (!ElidedArgCopyInstrs.count(&*I))
865 SDB->visit(*I);
866 else
867 SDB->visitDbgInfo(*I);
868 }
869
870 // Make sure the root of the DAG is up-to-date.
871 CurDAG->setRoot(SDB->getControlRoot());
872 HadTailCall = SDB->HasTailCall;
873 SDB->resolveOrClearDbgInfo();
874 SDB->clear();
875
876 // Final step, emit the lowered DAG as machine code.
877 CodeGenAndEmitDAG();
878}
879
880void SelectionDAGISel::ComputeLiveOutVRegInfo() {
883
884 Worklist.push_back(CurDAG->getRoot().getNode());
885 Added.insert(CurDAG->getRoot().getNode());
886
887 KnownBits Known;
888
889 do {
890 SDNode *N = Worklist.pop_back_val();
891
892 // Otherwise, add all chain operands to the worklist.
893 for (const SDValue &Op : N->op_values())
894 if (Op.getValueType() == MVT::Other && Added.insert(Op.getNode()).second)
895 Worklist.push_back(Op.getNode());
896
897 // If this is a CopyToReg with a vreg dest, process it.
898 if (N->getOpcode() != ISD::CopyToReg)
899 continue;
900
901 Register DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();
902 if (!DestReg.isVirtual())
903 continue;
904
905 // Ignore non-integer values.
906 SDValue Src = N->getOperand(2);
907 EVT SrcVT = Src.getValueType();
908 if (!SrcVT.isInteger())
909 continue;
910
911 unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);
912 Known = CurDAG->computeKnownBits(Src);
913 FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, Known);
914 } while (!Worklist.empty());
915}
916
917void SelectionDAGISel::CodeGenAndEmitDAG() {
918 StringRef GroupName = "sdag";
919 StringRef GroupDescription = "Instruction Selection and Scheduling";
920 std::string BlockName;
921 bool MatchFilterBB = false;
922 (void)MatchFilterBB;
923
924 // Pre-type legalization allow creation of any node types.
926
927#ifndef NDEBUG
928 MatchFilterBB = (FilterDAGBasicBlockName.empty() ||
930 FuncInfo->MBB->getBasicBlock()->getName());
931#endif
932#ifdef NDEBUG
936#endif
937 {
938 BlockName =
939 (MF->getName() + ":" + FuncInfo->MBB->getBasicBlock()->getName()).str();
940 }
941 ISEL_DUMP(dbgs() << "\nInitial selection DAG: "
942 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
943 << "'\n";
944 CurDAG->dump());
945
946#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
948 CurDAG->VerifyDAGDivergence();
949#endif
950
951 if (ViewDAGCombine1 && MatchFilterBB)
952 CurDAG->viewGraph("dag-combine1 input for " + BlockName);
953
954 // Run the DAG combiner in pre-legalize mode.
955 {
956 NamedRegionTimer T("combine1", "DAG Combining 1", GroupName,
957 GroupDescription, TimePassesIsEnabled);
959 }
960
961 ISEL_DUMP(dbgs() << "\nOptimized lowered selection DAG: "
962 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
963 << "'\n";
964 CurDAG->dump());
965
966#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
968 CurDAG->VerifyDAGDivergence();
969#endif
970
971 // Second step, hack on the DAG until it only uses operations and types that
972 // the target supports.
973 if (ViewLegalizeTypesDAGs && MatchFilterBB)
974 CurDAG->viewGraph("legalize-types input for " + BlockName);
975
976 bool Changed;
977 {
978 NamedRegionTimer T("legalize_types", "Type Legalization", GroupName,
979 GroupDescription, TimePassesIsEnabled);
980 Changed = CurDAG->LegalizeTypes();
981 }
982
983 ISEL_DUMP(dbgs() << "\nType-legalized selection DAG: "
984 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
985 << "'\n";
986 CurDAG->dump());
987
988#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
990 CurDAG->VerifyDAGDivergence();
991#endif
992
993 // Only allow creation of legal node types.
995
996 if (Changed) {
997 if (ViewDAGCombineLT && MatchFilterBB)
998 CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
999
1000 // Run the DAG combiner in post-type-legalize mode.
1001 {
1002 NamedRegionTimer T("combine_lt", "DAG Combining after legalize types",
1003 GroupName, GroupDescription, TimePassesIsEnabled);
1005 }
1006
1007 ISEL_DUMP(dbgs() << "\nOptimized type-legalized selection DAG: "
1008 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
1009 << "'\n";
1010 CurDAG->dump());
1011
1012#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
1013 if (TTI->hasBranchDivergence())
1014 CurDAG->VerifyDAGDivergence();
1015#endif
1016 }
1017
1018 {
1019 NamedRegionTimer T("legalize_vec", "Vector Legalization", GroupName,
1020 GroupDescription, TimePassesIsEnabled);
1021 Changed = CurDAG->LegalizeVectors();
1022 }
1023
1024 if (Changed) {
1025 ISEL_DUMP(dbgs() << "\nVector-legalized selection DAG: "
1026 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
1027 << "'\n";
1028 CurDAG->dump());
1029
1030#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
1031 if (TTI->hasBranchDivergence())
1032 CurDAG->VerifyDAGDivergence();
1033#endif
1034
1035 {
1036 NamedRegionTimer T("legalize_types2", "Type Legalization 2", GroupName,
1037 GroupDescription, TimePassesIsEnabled);
1039 }
1040
1041 ISEL_DUMP(dbgs() << "\nVector/type-legalized selection DAG: "
1042 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
1043 << "'\n";
1044 CurDAG->dump());
1045
1046#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
1047 if (TTI->hasBranchDivergence())
1048 CurDAG->VerifyDAGDivergence();
1049#endif
1050
1051 if (ViewDAGCombineLT && MatchFilterBB)
1052 CurDAG->viewGraph("dag-combine-lv input for " + BlockName);
1053
1054 // Run the DAG combiner in post-type-legalize mode.
1055 {
1056 NamedRegionTimer T("combine_lv", "DAG Combining after legalize vectors",
1057 GroupName, GroupDescription, TimePassesIsEnabled);
1059 }
1060
1061 ISEL_DUMP(dbgs() << "\nOptimized vector-legalized selection DAG: "
1062 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
1063 << "'\n";
1064 CurDAG->dump());
1065
1066#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
1067 if (TTI->hasBranchDivergence())
1068 CurDAG->VerifyDAGDivergence();
1069#endif
1070 }
1071
1072 if (ViewLegalizeDAGs && MatchFilterBB)
1073 CurDAG->viewGraph("legalize input for " + BlockName);
1074
1075 {
1076 NamedRegionTimer T("legalize", "DAG Legalization", GroupName,
1077 GroupDescription, TimePassesIsEnabled);
1078 CurDAG->Legalize();
1079 }
1080
1081 ISEL_DUMP(dbgs() << "\nLegalized selection DAG: "
1082 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
1083 << "'\n";
1084 CurDAG->dump());
1085
1086#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
1087 if (TTI->hasBranchDivergence())
1088 CurDAG->VerifyDAGDivergence();
1089#endif
1090
1091 if (ViewDAGCombine2 && MatchFilterBB)
1092 CurDAG->viewGraph("dag-combine2 input for " + BlockName);
1093
1094 // Run the DAG combiner in post-legalize mode.
1095 {
1096 NamedRegionTimer T("combine2", "DAG Combining 2", GroupName,
1097 GroupDescription, TimePassesIsEnabled);
1099 }
1100
1101 ISEL_DUMP(dbgs() << "\nOptimized legalized selection DAG: "
1102 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
1103 << "'\n";
1104 CurDAG->dump());
1105
1106#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS
1107 if (TTI->hasBranchDivergence())
1108 CurDAG->VerifyDAGDivergence();
1109#endif
1110
1112 ComputeLiveOutVRegInfo();
1113
1114 if (ViewISelDAGs && MatchFilterBB)
1115 CurDAG->viewGraph("isel input for " + BlockName);
1116
1117 // Third, instruction select all of the operations to machine code, adding the
1118 // code to the MachineBasicBlock.
1119 {
1120 NamedRegionTimer T("isel", "Instruction Selection", GroupName,
1121 GroupDescription, TimePassesIsEnabled);
1122 DoInstructionSelection();
1123 }
1124
1125 ISEL_DUMP(dbgs() << "\nSelected selection DAG: "
1126 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
1127 << "'\n";
1128 CurDAG->dump());
1129
1130 if (ViewSchedDAGs && MatchFilterBB)
1131 CurDAG->viewGraph("scheduler input for " + BlockName);
1132
1133 // Schedule machine code.
1134 ScheduleDAGSDNodes *Scheduler = CreateScheduler();
1135 {
1136 NamedRegionTimer T("sched", "Instruction Scheduling", GroupName,
1137 GroupDescription, TimePassesIsEnabled);
1138 Scheduler->Run(CurDAG, FuncInfo->MBB);
1139 }
1140
1141 if (ViewSUnitDAGs && MatchFilterBB)
1142 Scheduler->viewGraph();
1143
1144 // Emit machine code to BB. This can change 'BB' to the last block being
1145 // inserted into.
1146 MachineBasicBlock *FirstMBB = FuncInfo->MBB, *LastMBB;
1147 {
1148 NamedRegionTimer T("emit", "Instruction Creation", GroupName,
1149 GroupDescription, TimePassesIsEnabled);
1150
1151 // FuncInfo->InsertPt is passed by reference and set to the end of the
1152 // scheduled instructions.
1153 LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(FuncInfo->InsertPt);
1154 }
1155
1156 // If the block was split, make sure we update any references that are used to
1157 // update PHI nodes later on.
1158 if (FirstMBB != LastMBB)
1159 SDB->UpdateSplitBlock(FirstMBB, LastMBB);
1160
1161 // Free the scheduler state.
1162 {
1163 NamedRegionTimer T("cleanup", "Instruction Scheduling Cleanup", GroupName,
1164 GroupDescription, TimePassesIsEnabled);
1165 delete Scheduler;
1166 }
1167
1168 // Free the SelectionDAG state, now that we're finished with it.
1169 CurDAG->clear();
1170}
1171
1172namespace {
1173
1174/// ISelUpdater - helper class to handle updates of the instruction selection
1175/// graph.
1176class ISelUpdater : public SelectionDAG::DAGUpdateListener {
1177 SelectionDAG::allnodes_iterator &ISelPosition;
1178
1179public:
1180 ISelUpdater(SelectionDAG &DAG, SelectionDAG::allnodes_iterator &isp)
1181 : SelectionDAG::DAGUpdateListener(DAG), ISelPosition(isp) {}
1182
1183 /// NodeDeleted - Handle nodes deleted from the graph. If the node being
1184 /// deleted is the current ISelPosition node, update ISelPosition.
1185 ///
1186 void NodeDeleted(SDNode *N, SDNode *E) override {
1187 if (ISelPosition == SelectionDAG::allnodes_iterator(N))
1188 ++ISelPosition;
1189 }
1190
1191 /// NodeInserted - Handle new nodes inserted into the graph: propagate
1192 /// metadata from root nodes that also applies to new nodes, in case the root
1193 /// is later deleted.
1194 void NodeInserted(SDNode *N) override {
1195 SDNode *CurNode = &*ISelPosition;
1196 if (MDNode *MD = DAG.getPCSections(CurNode))
1197 DAG.addPCSections(N, MD);
1198 if (MDNode *MMRA = DAG.getMMRAMetadata(CurNode))
1199 DAG.addMMRAMetadata(N, MMRA);
1200 }
1201};
1202
1203} // end anonymous namespace
1204
1205// This function is used to enforce the topological node id property
1206// leveraged during instruction selection. Before the selection process all
1207// nodes are given a non-negative id such that all nodes have a greater id than
1208// their operands. As this holds transitively we can prune checks that a node N
1209// is a predecessor of M another by not recursively checking through M's
1210// operands if N's ID is larger than M's ID. This significantly improves
1211// performance of various legality checks (e.g. IsLegalToFold / UpdateChains).
1212
1213// However, when we fuse multiple nodes into a single node during the
1214// selection we may induce a predecessor relationship between inputs and
1215// outputs of distinct nodes being merged, violating the topological property.
1216// Should a fused node have a successor which has yet to be selected,
1217// our legality checks would be incorrect. To avoid this we mark all unselected
1218// successor nodes, i.e. id != -1, as invalid for pruning by bit-negating (x =>
1219// (-(x+1))) the ids and modify our pruning check to ignore negative Ids of M.
1220// We use bit-negation to more clearly enforce that node id -1 can only be
1221// achieved by selected nodes. As the conversion is reversable to the original
1222// Id, topological pruning can still be leveraged when looking for unselected
1223// nodes. This method is called internally in all ISel replacement related
1224// functions.
1227 Nodes.push_back(Node);
1228
1229 while (!Nodes.empty()) {
1230 SDNode *N = Nodes.pop_back_val();
1231 for (auto *U : N->users()) {
1232 auto UId = U->getNodeId();
1233 if (UId > 0) {
1235 Nodes.push_back(U);
1236 }
1237 }
1238 }
1239}
1240
1241// InvalidateNodeId - As explained in EnforceNodeIdInvariant, mark a
1242// NodeId with the equivalent node id which is invalid for topological
1243// pruning.
1245 int InvalidId = -(N->getNodeId() + 1);
1246 N->setNodeId(InvalidId);
1247}
1248
1249// getUninvalidatedNodeId - get original uninvalidated node id.
1251 int Id = N->getNodeId();
1252 if (Id < -1)
1253 return -(Id + 1);
1254 return Id;
1255}
1256
1257void SelectionDAGISel::DoInstructionSelection() {
1258 LLVM_DEBUG(dbgs() << "===== Instruction selection begins: "
1259 << printMBBReference(*FuncInfo->MBB) << " '"
1260 << FuncInfo->MBB->getName() << "'\n");
1261
1263
1264 // Select target instructions for the DAG.
1265 {
1266 // Number all nodes with a topological order and set DAGSize.
1268
1269 // Create a dummy node (which is not added to allnodes), that adds
1270 // a reference to the root node, preventing it from being deleted,
1271 // and tracking any changes of the root.
1272 HandleSDNode Dummy(CurDAG->getRoot());
1274 ++ISelPosition;
1275
1276 // Make sure that ISelPosition gets properly updated when nodes are deleted
1277 // in calls made from this function. New nodes inherit relevant metadata.
1278 ISelUpdater ISU(*CurDAG, ISelPosition);
1279
1280 // The AllNodes list is now topological-sorted. Visit the
1281 // nodes by starting at the end of the list (the root of the
1282 // graph) and preceding back toward the beginning (the entry
1283 // node).
1284 while (ISelPosition != CurDAG->allnodes_begin()) {
1285 SDNode *Node = &*--ISelPosition;
1286 // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
1287 // but there are currently some corner cases that it misses. Also, this
1288 // makes it theoretically possible to disable the DAGCombiner.
1289 if (Node->use_empty())
1290 continue;
1291
1292#ifndef NDEBUG
1294 Nodes.push_back(Node);
1295
1296 while (!Nodes.empty()) {
1297 auto N = Nodes.pop_back_val();
1298 if (N->getOpcode() == ISD::TokenFactor || N->getNodeId() < 0)
1299 continue;
1300 for (const SDValue &Op : N->op_values()) {
1301 if (Op->getOpcode() == ISD::TokenFactor)
1302 Nodes.push_back(Op.getNode());
1303 else {
1304 // We rely on topological ordering of node ids for checking for
1305 // cycles when fusing nodes during selection. All unselected nodes
1306 // successors of an already selected node should have a negative id.
1307 // This assertion will catch such cases. If this assertion triggers
1308 // it is likely you using DAG-level Value/Node replacement functions
1309 // (versus equivalent ISEL replacement) in backend-specific
1310 // selections. See comment in EnforceNodeIdInvariant for more
1311 // details.
1312 assert(Op->getNodeId() != -1 &&
1313 "Node has already selected predecessor node");
1314 }
1315 }
1316 }
1317#endif
1318
1319 // When we are using non-default rounding modes or FP exception behavior
1320 // FP operations are represented by StrictFP pseudo-operations. For
1321 // targets that do not (yet) understand strict FP operations directly,
1322 // we convert them to normal FP opcodes instead at this point. This
1323 // will allow them to be handled by existing target-specific instruction
1324 // selectors.
1325 if (!TLI->isStrictFPEnabled() && Node->isStrictFPOpcode()) {
1326 // For some opcodes, we need to call TLI->getOperationAction using
1327 // the first operand type instead of the result type. Note that this
1328 // must match what SelectionDAGLegalize::LegalizeOp is doing.
1329 EVT ActionVT;
1330 switch (Node->getOpcode()) {
1333 case ISD::STRICT_LRINT:
1334 case ISD::STRICT_LLRINT:
1335 case ISD::STRICT_LROUND:
1337 case ISD::STRICT_FSETCC:
1339 ActionVT = Node->getOperand(1).getValueType();
1340 break;
1341 default:
1342 ActionVT = Node->getValueType(0);
1343 break;
1344 }
1345 if (TLI->getOperationAction(Node->getOpcode(), ActionVT)
1348 }
1349
1350 LLVM_DEBUG(dbgs() << "\nISEL: Starting selection on root node: ";
1351 Node->dump(CurDAG));
1352
1353 Select(Node);
1354 }
1355
1356 CurDAG->setRoot(Dummy.getValue());
1357 }
1358
1359 LLVM_DEBUG(dbgs() << "\n===== Instruction selection ends:\n");
1360
1362}
1363
1365 for (const User *U : CPI->users()) {
1366 if (const IntrinsicInst *EHPtrCall = dyn_cast<IntrinsicInst>(U)) {
1367 Intrinsic::ID IID = EHPtrCall->getIntrinsicID();
1368 if (IID == Intrinsic::eh_exceptionpointer ||
1369 IID == Intrinsic::eh_exceptioncode)
1370 return true;
1371 }
1372 }
1373 return false;
1374}
1375
1376// wasm.landingpad.index intrinsic is for associating a landing pad index number
1377// with a catchpad instruction. Retrieve the landing pad index in the intrinsic
1378// and store the mapping in the function.
1380 const CatchPadInst *CPI) {
1381 MachineFunction *MF = MBB->getParent();
1382 // In case of single catch (...), we don't emit LSDA, so we don't need
1383 // this information.
1384 bool IsSingleCatchAllClause =
1385 CPI->arg_size() == 1 &&
1386 cast<Constant>(CPI->getArgOperand(0))->isNullValue();
1387 // cathchpads for longjmp use an empty type list, e.g. catchpad within %0 []
1388 // and they don't need LSDA info
1389 bool IsCatchLongjmp = CPI->arg_size() == 0;
1390 if (!IsSingleCatchAllClause && !IsCatchLongjmp) {
1391 // Create a mapping from landing pad label to landing pad index.
1392 bool IntrFound = false;
1393 for (const User *U : CPI->users()) {
1394 if (const auto *Call = dyn_cast<IntrinsicInst>(U)) {
1395 Intrinsic::ID IID = Call->getIntrinsicID();
1396 if (IID == Intrinsic::wasm_landingpad_index) {
1397 Value *IndexArg = Call->getArgOperand(1);
1398 int Index = cast<ConstantInt>(IndexArg)->getZExtValue();
1399 MF->setWasmLandingPadIndex(MBB, Index);
1400 IntrFound = true;
1401 break;
1402 }
1403 }
1404 }
1405 assert(IntrFound && "wasm.landingpad.index intrinsic not found!");
1406 (void)IntrFound;
1407 }
1408}
1409
1410/// PrepareEHLandingPad - Emit an EH_LABEL, set up live-in registers, and
1411/// do other setup for EH landing-pad blocks.
1412bool SelectionDAGISel::PrepareEHLandingPad() {
1414 const Constant *PersonalityFn = FuncInfo->Fn->getPersonalityFn();
1415 const BasicBlock *LLVMBB = MBB->getBasicBlock();
1416 const TargetRegisterClass *PtrRC =
1418
1419 auto Pers = classifyEHPersonality(PersonalityFn);
1420
1421 // Catchpads have one live-in register, which typically holds the exception
1422 // pointer or code.
1423 if (isFuncletEHPersonality(Pers)) {
1424 if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHIIt())) {
1426 // Get or create the virtual register to hold the pointer or code. Mark
1427 // the live in physreg and copy into the vreg.
1428 MCPhysReg EHPhysReg = TLI->getExceptionPointerRegister(PersonalityFn);
1429 assert(EHPhysReg && "target lacks exception pointer register");
1430 MBB->addLiveIn(EHPhysReg);
1431 unsigned VReg = FuncInfo->getCatchPadExceptionPointerVReg(CPI, PtrRC);
1432 BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(),
1433 TII->get(TargetOpcode::COPY), VReg)
1434 .addReg(EHPhysReg, RegState::Kill);
1435 }
1436 }
1437 return true;
1438 }
1439
1440 // Add a label to mark the beginning of the landing pad. Deletion of the
1441 // landing pad can thus be detected via the MachineModuleInfo.
1443
1444 const MCInstrDesc &II = TII->get(TargetOpcode::EH_LABEL);
1445 BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II)
1446 .addSym(Label);
1447
1448 // If the unwinder does not preserve all registers, ensure that the
1449 // function marks the clobbered registers as used.
1451 if (auto *RegMask = TRI.getCustomEHPadPreservedMask(*MF))
1453
1454 if (Pers == EHPersonality::Wasm_CXX) {
1455 if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHIIt()))
1457 } else {
1458 // Assign the call site to the landing pad's begin label.
1459 MF->setCallSiteLandingPad(Label, SDB->LPadToCallSiteMap[MBB]);
1460 // Mark exception register as live in.
1461 if (unsigned Reg = TLI->getExceptionPointerRegister(PersonalityFn))
1462 FuncInfo->ExceptionPointerVirtReg = MBB->addLiveIn(Reg, PtrRC);
1463 // Mark exception selector register as live in.
1464 if (unsigned Reg = TLI->getExceptionSelectorRegister(PersonalityFn))
1465 FuncInfo->ExceptionSelectorVirtReg = MBB->addLiveIn(Reg, PtrRC);
1466 }
1467
1468 return true;
1469}
1470
1471// Mark and Report IPToState for each Block under IsEHa
1472void SelectionDAGISel::reportIPToStateForBlocks(MachineFunction *MF) {
1474 if (!EHInfo)
1475 return;
1476 for (MachineBasicBlock &MBB : *MF) {
1477 const BasicBlock *BB = MBB.getBasicBlock();
1478 int State = EHInfo->BlockToStateMap[BB];
1479 if (BB->getFirstMayFaultInst()) {
1480 // Report IP range only for blocks with Faulty inst
1481 auto MBBb = MBB.getFirstNonPHI();
1482
1483 if (MBBb == MBB.end())
1484 continue;
1485
1486 MachineInstr *MIb = &*MBBb;
1487 if (MIb->isTerminator())
1488 continue;
1489
1490 // Insert EH Labels
1491 MCSymbol *BeginLabel = MF->getContext().createTempSymbol();
1492 MCSymbol *EndLabel = MF->getContext().createTempSymbol();
1493 EHInfo->addIPToStateRange(State, BeginLabel, EndLabel);
1494 BuildMI(MBB, MBBb, SDB->getCurDebugLoc(),
1495 TII->get(TargetOpcode::EH_LABEL))
1496 .addSym(BeginLabel);
1497 auto MBBe = MBB.instr_end();
1498 MachineInstr *MIe = &*(--MBBe);
1499 // insert before (possible multiple) terminators
1500 while (MIe->isTerminator())
1501 MIe = &*(--MBBe);
1502 ++MBBe;
1503 BuildMI(MBB, MBBe, SDB->getCurDebugLoc(),
1504 TII->get(TargetOpcode::EH_LABEL))
1505 .addSym(EndLabel);
1506 }
1507 }
1508}
1509
1510/// isFoldedOrDeadInstruction - Return true if the specified instruction is
1511/// side-effect free and is either dead or folded into a generated instruction.
1512/// Return false if it needs to be emitted.
1514 const FunctionLoweringInfo &FuncInfo) {
1515 return !I->mayWriteToMemory() && // Side-effecting instructions aren't folded.
1516 !I->isTerminator() && // Terminators aren't folded.
1517 !isa<DbgInfoIntrinsic>(I) && // Debug instructions aren't folded.
1518 !I->isEHPad() && // EH pad instructions aren't folded.
1519 !FuncInfo.isExportedInst(I); // Exported instrs must be computed.
1520}
1521
1523 const Value *Arg, DIExpression *Expr,
1524 DILocalVariable *Var,
1525 DebugLoc DbgLoc) {
1526 if (!Expr->isEntryValue() || !isa<Argument>(Arg))
1527 return false;
1528
1529 auto ArgIt = FuncInfo.ValueMap.find(Arg);
1530 if (ArgIt == FuncInfo.ValueMap.end())
1531 return false;
1532 Register ArgVReg = ArgIt->getSecond();
1533
1534 // Find the corresponding livein physical register to this argument.
1535 for (auto [PhysReg, VirtReg] : FuncInfo.RegInfo->liveins())
1536 if (VirtReg == ArgVReg) {
1537 // Append an op deref to account for the fact that this is a dbg_declare.
1538 Expr = DIExpression::append(Expr, dwarf::DW_OP_deref);
1539 FuncInfo.MF->setVariableDbgInfo(Var, Expr, PhysReg, DbgLoc);
1540 LLVM_DEBUG(dbgs() << "processDbgDeclare: setVariableDbgInfo Var=" << *Var
1541 << ", Expr=" << *Expr << ", MCRegister=" << PhysReg
1542 << ", DbgLoc=" << DbgLoc << "\n");
1543 return true;
1544 }
1545 return false;
1546}
1547
1549 const Value *Address, DIExpression *Expr,
1550 DILocalVariable *Var, DebugLoc DbgLoc) {
1551 if (!Address) {
1552 LLVM_DEBUG(dbgs() << "processDbgDeclares skipping " << *Var
1553 << " (bad address)\n");
1554 return false;
1555 }
1556
1557 if (processIfEntryValueDbgDeclare(FuncInfo, Address, Expr, Var, DbgLoc))
1558 return true;
1559
1560 MachineFunction *MF = FuncInfo.MF;
1561 const DataLayout &DL = MF->getDataLayout();
1562
1563 assert(Var && "Missing variable");
1564 assert(DbgLoc && "Missing location");
1565
1566 // Look through casts and constant offset GEPs. These mostly come from
1567 // inalloca.
1568 APInt Offset(DL.getTypeSizeInBits(Address->getType()), 0);
1569 Address = Address->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
1570
1571 // Check if the variable is a static alloca or a byval or inalloca
1572 // argument passed in memory. If it is not, then we will ignore this
1573 // intrinsic and handle this during isel like dbg.value.
1574 int FI = std::numeric_limits<int>::max();
1575 if (const auto *AI = dyn_cast<AllocaInst>(Address)) {
1576 auto SI = FuncInfo.StaticAllocaMap.find(AI);
1577 if (SI != FuncInfo.StaticAllocaMap.end())
1578 FI = SI->second;
1579 } else if (const auto *Arg = dyn_cast<Argument>(Address))
1580 FI = FuncInfo.getArgumentFrameIndex(Arg);
1581
1582 if (FI == std::numeric_limits<int>::max())
1583 return false;
1584
1585 if (Offset.getBoolValue())
1587 Offset.getZExtValue());
1588
1589 LLVM_DEBUG(dbgs() << "processDbgDeclare: setVariableDbgInfo Var=" << *Var
1590 << ", Expr=" << *Expr << ", FI=" << FI
1591 << ", DbgLoc=" << DbgLoc << "\n");
1592 MF->setVariableDbgInfo(Var, Expr, FI, DbgLoc);
1593 return true;
1594}
1595
1596/// Collect llvm.dbg.declare information. This is done after argument lowering
1597/// in case the declarations refer to arguments.
1599 for (const auto &I : instructions(*FuncInfo.Fn)) {
1600 const auto *DI = dyn_cast<DbgDeclareInst>(&I);
1601 if (DI && processDbgDeclare(FuncInfo, DI->getAddress(), DI->getExpression(),
1602 DI->getVariable(), DI->getDebugLoc()))
1603 FuncInfo.PreprocessedDbgDeclares.insert(DI);
1604 for (const DbgVariableRecord &DVR : filterDbgVars(I.getDbgRecordRange())) {
1606 processDbgDeclare(FuncInfo, DVR.getVariableLocationOp(0),
1607 DVR.getExpression(), DVR.getVariable(),
1608 DVR.getDebugLoc()))
1609 FuncInfo.PreprocessedDVRDeclares.insert(&DVR);
1610 }
1611 }
1612}
1613
1614/// Collect single location variable information generated with assignment
1615/// tracking. This is done after argument lowering in case the declarations
1616/// refer to arguments.
1618 FunctionVarLocs const *FnVarLocs) {
1619 for (auto It = FnVarLocs->single_locs_begin(),
1620 End = FnVarLocs->single_locs_end();
1621 It != End; ++It) {
1622 assert(!It->Values.hasArgList() && "Single loc variadic ops not supported");
1623 processDbgDeclare(FuncInfo, It->Values.getVariableLocationOp(0), It->Expr,
1624 FnVarLocs->getDILocalVariable(It->VariableID), It->DL);
1625 }
1626}
1627
1628void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) {
1629 FastISelFailed = false;
1630 // Initialize the Fast-ISel state, if needed.
1631 FastISel *FastIS = nullptr;
1633 LLVM_DEBUG(dbgs() << "Enabling fast-isel\n");
1634 FastIS = TLI->createFastISel(*FuncInfo, LibInfo);
1635 }
1636
1638
1639 // Lower arguments up front. An RPO iteration always visits the entry block
1640 // first.
1641 assert(*RPOT.begin() == &Fn.getEntryBlock());
1642 ++NumEntryBlocks;
1643
1644 // Set up FuncInfo for ISel. Entry blocks never have PHIs.
1645 FuncInfo->MBB = FuncInfo->getMBB(&Fn.getEntryBlock());
1646 FuncInfo->InsertPt = FuncInfo->MBB->begin();
1647
1649
1650 if (!FastIS) {
1651 LowerArguments(Fn);
1652 } else {
1653 // See if fast isel can lower the arguments.
1654 FastIS->startNewBlock();
1655 if (!FastIS->lowerArguments()) {
1656 FastISelFailed = true;
1657 // Fast isel failed to lower these arguments
1658 ++NumFastIselFailLowerArguments;
1659
1660 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1661 Fn.getSubprogram(),
1662 &Fn.getEntryBlock());
1663 R << "FastISel didn't lower all arguments: "
1664 << ore::NV("Prototype", Fn.getFunctionType());
1666
1667 // Use SelectionDAG argument lowering
1668 LowerArguments(Fn);
1669 CurDAG->setRoot(SDB->getControlRoot());
1670 SDB->clear();
1671 CodeGenAndEmitDAG();
1672 }
1673
1674 // If we inserted any instructions at the beginning, make a note of
1675 // where they are, so we can be sure to emit subsequent instructions
1676 // after them.
1677 if (FuncInfo->InsertPt != FuncInfo->MBB->begin())
1678 FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
1679 else
1680 FastIS->setLastLocalValue(nullptr);
1681 }
1682
1683 bool Inserted = SwiftError->createEntriesInEntryBlock(SDB->getCurDebugLoc());
1684
1685 if (FastIS && Inserted)
1686 FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
1687
1690 "expected AssignmentTrackingAnalysis pass results");
1692 } else {
1694 }
1695
1696 // Iterate over all basic blocks in the function.
1697 FuncInfo->VisitedBBs.assign(Fn.getMaxBlockNumber(), false);
1698 for (const BasicBlock *LLVMBB : RPOT) {
1700 bool AllPredsVisited = true;
1701 for (const BasicBlock *Pred : predecessors(LLVMBB)) {
1702 if (!FuncInfo->VisitedBBs[Pred->getNumber()]) {
1703 AllPredsVisited = false;
1704 break;
1705 }
1706 }
1707
1708 if (AllPredsVisited) {
1709 for (const PHINode &PN : LLVMBB->phis())
1710 FuncInfo->ComputePHILiveOutRegInfo(&PN);
1711 } else {
1712 for (const PHINode &PN : LLVMBB->phis())
1713 FuncInfo->InvalidatePHILiveOutRegInfo(&PN);
1714 }
1715
1716 FuncInfo->VisitedBBs[LLVMBB->getNumber()] = true;
1717 }
1718
1719 // Fake uses that follow tail calls are dropped. To avoid this, move
1720 // such fake uses in front of the tail call, provided they don't
1721 // use anything def'd by or after the tail call.
1722 {
1723 BasicBlock::iterator BBStart =
1724 const_cast<BasicBlock *>(LLVMBB)->getFirstNonPHIIt();
1725 BasicBlock::iterator BBEnd = const_cast<BasicBlock *>(LLVMBB)->end();
1726 preserveFakeUses(BBStart, BBEnd);
1727 }
1728
1729 BasicBlock::const_iterator const Begin = LLVMBB->getFirstNonPHIIt();
1730 BasicBlock::const_iterator const End = LLVMBB->end();
1732
1733 FuncInfo->MBB = FuncInfo->getMBB(LLVMBB);
1734 if (!FuncInfo->MBB)
1735 continue; // Some blocks like catchpads have no code or MBB.
1736
1737 // Insert new instructions after any phi or argument setup code.
1738 FuncInfo->InsertPt = FuncInfo->MBB->end();
1739
1740 // Setup an EH landing-pad block.
1741 FuncInfo->ExceptionPointerVirtReg = 0;
1742 FuncInfo->ExceptionSelectorVirtReg = 0;
1743 if (LLVMBB->isEHPad())
1744 if (!PrepareEHLandingPad())
1745 continue;
1746
1747 // Before doing SelectionDAG ISel, see if FastISel has been requested.
1748 if (FastIS) {
1749 if (LLVMBB != &Fn.getEntryBlock())
1750 FastIS->startNewBlock();
1751
1752 unsigned NumFastIselRemaining = std::distance(Begin, End);
1753
1754 // Pre-assign swifterror vregs.
1755 SwiftError->preassignVRegs(FuncInfo->MBB, Begin, End);
1756
1757 // Do FastISel on as many instructions as possible.
1758 for (; BI != Begin; --BI) {
1759 const Instruction *Inst = &*std::prev(BI);
1760
1761 // If we no longer require this instruction, skip it.
1762 if (isFoldedOrDeadInstruction(Inst, *FuncInfo) ||
1763 ElidedArgCopyInstrs.count(Inst)) {
1764 --NumFastIselRemaining;
1765 FastIS->handleDbgInfo(Inst);
1766 continue;
1767 }
1768
1769 // Bottom-up: reset the insert pos at the top, after any local-value
1770 // instructions.
1771 FastIS->recomputeInsertPt();
1772
1773 // Try to select the instruction with FastISel.
1774 if (FastIS->selectInstruction(Inst)) {
1775 --NumFastIselRemaining;
1776 ++NumFastIselSuccess;
1777
1778 FastIS->handleDbgInfo(Inst);
1779 // If fast isel succeeded, skip over all the folded instructions, and
1780 // then see if there is a load right before the selected instructions.
1781 // Try to fold the load if so.
1782 const Instruction *BeforeInst = Inst;
1783 while (BeforeInst != &*Begin) {
1784 BeforeInst = &*std::prev(BasicBlock::const_iterator(BeforeInst));
1785 if (!isFoldedOrDeadInstruction(BeforeInst, *FuncInfo))
1786 break;
1787 }
1788 if (BeforeInst != Inst && isa<LoadInst>(BeforeInst) &&
1789 BeforeInst->hasOneUse() &&
1790 FastIS->tryToFoldLoad(cast<LoadInst>(BeforeInst), Inst)) {
1791 // If we succeeded, don't re-select the load.
1793 << "FastISel folded load: " << *BeforeInst << "\n");
1794 FastIS->handleDbgInfo(BeforeInst);
1795 BI = std::next(BasicBlock::const_iterator(BeforeInst));
1796 --NumFastIselRemaining;
1797 ++NumFastIselSuccess;
1798 }
1799 continue;
1800 }
1801
1802 FastISelFailed = true;
1803
1804 // Then handle certain instructions as single-LLVM-Instruction blocks.
1805 // We cannot separate out GCrelocates to their own blocks since we need
1806 // to keep track of gc-relocates for a particular gc-statepoint. This is
1807 // done by SelectionDAGBuilder::LowerAsSTATEPOINT, called before
1808 // visitGCRelocate.
1809 if (isa<CallInst>(Inst) && !isa<GCStatepointInst>(Inst) &&
1810 !isa<GCRelocateInst>(Inst) && !isa<GCResultInst>(Inst)) {
1811 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1812 Inst->getDebugLoc(), LLVMBB);
1813
1814 R << "FastISel missed call";
1815
1816 if (R.isEnabled() || EnableFastISelAbort) {
1817 std::string InstStrStorage;
1818 raw_string_ostream InstStr(InstStrStorage);
1819 InstStr << *Inst;
1820
1821 R << ": " << InstStrStorage;
1822 }
1823
1825
1826 if (!Inst->getType()->isVoidTy() && !Inst->getType()->isTokenTy() &&
1827 !Inst->use_empty()) {
1828 Register &R = FuncInfo->ValueMap[Inst];
1829 if (!R)
1830 R = FuncInfo->CreateRegs(Inst);
1831 }
1832
1833 bool HadTailCall = false;
1834 MachineBasicBlock::iterator SavedInsertPt = FuncInfo->InsertPt;
1835 SelectBasicBlock(Inst->getIterator(), BI, HadTailCall);
1836
1837 // If the call was emitted as a tail call, we're done with the block.
1838 // We also need to delete any previously emitted instructions.
1839 if (HadTailCall) {
1840 FastIS->removeDeadCode(SavedInsertPt, FuncInfo->MBB->end());
1841 --BI;
1842 break;
1843 }
1844
1845 // Recompute NumFastIselRemaining as Selection DAG instruction
1846 // selection may have handled the call, input args, etc.
1847 unsigned RemainingNow = std::distance(Begin, BI);
1848 NumFastIselFailures += NumFastIselRemaining - RemainingNow;
1849 NumFastIselRemaining = RemainingNow;
1850 continue;
1851 }
1852
1853 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1854 Inst->getDebugLoc(), LLVMBB);
1855
1856 bool ShouldAbort = EnableFastISelAbort;
1857 if (Inst->isTerminator()) {
1858 // Use a different message for terminator misses.
1859 R << "FastISel missed terminator";
1860 // Don't abort for terminator unless the level is really high
1861 ShouldAbort = (EnableFastISelAbort > 2);
1862 } else {
1863 R << "FastISel missed";
1864 }
1865
1866 if (R.isEnabled() || EnableFastISelAbort) {
1867 std::string InstStrStorage;
1868 raw_string_ostream InstStr(InstStrStorage);
1869 InstStr << *Inst;
1870 R << ": " << InstStrStorage;
1871 }
1872
1873 reportFastISelFailure(*MF, *ORE, R, ShouldAbort);
1874
1875 NumFastIselFailures += NumFastIselRemaining;
1876 break;
1877 }
1878
1879 FastIS->recomputeInsertPt();
1880 }
1881
1882 if (SP->shouldEmitSDCheck(*LLVMBB)) {
1883 bool FunctionBasedInstrumentation =
1885 SDB->SPDescriptor.initialize(LLVMBB, FuncInfo->getMBB(LLVMBB),
1886 FunctionBasedInstrumentation);
1887 }
1888
1889 if (Begin != BI)
1890 ++NumDAGBlocks;
1891 else
1892 ++NumFastIselBlocks;
1893
1894 if (Begin != BI) {
1895 // Run SelectionDAG instruction selection on the remainder of the block
1896 // not handled by FastISel. If FastISel is not run, this is the entire
1897 // block.
1898 bool HadTailCall;
1899 SelectBasicBlock(Begin, BI, HadTailCall);
1900
1901 // But if FastISel was run, we already selected some of the block.
1902 // If we emitted a tail-call, we need to delete any previously emitted
1903 // instruction that follows it.
1904 if (FastIS && HadTailCall && FuncInfo->InsertPt != FuncInfo->MBB->end())
1905 FastIS->removeDeadCode(FuncInfo->InsertPt, FuncInfo->MBB->end());
1906 }
1907
1908 if (FastIS)
1909 FastIS->finishBasicBlock();
1910 FinishBasicBlock();
1911 FuncInfo->PHINodesToUpdate.clear();
1912 ElidedArgCopyInstrs.clear();
1913 }
1914
1915 // AsynchEH: Report Block State under -AsynchEH
1916 if (Fn.getParent()->getModuleFlag("eh-asynch"))
1917 reportIPToStateForBlocks(MF);
1918
1920
1922
1923 delete FastIS;
1924 SDB->clearDanglingDebugInfo();
1925 SDB->SPDescriptor.resetPerFunctionState();
1926}
1927
1928void
1929SelectionDAGISel::FinishBasicBlock() {
1930 LLVM_DEBUG(dbgs() << "Total amount of phi nodes to update: "
1931 << FuncInfo->PHINodesToUpdate.size() << "\n";
1932 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e;
1933 ++i) dbgs()
1934 << "Node " << i << " : (" << FuncInfo->PHINodesToUpdate[i].first
1935 << ", " << FuncInfo->PHINodesToUpdate[i].second << ")\n");
1936
1937 // Next, now that we know what the last MBB the LLVM BB expanded is, update
1938 // PHI nodes in successors.
1939 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) {
1940 MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[i].first);
1941 assert(PHI->isPHI() &&
1942 "This is not a machine PHI node that we are updating!");
1943 if (!FuncInfo->MBB->isSuccessor(PHI->getParent()))
1944 continue;
1945 PHI.addReg(FuncInfo->PHINodesToUpdate[i].second).addMBB(FuncInfo->MBB);
1946 }
1947
1948 // Handle stack protector.
1949 if (SDB->SPDescriptor.shouldEmitFunctionBasedCheckStackProtector()) {
1950 // The target provides a guard check function. There is no need to
1951 // generate error handling code or to split current basic block.
1952 MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
1953
1954 // Add load and check to the basicblock.
1955 FuncInfo->MBB = ParentMBB;
1956 FuncInfo->InsertPt =
1958 SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
1959 CurDAG->setRoot(SDB->getRoot());
1960 SDB->clear();
1961 CodeGenAndEmitDAG();
1962
1963 // Clear the Per-BB State.
1964 SDB->SPDescriptor.resetPerBBState();
1965 } else if (SDB->SPDescriptor.shouldEmitStackProtector()) {
1966 MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
1967 MachineBasicBlock *SuccessMBB = SDB->SPDescriptor.getSuccessMBB();
1968
1969 // Find the split point to split the parent mbb. At the same time copy all
1970 // physical registers used in the tail of parent mbb into virtual registers
1971 // before the split point and back into physical registers after the split
1972 // point. This prevents us needing to deal with Live-ins and many other
1973 // register allocation issues caused by us splitting the parent mbb. The
1974 // register allocator will clean up said virtual copies later on.
1975 MachineBasicBlock::iterator SplitPoint =
1977
1978 // Splice the terminator of ParentMBB into SuccessMBB.
1979 SuccessMBB->splice(SuccessMBB->end(), ParentMBB,
1980 SplitPoint,
1981 ParentMBB->end());
1982
1983 // Add compare/jump on neq/jump to the parent BB.
1984 FuncInfo->MBB = ParentMBB;
1985 FuncInfo->InsertPt = ParentMBB->end();
1986 SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
1987 CurDAG->setRoot(SDB->getRoot());
1988 SDB->clear();
1989 CodeGenAndEmitDAG();
1990
1991 // CodeGen Failure MBB if we have not codegened it yet.
1992 MachineBasicBlock *FailureMBB = SDB->SPDescriptor.getFailureMBB();
1993 if (FailureMBB->empty()) {
1994 FuncInfo->MBB = FailureMBB;
1995 FuncInfo->InsertPt = FailureMBB->end();
1996 SDB->visitSPDescriptorFailure(SDB->SPDescriptor);
1997 CurDAG->setRoot(SDB->getRoot());
1998 SDB->clear();
1999 CodeGenAndEmitDAG();
2000 }
2001
2002 // Clear the Per-BB State.
2003 SDB->SPDescriptor.resetPerBBState();
2004 }
2005
2006 // Lower each BitTestBlock.
2007 for (auto &BTB : SDB->SL->BitTestCases) {
2008 // Lower header first, if it wasn't already lowered
2009 if (!BTB.Emitted) {
2010 // Set the current basic block to the mbb we wish to insert the code into
2011 FuncInfo->MBB = BTB.Parent;
2012 FuncInfo->InsertPt = FuncInfo->MBB->end();
2013 // Emit the code
2014 SDB->visitBitTestHeader(BTB, FuncInfo->MBB);
2015 CurDAG->setRoot(SDB->getRoot());
2016 SDB->clear();
2017 CodeGenAndEmitDAG();
2018 }
2019
2020 BranchProbability UnhandledProb = BTB.Prob;
2021 for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; ++j) {
2022 UnhandledProb -= BTB.Cases[j].ExtraProb;
2023 // Set the current basic block to the mbb we wish to insert the code into
2024 FuncInfo->MBB = BTB.Cases[j].ThisBB;
2025 FuncInfo->InsertPt = FuncInfo->MBB->end();
2026 // Emit the code
2027
2028 // If all cases cover a contiguous range, it is not necessary to jump to
2029 // the default block after the last bit test fails. This is because the
2030 // range check during bit test header creation has guaranteed that every
2031 // case here doesn't go outside the range. In this case, there is no need
2032 // to perform the last bit test, as it will always be true. Instead, make
2033 // the second-to-last bit-test fall through to the target of the last bit
2034 // test, and delete the last bit test.
2035
2036 MachineBasicBlock *NextMBB;
2037 if ((BTB.ContiguousRange || BTB.FallthroughUnreachable) && j + 2 == ej) {
2038 // Second-to-last bit-test with contiguous range or omitted range
2039 // check: fall through to the target of the final bit test.
2040 NextMBB = BTB.Cases[j + 1].TargetBB;
2041 } else if (j + 1 == ej) {
2042 // For the last bit test, fall through to Default.
2043 NextMBB = BTB.Default;
2044 } else {
2045 // Otherwise, fall through to the next bit test.
2046 NextMBB = BTB.Cases[j + 1].ThisBB;
2047 }
2048
2049 SDB->visitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j],
2050 FuncInfo->MBB);
2051
2052 CurDAG->setRoot(SDB->getRoot());
2053 SDB->clear();
2054 CodeGenAndEmitDAG();
2055
2056 if ((BTB.ContiguousRange || BTB.FallthroughUnreachable) && j + 2 == ej) {
2057 // Since we're not going to use the final bit test, remove it.
2058 BTB.Cases.pop_back();
2059 break;
2060 }
2061 }
2062
2063 // Update PHI Nodes
2064 for (const std::pair<MachineInstr *, unsigned> &P :
2065 FuncInfo->PHINodesToUpdate) {
2066 MachineInstrBuilder PHI(*MF, P.first);
2067 MachineBasicBlock *PHIBB = PHI->getParent();
2068 assert(PHI->isPHI() &&
2069 "This is not a machine PHI node that we are updating!");
2070 // This is "default" BB. We have two jumps to it. From "header" BB and
2071 // from last "case" BB, unless the latter was skipped.
2072 if (PHIBB == BTB.Default) {
2073 PHI.addReg(P.second).addMBB(BTB.Parent);
2074 if (!BTB.ContiguousRange) {
2075 PHI.addReg(P.second).addMBB(BTB.Cases.back().ThisBB);
2076 }
2077 }
2078 // One of "cases" BB.
2079 for (const SwitchCG::BitTestCase &BT : BTB.Cases) {
2080 MachineBasicBlock* cBB = BT.ThisBB;
2081 if (cBB->isSuccessor(PHIBB))
2082 PHI.addReg(P.second).addMBB(cBB);
2083 }
2084 }
2085 }
2086 SDB->SL->BitTestCases.clear();
2087
2088 // If the JumpTable record is filled in, then we need to emit a jump table.
2089 // Updating the PHI nodes is tricky in this case, since we need to determine
2090 // whether the PHI is a successor of the range check MBB or the jump table MBB
2091 for (unsigned i = 0, e = SDB->SL->JTCases.size(); i != e; ++i) {
2092 // Lower header first, if it wasn't already lowered
2093 if (!SDB->SL->JTCases[i].first.Emitted) {
2094 // Set the current basic block to the mbb we wish to insert the code into
2095 FuncInfo->MBB = SDB->SL->JTCases[i].first.HeaderBB;
2096 FuncInfo->InsertPt = FuncInfo->MBB->end();
2097 // Emit the code
2098 SDB->visitJumpTableHeader(SDB->SL->JTCases[i].second,
2099 SDB->SL->JTCases[i].first, FuncInfo->MBB);
2100 CurDAG->setRoot(SDB->getRoot());
2101 SDB->clear();
2102 CodeGenAndEmitDAG();
2103 }
2104
2105 // Set the current basic block to the mbb we wish to insert the code into
2106 FuncInfo->MBB = SDB->SL->JTCases[i].second.MBB;
2107 FuncInfo->InsertPt = FuncInfo->MBB->end();
2108 // Emit the code
2109 SDB->visitJumpTable(SDB->SL->JTCases[i].second);
2110 CurDAG->setRoot(SDB->getRoot());
2111 SDB->clear();
2112 CodeGenAndEmitDAG();
2113
2114 // Update PHI Nodes
2115 for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
2116 pi != pe; ++pi) {
2117 MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
2118 MachineBasicBlock *PHIBB = PHI->getParent();
2119 assert(PHI->isPHI() &&
2120 "This is not a machine PHI node that we are updating!");
2121 // "default" BB. We can go there only from header BB.
2122 if (PHIBB == SDB->SL->JTCases[i].second.Default)
2123 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)
2124 .addMBB(SDB->SL->JTCases[i].first.HeaderBB);
2125 // JT BB. Just iterate over successors here
2126 if (FuncInfo->MBB->isSuccessor(PHIBB))
2127 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(FuncInfo->MBB);
2128 }
2129 }
2130 SDB->SL->JTCases.clear();
2131
2132 // If we generated any switch lowering information, build and codegen any
2133 // additional DAGs necessary.
2134 for (unsigned i = 0, e = SDB->SL->SwitchCases.size(); i != e; ++i) {
2135 // Set the current basic block to the mbb we wish to insert the code into
2136 FuncInfo->MBB = SDB->SL->SwitchCases[i].ThisBB;
2137 FuncInfo->InsertPt = FuncInfo->MBB->end();
2138
2139 // Determine the unique successors.
2141 Succs.push_back(SDB->SL->SwitchCases[i].TrueBB);
2142 if (SDB->SL->SwitchCases[i].TrueBB != SDB->SL->SwitchCases[i].FalseBB)
2143 Succs.push_back(SDB->SL->SwitchCases[i].FalseBB);
2144
2145 // Emit the code. Note that this could result in FuncInfo->MBB being split.
2146 SDB->visitSwitchCase(SDB->SL->SwitchCases[i], FuncInfo->MBB);
2147 CurDAG->setRoot(SDB->getRoot());
2148 SDB->clear();
2149 CodeGenAndEmitDAG();
2150
2151 // Remember the last block, now that any splitting is done, for use in
2152 // populating PHI nodes in successors.
2153 MachineBasicBlock *ThisBB = FuncInfo->MBB;
2154
2155 // Handle any PHI nodes in successors of this chunk, as if we were coming
2156 // from the original BB before switch expansion. Note that PHI nodes can
2157 // occur multiple times in PHINodesToUpdate. We have to be very careful to
2158 // handle them the right number of times.
2159 for (MachineBasicBlock *Succ : Succs) {
2160 FuncInfo->MBB = Succ;
2161 FuncInfo->InsertPt = FuncInfo->MBB->end();
2162 // FuncInfo->MBB may have been removed from the CFG if a branch was
2163 // constant folded.
2164 if (ThisBB->isSuccessor(FuncInfo->MBB)) {
2166 MBBI = FuncInfo->MBB->begin(), MBBE = FuncInfo->MBB->end();
2167 MBBI != MBBE && MBBI->isPHI(); ++MBBI) {
2169 // This value for this PHI node is recorded in PHINodesToUpdate.
2170 for (unsigned pn = 0; ; ++pn) {
2171 assert(pn != FuncInfo->PHINodesToUpdate.size() &&
2172 "Didn't find PHI entry!");
2173 if (FuncInfo->PHINodesToUpdate[pn].first == PHI) {
2174 PHI.addReg(FuncInfo->PHINodesToUpdate[pn].second).addMBB(ThisBB);
2175 break;
2176 }
2177 }
2178 }
2179 }
2180 }
2181 }
2182 SDB->SL->SwitchCases.clear();
2183}
2184
2185/// Create the scheduler. If a specific scheduler was specified
2186/// via the SchedulerRegistry, use it, otherwise select the
2187/// one preferred by the target.
2188///
2189ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {
2190 return ISHeuristic(this, OptLevel);
2191}
2192
2193//===----------------------------------------------------------------------===//
2194// Helper functions used by the generated instruction selector.
2195//===----------------------------------------------------------------------===//
2196// Calls to these methods are generated by tblgen.
2197
2198/// CheckAndMask - The isel is trying to match something like (and X, 255). If
2199/// the dag combiner simplified the 255, we still want to match. RHS is the
2200/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
2201/// specified in the .td file (e.g. 255).
2203 int64_t DesiredMaskS) const {
2204 const APInt &ActualMask = RHS->getAPIntValue();
2205 // TODO: Avoid implicit trunc?
2206 // See https://github.com/llvm/llvm-project/issues/112510.
2207 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS,
2208 /*isSigned=*/false, /*implicitTrunc=*/true);
2209
2210 // If the actual mask exactly matches, success!
2211 if (ActualMask == DesiredMask)
2212 return true;
2213
2214 // If the actual AND mask is allowing unallowed bits, this doesn't match.
2215 if (!ActualMask.isSubsetOf(DesiredMask))
2216 return false;
2217
2218 // Otherwise, the DAG Combiner may have proven that the value coming in is
2219 // either already zero or is not demanded. Check for known zero input bits.
2220 APInt NeededMask = DesiredMask & ~ActualMask;
2221 if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
2222 return true;
2223
2224 // TODO: check to see if missing bits are just not demanded.
2225
2226 // Otherwise, this pattern doesn't match.
2227 return false;
2228}
2229
2230/// CheckOrMask - The isel is trying to match something like (or X, 255). If
2231/// the dag combiner simplified the 255, we still want to match. RHS is the
2232/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
2233/// specified in the .td file (e.g. 255).
2235 int64_t DesiredMaskS) const {
2236 const APInt &ActualMask = RHS->getAPIntValue();
2237 // TODO: Avoid implicit trunc?
2238 // See https://github.com/llvm/llvm-project/issues/112510.
2239 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS,
2240 /*isSigned=*/false, /*implicitTrunc=*/true);
2241
2242 // If the actual mask exactly matches, success!
2243 if (ActualMask == DesiredMask)
2244 return true;
2245
2246 // If the actual AND mask is allowing unallowed bits, this doesn't match.
2247 if (!ActualMask.isSubsetOf(DesiredMask))
2248 return false;
2249
2250 // Otherwise, the DAG Combiner may have proven that the value coming in is
2251 // either already zero or is not demanded. Check for known zero input bits.
2252 APInt NeededMask = DesiredMask & ~ActualMask;
2254
2255 // If all the missing bits in the or are already known to be set, match!
2256 if (NeededMask.isSubsetOf(Known.One))
2257 return true;
2258
2259 // TODO: check to see if missing bits are just not demanded.
2260
2261 // Otherwise, this pattern doesn't match.
2262 return false;
2263}
2264
2265/// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
2266/// by tblgen. Others should not call it.
2268 const SDLoc &DL) {
2269 // Change the vector of SDValue into a list of SDNodeHandle for x86 might call
2270 // replaceAllUses when matching address.
2271
2272 std::list<HandleSDNode> Handles;
2273
2274 Handles.emplace_back(Ops[InlineAsm::Op_InputChain]); // 0
2275 Handles.emplace_back(Ops[InlineAsm::Op_AsmString]); // 1
2276 Handles.emplace_back(Ops[InlineAsm::Op_MDNode]); // 2, !srcloc
2277 Handles.emplace_back(
2278 Ops[InlineAsm::Op_ExtraInfo]); // 3 (SideEffect, AlignStack)
2279
2280 unsigned i = InlineAsm::Op_FirstOperand, e = Ops.size();
2281 if (Ops[e - 1].getValueType() == MVT::Glue)
2282 --e; // Don't process a glue operand if it is here.
2283
2284 while (i != e) {
2285 InlineAsm::Flag Flags(Ops[i]->getAsZExtVal());
2286 if (!Flags.isMemKind() && !Flags.isFuncKind()) {
2287 // Just skip over this operand, copying the operands verbatim.
2288 Handles.insert(Handles.end(), Ops.begin() + i,
2289 Ops.begin() + i + Flags.getNumOperandRegisters() + 1);
2290 i += Flags.getNumOperandRegisters() + 1;
2291 } else {
2292 assert(Flags.getNumOperandRegisters() == 1 &&
2293 "Memory operand with multiple values?");
2294
2295 unsigned TiedToOperand;
2296 if (Flags.isUseOperandTiedToDef(TiedToOperand)) {
2297 // We need the constraint ID from the operand this is tied to.
2298 unsigned CurOp = InlineAsm::Op_FirstOperand;
2299 Flags = InlineAsm::Flag(Ops[CurOp]->getAsZExtVal());
2300 for (; TiedToOperand; --TiedToOperand) {
2301 CurOp += Flags.getNumOperandRegisters() + 1;
2302 Flags = InlineAsm::Flag(Ops[CurOp]->getAsZExtVal());
2303 }
2304 }
2305
2306 // Otherwise, this is a memory operand. Ask the target to select it.
2307 std::vector<SDValue> SelOps;
2308 const InlineAsm::ConstraintCode ConstraintID =
2309 Flags.getMemoryConstraintID();
2310 if (SelectInlineAsmMemoryOperand(Ops[i + 1], ConstraintID, SelOps))
2311 report_fatal_error("Could not match memory address. Inline asm"
2312 " failure!");
2313
2314 // Add this to the output node.
2315 Flags = InlineAsm::Flag(Flags.isMemKind() ? InlineAsm::Kind::Mem
2317 SelOps.size());
2318 Flags.setMemConstraint(ConstraintID);
2319 Handles.emplace_back(CurDAG->getTargetConstant(Flags, DL, MVT::i32));
2320 Handles.insert(Handles.end(), SelOps.begin(), SelOps.end());
2321 i += 2;
2322 }
2323 }
2324
2325 // Add the glue input back if present.
2326 if (e != Ops.size())
2327 Handles.emplace_back(Ops.back());
2328
2329 Ops.clear();
2330 for (auto &handle : Handles)
2331 Ops.push_back(handle.getValue());
2332}
2333
2334/// findNonImmUse - Return true if "Def" is a predecessor of "Root" via a path
2335/// beyond "ImmedUse". We may ignore chains as they are checked separately.
2336static bool findNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse,
2337 bool IgnoreChains) {
2340 // Only check if we have non-immediate uses of Def.
2341 if (ImmedUse->isOnlyUserOf(Def))
2342 return false;
2343
2344 // We don't care about paths to Def that go through ImmedUse so mark it
2345 // visited and mark non-def operands as used.
2346 Visited.insert(ImmedUse);
2347 for (const SDValue &Op : ImmedUse->op_values()) {
2348 SDNode *N = Op.getNode();
2349 // Ignore chain deps (they are validated by
2350 // HandleMergeInputChains) and immediate uses
2351 if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)
2352 continue;
2353 if (!Visited.insert(N).second)
2354 continue;
2355 WorkList.push_back(N);
2356 }
2357
2358 // Initialize worklist to operands of Root.
2359 if (Root != ImmedUse) {
2360 for (const SDValue &Op : Root->op_values()) {
2361 SDNode *N = Op.getNode();
2362 // Ignore chains (they are validated by HandleMergeInputChains)
2363 if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)
2364 continue;
2365 if (!Visited.insert(N).second)
2366 continue;
2367 WorkList.push_back(N);
2368 }
2369 }
2370
2371 return SDNode::hasPredecessorHelper(Def, Visited, WorkList, 0, true);
2372}
2373
2374/// IsProfitableToFold - Returns true if it's profitable to fold the specific
2375/// operand node N of U during instruction selection that starts at Root.
2377 SDNode *Root) const {
2379 return false;
2380 return N.hasOneUse();
2381}
2382
2383/// IsLegalToFold - Returns true if the specific operand node N of
2384/// U can be folded during instruction selection that starts at Root.
2386 CodeGenOptLevel OptLevel,
2387 bool IgnoreChains) {
2389 return false;
2390
2391 // If Root use can somehow reach N through a path that doesn't contain
2392 // U then folding N would create a cycle. e.g. In the following
2393 // diagram, Root can reach N through X. If N is folded into Root, then
2394 // X is both a predecessor and a successor of U.
2395 //
2396 // [N*] //
2397 // ^ ^ //
2398 // / \ //
2399 // [U*] [X]? //
2400 // ^ ^ //
2401 // \ / //
2402 // \ / //
2403 // [Root*] //
2404 //
2405 // * indicates nodes to be folded together.
2406 //
2407 // If Root produces glue, then it gets (even more) interesting. Since it
2408 // will be "glued" together with its glue use in the scheduler, we need to
2409 // check if it might reach N.
2410 //
2411 // [N*] //
2412 // ^ ^ //
2413 // / \ //
2414 // [U*] [X]? //
2415 // ^ ^ //
2416 // \ \ //
2417 // \ | //
2418 // [Root*] | //
2419 // ^ | //
2420 // f | //
2421 // | / //
2422 // [Y] / //
2423 // ^ / //
2424 // f / //
2425 // | / //
2426 // [GU] //
2427 //
2428 // If GU (glue use) indirectly reaches N (the load), and Root folds N
2429 // (call it Fold), then X is a predecessor of GU and a successor of
2430 // Fold. But since Fold and GU are glued together, this will create
2431 // a cycle in the scheduling graph.
2432
2433 // If the node has glue, walk down the graph to the "lowest" node in the
2434 // glueged set.
2435 EVT VT = Root->getValueType(Root->getNumValues()-1);
2436 while (VT == MVT::Glue) {
2437 SDNode *GU = Root->getGluedUser();
2438 if (!GU)
2439 break;
2440 Root = GU;
2441 VT = Root->getValueType(Root->getNumValues()-1);
2442
2443 // If our query node has a glue result with a use, we've walked up it. If
2444 // the user (which has already been selected) has a chain or indirectly uses
2445 // the chain, HandleMergeInputChains will not consider it. Because of
2446 // this, we cannot ignore chains in this predicate.
2447 IgnoreChains = false;
2448 }
2449
2450 return !findNonImmUse(Root, N.getNode(), U, IgnoreChains);
2451}
2452
2453void SelectionDAGISel::Select_INLINEASM(SDNode *N) {
2454 SDLoc DL(N);
2455
2456 std::vector<SDValue> Ops(N->op_begin(), N->op_end());
2458
2459 const EVT VTs[] = {MVT::Other, MVT::Glue};
2460 SDValue New = CurDAG->getNode(N->getOpcode(), DL, VTs, Ops);
2461 New->setNodeId(-1);
2462 ReplaceUses(N, New.getNode());
2464}
2465
2466void SelectionDAGISel::Select_READ_REGISTER(SDNode *Op) {
2467 SDLoc dl(Op);
2468 MDNodeSDNode *MD = cast<MDNodeSDNode>(Op->getOperand(1));
2469 const MDString *RegStr = cast<MDString>(MD->getMD()->getOperand(0));
2470
2471 EVT VT = Op->getValueType(0);
2472 LLT Ty = VT.isSimple() ? getLLTForMVT(VT.getSimpleVT()) : LLT();
2473 Register Reg =
2474 TLI->getRegisterByName(RegStr->getString().data(), Ty,
2477 Op->getOperand(0), dl, Reg, Op->getValueType(0));
2478 New->setNodeId(-1);
2479 ReplaceUses(Op, New.getNode());
2481}
2482
2483void SelectionDAGISel::Select_WRITE_REGISTER(SDNode *Op) {
2484 SDLoc dl(Op);
2485 MDNodeSDNode *MD = cast<MDNodeSDNode>(Op->getOperand(1));
2486 const MDString *RegStr = cast<MDString>(MD->getMD()->getOperand(0));
2487
2488 EVT VT = Op->getOperand(2).getValueType();
2489 LLT Ty = VT.isSimple() ? getLLTForMVT(VT.getSimpleVT()) : LLT();
2490
2491 Register Reg = TLI->getRegisterByName(RegStr->getString().data(), Ty,
2494 Op->getOperand(0), dl, Reg, Op->getOperand(2));
2495 New->setNodeId(-1);
2496 ReplaceUses(Op, New.getNode());
2498}
2499
2500void SelectionDAGISel::Select_UNDEF(SDNode *N) {
2501 CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF, N->getValueType(0));
2502}
2503
2504// Use the generic target FAKE_USE target opcode. The chain operand
2505// must come last, because InstrEmitter::AddOperand() requires it.
2506void SelectionDAGISel::Select_FAKE_USE(SDNode *N) {
2507 CurDAG->SelectNodeTo(N, TargetOpcode::FAKE_USE, N->getValueType(0),
2508 N->getOperand(1), N->getOperand(0));
2509}
2510
2511void SelectionDAGISel::Select_FREEZE(SDNode *N) {
2512 // TODO: We don't have FREEZE pseudo-instruction in MachineInstr-level now.
2513 // If FREEZE instruction is added later, the code below must be changed as
2514 // well.
2515 CurDAG->SelectNodeTo(N, TargetOpcode::COPY, N->getValueType(0),
2516 N->getOperand(0));
2517}
2518
2519void SelectionDAGISel::Select_ARITH_FENCE(SDNode *N) {
2520 CurDAG->SelectNodeTo(N, TargetOpcode::ARITH_FENCE, N->getValueType(0),
2521 N->getOperand(0));
2522}
2523
2524void SelectionDAGISel::Select_MEMBARRIER(SDNode *N) {
2525 CurDAG->SelectNodeTo(N, TargetOpcode::MEMBARRIER, N->getValueType(0),
2526 N->getOperand(0));
2527}
2528
2529void SelectionDAGISel::Select_CONVERGENCECTRL_ANCHOR(SDNode *N) {
2530 CurDAG->SelectNodeTo(N, TargetOpcode::CONVERGENCECTRL_ANCHOR,
2531 N->getValueType(0));
2532}
2533
2534void SelectionDAGISel::Select_CONVERGENCECTRL_ENTRY(SDNode *N) {
2535 CurDAG->SelectNodeTo(N, TargetOpcode::CONVERGENCECTRL_ENTRY,
2536 N->getValueType(0));
2537}
2538
2539void SelectionDAGISel::Select_CONVERGENCECTRL_LOOP(SDNode *N) {
2540 CurDAG->SelectNodeTo(N, TargetOpcode::CONVERGENCECTRL_LOOP,
2541 N->getValueType(0), N->getOperand(0));
2542}
2543
2544void SelectionDAGISel::pushStackMapLiveVariable(SmallVectorImpl<SDValue> &Ops,
2545 SDValue OpVal, SDLoc DL) {
2546 SDNode *OpNode = OpVal.getNode();
2547
2548 // FrameIndex nodes should have been directly emitted to TargetFrameIndex
2549 // nodes at DAG-construction time.
2550 assert(OpNode->getOpcode() != ISD::FrameIndex);
2551
2552 if (OpNode->getOpcode() == ISD::Constant) {
2553 Ops.push_back(
2554 CurDAG->getTargetConstant(StackMaps::ConstantOp, DL, MVT::i64));
2556 OpVal.getValueType()));
2557 } else {
2558 Ops.push_back(OpVal);
2559 }
2560}
2561
2562void SelectionDAGISel::Select_STACKMAP(SDNode *N) {
2564 auto *It = N->op_begin();
2565 SDLoc DL(N);
2566
2567 // Stash the chain and glue operands so we can move them to the end.
2568 SDValue Chain = *It++;
2569 SDValue InGlue = *It++;
2570
2571 // <id> operand.
2572 SDValue ID = *It++;
2573 assert(ID.getValueType() == MVT::i64);
2574 Ops.push_back(ID);
2575
2576 // <numShadowBytes> operand.
2577 SDValue Shad = *It++;
2578 assert(Shad.getValueType() == MVT::i32);
2579 Ops.push_back(Shad);
2580
2581 // Live variable operands.
2582 for (; It != N->op_end(); It++)
2583 pushStackMapLiveVariable(Ops, *It, DL);
2584
2585 Ops.push_back(Chain);
2586 Ops.push_back(InGlue);
2587
2588 SDVTList NodeTys = CurDAG->getVTList(MVT::Other, MVT::Glue);
2589 CurDAG->SelectNodeTo(N, TargetOpcode::STACKMAP, NodeTys, Ops);
2590}
2591
2592void SelectionDAGISel::Select_PATCHPOINT(SDNode *N) {
2594 auto *It = N->op_begin();
2595 SDLoc DL(N);
2596
2597 // Cache arguments that will be moved to the end in the target node.
2598 SDValue Chain = *It++;
2599 std::optional<SDValue> Glue;
2600 if (It->getValueType() == MVT::Glue)
2601 Glue = *It++;
2602 SDValue RegMask = *It++;
2603
2604 // <id> operand.
2605 SDValue ID = *It++;
2606 assert(ID.getValueType() == MVT::i64);
2607 Ops.push_back(ID);
2608
2609 // <numShadowBytes> operand.
2610 SDValue Shad = *It++;
2611 assert(Shad.getValueType() == MVT::i32);
2612 Ops.push_back(Shad);
2613
2614 // Add the callee.
2615 Ops.push_back(*It++);
2616
2617 // Add <numArgs>.
2618 SDValue NumArgs = *It++;
2619 assert(NumArgs.getValueType() == MVT::i32);
2620 Ops.push_back(NumArgs);
2621
2622 // Calling convention.
2623 Ops.push_back(*It++);
2624
2625 // Push the args for the call.
2626 for (uint64_t I = NumArgs->getAsZExtVal(); I != 0; I--)
2627 Ops.push_back(*It++);
2628
2629 // Now push the live variables.
2630 for (; It != N->op_end(); It++)
2631 pushStackMapLiveVariable(Ops, *It, DL);
2632
2633 // Finally, the regmask, chain and (if present) glue are moved to the end.
2634 Ops.push_back(RegMask);
2635 Ops.push_back(Chain);
2636 if (Glue.has_value())
2637 Ops.push_back(*Glue);
2638
2639 SDVTList NodeTys = N->getVTList();
2640 CurDAG->SelectNodeTo(N, TargetOpcode::PATCHPOINT, NodeTys, Ops);
2641}
2642
2643/// GetVBR - decode a vbr encoding whose top bit is set.
2645GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {
2646 assert(Val >= 128 && "Not a VBR");
2647 Val &= 127; // Remove first vbr bit.
2648
2649 unsigned Shift = 7;
2650 uint64_t NextBits;
2651 do {
2652 NextBits = MatcherTable[Idx++];
2653 Val |= (NextBits&127) << Shift;
2654 Shift += 7;
2655 } while (NextBits & 128);
2656
2657 return Val;
2658}
2659
2660/// getSimpleVT - Decode a value in MatcherTable, if it's a VBR encoded value,
2661/// use GetVBR to decode it.
2663getSimpleVT(const unsigned char *MatcherTable, unsigned &MatcherIndex) {
2664 unsigned SimpleVT = MatcherTable[MatcherIndex++];
2665 if (SimpleVT & 128)
2666 SimpleVT = GetVBR(SimpleVT, MatcherTable, MatcherIndex);
2667
2668 return static_cast<MVT::SimpleValueType>(SimpleVT);
2669}
2670
2671void SelectionDAGISel::Select_JUMP_TABLE_DEBUG_INFO(SDNode *N) {
2672 SDLoc dl(N);
2673 CurDAG->SelectNodeTo(N, TargetOpcode::JUMP_TABLE_DEBUG_INFO, MVT::Glue,
2674 CurDAG->getTargetConstant(N->getConstantOperandVal(1),
2675 dl, MVT::i64, true));
2676}
2677
2678/// When a match is complete, this method updates uses of interior chain results
2679/// to use the new results.
2680void SelectionDAGISel::UpdateChains(
2681 SDNode *NodeToMatch, SDValue InputChain,
2682 SmallVectorImpl<SDNode *> &ChainNodesMatched, bool isMorphNodeTo) {
2683 SmallVector<SDNode*, 4> NowDeadNodes;
2684
2685 // Now that all the normal results are replaced, we replace the chain and
2686 // glue results if present.
2687 if (!ChainNodesMatched.empty()) {
2688 assert(InputChain.getNode() &&
2689 "Matched input chains but didn't produce a chain");
2690 // Loop over all of the nodes we matched that produced a chain result.
2691 // Replace all the chain results with the final chain we ended up with.
2692 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2693 SDNode *ChainNode = ChainNodesMatched[i];
2694 // If ChainNode is null, it's because we replaced it on a previous
2695 // iteration and we cleared it out of the map. Just skip it.
2696 if (!ChainNode)
2697 continue;
2698
2699 assert(ChainNode->getOpcode() != ISD::DELETED_NODE &&
2700 "Deleted node left in chain");
2701
2702 // Don't replace the results of the root node if we're doing a
2703 // MorphNodeTo.
2704 if (ChainNode == NodeToMatch && isMorphNodeTo)
2705 continue;
2706
2707 SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);
2708 if (ChainVal.getValueType() == MVT::Glue)
2709 ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
2710 assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
2712 *CurDAG, [&](SDNode *N, SDNode *E) {
2713 std::replace(ChainNodesMatched.begin(), ChainNodesMatched.end(), N,
2714 static_cast<SDNode *>(nullptr));
2715 });
2716 if (ChainNode->getOpcode() != ISD::TokenFactor)
2717 ReplaceUses(ChainVal, InputChain);
2718
2719 // If the node became dead and we haven't already seen it, delete it.
2720 if (ChainNode != NodeToMatch && ChainNode->use_empty() &&
2721 !llvm::is_contained(NowDeadNodes, ChainNode))
2722 NowDeadNodes.push_back(ChainNode);
2723 }
2724 }
2725
2726 if (!NowDeadNodes.empty())
2727 CurDAG->RemoveDeadNodes(NowDeadNodes);
2728
2729 LLVM_DEBUG(dbgs() << "ISEL: Match complete!\n");
2730}
2731
2732/// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
2733/// operation for when the pattern matched at least one node with a chains. The
2734/// input vector contains a list of all of the chained nodes that we match. We
2735/// must determine if this is a valid thing to cover (i.e. matching it won't
2736/// induce cycles in the DAG) and if so, creating a TokenFactor node. that will
2737/// be used as the input node chain for the generated nodes.
2738static SDValue
2740 SelectionDAG *CurDAG) {
2741
2744 SmallVector<SDValue, 3> InputChains;
2745 unsigned int Max = 8192;
2746
2747 // Quick exit on trivial merge.
2748 if (ChainNodesMatched.size() == 1)
2749 return ChainNodesMatched[0]->getOperand(0);
2750
2751 // Add chains that aren't already added (internal). Peek through
2752 // token factors.
2753 std::function<void(const SDValue)> AddChains = [&](const SDValue V) {
2754 if (V.getValueType() != MVT::Other)
2755 return;
2756 if (V->getOpcode() == ISD::EntryToken)
2757 return;
2758 if (!Visited.insert(V.getNode()).second)
2759 return;
2760 if (V->getOpcode() == ISD::TokenFactor) {
2761 for (const SDValue &Op : V->op_values())
2762 AddChains(Op);
2763 } else
2764 InputChains.push_back(V);
2765 };
2766
2767 for (auto *N : ChainNodesMatched) {
2768 Worklist.push_back(N);
2769 Visited.insert(N);
2770 }
2771
2772 while (!Worklist.empty())
2773 AddChains(Worklist.pop_back_val()->getOperand(0));
2774
2775 // Skip the search if there are no chain dependencies.
2776 if (InputChains.size() == 0)
2777 return CurDAG->getEntryNode();
2778
2779 // If one of these chains is a successor of input, we must have a
2780 // node that is both the predecessor and successor of the
2781 // to-be-merged nodes. Fail.
2782 Visited.clear();
2783 for (SDValue V : InputChains)
2784 Worklist.push_back(V.getNode());
2785
2786 for (auto *N : ChainNodesMatched)
2787 if (SDNode::hasPredecessorHelper(N, Visited, Worklist, Max, true))
2788 return SDValue();
2789
2790 // Return merged chain.
2791 if (InputChains.size() == 1)
2792 return InputChains[0];
2793 return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]),
2794 MVT::Other, InputChains);
2795}
2796
2797/// MorphNode - Handle morphing a node in place for the selector.
2798SDNode *SelectionDAGISel::
2799MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
2800 ArrayRef<SDValue> Ops, unsigned EmitNodeInfo) {
2801 // It is possible we're using MorphNodeTo to replace a node with no
2802 // normal results with one that has a normal result (or we could be
2803 // adding a chain) and the input could have glue and chains as well.
2804 // In this case we need to shift the operands down.
2805 // FIXME: This is a horrible hack and broken in obscure cases, no worse
2806 // than the old isel though.
2807 int OldGlueResultNo = -1, OldChainResultNo = -1;
2808
2809 unsigned NTMNumResults = Node->getNumValues();
2810 if (Node->getValueType(NTMNumResults-1) == MVT::Glue) {
2811 OldGlueResultNo = NTMNumResults-1;
2812 if (NTMNumResults != 1 &&
2813 Node->getValueType(NTMNumResults-2) == MVT::Other)
2814 OldChainResultNo = NTMNumResults-2;
2815 } else if (Node->getValueType(NTMNumResults-1) == MVT::Other)
2816 OldChainResultNo = NTMNumResults-1;
2817
2818 // Call the underlying SelectionDAG routine to do the transmogrification. Note
2819 // that this deletes operands of the old node that become dead.
2820 SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops);
2821
2822 // MorphNodeTo can operate in two ways: if an existing node with the
2823 // specified operands exists, it can just return it. Otherwise, it
2824 // updates the node in place to have the requested operands.
2825 if (Res == Node) {
2826 // If we updated the node in place, reset the node ID. To the isel,
2827 // this should be just like a newly allocated machine node.
2828 Res->setNodeId(-1);
2829 }
2830
2831 unsigned ResNumResults = Res->getNumValues();
2832 // Move the glue if needed.
2833 if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 &&
2834 static_cast<unsigned>(OldGlueResultNo) != ResNumResults - 1)
2835 ReplaceUses(SDValue(Node, OldGlueResultNo),
2836 SDValue(Res, ResNumResults - 1));
2837
2838 if ((EmitNodeInfo & OPFL_GlueOutput) != 0)
2839 --ResNumResults;
2840
2841 // Move the chain reference if needed.
2842 if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
2843 static_cast<unsigned>(OldChainResultNo) != ResNumResults - 1)
2844 ReplaceUses(SDValue(Node, OldChainResultNo),
2845 SDValue(Res, ResNumResults - 1));
2846
2847 // Otherwise, no replacement happened because the node already exists. Replace
2848 // Uses of the old node with the new one.
2849 if (Res != Node) {
2850 ReplaceNode(Node, Res);
2851 } else {
2853 }
2854
2855 return Res;
2856}
2857
2858/// CheckSame - Implements OP_CheckSame.
2860CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2861 const SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes) {
2862 // Accept if it is exactly the same as a previously recorded node.
2863 unsigned RecNo = MatcherTable[MatcherIndex++];
2864 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2865 return N == RecordedNodes[RecNo].first;
2866}
2867
2868/// CheckChildSame - Implements OP_CheckChildXSame.
2870 const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2871 const SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes,
2872 unsigned ChildNo) {
2873 if (ChildNo >= N.getNumOperands())
2874 return false; // Match fails if out of range child #.
2875 return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo),
2876 RecordedNodes);
2877}
2878
2879/// CheckPatternPredicate - Implements OP_CheckPatternPredicate.
2881CheckPatternPredicate(unsigned Opcode, const unsigned char *MatcherTable,
2882 unsigned &MatcherIndex, const SelectionDAGISel &SDISel) {
2883 bool TwoBytePredNo =
2885 unsigned PredNo =
2886 TwoBytePredNo || Opcode == SelectionDAGISel::OPC_CheckPatternPredicate
2887 ? MatcherTable[MatcherIndex++]
2889 if (TwoBytePredNo)
2890 PredNo |= MatcherTable[MatcherIndex++] << 8;
2891 return SDISel.CheckPatternPredicate(PredNo);
2892}
2893
2894/// CheckNodePredicate - Implements OP_CheckNodePredicate.
2896CheckNodePredicate(unsigned Opcode, const unsigned char *MatcherTable,
2897 unsigned &MatcherIndex, const SelectionDAGISel &SDISel,
2898 SDNode *N) {
2899 unsigned PredNo = Opcode == SelectionDAGISel::OPC_CheckPredicate
2900 ? MatcherTable[MatcherIndex++]
2902 return SDISel.CheckNodePredicate(N, PredNo);
2903}
2904
2906CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2907 SDNode *N) {
2908 uint16_t Opc = MatcherTable[MatcherIndex++];
2909 Opc |= static_cast<uint16_t>(MatcherTable[MatcherIndex++]) << 8;
2910 return N->getOpcode() == Opc;
2911}
2912
2914 SDValue N,
2915 const TargetLowering *TLI,
2916 const DataLayout &DL) {
2917 if (N.getValueType() == VT)
2918 return true;
2919
2920 // Handle the case when VT is iPTR.
2921 return VT == MVT::iPTR && N.getValueType() == TLI->getPointerTy(DL);
2922}
2923
2926 const DataLayout &DL, unsigned ChildNo) {
2927 if (ChildNo >= N.getNumOperands())
2928 return false; // Match fails if out of range child #.
2929 return ::CheckType(VT, N.getOperand(ChildNo), TLI, DL);
2930}
2931
2933CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2934 SDValue N) {
2935 return cast<CondCodeSDNode>(N)->get() ==
2936 static_cast<ISD::CondCode>(MatcherTable[MatcherIndex++]);
2937}
2938
2940CheckChild2CondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2941 SDValue N) {
2942 if (2 >= N.getNumOperands())
2943 return false;
2944 return ::CheckCondCode(MatcherTable, MatcherIndex, N.getOperand(2));
2945}
2946
2948CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2949 SDValue N, const TargetLowering *TLI, const DataLayout &DL) {
2950 MVT::SimpleValueType VT = getSimpleVT(MatcherTable, MatcherIndex);
2951 if (cast<VTSDNode>(N)->getVT() == VT)
2952 return true;
2953
2954 // Handle the case when VT is iPTR.
2955 return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI->getPointerTy(DL);
2956}
2957
2958// Bit 0 stores the sign of the immediate. The upper bits contain the magnitude
2959// shifted left by 1.
2961 if ((V & 1) == 0)
2962 return V >> 1;
2963 if (V != 1)
2964 return -(V >> 1);
2965 // There is no such thing as -0 with integers. "-0" really means MININT.
2966 return 1ULL << 63;
2967}
2968
2970CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2971 SDValue N) {
2972 int64_t Val = MatcherTable[MatcherIndex++];
2973 if (Val & 128)
2974 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2975
2976 Val = decodeSignRotatedValue(Val);
2977
2978 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N);
2979 return C && C->getAPIntValue().trySExtValue() == Val;
2980}
2981
2983CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2984 SDValue N, unsigned ChildNo) {
2985 if (ChildNo >= N.getNumOperands())
2986 return false; // Match fails if out of range child #.
2987 return ::CheckInteger(MatcherTable, MatcherIndex, N.getOperand(ChildNo));
2988}
2989
2991CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2992 SDValue N, const SelectionDAGISel &SDISel) {
2993 int64_t Val = MatcherTable[MatcherIndex++];
2994 if (Val & 128)
2995 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2996
2997 if (N->getOpcode() != ISD::AND) return false;
2998
2999 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
3000 return C && SDISel.CheckAndMask(N.getOperand(0), C, Val);
3001}
3002
3004CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
3005 const SelectionDAGISel &SDISel) {
3006 int64_t Val = MatcherTable[MatcherIndex++];
3007 if (Val & 128)
3008 Val = GetVBR(Val, MatcherTable, MatcherIndex);
3009
3010 if (N->getOpcode() != ISD::OR) return false;
3011
3012 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
3013 return C && SDISel.CheckOrMask(N.getOperand(0), C, Val);
3014}
3015
3016/// IsPredicateKnownToFail - If we know how and can do so without pushing a
3017/// scope, evaluate the current node. If the current predicate is known to
3018/// fail, set Result=true and return anything. If the current predicate is
3019/// known to pass, set Result=false and return the MatcherIndex to continue
3020/// with. If the current predicate is unknown, set Result=false and return the
3021/// MatcherIndex to continue with.
3022static unsigned IsPredicateKnownToFail(const unsigned char *Table,
3023 unsigned Index, SDValue N,
3024 bool &Result,
3025 const SelectionDAGISel &SDISel,
3026 SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) {
3027 unsigned Opcode = Table[Index++];
3028 switch (Opcode) {
3029 default:
3030 Result = false;
3031 return Index-1; // Could not evaluate this predicate.
3033 Result = !::CheckSame(Table, Index, N, RecordedNodes);
3034 return Index;
3039 Result = !::CheckChildSame(Table, Index, N, RecordedNodes,
3040 Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Same);
3041 return Index;
3052 Result = !::CheckPatternPredicate(Opcode, Table, Index, SDISel);
3053 return Index;
3063 Result = !::CheckNodePredicate(Opcode, Table, Index, SDISel, N.getNode());
3064 return Index;
3066 Result = !::CheckOpcode(Table, Index, N.getNode());
3067 return Index;
3072 switch (Opcode) {
3074 VT = MVT::i32;
3075 break;
3077 VT = MVT::i64;
3078 break;
3079 default:
3080 VT = getSimpleVT(Table, Index);
3081 break;
3082 }
3083 Result = !::CheckType(VT, N, SDISel.TLI, SDISel.CurDAG->getDataLayout());
3084 return Index;
3085 }
3087 unsigned Res = Table[Index++];
3088 Result = !::CheckType(getSimpleVT(Table, Index), N.getValue(Res),
3089 SDISel.TLI, SDISel.CurDAG->getDataLayout());
3090 return Index;
3091 }
3117 unsigned ChildNo;
3120 VT = MVT::i32;
3122 } else if (Opcode >= SelectionDAGISel::OPC_CheckChild0TypeI64 &&
3124 VT = MVT::i64;
3126 } else {
3127 VT = getSimpleVT(Table, Index);
3128 ChildNo = Opcode - SelectionDAGISel::OPC_CheckChild0Type;
3129 }
3130 Result = !::CheckChildType(VT, N, SDISel.TLI,
3131 SDISel.CurDAG->getDataLayout(), ChildNo);
3132 return Index;
3133 }
3135 Result = !::CheckCondCode(Table, Index, N);
3136 return Index;
3138 Result = !::CheckChild2CondCode(Table, Index, N);
3139 return Index;
3141 Result = !::CheckValueType(Table, Index, N, SDISel.TLI,
3142 SDISel.CurDAG->getDataLayout());
3143 return Index;
3145 Result = !::CheckInteger(Table, Index, N);
3146 return Index;
3152 Result = !::CheckChildInteger(Table, Index, N,
3154 return Index;
3156 Result = !::CheckAndImm(Table, Index, N, SDISel);
3157 return Index;
3159 Result = !::CheckOrImm(Table, Index, N, SDISel);
3160 return Index;
3161 }
3162}
3163
3164namespace {
3165
3166struct MatchScope {
3167 /// FailIndex - If this match fails, this is the index to continue with.
3168 unsigned FailIndex;
3169
3170 /// NodeStack - The node stack when the scope was formed.
3171 SmallVector<SDValue, 4> NodeStack;
3172
3173 /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
3174 unsigned NumRecordedNodes;
3175
3176 /// NumMatchedMemRefs - The number of matched memref entries.
3177 unsigned NumMatchedMemRefs;
3178
3179 /// InputChain/InputGlue - The current chain/glue
3180 SDValue InputChain, InputGlue;
3181
3182 /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.
3183 bool HasChainNodesMatched;
3184};
3185
3186/// \A DAG update listener to keep the matching state
3187/// (i.e. RecordedNodes and MatchScope) uptodate if the target is allowed to
3188/// change the DAG while matching. X86 addressing mode matcher is an example
3189/// for this.
3190class MatchStateUpdater : public SelectionDAG::DAGUpdateListener
3191{
3192 SDNode **NodeToMatch;
3194 SmallVectorImpl<MatchScope> &MatchScopes;
3195
3196public:
3197 MatchStateUpdater(SelectionDAG &DAG, SDNode **NodeToMatch,
3198 SmallVectorImpl<std::pair<SDValue, SDNode *>> &RN,
3200 : SelectionDAG::DAGUpdateListener(DAG), NodeToMatch(NodeToMatch),
3201 RecordedNodes(RN), MatchScopes(MS) {}
3202
3203 void NodeDeleted(SDNode *N, SDNode *E) override {
3204 // Some early-returns here to avoid the search if we deleted the node or
3205 // if the update comes from MorphNodeTo (MorphNodeTo is the last thing we
3206 // do, so it's unnecessary to update matching state at that point).
3207 // Neither of these can occur currently because we only install this
3208 // update listener during matching a complex patterns.
3209 if (!E || E->isMachineOpcode())
3210 return;
3211 // Check if NodeToMatch was updated.
3212 if (N == *NodeToMatch)
3213 *NodeToMatch = E;
3214 // Performing linear search here does not matter because we almost never
3215 // run this code. You'd have to have a CSE during complex pattern
3216 // matching.
3217 for (auto &I : RecordedNodes)
3218 if (I.first.getNode() == N)
3219 I.first.setNode(E);
3220
3221 for (auto &I : MatchScopes)
3222 for (auto &J : I.NodeStack)
3223 if (J.getNode() == N)
3224 J.setNode(E);
3225 }
3226};
3227
3228} // end anonymous namespace
3229
3231 const unsigned char *MatcherTable,
3232 unsigned TableSize) {
3233 // FIXME: Should these even be selected? Handle these cases in the caller?
3234 switch (NodeToMatch->getOpcode()) {
3235 default:
3236 break;
3237 case ISD::EntryToken: // These nodes remain the same.
3238 case ISD::BasicBlock:
3239 case ISD::Register:
3240 case ISD::RegisterMask:
3241 case ISD::HANDLENODE:
3242 case ISD::MDNODE_SDNODE:
3248 case ISD::MCSymbol:
3253 case ISD::TokenFactor:
3254 case ISD::CopyFromReg:
3255 case ISD::CopyToReg:
3256 case ISD::EH_LABEL:
3259 case ISD::LIFETIME_END:
3260 case ISD::PSEUDO_PROBE:
3261 NodeToMatch->setNodeId(-1); // Mark selected.
3262 return;
3263 case ISD::AssertSext:
3264 case ISD::AssertZext:
3265 case ISD::AssertAlign:
3266 ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
3267 CurDAG->RemoveDeadNode(NodeToMatch);
3268 return;
3269 case ISD::INLINEASM:
3270 case ISD::INLINEASM_BR:
3271 Select_INLINEASM(NodeToMatch);
3272 return;
3273 case ISD::READ_REGISTER:
3274 Select_READ_REGISTER(NodeToMatch);
3275 return;
3277 Select_WRITE_REGISTER(NodeToMatch);
3278 return;
3279 case ISD::UNDEF:
3280 Select_UNDEF(NodeToMatch);
3281 return;
3282 case ISD::FAKE_USE:
3283 Select_FAKE_USE(NodeToMatch);
3284 return;
3285 case ISD::FREEZE:
3286 Select_FREEZE(NodeToMatch);
3287 return;
3288 case ISD::ARITH_FENCE:
3289 Select_ARITH_FENCE(NodeToMatch);
3290 return;
3291 case ISD::MEMBARRIER:
3292 Select_MEMBARRIER(NodeToMatch);
3293 return;
3294 case ISD::STACKMAP:
3295 Select_STACKMAP(NodeToMatch);
3296 return;
3297 case ISD::PATCHPOINT:
3298 Select_PATCHPOINT(NodeToMatch);
3299 return;
3301 Select_JUMP_TABLE_DEBUG_INFO(NodeToMatch);
3302 return;
3304 Select_CONVERGENCECTRL_ANCHOR(NodeToMatch);
3305 return;
3307 Select_CONVERGENCECTRL_ENTRY(NodeToMatch);
3308 return;
3310 Select_CONVERGENCECTRL_LOOP(NodeToMatch);
3311 return;
3312 }
3313
3314 assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
3315
3316 // Set up the node stack with NodeToMatch as the only node on the stack.
3317 SmallVector<SDValue, 8> NodeStack;
3318 SDValue N = SDValue(NodeToMatch, 0);
3319 NodeStack.push_back(N);
3320
3321 // MatchScopes - Scopes used when matching, if a match failure happens, this
3322 // indicates where to continue checking.
3323 SmallVector<MatchScope, 8> MatchScopes;
3324
3325 // RecordedNodes - This is the set of nodes that have been recorded by the
3326 // state machine. The second value is the parent of the node, or null if the
3327 // root is recorded.
3329
3330 // MatchedMemRefs - This is the set of MemRef's we've seen in the input
3331 // pattern.
3333
3334 // These are the current input chain and glue for use when generating nodes.
3335 // Various Emit operations change these. For example, emitting a copytoreg
3336 // uses and updates these.
3337 SDValue InputChain, InputGlue;
3338
3339 // ChainNodesMatched - If a pattern matches nodes that have input/output
3340 // chains, the OPC_EmitMergeInputChains operation is emitted which indicates
3341 // which ones they are. The result is captured into this list so that we can
3342 // update the chain results when the pattern is complete.
3343 SmallVector<SDNode*, 3> ChainNodesMatched;
3344
3345 LLVM_DEBUG(dbgs() << "ISEL: Starting pattern match\n");
3346
3347 // Determine where to start the interpreter. Normally we start at opcode #0,
3348 // but if the state machine starts with an OPC_SwitchOpcode, then we
3349 // accelerate the first lookup (which is guaranteed to be hot) with the
3350 // OpcodeOffset table.
3351 unsigned MatcherIndex = 0;
3352
3353 if (!OpcodeOffset.empty()) {
3354 // Already computed the OpcodeOffset table, just index into it.
3355 if (N.getOpcode() < OpcodeOffset.size())
3356 MatcherIndex = OpcodeOffset[N.getOpcode()];
3357 LLVM_DEBUG(dbgs() << " Initial Opcode index to " << MatcherIndex << "\n");
3358
3359 } else if (MatcherTable[0] == OPC_SwitchOpcode) {
3360 // Otherwise, the table isn't computed, but the state machine does start
3361 // with an OPC_SwitchOpcode instruction. Populate the table now, since this
3362 // is the first time we're selecting an instruction.
3363 unsigned Idx = 1;
3364 while (true) {
3365 // Get the size of this case.
3366 unsigned CaseSize = MatcherTable[Idx++];
3367 if (CaseSize & 128)
3368 CaseSize = GetVBR(CaseSize, MatcherTable, Idx);
3369 if (CaseSize == 0) break;
3370
3371 // Get the opcode, add the index to the table.
3372 uint16_t Opc = MatcherTable[Idx++];
3373 Opc |= static_cast<uint16_t>(MatcherTable[Idx++]) << 8;
3374 if (Opc >= OpcodeOffset.size())
3375 OpcodeOffset.resize((Opc+1)*2);
3376 OpcodeOffset[Opc] = Idx;
3377 Idx += CaseSize;
3378 }
3379
3380 // Okay, do the lookup for the first opcode.
3381 if (N.getOpcode() < OpcodeOffset.size())
3382 MatcherIndex = OpcodeOffset[N.getOpcode()];
3383 }
3384
3385 while (true) {
3386 assert(MatcherIndex < TableSize && "Invalid index");
3387#ifndef NDEBUG
3388 unsigned CurrentOpcodeIndex = MatcherIndex;
3389#endif
3390 BuiltinOpcodes Opcode =
3391 static_cast<BuiltinOpcodes>(MatcherTable[MatcherIndex++]);
3392 switch (Opcode) {
3393 case OPC_Scope: {
3394 // Okay, the semantics of this operation are that we should push a scope
3395 // then evaluate the first child. However, pushing a scope only to have
3396 // the first check fail (which then pops it) is inefficient. If we can
3397 // determine immediately that the first check (or first several) will
3398 // immediately fail, don't even bother pushing a scope for them.
3399 unsigned FailIndex;
3400
3401 while (true) {
3402 unsigned NumToSkip = MatcherTable[MatcherIndex++];
3403 if (NumToSkip & 128)
3404 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
3405 // Found the end of the scope with no match.
3406 if (NumToSkip == 0) {
3407 FailIndex = 0;
3408 break;
3409 }
3410
3411 FailIndex = MatcherIndex+NumToSkip;
3412
3413 unsigned MatcherIndexOfPredicate = MatcherIndex;
3414 (void)MatcherIndexOfPredicate; // silence warning.
3415
3416 // If we can't evaluate this predicate without pushing a scope (e.g. if
3417 // it is a 'MoveParent') or if the predicate succeeds on this node, we
3418 // push the scope and evaluate the full predicate chain.
3419 bool Result;
3420 MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,
3421 Result, *this, RecordedNodes);
3422 if (!Result)
3423 break;
3424
3425 LLVM_DEBUG(
3426 dbgs() << " Skipped scope entry (due to false predicate) at "
3427 << "index " << MatcherIndexOfPredicate << ", continuing at "
3428 << FailIndex << "\n");
3429 ++NumDAGIselRetries;
3430
3431 // Otherwise, we know that this case of the Scope is guaranteed to fail,
3432 // move to the next case.
3433 MatcherIndex = FailIndex;
3434 }
3435
3436 // If the whole scope failed to match, bail.
3437 if (FailIndex == 0) break;
3438
3439 // Push a MatchScope which indicates where to go if the first child fails
3440 // to match.
3441 MatchScope NewEntry;
3442 NewEntry.FailIndex = FailIndex;
3443 NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
3444 NewEntry.NumRecordedNodes = RecordedNodes.size();
3445 NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
3446 NewEntry.InputChain = InputChain;
3447 NewEntry.InputGlue = InputGlue;
3448 NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
3449 MatchScopes.push_back(NewEntry);
3450 continue;
3451 }
3452 case OPC_RecordNode: {
3453 // Remember this node, it may end up being an operand in the pattern.
3454 SDNode *Parent = nullptr;
3455 if (NodeStack.size() > 1)
3456 Parent = NodeStack[NodeStack.size()-2].getNode();
3457 RecordedNodes.push_back(std::make_pair(N, Parent));
3458 continue;
3459 }
3460
3465 unsigned ChildNo = Opcode-OPC_RecordChild0;
3466 if (ChildNo >= N.getNumOperands())
3467 break; // Match fails if out of range child #.
3468
3469 RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo),
3470 N.getNode()));
3471 continue;
3472 }
3473 case OPC_RecordMemRef:
3474 if (auto *MN = dyn_cast<MemSDNode>(N))
3475 MatchedMemRefs.push_back(MN->getMemOperand());
3476 else {
3477 LLVM_DEBUG(dbgs() << "Expected MemSDNode "; N->dump(CurDAG);
3478 dbgs() << '\n');
3479 }
3480
3481 continue;
3482
3484 // If the current node has an input glue, capture it in InputGlue.
3485 if (N->getNumOperands() != 0 &&
3486 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue)
3487 InputGlue = N->getOperand(N->getNumOperands()-1);
3488 continue;
3489
3490 case OPC_MoveChild: {
3491 unsigned ChildNo = MatcherTable[MatcherIndex++];
3492 if (ChildNo >= N.getNumOperands())
3493 break; // Match fails if out of range child #.
3494 N = N.getOperand(ChildNo);
3495 NodeStack.push_back(N);
3496 continue;
3497 }
3498
3499 case OPC_MoveChild0: case OPC_MoveChild1:
3500 case OPC_MoveChild2: case OPC_MoveChild3:
3501 case OPC_MoveChild4: case OPC_MoveChild5:
3502 case OPC_MoveChild6: case OPC_MoveChild7: {
3503 unsigned ChildNo = Opcode-OPC_MoveChild0;
3504 if (ChildNo >= N.getNumOperands())
3505 break; // Match fails if out of range child #.
3506 N = N.getOperand(ChildNo);
3507 NodeStack.push_back(N);
3508 continue;
3509 }
3510
3511 case OPC_MoveSibling:
3512 case OPC_MoveSibling0:
3513 case OPC_MoveSibling1:
3514 case OPC_MoveSibling2:
3515 case OPC_MoveSibling3:
3516 case OPC_MoveSibling4:
3517 case OPC_MoveSibling5:
3518 case OPC_MoveSibling6:
3519 case OPC_MoveSibling7: {
3520 // Pop the current node off the NodeStack.
3521 NodeStack.pop_back();
3522 assert(!NodeStack.empty() && "Node stack imbalance!");
3523 N = NodeStack.back();
3524
3525 unsigned SiblingNo = Opcode == OPC_MoveSibling
3526 ? MatcherTable[MatcherIndex++]
3527 : Opcode - OPC_MoveSibling0;
3528 if (SiblingNo >= N.getNumOperands())
3529 break; // Match fails if out of range sibling #.
3530 N = N.getOperand(SiblingNo);
3531 NodeStack.push_back(N);
3532 continue;
3533 }
3534 case OPC_MoveParent:
3535 // Pop the current node off the NodeStack.
3536 NodeStack.pop_back();
3537 assert(!NodeStack.empty() && "Node stack imbalance!");
3538 N = NodeStack.back();
3539 continue;
3540
3541 case OPC_CheckSame:
3542 if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break;
3543 continue;
3544
3547 if (!::CheckChildSame(MatcherTable, MatcherIndex, N, RecordedNodes,
3548 Opcode-OPC_CheckChild0Same))
3549 break;
3550 continue;
3551
3562 if (!::CheckPatternPredicate(Opcode, MatcherTable, MatcherIndex, *this))
3563 break;
3564 continue;
3573 case OPC_CheckPredicate:
3574 if (!::CheckNodePredicate(Opcode, MatcherTable, MatcherIndex, *this,
3575 N.getNode()))
3576 break;
3577 continue;
3579 unsigned OpNum = MatcherTable[MatcherIndex++];
3581
3582 for (unsigned i = 0; i < OpNum; ++i)
3583 Operands.push_back(RecordedNodes[MatcherTable[MatcherIndex++]].first);
3584
3585 unsigned PredNo = MatcherTable[MatcherIndex++];
3586 if (!CheckNodePredicateWithOperands(N.getNode(), PredNo, Operands))
3587 break;
3588 continue;
3589 }
3598 case OPC_CheckComplexPat7: {
3599 unsigned CPNum = Opcode == OPC_CheckComplexPat
3600 ? MatcherTable[MatcherIndex++]
3601 : Opcode - OPC_CheckComplexPat0;
3602 unsigned RecNo = MatcherTable[MatcherIndex++];
3603 assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat");
3604
3605 // If target can modify DAG during matching, keep the matching state
3606 // consistent.
3607 std::unique_ptr<MatchStateUpdater> MSU;
3609 MSU.reset(new MatchStateUpdater(*CurDAG, &NodeToMatch, RecordedNodes,
3610 MatchScopes));
3611
3612 if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second,
3613 RecordedNodes[RecNo].first, CPNum,
3614 RecordedNodes))
3615 break;
3616 continue;
3617 }
3618 case OPC_CheckOpcode:
3619 if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break;
3620 continue;
3621
3622 case OPC_CheckType:
3623 case OPC_CheckTypeI32:
3624 case OPC_CheckTypeI64:
3626 switch (Opcode) {
3627 case OPC_CheckTypeI32:
3628 VT = MVT::i32;
3629 break;
3630 case OPC_CheckTypeI64:
3631 VT = MVT::i64;
3632 break;
3633 default:
3634 VT = getSimpleVT(MatcherTable, MatcherIndex);
3635 break;
3636 }
3637 if (!::CheckType(VT, N, TLI, CurDAG->getDataLayout()))
3638 break;
3639 continue;
3640
3641 case OPC_CheckTypeRes: {
3642 unsigned Res = MatcherTable[MatcherIndex++];
3643 if (!::CheckType(getSimpleVT(MatcherTable, MatcherIndex), N.getValue(Res),
3645 break;
3646 continue;
3647 }
3648
3649 case OPC_SwitchOpcode: {
3650 unsigned CurNodeOpcode = N.getOpcode();
3651 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3652 unsigned CaseSize;
3653 while (true) {
3654 // Get the size of this case.
3655 CaseSize = MatcherTable[MatcherIndex++];
3656 if (CaseSize & 128)
3657 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3658 if (CaseSize == 0) break;
3659
3660 uint16_t Opc = MatcherTable[MatcherIndex++];
3661 Opc |= static_cast<uint16_t>(MatcherTable[MatcherIndex++]) << 8;
3662
3663 // If the opcode matches, then we will execute this case.
3664 if (CurNodeOpcode == Opc)
3665 break;
3666
3667 // Otherwise, skip over this case.
3668 MatcherIndex += CaseSize;
3669 }
3670
3671 // If no cases matched, bail out.
3672 if (CaseSize == 0) break;
3673
3674 // Otherwise, execute the case we found.
3675 LLVM_DEBUG(dbgs() << " OpcodeSwitch from " << SwitchStart << " to "
3676 << MatcherIndex << "\n");
3677 continue;
3678 }
3679
3680 case OPC_SwitchType: {
3681 MVT CurNodeVT = N.getSimpleValueType();
3682 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3683 unsigned CaseSize;
3684 while (true) {
3685 // Get the size of this case.
3686 CaseSize = MatcherTable[MatcherIndex++];
3687 if (CaseSize & 128)
3688 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3689 if (CaseSize == 0) break;
3690
3691 MVT CaseVT = getSimpleVT(MatcherTable, MatcherIndex);
3692 if (CaseVT == MVT::iPTR)
3693 CaseVT = TLI->getPointerTy(CurDAG->getDataLayout());
3694
3695 // If the VT matches, then we will execute this case.
3696 if (CurNodeVT == CaseVT)
3697 break;
3698
3699 // Otherwise, skip over this case.
3700 MatcherIndex += CaseSize;
3701 }
3702
3703 // If no cases matched, bail out.
3704 if (CaseSize == 0) break;
3705
3706 // Otherwise, execute the case we found.
3707 LLVM_DEBUG(dbgs() << " TypeSwitch[" << CurNodeVT
3708 << "] from " << SwitchStart << " to " << MatcherIndex
3709 << '\n');
3710 continue;
3711 }
3737 unsigned ChildNo;
3740 VT = MVT::i32;
3742 } else if (Opcode >= SelectionDAGISel::OPC_CheckChild0TypeI64 &&
3744 VT = MVT::i64;
3746 } else {
3747 VT = getSimpleVT(MatcherTable, MatcherIndex);
3748 ChildNo = Opcode - SelectionDAGISel::OPC_CheckChild0Type;
3749 }
3750 if (!::CheckChildType(VT, N, TLI, CurDAG->getDataLayout(), ChildNo))
3751 break;
3752 continue;
3753 }
3754 case OPC_CheckCondCode:
3755 if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break;
3756 continue;
3758 if (!::CheckChild2CondCode(MatcherTable, MatcherIndex, N)) break;
3759 continue;
3760 case OPC_CheckValueType:
3761 if (!::CheckValueType(MatcherTable, MatcherIndex, N, TLI,
3763 break;
3764 continue;
3765 case OPC_CheckInteger:
3766 if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break;
3767 continue;
3771 if (!::CheckChildInteger(MatcherTable, MatcherIndex, N,
3772 Opcode-OPC_CheckChild0Integer)) break;
3773 continue;
3774 case OPC_CheckAndImm:
3775 if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break;
3776 continue;
3777 case OPC_CheckOrImm:
3778 if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break;
3779 continue;
3781 if (!ISD::isConstantSplatVectorAllOnes(N.getNode()))
3782 break;
3783 continue;
3785 if (!ISD::isConstantSplatVectorAllZeros(N.getNode()))
3786 break;
3787 continue;
3788
3790 assert(NodeStack.size() != 1 && "No parent node");
3791 // Verify that all intermediate nodes between the root and this one have
3792 // a single use (ignoring chains, which are handled in UpdateChains).
3793 bool HasMultipleUses = false;
3794 for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i) {
3795 unsigned NNonChainUses = 0;
3796 SDNode *NS = NodeStack[i].getNode();
3797 for (const SDUse &U : NS->uses())
3798 if (U.getValueType() != MVT::Other)
3799 if (++NNonChainUses > 1) {
3800 HasMultipleUses = true;
3801 break;
3802 }
3803 if (HasMultipleUses) break;
3804 }
3805 if (HasMultipleUses) break;
3806
3807 // Check to see that the target thinks this is profitable to fold and that
3808 // we can fold it without inducing cycles in the graph.
3809 if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3810 NodeToMatch) ||
3811 !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3812 NodeToMatch, OptLevel,
3813 true/*We validate our own chains*/))
3814 break;
3815
3816 continue;
3817 }
3818 case OPC_EmitInteger:
3819 case OPC_EmitInteger8:
3820 case OPC_EmitInteger16:
3821 case OPC_EmitInteger32:
3822 case OPC_EmitInteger64:
3826 switch (Opcode) {
3827 case OPC_EmitInteger8:
3828 VT = MVT::i8;
3829 break;
3830 case OPC_EmitInteger16:
3831 VT = MVT::i16;
3832 break;
3833 case OPC_EmitInteger32:
3835 VT = MVT::i32;
3836 break;
3837 case OPC_EmitInteger64:
3838 VT = MVT::i64;
3839 break;
3840 default:
3841 VT = getSimpleVT(MatcherTable, MatcherIndex);
3842 break;
3843 }
3844 int64_t Val = MatcherTable[MatcherIndex++];
3845 if (Val & 128)
3846 Val = GetVBR(Val, MatcherTable, MatcherIndex);
3847 if (Opcode >= OPC_EmitInteger && Opcode <= OPC_EmitInteger64)
3848 Val = decodeSignRotatedValue(Val);
3849 RecordedNodes.push_back(std::pair<SDValue, SDNode *>(
3850 CurDAG->getSignedConstant(Val, SDLoc(NodeToMatch), VT,
3851 /*isTarget=*/true),
3852 nullptr));
3853 continue;
3854 }
3855 case OPC_EmitRegister:
3857 case OPC_EmitRegisterI64: {
3859 switch (Opcode) {
3861 VT = MVT::i32;
3862 break;
3864 VT = MVT::i64;
3865 break;
3866 default:
3867 VT = getSimpleVT(MatcherTable, MatcherIndex);
3868 break;
3869 }
3870 unsigned RegNo = MatcherTable[MatcherIndex++];
3871 RecordedNodes.push_back(std::pair<SDValue, SDNode *>(
3872 CurDAG->getRegister(RegNo, VT), nullptr));
3873 continue;
3874 }
3875 case OPC_EmitRegister2: {
3876 // For targets w/ more than 256 register names, the register enum
3877 // values are stored in two bytes in the matcher table (just like
3878 // opcodes).
3879 MVT::SimpleValueType VT = getSimpleVT(MatcherTable, MatcherIndex);
3880 unsigned RegNo = MatcherTable[MatcherIndex++];
3881 RegNo |= MatcherTable[MatcherIndex++] << 8;
3882 RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3883 CurDAG->getRegister(RegNo, VT), nullptr));
3884 continue;
3885 }
3886
3896 // Convert from IMM/FPIMM to target version.
3897 unsigned RecNo = Opcode == OPC_EmitConvertToTarget
3898 ? MatcherTable[MatcherIndex++]
3899 : Opcode - OPC_EmitConvertToTarget0;
3900 assert(RecNo < RecordedNodes.size() && "Invalid EmitConvertToTarget");
3901 SDValue Imm = RecordedNodes[RecNo].first;
3902
3903 if (Imm->getOpcode() == ISD::Constant) {
3904 const ConstantInt *Val=cast<ConstantSDNode>(Imm)->getConstantIntValue();
3905 Imm = CurDAG->getTargetConstant(*Val, SDLoc(NodeToMatch),
3906 Imm.getValueType());
3907 } else if (Imm->getOpcode() == ISD::ConstantFP) {
3908 const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
3909 Imm = CurDAG->getTargetConstantFP(*Val, SDLoc(NodeToMatch),
3910 Imm.getValueType());
3911 }
3912
3913 RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second));
3914 continue;
3915 }
3916
3917 case OPC_EmitMergeInputChains1_0: // OPC_EmitMergeInputChains, 1, 0
3918 case OPC_EmitMergeInputChains1_1: // OPC_EmitMergeInputChains, 1, 1
3919 case OPC_EmitMergeInputChains1_2: { // OPC_EmitMergeInputChains, 1, 2
3920 // These are space-optimized forms of OPC_EmitMergeInputChains.
3921 assert(!InputChain.getNode() &&
3922 "EmitMergeInputChains should be the first chain producing node");
3923 assert(ChainNodesMatched.empty() &&
3924 "Should only have one EmitMergeInputChains per match");
3925
3926 // Read all of the chained nodes.
3927 unsigned RecNo = Opcode - OPC_EmitMergeInputChains1_0;
3928 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3929 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3930
3931 // If the chained node is not the root, we can't fold it if it has
3932 // multiple uses.
3933 // FIXME: What if other value results of the node have uses not matched
3934 // by this pattern?
3935 if (ChainNodesMatched.back() != NodeToMatch &&
3936 !RecordedNodes[RecNo].first.hasOneUse()) {
3937 ChainNodesMatched.clear();
3938 break;
3939 }
3940
3941 // Merge the input chains if they are not intra-pattern references.
3942 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3943
3944 if (!InputChain.getNode())
3945 break; // Failed to merge.
3946 continue;
3947 }
3948
3950 assert(!InputChain.getNode() &&
3951 "EmitMergeInputChains should be the first chain producing node");
3952 // This node gets a list of nodes we matched in the input that have
3953 // chains. We want to token factor all of the input chains to these nodes
3954 // together. However, if any of the input chains is actually one of the
3955 // nodes matched in this pattern, then we have an intra-match reference.
3956 // Ignore these because the newly token factored chain should not refer to
3957 // the old nodes.
3958 unsigned NumChains = MatcherTable[MatcherIndex++];
3959 assert(NumChains != 0 && "Can't TF zero chains");
3960
3961 assert(ChainNodesMatched.empty() &&
3962 "Should only have one EmitMergeInputChains per match");
3963
3964 // Read all of the chained nodes.
3965 for (unsigned i = 0; i != NumChains; ++i) {
3966 unsigned RecNo = MatcherTable[MatcherIndex++];
3967 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3968 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3969
3970 // If the chained node is not the root, we can't fold it if it has
3971 // multiple uses.
3972 // FIXME: What if other value results of the node have uses not matched
3973 // by this pattern?
3974 if (ChainNodesMatched.back() != NodeToMatch &&
3975 !RecordedNodes[RecNo].first.hasOneUse()) {
3976 ChainNodesMatched.clear();
3977 break;
3978 }
3979 }
3980
3981 // If the inner loop broke out, the match fails.
3982 if (ChainNodesMatched.empty())
3983 break;
3984
3985 // Merge the input chains if they are not intra-pattern references.
3986 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3987
3988 if (!InputChain.getNode())
3989 break; // Failed to merge.
3990
3991 continue;
3992 }
3993
3994 case OPC_EmitCopyToReg:
3995 case OPC_EmitCopyToReg0:
3996 case OPC_EmitCopyToReg1:
3997 case OPC_EmitCopyToReg2:
3998 case OPC_EmitCopyToReg3:
3999 case OPC_EmitCopyToReg4:
4000 case OPC_EmitCopyToReg5:
4001 case OPC_EmitCopyToReg6:
4002 case OPC_EmitCopyToReg7:
4004 unsigned RecNo =
4005 Opcode >= OPC_EmitCopyToReg0 && Opcode <= OPC_EmitCopyToReg7
4006 ? Opcode - OPC_EmitCopyToReg0
4007 : MatcherTable[MatcherIndex++];
4008 assert(RecNo < RecordedNodes.size() && "Invalid EmitCopyToReg");
4009 unsigned DestPhysReg = MatcherTable[MatcherIndex++];
4010 if (Opcode == OPC_EmitCopyToRegTwoByte)
4011 DestPhysReg |= MatcherTable[MatcherIndex++] << 8;
4012
4013 if (!InputChain.getNode())
4014 InputChain = CurDAG->getEntryNode();
4015
4016 InputChain = CurDAG->getCopyToReg(InputChain, SDLoc(NodeToMatch),
4017 DestPhysReg, RecordedNodes[RecNo].first,
4018 InputGlue);
4019
4020 InputGlue = InputChain.getValue(1);
4021 continue;
4022 }
4023
4024 case OPC_EmitNodeXForm: {
4025 unsigned XFormNo = MatcherTable[MatcherIndex++];
4026 unsigned RecNo = MatcherTable[MatcherIndex++];
4027 assert(RecNo < RecordedNodes.size() && "Invalid EmitNodeXForm");
4028 SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo);
4029 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, nullptr));
4030 continue;
4031 }
4032 case OPC_Coverage: {
4033 // This is emitted right before MorphNode/EmitNode.
4034 // So it should be safe to assume that this node has been selected
4035 unsigned index = MatcherTable[MatcherIndex++];
4036 index |= (MatcherTable[MatcherIndex++] << 8);
4037 index |= (MatcherTable[MatcherIndex++] << 16);
4038 index |= (MatcherTable[MatcherIndex++] << 24);
4039 dbgs() << "COVERED: " << getPatternForIndex(index) << "\n";
4040 dbgs() << "INCLUDED: " << getIncludePathForIndex(index) << "\n";
4041 continue;
4042 }
4043
4044 case OPC_EmitNode:
4045 case OPC_EmitNode0:
4046 case OPC_EmitNode1:
4047 case OPC_EmitNode2:
4048 case OPC_EmitNode0None:
4049 case OPC_EmitNode1None:
4050 case OPC_EmitNode2None:
4051 case OPC_EmitNode0Chain:
4052 case OPC_EmitNode1Chain:
4053 case OPC_EmitNode2Chain:
4054 case OPC_MorphNodeTo:
4055 case OPC_MorphNodeTo0:
4056 case OPC_MorphNodeTo1:
4057 case OPC_MorphNodeTo2:
4070 uint16_t TargetOpc = MatcherTable[MatcherIndex++];
4071 TargetOpc |= static_cast<uint16_t>(MatcherTable[MatcherIndex++]) << 8;
4072 unsigned EmitNodeInfo;
4073 if (Opcode >= OPC_EmitNode0None && Opcode <= OPC_EmitNode2Chain) {
4074 if (Opcode >= OPC_EmitNode0Chain && Opcode <= OPC_EmitNode2Chain)
4075 EmitNodeInfo = OPFL_Chain;
4076 else
4077 EmitNodeInfo = OPFL_None;
4078 } else if (Opcode >= OPC_MorphNodeTo0None &&
4079 Opcode <= OPC_MorphNodeTo2GlueOutput) {
4080 if (Opcode >= OPC_MorphNodeTo0Chain && Opcode <= OPC_MorphNodeTo2Chain)
4081 EmitNodeInfo = OPFL_Chain;
4082 else if (Opcode >= OPC_MorphNodeTo0GlueInput &&
4083 Opcode <= OPC_MorphNodeTo2GlueInput)
4084 EmitNodeInfo = OPFL_GlueInput;
4085 else if (Opcode >= OPC_MorphNodeTo0GlueOutput &&
4087 EmitNodeInfo = OPFL_GlueOutput;
4088 else
4089 EmitNodeInfo = OPFL_None;
4090 } else
4091 EmitNodeInfo = MatcherTable[MatcherIndex++];
4092 // Get the result VT list.
4093 unsigned NumVTs;
4094 // If this is one of the compressed forms, get the number of VTs based
4095 // on the Opcode. Otherwise read the next byte from the table.
4096 if (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2)
4097 NumVTs = Opcode - OPC_MorphNodeTo0;
4098 else if (Opcode >= OPC_MorphNodeTo0None && Opcode <= OPC_MorphNodeTo2None)
4099 NumVTs = Opcode - OPC_MorphNodeTo0None;
4100 else if (Opcode >= OPC_MorphNodeTo0Chain &&
4101 Opcode <= OPC_MorphNodeTo2Chain)
4102 NumVTs = Opcode - OPC_MorphNodeTo0Chain;
4103 else if (Opcode >= OPC_MorphNodeTo0GlueInput &&
4104 Opcode <= OPC_MorphNodeTo2GlueInput)
4105 NumVTs = Opcode - OPC_MorphNodeTo0GlueInput;
4106 else if (Opcode >= OPC_MorphNodeTo0GlueOutput &&
4108 NumVTs = Opcode - OPC_MorphNodeTo0GlueOutput;
4109 else if (Opcode >= OPC_EmitNode0 && Opcode <= OPC_EmitNode2)
4110 NumVTs = Opcode - OPC_EmitNode0;
4111 else if (Opcode >= OPC_EmitNode0None && Opcode <= OPC_EmitNode2None)
4112 NumVTs = Opcode - OPC_EmitNode0None;
4113 else if (Opcode >= OPC_EmitNode0Chain && Opcode <= OPC_EmitNode2Chain)
4114 NumVTs = Opcode - OPC_EmitNode0Chain;
4115 else
4116 NumVTs = MatcherTable[MatcherIndex++];
4118 for (unsigned i = 0; i != NumVTs; ++i) {
4119 MVT::SimpleValueType VT = getSimpleVT(MatcherTable, MatcherIndex);
4120 if (VT == MVT::iPTR)
4122 VTs.push_back(VT);
4123 }
4124
4125 if (EmitNodeInfo & OPFL_Chain)
4126 VTs.push_back(MVT::Other);
4127 if (EmitNodeInfo & OPFL_GlueOutput)
4128 VTs.push_back(MVT::Glue);
4129
4130 // This is hot code, so optimize the two most common cases of 1 and 2
4131 // results.
4132 SDVTList VTList;
4133 if (VTs.size() == 1)
4134 VTList = CurDAG->getVTList(VTs[0]);
4135 else if (VTs.size() == 2)
4136 VTList = CurDAG->getVTList(VTs[0], VTs[1]);
4137 else
4138 VTList = CurDAG->getVTList(VTs);
4139
4140 // Get the operand list.
4141 unsigned NumOps = MatcherTable[MatcherIndex++];
4143 for (unsigned i = 0; i != NumOps; ++i) {
4144 unsigned RecNo = MatcherTable[MatcherIndex++];
4145 if (RecNo & 128)
4146 RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
4147
4148 assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");
4149 Ops.push_back(RecordedNodes[RecNo].first);
4150 }
4151
4152 // If there are variadic operands to add, handle them now.
4153 if (EmitNodeInfo & OPFL_VariadicInfo) {
4154 // Determine the start index to copy from.
4155 unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
4156 FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
4157 assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
4158 "Invalid variadic node");
4159 // Copy all of the variadic operands, not including a potential glue
4160 // input.
4161 for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
4162 i != e; ++i) {
4163 SDValue V = NodeToMatch->getOperand(i);
4164 if (V.getValueType() == MVT::Glue) break;
4165 Ops.push_back(V);
4166 }
4167 }
4168
4169 // If this has chain/glue inputs, add them.
4170 if (EmitNodeInfo & OPFL_Chain)
4171 Ops.push_back(InputChain);
4172 if ((EmitNodeInfo & OPFL_GlueInput) && InputGlue.getNode() != nullptr)
4173 Ops.push_back(InputGlue);
4174
4175 // Check whether any matched node could raise an FP exception. Since all
4176 // such nodes must have a chain, it suffices to check ChainNodesMatched.
4177 // We need to perform this check before potentially modifying one of the
4178 // nodes via MorphNode.
4179 bool MayRaiseFPException =
4180 llvm::any_of(ChainNodesMatched, [this](SDNode *N) {
4181 return mayRaiseFPException(N) && !N->getFlags().hasNoFPExcept();
4182 });
4183
4184 // Create the node.
4185 MachineSDNode *Res = nullptr;
4186 bool IsMorphNodeTo =
4187 Opcode == OPC_MorphNodeTo ||
4188 (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2GlueOutput);
4189 if (!IsMorphNodeTo) {
4190 // If this is a normal EmitNode command, just create the new node and
4191 // add the results to the RecordedNodes list.
4192 Res = CurDAG->getMachineNode(TargetOpc, SDLoc(NodeToMatch),
4193 VTList, Ops);
4194
4195 // Add all the non-glue/non-chain results to the RecordedNodes list.
4196 for (unsigned i = 0, e = VTs.size(); i != e; ++i) {
4197 if (VTs[i] == MVT::Other || VTs[i] == MVT::Glue) break;
4198 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i),
4199 nullptr));
4200 }
4201 } else {
4202 assert(NodeToMatch->getOpcode() != ISD::DELETED_NODE &&
4203 "NodeToMatch was removed partway through selection");
4205 SDNode *E) {
4207 auto &Chain = ChainNodesMatched;
4208 assert((!E || !is_contained(Chain, N)) &&
4209 "Chain node replaced during MorphNode");
4210 llvm::erase(Chain, N);
4211 });
4212 Res = cast<MachineSDNode>(MorphNode(NodeToMatch, TargetOpc, VTList,
4213 Ops, EmitNodeInfo));
4214 }
4215
4216 // Set the NoFPExcept flag when no original matched node could
4217 // raise an FP exception, but the new node potentially might.
4218 if (!MayRaiseFPException && mayRaiseFPException(Res))
4219 Res->setFlags(Res->getFlags() | SDNodeFlags::NoFPExcept);
4220
4221 // If the node had chain/glue results, update our notion of the current
4222 // chain and glue.
4223 if (EmitNodeInfo & OPFL_GlueOutput) {
4224 InputGlue = SDValue(Res, VTs.size()-1);
4225 if (EmitNodeInfo & OPFL_Chain)
4226 InputChain = SDValue(Res, VTs.size()-2);
4227 } else if (EmitNodeInfo & OPFL_Chain)
4228 InputChain = SDValue(Res, VTs.size()-1);
4229
4230 // If the OPFL_MemRefs glue is set on this node, slap all of the
4231 // accumulated memrefs onto it.
4232 //
4233 // FIXME: This is vastly incorrect for patterns with multiple outputs
4234 // instructions that access memory and for ComplexPatterns that match
4235 // loads.
4236 if (EmitNodeInfo & OPFL_MemRefs) {
4237 // Only attach load or store memory operands if the generated
4238 // instruction may load or store.
4239 const MCInstrDesc &MCID = TII->get(TargetOpc);
4240 bool mayLoad = MCID.mayLoad();
4241 bool mayStore = MCID.mayStore();
4242
4243 // We expect to have relatively few of these so just filter them into a
4244 // temporary buffer so that we can easily add them to the instruction.
4246 for (MachineMemOperand *MMO : MatchedMemRefs) {
4247 if (MMO->isLoad()) {
4248 if (mayLoad)
4249 FilteredMemRefs.push_back(MMO);
4250 } else if (MMO->isStore()) {
4251 if (mayStore)
4252 FilteredMemRefs.push_back(MMO);
4253 } else {
4254 FilteredMemRefs.push_back(MMO);
4255 }
4256 }
4257
4258 CurDAG->setNodeMemRefs(Res, FilteredMemRefs);
4259 }
4260
4261 LLVM_DEBUG({
4262 if (!MatchedMemRefs.empty() && Res->memoperands_empty())
4263 dbgs() << " Dropping mem operands\n";
4264 dbgs() << " " << (IsMorphNodeTo ? "Morphed" : "Created") << " node: ";
4265 Res->dump(CurDAG);
4266 });
4267
4268 // If this was a MorphNodeTo then we're completely done!
4269 if (IsMorphNodeTo) {
4270 // Update chain uses.
4271 UpdateChains(Res, InputChain, ChainNodesMatched, true);
4272 return;
4273 }
4274 continue;
4275 }
4276
4277 case OPC_CompleteMatch: {
4278 // The match has been completed, and any new nodes (if any) have been
4279 // created. Patch up references to the matched dag to use the newly
4280 // created nodes.
4281 unsigned NumResults = MatcherTable[MatcherIndex++];
4282
4283 for (unsigned i = 0; i != NumResults; ++i) {
4284 unsigned ResSlot = MatcherTable[MatcherIndex++];
4285 if (ResSlot & 128)
4286 ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);
4287
4288 assert(ResSlot < RecordedNodes.size() && "Invalid CompleteMatch");
4289 SDValue Res = RecordedNodes[ResSlot].first;
4290
4291 assert(i < NodeToMatch->getNumValues() &&
4292 NodeToMatch->getValueType(i) != MVT::Other &&
4293 NodeToMatch->getValueType(i) != MVT::Glue &&
4294 "Invalid number of results to complete!");
4295 assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
4296 NodeToMatch->getValueType(i) == MVT::iPTR ||
4297 Res.getValueType() == MVT::iPTR ||
4298 NodeToMatch->getValueType(i).getSizeInBits() ==
4299 Res.getValueSizeInBits()) &&
4300 "invalid replacement");
4301 ReplaceUses(SDValue(NodeToMatch, i), Res);
4302 }
4303
4304 // Update chain uses.
4305 UpdateChains(NodeToMatch, InputChain, ChainNodesMatched, false);
4306
4307 // If the root node defines glue, we need to update it to the glue result.
4308 // TODO: This never happens in our tests and I think it can be removed /
4309 // replaced with an assert, but if we do it this the way the change is
4310 // NFC.
4311 if (NodeToMatch->getValueType(NodeToMatch->getNumValues() - 1) ==
4312 MVT::Glue &&
4313 InputGlue.getNode())
4314 ReplaceUses(SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1),
4315 InputGlue);
4316
4317 assert(NodeToMatch->use_empty() &&
4318 "Didn't replace all uses of the node?");
4319 CurDAG->RemoveDeadNode(NodeToMatch);
4320
4321 return;
4322 }
4323 }
4324
4325 // If the code reached this point, then the match failed. See if there is
4326 // another child to try in the current 'Scope', otherwise pop it until we
4327 // find a case to check.
4328 LLVM_DEBUG(dbgs() << " Match failed at index " << CurrentOpcodeIndex
4329 << "\n");
4330 ++NumDAGIselRetries;
4331 while (true) {
4332 if (MatchScopes.empty()) {
4333 CannotYetSelect(NodeToMatch);
4334 return;
4335 }
4336
4337 // Restore the interpreter state back to the point where the scope was
4338 // formed.
4339 MatchScope &LastScope = MatchScopes.back();
4340 RecordedNodes.resize(LastScope.NumRecordedNodes);
4341 NodeStack.clear();
4342 NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());
4343 N = NodeStack.back();
4344
4345 if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
4346 MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
4347 MatcherIndex = LastScope.FailIndex;
4348
4349 LLVM_DEBUG(dbgs() << " Continuing at " << MatcherIndex << "\n");
4350
4351 InputChain = LastScope.InputChain;
4352 InputGlue = LastScope.InputGlue;
4353 if (!LastScope.HasChainNodesMatched)
4354 ChainNodesMatched.clear();
4355
4356 // Check to see what the offset is at the new MatcherIndex. If it is zero
4357 // we have reached the end of this scope, otherwise we have another child
4358 // in the current scope to try.
4359 unsigned NumToSkip = MatcherTable[MatcherIndex++];
4360 if (NumToSkip & 128)
4361 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
4362
4363 // If we have another child in this scope to match, update FailIndex and
4364 // try it.
4365 if (NumToSkip != 0) {
4366 LastScope.FailIndex = MatcherIndex+NumToSkip;
4367 break;
4368 }
4369
4370 // End of this scope, pop it and try the next child in the containing
4371 // scope.
4372 MatchScopes.pop_back();
4373 }
4374 }
4375}
4376
4377/// Return whether the node may raise an FP exception.
4379 // For machine opcodes, consult the MCID flag.
4380 if (N->isMachineOpcode()) {
4381 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
4382 return MCID.mayRaiseFPException();
4383 }
4384
4385 // For ISD opcodes, only StrictFP opcodes may raise an FP
4386 // exception.
4387 if (N->isTargetOpcode()) {
4389 return TSI.mayRaiseFPException(N->getOpcode());
4390 }
4391 return N->isStrictFPOpcode();
4392}
4393
4395 assert(N->getOpcode() == ISD::OR && "Unexpected opcode");
4396 auto *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
4397 if (!C)
4398 return false;
4399
4400 // Detect when "or" is used to add an offset to a stack object.
4401 if (auto *FN = dyn_cast<FrameIndexSDNode>(N->getOperand(0))) {
4403 Align A = MFI.getObjectAlign(FN->getIndex());
4404 int32_t Off = C->getSExtValue();
4405 // If the alleged offset fits in the zero bits guaranteed by
4406 // the alignment, then this or is really an add.
4407 return (Off >= 0) && (((A.value() - 1) & Off) == unsigned(Off));
4408 }
4409 return false;
4410}
4411
4412void SelectionDAGISel::CannotYetSelect(SDNode *N) {
4413 std::string msg;
4414 raw_string_ostream Msg(msg);
4415 Msg << "Cannot select: ";
4416
4417 if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&
4418 N->getOpcode() != ISD::INTRINSIC_WO_CHAIN &&
4419 N->getOpcode() != ISD::INTRINSIC_VOID) {
4420 N->printrFull(Msg, CurDAG);
4421 Msg << "\nIn function: " << MF->getName();
4422 } else {
4423 bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other;
4424 unsigned iid = N->getConstantOperandVal(HasInputChain);
4425 if (iid < Intrinsic::num_intrinsics)
4426 Msg << "intrinsic %" << Intrinsic::getBaseName((Intrinsic::ID)iid);
4427 else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo())
4428 Msg << "target intrinsic %" << TII->getName(iid);
4429 else
4430 Msg << "unknown intrinsic #" << iid;
4431 }
4433}
unsigned const MachineRegisterInfo * MRI
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineInstrBuilder & UseMI
AMDGPU Register Bank Select
Rewrite undef for PHI
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
MachineBasicBlock MachineBasicBlock::iterator MBBI
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:340
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(...)
Definition: Debug.h:106
This file defines the DenseMap class.
bool End
Definition: ELF_riscv.cpp:480
This file defines the FastISel class.
IRTranslator LLVM IR MI
Module.h This file contains the declarations for the Module class.
#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
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static Type * getValueType(Value *V)
Returns the type of the given value/instruction V.
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 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 MVT::SimpleValueType getSimpleVT(const unsigned char *MatcherTable, unsigned &MatcherIndex)
getSimpleVT - Decode a value in MatcherTable, if it's a VBR encoded value, use GetVBR to decode it.
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 void preserveFakeUses(BasicBlock::iterator Begin, BasicBlock::iterator End)
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 LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckNodePredicate(unsigned Opcode, const unsigned char *MatcherTable, unsigned &MatcherIndex, const SelectionDAGISel &SDISel, SDNode *N)
CheckNodePredicate - Implements OP_CheckNodePredicate.
static cl::opt< RegisterScheduler::FunctionPassCtor, false, RegisterPassParser< RegisterScheduler > > ISHeuristic("pre-RA-sched", cl::init(&createDefaultScheduler), cl::Hidden, cl::desc("Instruction schedulers available (before register" " allocation):"))
ISHeuristic command line option for instruction schedulers.
static cl::opt< bool > EnableFastISelFallbackReport("fast-isel-report-on-fallback", cl::Hidden, cl::desc("Emit a diagnostic when \"fast\" instruction selection " "falls back to SelectionDAG."))
static bool processDbgDeclare(FunctionLoweringInfo &FuncInfo, const Value *Address, DIExpression *Expr, DILocalVariable *Var, DebugLoc DbgLoc)
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDNode *N)
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, unsigned ChildNo)
static cl::opt< std::string > FilterDAGBasicBlockName("filter-view-dags", cl::Hidden, cl::desc("Only display the basic block whose name " "matches this for all view-*-dags options"))
static SDValue HandleMergeInputChains(SmallVectorImpl< SDNode * > &ChainNodesMatched, SelectionDAG *CurDAG)
HandleMergeInputChains - This implements the OPC_EmitMergeInputChains operation for when the pattern ...
static bool isFoldedOrDeadInstruction(const Instruction *I, const FunctionLoweringInfo &FuncInfo)
isFoldedOrDeadInstruction - Return true if the specified instruction is side-effect free and is eithe...
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:166
This file describes how to lower LLVM code to machine code.
This pass exposes codegen information to IR-level passes.
LLVM IR instance of the generic uniformity analysis.
Value * RHS
Value * LHS
DEMANGLE_DUMP_METHOD void dump() const
A manager for alias analyses.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Class for arbitrary precision integers.
Definition: APInt.h:78
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
Definition: APInt.h:1257
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:429
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:410
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
This class represents an incoming formal argument to a Function.
Definition: Argument.h:31
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
LLVM Basic Block Representation.
Definition: BasicBlock.h:61
iterator end()
Definition: BasicBlock.h:474
unsigned getNumber() const
Definition: BasicBlock.h:104
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:530
InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:381
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:178
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:177
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:688
const Instruction * getFirstMayFaultInst() const
Returns the first potential AsynchEH faulty instruction currently it checks for loads/stores (which m...
Definition: BasicBlock.cpp:358
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Analysis pass which computes BranchProbabilityInfo.
Legacy analysis pass which computes BranchProbabilityInfo.
This class represents a function call, abstracting a target machine's calling convention.
ConstantFP - Floating Point Values [float, double].
Definition: Constants.h:271
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
This is an important base class in LLVM.
Definition: Constant.h:42
DWARF expression.
bool isEntryValue() const
Check if the expression consists of exactly one entry value operand.
static DIExpression * append(const DIExpression *Expr, ArrayRef< uint64_t > Ops)
Append the opcodes Ops to DIExpr.
static DIExpression * prepend(const DIExpression *Expr, uint8_t Flags, int64_t Offset=0)
Prepend DIExpr with a deref and offset operation and optionally turn it into a stack value or/and an ...
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:63
Record of a variable value-assignment, aka a non instruction representation of the dbg....
A debug info location.
Definition: DebugLoc.h:33
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:156
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:211
Diagnostic information for ISel fallback path.
This is a fast-path instruction selection class that generates poor code and doesn't support illegal ...
Definition: FastISel.h:66
void setLastLocalValue(MachineInstr *I)
Update the position of the last instruction emitted for materializing constants for use in the curren...
Definition: FastISel.h:237
void handleDbgInfo(const Instruction *II)
Target-independent lowering of non-instruction debug info associated with this instruction.
Definition: FastISel.cpp:1192
bool tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst)
We're checking to see if we can fold LI into FoldInst.
Definition: FastISel.cpp:2315
void removeDeadCode(MachineBasicBlock::iterator I, MachineBasicBlock::iterator E)
Remove all dead instructions between the I and E.
Definition: FastISel.cpp:409
void startNewBlock()
Set the current block to which generated machine instructions will be appended.
Definition: FastISel.cpp:123
bool selectInstruction(const Instruction *I)
Do "fast" instruction selection for the given LLVM IR instruction and append the generated machine in...
Definition: FastISel.cpp:1585
void finishBasicBlock()
Flush the local value map.
Definition: FastISel.cpp:136
void recomputeInsertPt()
Reset InsertPt to prepare for inserting instructions into the current block.
Definition: FastISel.cpp:400
bool lowerArguments()
Do "fast" instruction selection for function arguments and append the machine instructions to the cur...
Definition: FastISel.cpp:138
unsigned arg_size() const
arg_size - Return the number of funcletpad arguments.
Definition: InstrTypes.h:2351
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th funcletpad argument.
Definition: InstrTypes.h:2367
FunctionLoweringInfo - This contains information that is global to a function that is used when lower...
SmallPtrSet< const DbgVariableRecord *, 8 > PreprocessedDVRDeclares
DenseMap< const AllocaInst *, int > StaticAllocaMap
StaticAllocaMap - Keep track of frame indices for fixed sized allocas in the entry block.
int getArgumentFrameIndex(const Argument *A)
getArgumentFrameIndex - Get frame index for the byval argument.
bool isExportedInst(const Value *V) const
isExportedInst - Return true if the specified value is an instruction exported from its block.
SmallPtrSet< const DbgDeclareInst *, 8 > PreprocessedDbgDeclares
Collection of dbg.declare instructions handled after argument lowering and before ISel proper.
DenseMap< const Value *, Register > ValueMap
ValueMap - Since we emit code for the function a basic block at a time, we must remember which virtua...
MachineRegisterInfo * RegInfo
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:178
Data structure describing the variable locations in a function.
const VarLocInfo * single_locs_begin() const
DILocalVariable * getDILocalVariable(const VarLocInfo *Loc) const
Return the DILocalVariable for the location definition represented by ID.
const VarLocInfo * single_locs_end() const
One past the last single-location variable location definition.
const BasicBlock & getEntryBlock() const
Definition: Function.h:809
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:216
unsigned getMaxBlockNumber() const
Return a value larger than the largest block number.
Definition: Function.h:828
iterator_range< arg_iterator > args()
Definition: Function.h:892
DISubprogram * getSubprogram() const
Get the attached subprogram.
Definition: Metadata.cpp:1874
bool hasGC() const
hasGC/getGC/setGC/clearGC - The name of the garbage collection algorithm to use during code generatio...
Definition: Function.h:345
bool hasOptNone() const
Do not optimize this function (-O0).
Definition: Function.h:701
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:369
An analysis pass which caches information about the Function.
Definition: GCMetadata.h:180
An analysis pass which caches information about the entire Module.
Definition: GCMetadata.h:203
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:657
This class is used to form a handle around another node that is persistent and is updated across invo...
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:511
bool isTerminator() const
Definition: Instruction.h:313
A wrapper class for inspecting calls to intrinsic functions.
Definition: IntrinsicInst.h:48
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
Definition: IntrinsicInst.h:55
void diagnose(const DiagnosticInfo &DI)
Report a message to the currently installed diagnostic handler.
This is an alternative analysis pass to BlockFrequencyInfoWrapperPass.
static void getLazyBFIAnalysisUsage(AnalysisUsage &AU)
Helper for client passes to set up the analysis usage on behalf of this pass.
MCSymbol * createTempSymbol()
Create a temporary symbol with a unique name.
Definition: MCContext.cpp:345
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
bool mayStore() const
Return true if this instruction could possibly modify memory.
Definition: MCInstrDesc.h:444
bool mayLoad() const
Return true if this instruction could possibly read memory.
Definition: MCInstrDesc.h:438
bool mayRaiseFPException() const
Return true if this instruction may raise a floating-point exception.
Definition: MCInstrDesc.h:447
bool isCall() const
Return true if the instruction is a call.
Definition: MCInstrDesc.h:288
bool isReturn() const
Return true if the instruction is a return.
Definition: MCInstrDesc.h:276
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
Definition: MCInstrInfo.h:63
StringRef getName(unsigned Opcode) const
Returns the name for the instructions with the given opcode.
Definition: MCInstrInfo.h:70
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:41
const MDNode * getMD() const
Metadata node.
Definition: Metadata.h:1073
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1434
A single uniqued string.
Definition: Metadata.h:724
StringRef getString() const
Definition: Metadata.cpp:616
Machine Value Type.
SimpleValueType SimpleTy
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
iterator getFirstNonPHI()
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
instr_iterator instr_end()
void addLiveIn(MCRegister PhysReg, LaneBitmask LaneMask=LaneBitmask::getAll())
Adds the specified register as a live in.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator insertAfter(iterator I, MachineInstr *MI)
Insert MI into the instruction list after I.
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
bool hasCalls() const
Return true if the current function has any function calls.
Align getObjectAlign(int ObjectIdx) const
Return the alignment of the specified stack object.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
bool hasProperty(Property P) const
const WinEHFuncInfo * getWinEHFuncInfo() const
getWinEHFuncInfo - Return information about how the current function uses Windows exception handling.
bool useDebugInstrRef() const
Returns true if the function's variable locations are tracked with instruction referencing.
void setHasInlineAsm(bool B)
Set a flag that indicates that the function contains inline assembly.
void setWasmLandingPadIndex(const MachineBasicBlock *LPad, unsigned Index)
Map the landing pad to its index. Used for Wasm exception handling.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
bool hasInlineAsm() const
Returns true if the function contains any inline assembly.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
void finalizeDebugInstrRefs()
Finalise any partially emitted debug instructions.
void setCallSiteLandingPad(MCSymbol *Sym, ArrayRef< unsigned > Sites)
Map the landing pad's EH symbol to the call site indexes.
void setUseDebugInstrRef(bool UseInstrRef)
Set whether this function will use instruction referencing or not.
MCContext & getContext() const
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
const DataLayout & getDataLayout() const
Return the DataLayout attached to the Module associated to this MF.
MCSymbol * addLandingPad(MachineBasicBlock *LandingPad)
Add a new panding pad, and extract the exception handling information from the landingpad instruction...
Function & getFunction()
Return the LLVM function that this machine code represents.
bool shouldUseDebugInstrRef() const
Determine whether, in the current machine configuration, we should use instruction referencing or not...
const MachineFunctionProperties & getProperties() const
Get the function properties.
void setVariableDbgInfo(const DILocalVariable *Var, const DIExpression *Expr, int Slot, const DILocation *Loc)
Collect information used to emit debugging information of a variable in a stack slot.
const MachineBasicBlock & front() const
void print(raw_ostream &OS, const SlotIndexes *=nullptr) const
print - Print out the MachineFunction in a format suitable for debugging to the specified stream.
const MachineInstrBuilder & addSym(MCSymbol *Sym, unsigned char TargetFlags=0) const
const MachineInstrBuilder & addReg(Register RegNo, unsigned flags=0, unsigned SubReg=0) const
Add a new virtual register operand.
Representation of each machine instruction.
Definition: MachineInstr.h:71
bool isTerminator(QueryType Type=AnyInBundle) const
Returns true if this instruction part of the terminator for a basic block.
Definition: MachineInstr.h:983
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:587
A description of a memory reference used in the backend.
An analysis that produces MachineModuleInfo for a module.
This class contains meta information specific to a module.
Register getReg() const
getReg - Returns the register number.
MachinePassRegistry - Track the registration of machine passes.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
void EmitLiveInCopies(MachineBasicBlock *EntryMBB, const TargetRegisterInfo &TRI, const TargetInstrInfo &TII)
EmitLiveInCopies - Emit copies to initialize livein virtual registers into the given entry block.
ArrayRef< std::pair< MCRegister, Register > > liveins() const
iterator_range< use_instr_iterator > use_instructions(Register Reg) const
void addPhysRegsUsedFromRegMask(const uint32_t *RegMask)
addPhysRegsUsedFromRegMask - Mark any registers not in RegMask as used.
An SDNode that represents everything that will be needed to construct a MachineInstr.
Metadata * getModuleFlag(StringRef Key) const
Return the corresponding value if Key appears in module flags, otherwise return null.
Definition: Module.cpp:354
This class is used by SelectionDAGISel to temporarily override the optimization level on a per-functi...
OptLevelChanger(SelectionDAGISel &ISel, CodeGenOptLevel NewOptLevel)
The optimization diagnostic interface.
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file.
Diagnostic information for missed-optimization remarks.
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:692
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
AnalysisType * getAnalysisIfAvailable() const
getAnalysisIfAvailable<AnalysisType>() - Subclasses use this function to get analysis information tha...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
RegisterPassParser class - Handle the addition of new machine passes.
ScheduleDAGSDNodes *(*)(SelectionDAGISel *, CodeGenOptLevel) FunctionPassCtor
static MachinePassRegistry< FunctionPassCtor > Registry
RegisterScheduler class - Track the registration of instruction schedulers.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
static unsigned virtReg2Index(Register Reg)
Convert a virtual register number to a 0-based index.
Definition: Register.h:77
constexpr bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
Wrapper class for IR location info (IR ordering and DebugLoc) to be passed into SDNode creation funct...
Represents one node in the SelectionDAG.
bool isMachineOpcode() const
Test if this node has a post-isel opcode, directly corresponding to a MachineInstr opcode.
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
SDNode * getGluedUser() const
If this node has a glue value with a user, return the user (there is at most one).
bool isOnlyUserOf(const SDNode *N) const
Return true if this node is the only use of N.
iterator_range< value_op_iterator > op_values() const
iterator_range< use_iterator > uses()
void setNodeId(int Id)
Set unique node id.
static bool hasPredecessorHelper(const SDNode *N, SmallPtrSetImpl< const SDNode * > &Visited, SmallVectorImpl< const SDNode * > &Worklist, unsigned int MaxSteps=0, bool TopologicalPrune=false)
Returns true if N is a predecessor of any node in Worklist.
uint64_t getAsZExtVal() const
Helper method returns the zero-extended integer value of a ConstantSDNode.
bool use_empty() const
Return true if there are no uses of this node.
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
unsigned getNumOperands() const
Return the number of values used by this operation.
const SDValue & getOperand(unsigned Num) const
EVT getValueType(unsigned ResNo) const
Return the type of a specified result.
Represents a use of a SDNode.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
SDNode * getNode() const
get the SDNode which holds the desired result
SDValue getValue(unsigned R) const
EVT getValueType() const
Return the ValueType of the referenced return value.
TypeSize getValueSizeInBits() const
Returns the size of the value in bits.
void copyToMachineFrameInfo(MachineFrameInfo &MFI) const
bool shouldEmitSDCheck(const BasicBlock &BB) const
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
SelectionDAGBuilder - This is the common target-independent lowering implementation that is parameter...
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
SelectionDAGISelLegacy(char &ID, std::unique_ptr< SelectionDAGISel > S)
PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
std::optional< BatchAAResults > BatchAA
std::unique_ptr< FunctionLoweringInfo > FuncInfo
SmallPtrSet< const Instruction *, 4 > ElidedArgCopyInstrs
virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op, InlineAsm::ConstraintCode ConstraintID, std::vector< SDValue > &OutOps)
SelectInlineAsmMemoryOperand - Select the specified address as a target addressing mode,...
bool CheckOrMask(SDValue LHS, ConstantSDNode *RHS, int64_t DesiredMaskS) const
CheckOrMask - The isel is trying to match something like (or X, 255).
AssumptionCache * AC
void initializeAnalysisResults(MachineFunctionAnalysisManager &MFAM)
MachineModuleInfo * MMI
const TargetLowering * TLI
virtual void PostprocessISelDAG()
PostprocessISelDAG() - This hook allows the target to hack on the graph right after selection.
MachineFunction * MF
virtual bool CheckNodePredicate(SDNode *N, unsigned PredNo) const
CheckNodePredicate - This function is generated by tblgen in the target.
std::unique_ptr< OptimizationRemarkEmitter > ORE
Current optimization remark emitter.
MachineRegisterInfo * RegInfo
unsigned DAGSize
DAGSize - Size of DAG being instruction selected.
bool isOrEquivalentToAdd(const SDNode *N) const
virtual bool CheckComplexPattern(SDNode *Root, SDNode *Parent, SDValue N, unsigned PatternNo, SmallVectorImpl< std::pair< SDValue, SDNode * > > &Result)
virtual bool CheckPatternPredicate(unsigned PredNo) const
CheckPatternPredicate - This function is generated by tblgen in the target.
static int getNumFixedFromVariadicInfo(unsigned Flags)
getNumFixedFromVariadicInfo - Transform an EmitNode flags word into the number of fixed arity values ...
const TargetLibraryInfo * LibInfo
static int getUninvalidatedNodeId(SDNode *N)
const TargetInstrInfo * TII
CodeGenOptLevel OptLevel
virtual bool CheckNodePredicateWithOperands(SDNode *N, unsigned PredNo, const SmallVectorImpl< SDValue > &Operands) const
CheckNodePredicateWithOperands - This function is generated by tblgen in the target.
GCFunctionInfo * GFI
void SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable, unsigned TableSize)
static void EnforceNodeIdInvariant(SDNode *N)
void ReplaceUses(SDValue F, SDValue T)
ReplaceUses - replace all uses of the old node F with the use of the new node T.
virtual bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const
IsProfitableToFold - Returns true if it's profitable to fold the specific operand node N of U during ...
virtual SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo)
bool MatchFilterFuncName
True if the function currently processing is in the function printing list (i.e.
void SelectInlineAsmMemoryOperands(std::vector< SDValue > &Ops, const SDLoc &DL)
SelectInlineAsmMemoryOperands - Calls to this are automatically generated by tblgen.
static bool IsLegalToFold(SDValue N, SDNode *U, SDNode *Root, CodeGenOptLevel OptLevel, bool IgnoreChains=false)
IsLegalToFold - Returns true if the specific operand node N of U can be folded during instruction sel...
virtual bool ComplexPatternFuncMutatesDAG() const
Return true if complex patterns for this target can mutate the DAG.
virtual void PreprocessISelDAG()
PreprocessISelDAG - This hook allows targets to hack on the graph before instruction selection starts...
BatchAAResults * getBatchAA() const
Returns a (possibly null) pointer to the current BatchAAResults.
bool CheckAndMask(SDValue LHS, ConstantSDNode *RHS, int64_t DesiredMaskS) const
CheckAndMask - The isel is trying to match something like (and X, 255).
SwiftErrorValueTracking * SwiftError
virtual StringRef getPatternForIndex(unsigned index)
getPatternForIndex - Patterns selected by tablegen during ISEL
bool mayRaiseFPException(SDNode *Node) const
Return whether the node may raise an FP exception.
std::unique_ptr< SelectionDAGBuilder > SDB
void ReplaceNode(SDNode *F, SDNode *T)
Replace all uses of F with T, then remove F from the DAG.
SelectionDAGISel(TargetMachine &tm, CodeGenOptLevel OL=CodeGenOptLevel::Default)
virtual bool runOnMachineFunction(MachineFunction &mf)
static void InvalidateNodeId(SDNode *N)
virtual StringRef getIncludePathForIndex(unsigned index)
getIncludePathForIndex - get the td source location of pattern instantiation
Targets can subclass this to parameterize the SelectionDAG lowering and instruction selection process...
virtual bool mayRaiseFPException(unsigned Opcode) const
Returns true if a node with the given target-specific opcode may raise a floating-point exception.
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:228
const SDValue & getRoot() const
Return the root tag of the SelectionDAG.
Definition: SelectionDAG.h:577
SDValue getCopyToReg(SDValue Chain, const SDLoc &dl, Register Reg, SDValue N)
Definition: SelectionDAG.h:802
SDVTList getVTList(EVT VT)
Return an SDVTList that represents the list of values specified.
MachineSDNode * getMachineNode(unsigned Opcode, const SDLoc &dl, EVT VT)
These are used for target selectors to create a new node with specified return type(s),...
bool LegalizeVectors()
This transforms the SelectionDAG into a SelectionDAG that only uses vector math operations supported ...
SDNode * SelectNodeTo(SDNode *N, unsigned MachineOpc, EVT VT)
These are used for target selectors to mutate the specified node to have the specified return type,...
void Combine(CombineLevel Level, BatchAAResults *BatchAA, CodeGenOptLevel OptLevel)
This iterates over the nodes in the SelectionDAG, folding certain types of nodes together,...
void setFunctionLoweringInfo(FunctionLoweringInfo *FuncInfo)
Definition: SelectionDAG.h:484
SDValue getRegister(Register Reg, EVT VT)
SDNode * mutateStrictFPToFP(SDNode *Node)
Mutate the specified strict FP node to its non-strict equivalent, unlinking the node from its chain a...
bool NewNodesMustHaveLegalTypes
When true, additional steps are taken to ensure that getConstant() and similar functions return DAG n...
Definition: SelectionDAG.h:397
void salvageDebugInfo(SDNode &N)
To be invoked on an SDNode that is slated to be erased.
SDNode * MorphNodeTo(SDNode *N, unsigned Opc, SDVTList VTs, ArrayRef< SDValue > Ops)
This mutates the specified node to have the specified return type, opcode, and operands.
allnodes_const_iterator allnodes_begin() const
Definition: SelectionDAG.h:557
SDValue getCopyFromReg(SDValue Chain, const SDLoc &dl, Register Reg, EVT VT)
Definition: SelectionDAG.h:828
void setNodeMemRefs(MachineSDNode *N, ArrayRef< MachineMemOperand * > NewMemRefs)
Mutate the specified machine node's memory references to the provided list.
const DataLayout & getDataLayout() const
Definition: SelectionDAG.h:497
void viewGraph(const std::string &Title)
Pop up a GraphViz/gv window with the DAG rendered using 'dot'.
void Legalize()
This transforms the SelectionDAG into a SelectionDAG that is compatible with the target instruction s...
const SelectionDAGTargetInfo & getSelectionDAGInfo() const
Definition: SelectionDAG.h:505
void clear()
Clear state and free memory necessary to make this SelectionDAG ready to process a new block.
SDValue getSignedConstant(int64_t Val, const SDLoc &DL, EVT VT, bool isTarget=false, bool isOpaque=false)
void RemoveDeadNodes()
This method deletes all unreachable nodes in the SelectionDAG.
void RemoveDeadNode(SDNode *N)
Remove the specified node from the system.
SDValue getTargetConstantFP(double Val, const SDLoc &DL, EVT VT)
Definition: SelectionDAG.h:737
SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, ArrayRef< SDUse > Ops)
Gets or creates the specified node.
unsigned AssignTopologicalOrder()
Topological-sort the AllNodes list and a assign a unique node id for each node in the DAG based on th...
SDValue getTargetConstant(uint64_t Val, const SDLoc &DL, EVT VT, bool isOpaque=false)
Definition: SelectionDAG.h:701
unsigned ComputeNumSignBits(SDValue Op, unsigned Depth=0) const
Return the number of times the sign bit of the register is replicated into the other bits.
MachineFunction & getMachineFunction() const
Definition: SelectionDAG.h:492
const FunctionVarLocs * getFunctionVarLocs() const
Returns the result of the AssignmentTrackingAnalysis pass if it's available, otherwise return nullptr...
Definition: SelectionDAG.h:509
KnownBits computeKnownBits(SDValue Op, unsigned Depth=0) const
Determine which bits of Op are known to be either zero or one and return them in Known.
bool MaskedValueIsZero(SDValue Op, const APInt &Mask, unsigned Depth=0) const
Return true if 'Op & Mask' is known to be zero.
const SDValue & setRoot(SDValue N)
Set the current root tag of the SelectionDAG.
Definition: SelectionDAG.h:586
void init(MachineFunction &NewMF, OptimizationRemarkEmitter &NewORE, Pass *PassPtr, const TargetLibraryInfo *LibraryInfo, UniformityInfo *UA, ProfileSummaryInfo *PSIin, BlockFrequencyInfo *BFIin, MachineModuleInfo &MMI, FunctionVarLocs const *FnVarLocs)
Prepare this SelectionDAG to process code in the given MachineFunction.
SDValue getEntryNode() const
Return the token chain corresponding to the entry of the function.
Definition: SelectionDAG.h:580
ilist< SDNode >::iterator allnodes_iterator
Definition: SelectionDAG.h:560
bool LegalizeTypes()
This transforms the SelectionDAG into a SelectionDAG that only uses types natively supported by the t...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:384
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:519
bool empty() const
Definition: SmallVector.h:81
size_t size() const
Definition: SmallVector.h:78
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:573
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:683
void resize(size_type N)
Definition: SmallVector.h:638
void push_back(const T &Elt)
Definition: SmallVector.h:413
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:51
constexpr const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:144
bool createEntriesInEntryBlock(DebugLoc DbgLoc)
Create initial definitions of swifterror values in the entry block of the current function.
void setFunction(MachineFunction &MF)
Initialize data structures for specified new function.
void preassignVRegs(MachineBasicBlock *MBB, BasicBlock::const_iterator Begin, BasicBlock::const_iterator End)
void propagateVRegs()
Propagate assigned swifterror vregs through a function, synthesizing PHI nodes when needed to maintai...
Analysis pass providing the TargetTransformInfo.
TargetIntrinsicInfo - Interface to description of machine instruction set.
Analysis pass providing the TargetLibraryInfo.
virtual const TargetRegisterClass * getRegClassFor(MVT VT, bool isDivergent=false) const
Return the register class that should be used for the specified value type.
virtual Function * getSSPStackGuardCheck(const Module &M) const
If the target has a standard stack protection check function that performs validation and error handl...
Sched::Preference getSchedulingPreference() const
Return target scheduling preference.
bool isStrictFPEnabled() const
Return true if the target support strict float operation.
virtual MVT getPointerTy(const DataLayout &DL, uint32_t AS=0) const
Return the pointer type for the given address space, defaults to the pointer type from the data layou...
virtual Register getExceptionPointerRegister(const Constant *PersonalityFn) const
If a physical register, this returns the register that receives the exception address on entry to an ...
virtual Register getExceptionSelectorRegister(const Constant *PersonalityFn) const
If a physical register, this returns the register that receives the exception typeid on entry to a la...
LegalizeAction getOperationAction(unsigned Op, EVT VT) const
Return how this operation should be treated: either it is legal, needs to be promoted to a larger siz...
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
virtual Register getRegisterByName(const char *RegName, LLT Ty, const MachineFunction &MF) const
Return the register ID of the name passed in.
virtual void insertCopiesSplitCSR(MachineBasicBlock *Entry, const SmallVectorImpl< MachineBasicBlock * > &Exits) const
Insert explicit copies in entry and exit blocks.
virtual void AdjustInstrPostInstrSelection(MachineInstr &MI, SDNode *Node) const
This method should be implemented by targets that mark instructions with the 'hasPostISelHook' flag.
virtual void initializeSplitCSR(MachineBasicBlock *Entry) const
Perform necessary initialization to handle a subset of CSRs explicitly via copies.
virtual MachineBasicBlock * EmitInstrWithCustomInserter(MachineInstr &MI, MachineBasicBlock *MBB) const
This method should be implemented by targets that mark instructions with the 'usesCustomInserter' fla...
virtual FastISel * createFastISel(FunctionLoweringInfo &, const TargetLibraryInfo *) const
This method returns a target specific FastISel object, or null if the target does not support "fast" ...
virtual bool supportSplitCSR(MachineFunction *MF) const
Return true if the target supports that a subset of CSRs for the given machine function is handled ex...
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:77
virtual const TargetIntrinsicInfo * getIntrinsicInfo() const
If intrinsic information is available, return it. If not, return null.
void setFastISel(bool Enable)
void setOptLevel(CodeGenOptLevel Level)
Overrides the optimization level.
TargetOptions Options
unsigned EnableFastISel
EnableFastISel - This flag enables fast-path instruction selection which trades away generated code q...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetInstrInfo * getInstrInfo() const
virtual const TargetLowering * getTargetLowering() const
Wrapper pass for TargetTransformInfo.
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
bool hasBranchDivergence(const Function *F=nullptr) const
Return true if branch divergence exists.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
bool isTokenTy() const
Return true if this is 'token'.
Definition: Type.h:234
bool isVoidTy() const
Return true if this is 'void'.
Definition: Type.h:139
Analysis pass which computes UniformityInfo.
Legacy analysis pass which computes a CycleInfo.
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
iterator_range< user_iterator > users()
Definition: Value.h:421
bool use_empty() const
Definition: Value.h:344
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
self_iterator getIterator()
Definition: ilist_node.h:132
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:661
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
bool isConstantSplatVectorAllOnes(const SDNode *N, bool BuildVectorOnly=false)
Return true if the specified node is a BUILD_VECTOR or SPLAT_VECTOR where all of the elements are ~0 ...
@ TargetConstantPool
Definition: ISDOpcodes.h:174
@ CONVERGENCECTRL_ANCHOR
Definition: ISDOpcodes.h:1470
@ MDNODE_SDNODE
MDNODE_SDNODE - This is a node that holdes an MDNode*, which is used to reference metadata in the IR.
Definition: ISDOpcodes.h:1242
@ STRICT_FSETCC
STRICT_FSETCC/STRICT_FSETCCS - Constrained versions of SETCC, used for floating-point operands only.
Definition: ISDOpcodes.h:491
@ DELETED_NODE
DELETED_NODE - This is an illegal value that is used to catch errors.
Definition: ISDOpcodes.h:44
@ JUMP_TABLE_DEBUG_INFO
JUMP_TABLE_DEBUG_INFO - Jumptable debug info.
Definition: ISDOpcodes.h:1131
@ TargetBlockAddress
Definition: ISDOpcodes.h:176
@ ConstantFP
Definition: ISDOpcodes.h:77
@ INTRINSIC_VOID
OUTCHAIN = INTRINSIC_VOID(INCHAIN, INTRINSICID, arg1, arg2, ...) This node represents a target intrin...
Definition: ISDOpcodes.h:205
@ MEMBARRIER
MEMBARRIER - Compiler barrier only; generate a no-op.
Definition: ISDOpcodes.h:1299
@ STRICT_FSETCCS
Definition: ISDOpcodes.h:492
@ FAKE_USE
FAKE_USE represents a use of the operand but does not do anything.
Definition: ISDOpcodes.h:1383
@ FrameIndex
Definition: ISDOpcodes.h:80
@ EH_LABEL
EH_LABEL - Represents a label in mid basic block used to track locations needed for debug and excepti...
Definition: ISDOpcodes.h:1173
@ ANNOTATION_LABEL
ANNOTATION_LABEL - Represents a mid basic block label used by annotations.
Definition: ISDOpcodes.h:1179
@ STRICT_UINT_TO_FP
Definition: ISDOpcodes.h:465
@ TargetExternalSymbol
Definition: ISDOpcodes.h:175
@ CONVERGENCECTRL_ENTRY
Definition: ISDOpcodes.h:1471
@ TargetJumpTable
Definition: ISDOpcodes.h:173
@ WRITE_REGISTER
Definition: ISDOpcodes.h:125
@ STRICT_LROUND
Definition: ISDOpcodes.h:446
@ UNDEF
UNDEF - An undefined node.
Definition: ISDOpcodes.h:218
@ RegisterMask
Definition: ISDOpcodes.h:75
@ AssertAlign
AssertAlign - These nodes record if a register contains a value that has a known alignment and the tr...
Definition: ISDOpcodes.h:68
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
@ CopyFromReg
CopyFromReg - This node indicates that the input value is a virtual or physical register that is defi...
Definition: ISDOpcodes.h:215
@ TargetGlobalAddress
TargetGlobalAddress - Like GlobalAddress, but the DAG does no folding or anything else with this node...
Definition: ISDOpcodes.h:170
@ ARITH_FENCE
ARITH_FENCE - This corresponds to a arithmetic fence intrinsic.
Definition: ISDOpcodes.h:1296
@ EntryToken
EntryToken - This is the marker used to indicate the start of a region.
Definition: ISDOpcodes.h:47
@ READ_REGISTER
READ_REGISTER, WRITE_REGISTER - This node represents llvm.register on the DAG, which implements the n...
Definition: ISDOpcodes.h:124
@ CopyToReg
CopyToReg - This node has three operands: a chain, a register number to set to this value,...
Definition: ISDOpcodes.h:209
@ TargetConstantFP
Definition: ISDOpcodes.h:165
@ STRICT_LRINT
Definition: ISDOpcodes.h:448
@ TargetFrameIndex
Definition: ISDOpcodes.h:172
@ LIFETIME_START
This corresponds to the llvm.lifetime.
Definition: ISDOpcodes.h:1377
@ STRICT_SINT_TO_FP
STRICT_[US]INT_TO_FP - Convert a signed or unsigned integer to a floating point value.
Definition: ISDOpcodes.h:464
@ HANDLENODE
HANDLENODE node - Used as a handle for various purposes.
Definition: ISDOpcodes.h:1262
@ INLINEASM_BR
INLINEASM_BR - Branching version of inline asm. Used by asm-goto.
Definition: ISDOpcodes.h:1168
@ TargetConstant
TargetConstant* - Like Constant*, but the DAG does not do any folding, simplification,...
Definition: ISDOpcodes.h:164
@ AND
Bitwise operators - logical and, logical or, logical xor.
Definition: ISDOpcodes.h:709
@ INTRINSIC_WO_CHAIN
RESULT = INTRINSIC_WO_CHAIN(INTRINSICID, arg1, arg2, ...) This node represents a target intrinsic fun...
Definition: ISDOpcodes.h:190
@ PSEUDO_PROBE
Pseudo probe for AutoFDO, as a place holder in a basic block to improve the sample counts quality.
Definition: ISDOpcodes.h:1402
@ FREEZE
FREEZE - FREEZE(VAL) returns an arbitrary value if VAL is UNDEF (or is evaluated to UNDEF),...
Definition: ISDOpcodes.h:223
@ TokenFactor
TokenFactor - This node takes multiple tokens as input and produces a single token result.
Definition: ISDOpcodes.h:52
@ STRICT_LLRINT
Definition: ISDOpcodes.h:449
@ STRICT_LLROUND
Definition: ISDOpcodes.h:447
@ CONVERGENCECTRL_LOOP
Definition: ISDOpcodes.h:1472
@ INLINEASM
INLINEASM - Represents an inline asm block.
Definition: ISDOpcodes.h:1165
@ AssertSext
AssertSext, AssertZext - These nodes record if a register contains a value that has already been zero...
Definition: ISDOpcodes.h:61
@ AssertZext
Definition: ISDOpcodes.h:62
@ INTRINSIC_W_CHAIN
RESULT,OUTCHAIN = INTRINSIC_W_CHAIN(INCHAIN, INTRINSICID, arg1, ...) This node represents a target in...
Definition: ISDOpcodes.h:198
@ TargetGlobalTLSAddress
Definition: ISDOpcodes.h:171
bool isConstantSplatVectorAllZeros(const SDNode *N, bool BuildVectorOnly=false)
Return true if the specified node is a BUILD_VECTOR or SPLAT_VECTOR where all of the elements are 0 o...
CondCode
ISD::CondCode enum - These are ordered carefully to make the bitfields below work out,...
Definition: ISDOpcodes.h:1610
StringRef getBaseName(ID id)
Return the LLVM name for an intrinsic, without encoded types for overloading, such as "llvm....
Definition: Intrinsics.cpp:42
@ Kill
The last use of a register.
Reg
All possible values of the reg field in the ModR/M byte.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
DiagnosticInfoOptimizationBase::Argument NV
const_iterator end(StringRef path LLVM_LIFETIME_BOUND)
Get end iterator over path.
Definition: Path.cpp:235
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
ScheduleDAGSDNodes * createDefaultScheduler(SelectionDAGISel *IS, CodeGenOptLevel OptLevel)
createDefaultScheduler - This creates an instruction scheduler appropriate for the target.
@ Offset
Definition: DWP.cpp:480
bool succ_empty(const Instruction *I)
Definition: CFG.h:255
ScheduleDAGSDNodes * createBURRListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel OptLevel)
createBURRListDAGScheduler - This creates a bottom up register usage reduction list scheduler.
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
ScheduleDAGSDNodes * createHybridListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel)
createHybridListDAGScheduler - This creates a bottom up register pressure aware list scheduler that m...
MachineBasicBlock::iterator findSplitPointForStackProtector(MachineBasicBlock *BB, const TargetInstrInfo &TII)
Find the split point at which to splice the end of BB into its success stack protector check machine ...
bool TimePassesIsEnabled
If the user specifies the -time-passes argument on an LLVM tool command line then the value of this b...
LLT getLLTForMVT(MVT Ty)
Get a rough equivalent of an LLT for a given MVT.
void initializeBranchProbabilityInfoWrapperPassPass(PassRegistry &)
ScheduleDAGSDNodes * createFastDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel OptLevel)
createFastDAGScheduler - This creates a "fast" scheduler.
PreservedAnalyses getMachineFunctionPassPreservedAnalyses()
Returns the minimum set of Analyses that all machine function passes must preserve.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
Definition: STLExtras.h:2107
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1746
ScheduleDAGSDNodes * createDAGLinearizer(SelectionDAGISel *IS, CodeGenOptLevel OptLevel)
createDAGLinearizer - This creates a "no-scheduling" scheduler which linearize the DAG using topologi...
void initializeAAResultsWrapperPassPass(PassRegistry &)
void initializeGCModuleInfoPass(PassRegistry &)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool isFunctionInPrintList(StringRef FunctionName)
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:167
EHPersonality classifyEHPersonality(const Value *Pers)
See if the given exception handling personality function is one that we understand.
CodeGenOptLevel
Code generation optimization level.
Definition: CodeGen.h:54
bool isFuncletEHPersonality(EHPersonality Pers)
Returns true if this is a personality function that invokes handler funclets (which must return to it...
@ AfterLegalizeDAG
Definition: DAGCombine.h:19
@ AfterLegalizeVectorOps
Definition: DAGCombine.h:18
@ BeforeLegalizeTypes
Definition: DAGCombine.h:16
@ AfterLegalizeTypes
Definition: DAGCombine.h:17
ScheduleDAGSDNodes * createSourceListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel OptLevel)
createSourceListDAGScheduler - This creates a bottom up list scheduler that schedules nodes in source...
bool isAssignmentTrackingEnabled(const Module &M)
Return true if assignment tracking is enabled for module M.
Definition: DebugInfo.cpp:2299
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1873
ScheduleDAGSDNodes * createILPListDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel)
createILPListDAGScheduler - This creates a bottom up register pressure aware list scheduler that trie...
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1903
void initializeTargetLibraryInfoWrapperPassPass(PassRegistry &)
ScheduleDAGSDNodes * createVLIWDAGScheduler(SelectionDAGISel *IS, CodeGenOptLevel OptLevel)
createVLIWDAGScheduler - Scheduler for VLIW targets.
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
#define N
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
Extended Value Type.
Definition: ValueTypes.h:35
bool isSimple() const
Test if the given EVT is simple (as opposed to being extended).
Definition: ValueTypes.h:137
TypeSize getSizeInBits() const
Return the size of the specified value type in bits.
Definition: ValueTypes.h:368
MVT getSimpleVT() const
Return the SimpleValueType held in the specified simple EVT.
Definition: ValueTypes.h:311
bool isInteger() const
Return true if this is an integer or a vector integer type.
Definition: ValueTypes.h:152
This class is basically a combination of TimeRegion and Timer.
Definition: Timer.h:168
This represents a list of ValueType's that has been intern'd by a SelectionDAG.
Clients of various APIs that cause global effects on the DAG can optionally implement this interface.
Definition: SelectionDAG.h:317
void addIPToStateRange(const InvokeInst *II, MCSymbol *InvokeBegin, MCSymbol *InvokeEnd)
DenseMap< const BasicBlock *, int > BlockToStateMap
Definition: WinEHFuncInfo.h:95