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