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