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