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