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