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