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