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