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/None.h"
19 #include "llvm/ADT/PostOrderIterator.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallSet.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/ADT/Statistic.h"
25 #include "llvm/ADT/StringRef.h"
26 #include "llvm/Analysis/AliasAnalysis.h"
27 #include "llvm/Analysis/BranchProbabilityInfo.h"
28 #include "llvm/Analysis/CFG.h"
29 #include "llvm/Analysis/EHPersonalities.h"
30 #include "llvm/Analysis/LazyBlockFrequencyInfo.h"
31 #include "llvm/Analysis/LegacyDivergenceAnalysis.h"
32 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
33 #include "llvm/Analysis/ProfileSummaryInfo.h"
34 #include "llvm/Analysis/TargetLibraryInfo.h"
35 #include "llvm/Analysis/TargetTransformInfo.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/StackProtector.h"
55 #include "llvm/CodeGen/SwiftErrorValueTracking.h"
56 #include "llvm/CodeGen/TargetInstrInfo.h"
57 #include "llvm/CodeGen/TargetLowering.h"
58 #include "llvm/CodeGen/TargetRegisterInfo.h"
59 #include "llvm/CodeGen/TargetSubtargetInfo.h"
60 #include "llvm/CodeGen/ValueTypes.h"
61 #include "llvm/IR/BasicBlock.h"
62 #include "llvm/IR/Constants.h"
63 #include "llvm/IR/DataLayout.h"
64 #include "llvm/IR/DebugInfoMetadata.h"
65 #include "llvm/IR/DebugLoc.h"
66 #include "llvm/IR/DiagnosticInfo.h"
67 #include "llvm/IR/Dominators.h"
68 #include "llvm/IR/Function.h"
69 #include "llvm/IR/InlineAsm.h"
70 #include "llvm/IR/InstIterator.h"
71 #include "llvm/IR/InstrTypes.h"
72 #include "llvm/IR/Instruction.h"
73 #include "llvm/IR/Instructions.h"
74 #include "llvm/IR/IntrinsicInst.h"
75 #include "llvm/IR/Intrinsics.h"
76 #include "llvm/IR/IntrinsicsWebAssembly.h"
77 #include "llvm/IR/Metadata.h"
78 #include "llvm/IR/Statepoint.h"
79 #include "llvm/IR/Type.h"
80 #include "llvm/IR/User.h"
81 #include "llvm/IR/Value.h"
82 #include "llvm/InitializePasses.h"
83 #include "llvm/MC/MCInstrDesc.h"
84 #include "llvm/MC/MCRegisterInfo.h"
85 #include "llvm/Pass.h"
86 #include "llvm/Support/BranchProbability.h"
87 #include "llvm/Support/Casting.h"
88 #include "llvm/Support/CodeGen.h"
89 #include "llvm/Support/CommandLine.h"
90 #include "llvm/Support/Compiler.h"
91 #include "llvm/Support/Debug.h"
92 #include "llvm/Support/ErrorHandling.h"
93 #include "llvm/Support/KnownBits.h"
94 #include "llvm/Support/MachineValueType.h"
95 #include "llvm/Support/Timer.h"
96 #include "llvm/Support/raw_ostream.h"
97 #include "llvm/Target/TargetIntrinsicInfo.h"
98 #include "llvm/Target/TargetMachine.h"
99 #include "llvm/Target/TargetOptions.h"
100 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
101 #include <algorithm>
102 #include <cassert>
103 #include <cstdint>
104 #include <iterator>
105 #include <limits>
106 #include <memory>
107 #include <string>
108 #include <utility>
109 #include <vector>
110
111 using namespace llvm;
112
113 #define DEBUG_TYPE "isel"
114
115 STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on");
116 STATISTIC(NumFastIselSuccess, "Number of instructions fast isel selected");
117 STATISTIC(NumFastIselBlocks, "Number of blocks selected entirely by fast isel");
118 STATISTIC(NumDAGBlocks, "Number of blocks selected using DAG");
119 STATISTIC(NumDAGIselRetries,"Number of times dag isel has to try another path");
120 STATISTIC(NumEntryBlocks, "Number of entry blocks encountered");
121 STATISTIC(NumFastIselFailLowerArguments,
122 "Number of entry blocks where fast isel failed to lower arguments");
123
124 static cl::opt<int> EnableFastISelAbort(
125 "fast-isel-abort", cl::Hidden,
126 cl::desc("Enable abort calls when \"fast\" instruction selection "
127 "fails to lower an instruction: 0 disable the abort, 1 will "
128 "abort but for args, calls and terminators, 2 will also "
129 "abort for argument lowering, and 3 will never fallback "
130 "to SelectionDAG."));
131
132 static cl::opt<bool> EnableFastISelFallbackReport(
133 "fast-isel-report-on-fallback", cl::Hidden,
134 cl::desc("Emit a diagnostic when \"fast\" instruction selection "
135 "falls back to SelectionDAG."));
136
137 static cl::opt<bool>
138 UseMBPI("use-mbpi",
139 cl::desc("use Machine Branch Probability Info"),
140 cl::init(true), cl::Hidden);
141
142 #ifndef NDEBUG
143 static cl::opt<std::string>
144 FilterDAGBasicBlockName("filter-view-dags", cl::Hidden,
145 cl::desc("Only display the basic block whose name "
146 "matches this for all view-*-dags options"));
147 static cl::opt<bool>
148 ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
149 cl::desc("Pop up a window to show dags before the first "
150 "dag combine pass"));
151 static cl::opt<bool>
152 ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden,
153 cl::desc("Pop up a window to show dags before legalize types"));
154 static cl::opt<bool>
155 ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden,
156 cl::desc("Pop up a window to show dags before the post "
157 "legalize types dag combine pass"));
158 static cl::opt<bool>
159 ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
160 cl::desc("Pop up a window to show dags before legalize"));
161 static cl::opt<bool>
162 ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
163 cl::desc("Pop up a window to show dags before the second "
164 "dag combine pass"));
165 static cl::opt<bool>
166 ViewISelDAGs("view-isel-dags", cl::Hidden,
167 cl::desc("Pop up a window to show isel dags as they are selected"));
168 static cl::opt<bool>
169 ViewSchedDAGs("view-sched-dags", cl::Hidden,
170 cl::desc("Pop up a window to show sched dags as they are processed"));
171 static cl::opt<bool>
172 ViewSUnitDAGs("view-sunit-dags", cl::Hidden,
173 cl::desc("Pop up a window to show SUnit dags after they are processed"));
174 #else
175 static const bool ViewDAGCombine1 = false, ViewLegalizeTypesDAGs = false,
176 ViewDAGCombineLT = false, ViewLegalizeDAGs = false,
177 ViewDAGCombine2 = false, ViewISelDAGs = false,
178 ViewSchedDAGs = false, ViewSUnitDAGs = false;
179 #endif
180
181 //===---------------------------------------------------------------------===//
182 ///
183 /// RegisterScheduler class - Track the registration of instruction schedulers.
184 ///
185 //===---------------------------------------------------------------------===//
186 MachinePassRegistry<RegisterScheduler::FunctionPassCtor>
187 RegisterScheduler::Registry;
188
189 //===---------------------------------------------------------------------===//
190 ///
191 /// ISHeuristic command line option for instruction schedulers.
192 ///
193 //===---------------------------------------------------------------------===//
194 static cl::opt<RegisterScheduler::FunctionPassCtor, false,
195 RegisterPassParser<RegisterScheduler>>
196 ISHeuristic("pre-RA-sched",
197 cl::init(&createDefaultScheduler), cl::Hidden,
198 cl::desc("Instruction schedulers available (before register"
199 " allocation):"));
200
201 static RegisterScheduler
202 defaultListDAGScheduler("default", "Best scheduler for the target",
203 createDefaultScheduler);
204
205 namespace llvm {
206
207 //===--------------------------------------------------------------------===//
208 /// This class is used by SelectionDAGISel to temporarily override
209 /// the optimization level on a per-function basis.
210 class OptLevelChanger {
211 SelectionDAGISel &IS;
212 CodeGenOpt::Level SavedOptLevel;
213 bool SavedFastISel;
214
215 public:
OptLevelChanger(SelectionDAGISel & ISel,CodeGenOpt::Level NewOptLevel)216 OptLevelChanger(SelectionDAGISel &ISel,
217 CodeGenOpt::Level NewOptLevel) : IS(ISel) {
218 SavedOptLevel = IS.OptLevel;
219 SavedFastISel = IS.TM.Options.EnableFastISel;
220 if (NewOptLevel == SavedOptLevel)
221 return;
222 IS.OptLevel = NewOptLevel;
223 IS.TM.setOptLevel(NewOptLevel);
224 LLVM_DEBUG(dbgs() << "\nChanging optimization level for Function "
225 << IS.MF->getFunction().getName() << "\n");
226 LLVM_DEBUG(dbgs() << "\tBefore: -O" << SavedOptLevel << " ; After: -O"
227 << NewOptLevel << "\n");
228 if (NewOptLevel == CodeGenOpt::None) {
229 IS.TM.setFastISel(IS.TM.getO0WantsFastISel());
230 LLVM_DEBUG(
231 dbgs() << "\tFastISel is "
232 << (IS.TM.Options.EnableFastISel ? "enabled" : "disabled")
233 << "\n");
234 }
235 }
236
~OptLevelChanger()237 ~OptLevelChanger() {
238 if (IS.OptLevel == SavedOptLevel)
239 return;
240 LLVM_DEBUG(dbgs() << "\nRestoring optimization level for Function "
241 << IS.MF->getFunction().getName() << "\n");
242 LLVM_DEBUG(dbgs() << "\tBefore: -O" << IS.OptLevel << " ; After: -O"
243 << SavedOptLevel << "\n");
244 IS.OptLevel = SavedOptLevel;
245 IS.TM.setOptLevel(SavedOptLevel);
246 IS.TM.setFastISel(SavedFastISel);
247 }
248 };
249
250 //===--------------------------------------------------------------------===//
251 /// createDefaultScheduler - This creates an instruction scheduler appropriate
252 /// for the target.
createDefaultScheduler(SelectionDAGISel * IS,CodeGenOpt::Level OptLevel)253 ScheduleDAGSDNodes* createDefaultScheduler(SelectionDAGISel *IS,
254 CodeGenOpt::Level OptLevel) {
255 const TargetLowering *TLI = IS->TLI;
256 const TargetSubtargetInfo &ST = IS->MF->getSubtarget();
257
258 // Try first to see if the Target has its own way of selecting a scheduler
259 if (auto *SchedulerCtor = ST.getDAGScheduler(OptLevel)) {
260 return SchedulerCtor(IS, OptLevel);
261 }
262
263 if (OptLevel == CodeGenOpt::None ||
264 (ST.enableMachineScheduler() && ST.enableMachineSchedDefaultSched()) ||
265 TLI->getSchedulingPreference() == Sched::Source)
266 return createSourceListDAGScheduler(IS, OptLevel);
267 if (TLI->getSchedulingPreference() == Sched::RegPressure)
268 return createBURRListDAGScheduler(IS, OptLevel);
269 if (TLI->getSchedulingPreference() == Sched::Hybrid)
270 return createHybridListDAGScheduler(IS, OptLevel);
271 if (TLI->getSchedulingPreference() == Sched::VLIW)
272 return createVLIWDAGScheduler(IS, OptLevel);
273 if (TLI->getSchedulingPreference() == Sched::Fast)
274 return createFastDAGScheduler(IS, OptLevel);
275 if (TLI->getSchedulingPreference() == Sched::Linearize)
276 return createDAGLinearizer(IS, OptLevel);
277 assert(TLI->getSchedulingPreference() == Sched::ILP &&
278 "Unknown sched type!");
279 return createILPListDAGScheduler(IS, OptLevel);
280 }
281
282 } // end namespace llvm
283
284 // EmitInstrWithCustomInserter - This method should be implemented by targets
285 // that mark instructions with the 'usesCustomInserter' flag. These
286 // instructions are special in various ways, which require special support to
287 // insert. The specified MachineInstr is created but not inserted into any
288 // basic blocks, and this method is called to expand it into a sequence of
289 // instructions, potentially also creating new basic blocks and control flow.
290 // When new basic blocks are inserted and the edges from MBB to its successors
291 // are modified, the method should insert pairs of <OldSucc, NewSucc> into the
292 // DenseMap.
293 MachineBasicBlock *
EmitInstrWithCustomInserter(MachineInstr & MI,MachineBasicBlock * MBB) const294 TargetLowering::EmitInstrWithCustomInserter(MachineInstr &MI,
295 MachineBasicBlock *MBB) const {
296 #ifndef NDEBUG
297 dbgs() << "If a target marks an instruction with "
298 "'usesCustomInserter', it must implement "
299 "TargetLowering::EmitInstrWithCustomInserter!";
300 #endif
301 llvm_unreachable(nullptr);
302 }
303
AdjustInstrPostInstrSelection(MachineInstr & MI,SDNode * Node) const304 void TargetLowering::AdjustInstrPostInstrSelection(MachineInstr &MI,
305 SDNode *Node) const {
306 assert(!MI.hasPostISelHook() &&
307 "If a target marks an instruction with 'hasPostISelHook', "
308 "it must implement TargetLowering::AdjustInstrPostInstrSelection!");
309 }
310
311 //===----------------------------------------------------------------------===//
312 // SelectionDAGISel code
313 //===----------------------------------------------------------------------===//
314
SelectionDAGISel(TargetMachine & tm,CodeGenOpt::Level OL)315 SelectionDAGISel::SelectionDAGISel(TargetMachine &tm, CodeGenOpt::Level OL)
316 : MachineFunctionPass(ID), TM(tm), FuncInfo(new FunctionLoweringInfo()),
317 SwiftError(new SwiftErrorValueTracking()),
318 CurDAG(new SelectionDAG(tm, OL)),
319 SDB(std::make_unique<SelectionDAGBuilder>(*CurDAG, *FuncInfo, *SwiftError,
320 OL)),
321 AA(), GFI(), OptLevel(OL), DAGSize(0) {
322 initializeGCModuleInfoPass(*PassRegistry::getPassRegistry());
323 initializeBranchProbabilityInfoWrapperPassPass(
324 *PassRegistry::getPassRegistry());
325 initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
326 initializeTargetLibraryInfoWrapperPassPass(*PassRegistry::getPassRegistry());
327 }
328
~SelectionDAGISel()329 SelectionDAGISel::~SelectionDAGISel() {
330 delete CurDAG;
331 delete SwiftError;
332 }
333
getAnalysisUsage(AnalysisUsage & AU) const334 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
335 if (OptLevel != CodeGenOpt::None)
336 AU.addRequired<AAResultsWrapperPass>();
337 AU.addRequired<GCModuleInfo>();
338 AU.addRequired<StackProtector>();
339 AU.addPreserved<GCModuleInfo>();
340 AU.addRequired<TargetLibraryInfoWrapperPass>();
341 AU.addRequired<TargetTransformInfoWrapperPass>();
342 if (UseMBPI && OptLevel != CodeGenOpt::None)
343 AU.addRequired<BranchProbabilityInfoWrapperPass>();
344 AU.addRequired<ProfileSummaryInfoWrapperPass>();
345 if (OptLevel != CodeGenOpt::None)
346 LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU);
347 MachineFunctionPass::getAnalysisUsage(AU);
348 }
349
350 /// SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that
351 /// may trap on it. In this case we have to split the edge so that the path
352 /// through the predecessor block that doesn't go to the phi block doesn't
353 /// execute the possibly trapping instruction. If available, we pass domtree
354 /// and loop info to be updated when we split critical edges. This is because
355 /// SelectionDAGISel preserves these analyses.
356 /// This is required for correctness, so it must be done at -O0.
357 ///
SplitCriticalSideEffectEdges(Function & Fn,DominatorTree * DT,LoopInfo * LI)358 static void SplitCriticalSideEffectEdges(Function &Fn, DominatorTree *DT,
359 LoopInfo *LI) {
360 // Loop for blocks with phi nodes.
361 for (BasicBlock &BB : Fn) {
362 PHINode *PN = dyn_cast<PHINode>(BB.begin());
363 if (!PN) continue;
364
365 ReprocessBlock:
366 // For each block with a PHI node, check to see if any of the input values
367 // are potentially trapping constant expressions. Constant expressions are
368 // the only potentially trapping value that can occur as the argument to a
369 // PHI.
370 for (BasicBlock::iterator I = BB.begin(); (PN = dyn_cast<PHINode>(I)); ++I)
371 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
372 ConstantExpr *CE = dyn_cast<ConstantExpr>(PN->getIncomingValue(i));
373 if (!CE || !CE->canTrap()) continue;
374
375 // The only case we have to worry about is when the edge is critical.
376 // Since this block has a PHI Node, we assume it has multiple input
377 // edges: check to see if the pred has multiple successors.
378 BasicBlock *Pred = PN->getIncomingBlock(i);
379 if (Pred->getTerminator()->getNumSuccessors() == 1)
380 continue;
381
382 // Okay, we have to split this edge.
383 SplitCriticalEdge(
384 Pred->getTerminator(), GetSuccessorNumber(Pred, &BB),
385 CriticalEdgeSplittingOptions(DT, LI).setMergeIdenticalEdges());
386 goto ReprocessBlock;
387 }
388 }
389 }
390
computeUsesMSVCFloatingPoint(const Triple & TT,const Function & F,MachineModuleInfo & MMI)391 static void computeUsesMSVCFloatingPoint(const Triple &TT, const Function &F,
392 MachineModuleInfo &MMI) {
393 // Only needed for MSVC
394 if (!TT.isWindowsMSVCEnvironment())
395 return;
396
397 // If it's already set, nothing to do.
398 if (MMI.usesMSVCFloatingPoint())
399 return;
400
401 for (const Instruction &I : instructions(F)) {
402 if (I.getType()->isFPOrFPVectorTy()) {
403 MMI.setUsesMSVCFloatingPoint(true);
404 return;
405 }
406 for (const auto &Op : I.operands()) {
407 if (Op->getType()->isFPOrFPVectorTy()) {
408 MMI.setUsesMSVCFloatingPoint(true);
409 return;
410 }
411 }
412 }
413 }
414
runOnMachineFunction(MachineFunction & mf)415 bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
416 // If we already selected that function, we do not need to run SDISel.
417 if (mf.getProperties().hasProperty(
418 MachineFunctionProperties::Property::Selected))
419 return false;
420 // Do some sanity-checking on the command-line options.
421 assert((!EnableFastISelAbort || TM.Options.EnableFastISel) &&
422 "-fast-isel-abort > 0 requires -fast-isel");
423
424 const Function &Fn = mf.getFunction();
425 MF = &mf;
426
427 // Reset the target options before resetting the optimization
428 // level below.
429 // FIXME: This is a horrible hack and should be processed via
430 // codegen looking at the optimization level explicitly when
431 // it wants to look at it.
432 TM.resetTargetOptions(Fn);
433 // Reset OptLevel to None for optnone functions.
434 CodeGenOpt::Level NewOptLevel = OptLevel;
435 if (OptLevel != CodeGenOpt::None && skipFunction(Fn))
436 NewOptLevel = CodeGenOpt::None;
437 OptLevelChanger OLC(*this, NewOptLevel);
438
439 TII = MF->getSubtarget().getInstrInfo();
440 TLI = MF->getSubtarget().getTargetLowering();
441 RegInfo = &MF->getRegInfo();
442 LibInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(Fn);
443 GFI = Fn.hasGC() ? &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn) : nullptr;
444 ORE = std::make_unique<OptimizationRemarkEmitter>(&Fn);
445 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
446 DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
447 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
448 LoopInfo *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
449 auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
450 BlockFrequencyInfo *BFI = nullptr;
451 if (PSI && PSI->hasProfileSummary() && OptLevel != CodeGenOpt::None)
452 BFI = &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI();
453
454 LLVM_DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n");
455
456 SplitCriticalSideEffectEdges(const_cast<Function &>(Fn), DT, LI);
457
458 CurDAG->init(*MF, *ORE, this, LibInfo,
459 getAnalysisIfAvailable<LegacyDivergenceAnalysis>(), PSI, BFI);
460 FuncInfo->set(Fn, *MF, CurDAG);
461 SwiftError->setFunction(*MF);
462
463 // Now get the optional analyzes if we want to.
464 // This is based on the possibly changed OptLevel (after optnone is taken
465 // into account). That's unfortunate but OK because it just means we won't
466 // ask for passes that have been required anyway.
467
468 if (UseMBPI && OptLevel != CodeGenOpt::None)
469 FuncInfo->BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
470 else
471 FuncInfo->BPI = nullptr;
472
473 if (OptLevel != CodeGenOpt::None)
474 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
475 else
476 AA = nullptr;
477
478 SDB->init(GFI, AA, LibInfo);
479
480 MF->setHasInlineAsm(false);
481
482 FuncInfo->SplitCSR = false;
483
484 // We split CSR if the target supports it for the given function
485 // and the function has only return exits.
486 if (OptLevel != CodeGenOpt::None && TLI->supportSplitCSR(MF)) {
487 FuncInfo->SplitCSR = true;
488
489 // Collect all the return blocks.
490 for (const BasicBlock &BB : Fn) {
491 if (!succ_empty(&BB))
492 continue;
493
494 const Instruction *Term = BB.getTerminator();
495 if (isa<UnreachableInst>(Term) || isa<ReturnInst>(Term))
496 continue;
497
498 // Bail out if the exit block is not Return nor Unreachable.
499 FuncInfo->SplitCSR = false;
500 break;
501 }
502 }
503
504 MachineBasicBlock *EntryMBB = &MF->front();
505 if (FuncInfo->SplitCSR)
506 // This performs initialization so lowering for SplitCSR will be correct.
507 TLI->initializeSplitCSR(EntryMBB);
508
509 SelectAllBasicBlocks(Fn);
510 if (FastISelFailed && EnableFastISelFallbackReport) {
511 DiagnosticInfoISelFallback DiagFallback(Fn);
512 Fn.getContext().diagnose(DiagFallback);
513 }
514
515 // Replace forward-declared registers with the registers containing
516 // the desired value.
517 // Note: it is important that this happens **before** the call to
518 // EmitLiveInCopies, since implementations can skip copies of unused
519 // registers. If we don't apply the reg fixups before, some registers may
520 // appear as unused and will be skipped, resulting in bad MI.
521 MachineRegisterInfo &MRI = MF->getRegInfo();
522 for (DenseMap<Register, Register>::iterator I = FuncInfo->RegFixups.begin(),
523 E = FuncInfo->RegFixups.end();
524 I != E; ++I) {
525 Register From = I->first;
526 Register To = I->second;
527 // If To is also scheduled to be replaced, find what its ultimate
528 // replacement is.
529 while (true) {
530 DenseMap<Register, Register>::iterator J = FuncInfo->RegFixups.find(To);
531 if (J == E)
532 break;
533 To = J->second;
534 }
535 // Make sure the new register has a sufficiently constrained register class.
536 if (Register::isVirtualRegister(From) && Register::isVirtualRegister(To))
537 MRI.constrainRegClass(To, MRI.getRegClass(From));
538 // Replace it.
539
540 // Replacing one register with another won't touch the kill flags.
541 // We need to conservatively clear the kill flags as a kill on the old
542 // register might dominate existing uses of the new register.
543 if (!MRI.use_empty(To))
544 MRI.clearKillFlags(From);
545 MRI.replaceRegWith(From, To);
546 }
547
548 // If the first basic block in the function has live ins that need to be
549 // copied into vregs, emit the copies into the top of the block before
550 // emitting the code for the block.
551 const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();
552 RegInfo->EmitLiveInCopies(EntryMBB, TRI, *TII);
553
554 // Insert copies in the entry block and the return blocks.
555 if (FuncInfo->SplitCSR) {
556 SmallVector<MachineBasicBlock*, 4> Returns;
557 // Collect all the return blocks.
558 for (MachineBasicBlock &MBB : mf) {
559 if (!MBB.succ_empty())
560 continue;
561
562 MachineBasicBlock::iterator Term = MBB.getFirstTerminator();
563 if (Term != MBB.end() && Term->isReturn()) {
564 Returns.push_back(&MBB);
565 continue;
566 }
567 }
568 TLI->insertCopiesSplitCSR(EntryMBB, Returns);
569 }
570
571 DenseMap<unsigned, unsigned> LiveInMap;
572 if (!FuncInfo->ArgDbgValues.empty())
573 for (std::pair<unsigned, unsigned> LI : RegInfo->liveins())
574 if (LI.second)
575 LiveInMap.insert(LI);
576
577 // Insert DBG_VALUE instructions for function arguments to the entry block.
578 for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; ++i) {
579 MachineInstr *MI = FuncInfo->ArgDbgValues[e - i - 1];
580 assert(MI->getOpcode() != TargetOpcode::DBG_VALUE_LIST &&
581 "Function parameters should not be described by DBG_VALUE_LIST.");
582 bool hasFI = MI->getOperand(0).isFI();
583 Register Reg =
584 hasFI ? TRI.getFrameRegister(*MF) : MI->getOperand(0).getReg();
585 if (Register::isPhysicalRegister(Reg))
586 EntryMBB->insert(EntryMBB->begin(), MI);
587 else {
588 MachineInstr *Def = RegInfo->getVRegDef(Reg);
589 if (Def) {
590 MachineBasicBlock::iterator InsertPos = Def;
591 // FIXME: VR def may not be in entry block.
592 Def->getParent()->insert(std::next(InsertPos), MI);
593 } else
594 LLVM_DEBUG(dbgs() << "Dropping debug info for dead vreg"
595 << Register::virtReg2Index(Reg) << "\n");
596 }
597
598 // If Reg is live-in then update debug info to track its copy in a vreg.
599 DenseMap<unsigned, unsigned>::iterator LDI = LiveInMap.find(Reg);
600 if (LDI != LiveInMap.end()) {
601 assert(!hasFI && "There's no handling of frame pointer updating here yet "
602 "- add if needed");
603 MachineInstr *Def = RegInfo->getVRegDef(LDI->second);
604 MachineBasicBlock::iterator InsertPos = Def;
605 const MDNode *Variable = MI->getDebugVariable();
606 const MDNode *Expr = MI->getDebugExpression();
607 DebugLoc DL = MI->getDebugLoc();
608 bool IsIndirect = MI->isIndirectDebugValue();
609 if (IsIndirect)
610 assert(MI->getOperand(1).getImm() == 0 &&
611 "DBG_VALUE with nonzero offset");
612 assert(cast<DILocalVariable>(Variable)->isValidLocationForIntrinsic(DL) &&
613 "Expected inlined-at fields to agree");
614 assert(MI->getOpcode() != TargetOpcode::DBG_VALUE_LIST &&
615 "Didn't expect to see a DBG_VALUE_LIST here");
616 // Def is never a terminator here, so it is ok to increment InsertPos.
617 BuildMI(*EntryMBB, ++InsertPos, DL, TII->get(TargetOpcode::DBG_VALUE),
618 IsIndirect, LDI->second, Variable, Expr);
619
620 // If this vreg is directly copied into an exported register then
621 // that COPY instructions also need DBG_VALUE, if it is the only
622 // user of LDI->second.
623 MachineInstr *CopyUseMI = nullptr;
624 for (MachineRegisterInfo::use_instr_iterator
625 UI = RegInfo->use_instr_begin(LDI->second),
626 E = RegInfo->use_instr_end(); UI != E; ) {
627 MachineInstr *UseMI = &*(UI++);
628 if (UseMI->isDebugValue()) continue;
629 if (UseMI->isCopy() && !CopyUseMI && UseMI->getParent() == EntryMBB) {
630 CopyUseMI = UseMI; continue;
631 }
632 // Otherwise this is another use or second copy use.
633 CopyUseMI = nullptr; break;
634 }
635 if (CopyUseMI &&
636 TRI.getRegSizeInBits(LDI->second, MRI) ==
637 TRI.getRegSizeInBits(CopyUseMI->getOperand(0).getReg(), MRI)) {
638 // Use MI's debug location, which describes where Variable was
639 // declared, rather than whatever is attached to CopyUseMI.
640 MachineInstr *NewMI =
641 BuildMI(*MF, DL, TII->get(TargetOpcode::DBG_VALUE), IsIndirect,
642 CopyUseMI->getOperand(0).getReg(), Variable, Expr);
643 MachineBasicBlock::iterator Pos = CopyUseMI;
644 EntryMBB->insertAfter(Pos, NewMI);
645 }
646 }
647 }
648
649 // Determine if there are any calls in this machine function.
650 MachineFrameInfo &MFI = MF->getFrameInfo();
651 for (const auto &MBB : *MF) {
652 if (MFI.hasCalls() && MF->hasInlineAsm())
653 break;
654
655 for (const auto &MI : MBB) {
656 const MCInstrDesc &MCID = TII->get(MI.getOpcode());
657 if ((MCID.isCall() && !MCID.isReturn()) ||
658 MI.isStackAligningInlineAsm()) {
659 MFI.setHasCalls(true);
660 }
661 if (MI.isInlineAsm()) {
662 MF->setHasInlineAsm(true);
663 }
664 }
665 }
666
667 // Determine if there is a call to setjmp in the machine function.
668 MF->setExposesReturnsTwice(Fn.callsFunctionThatReturnsTwice());
669
670 // Determine if floating point is used for msvc
671 computeUsesMSVCFloatingPoint(TM.getTargetTriple(), Fn, MF->getMMI());
672
673 // Release function-specific state. SDB and CurDAG are already cleared
674 // at this point.
675 FuncInfo->clear();
676
677 LLVM_DEBUG(dbgs() << "*** MachineFunction at end of ISel ***\n");
678 LLVM_DEBUG(MF->print(dbgs()));
679
680 return true;
681 }
682
reportFastISelFailure(MachineFunction & MF,OptimizationRemarkEmitter & ORE,OptimizationRemarkMissed & R,bool ShouldAbort)683 static void reportFastISelFailure(MachineFunction &MF,
684 OptimizationRemarkEmitter &ORE,
685 OptimizationRemarkMissed &R,
686 bool ShouldAbort) {
687 // Print the function name explicitly if we don't have a debug location (which
688 // makes the diagnostic less useful) or if we're going to emit a raw error.
689 if (!R.getLocation().isValid() || ShouldAbort)
690 R << (" (in function: " + MF.getName() + ")").str();
691
692 if (ShouldAbort)
693 report_fatal_error(R.getMsg());
694
695 ORE.emit(R);
696 }
697
SelectBasicBlock(BasicBlock::const_iterator Begin,BasicBlock::const_iterator End,bool & HadTailCall)698 void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,
699 BasicBlock::const_iterator End,
700 bool &HadTailCall) {
701 // Allow creating illegal types during DAG building for the basic block.
702 CurDAG->NewNodesMustHaveLegalTypes = false;
703
704 // Lower the instructions. If a call is emitted as a tail call, cease emitting
705 // nodes for this block.
706 for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I) {
707 if (!ElidedArgCopyInstrs.count(&*I))
708 SDB->visit(*I);
709 }
710
711 // Make sure the root of the DAG is up-to-date.
712 CurDAG->setRoot(SDB->getControlRoot());
713 HadTailCall = SDB->HasTailCall;
714 SDB->resolveOrClearDbgInfo();
715 SDB->clear();
716
717 // Final step, emit the lowered DAG as machine code.
718 CodeGenAndEmitDAG();
719 }
720
ComputeLiveOutVRegInfo()721 void SelectionDAGISel::ComputeLiveOutVRegInfo() {
722 SmallPtrSet<SDNode *, 16> Added;
723 SmallVector<SDNode*, 128> Worklist;
724
725 Worklist.push_back(CurDAG->getRoot().getNode());
726 Added.insert(CurDAG->getRoot().getNode());
727
728 KnownBits Known;
729
730 do {
731 SDNode *N = Worklist.pop_back_val();
732
733 // Otherwise, add all chain operands to the worklist.
734 for (const SDValue &Op : N->op_values())
735 if (Op.getValueType() == MVT::Other && Added.insert(Op.getNode()).second)
736 Worklist.push_back(Op.getNode());
737
738 // If this is a CopyToReg with a vreg dest, process it.
739 if (N->getOpcode() != ISD::CopyToReg)
740 continue;
741
742 unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();
743 if (!Register::isVirtualRegister(DestReg))
744 continue;
745
746 // Ignore non-integer values.
747 SDValue Src = N->getOperand(2);
748 EVT SrcVT = Src.getValueType();
749 if (!SrcVT.isInteger())
750 continue;
751
752 unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);
753 Known = CurDAG->computeKnownBits(Src);
754 FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, Known);
755 } while (!Worklist.empty());
756 }
757
CodeGenAndEmitDAG()758 void SelectionDAGISel::CodeGenAndEmitDAG() {
759 StringRef GroupName = "sdag";
760 StringRef GroupDescription = "Instruction Selection and Scheduling";
761 std::string BlockName;
762 bool MatchFilterBB = false; (void)MatchFilterBB;
763 #ifndef NDEBUG
764 TargetTransformInfo &TTI =
765 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(*FuncInfo->Fn);
766 #endif
767
768 // Pre-type legalization allow creation of any node types.
769 CurDAG->NewNodesMustHaveLegalTypes = false;
770
771 #ifndef NDEBUG
772 MatchFilterBB = (FilterDAGBasicBlockName.empty() ||
773 FilterDAGBasicBlockName ==
774 FuncInfo->MBB->getBasicBlock()->getName());
775 #endif
776 #ifdef NDEBUG
777 if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewDAGCombineLT ||
778 ViewLegalizeDAGs || ViewDAGCombine2 || ViewISelDAGs || ViewSchedDAGs ||
779 ViewSUnitDAGs)
780 #endif
781 {
782 BlockName =
783 (MF->getName() + ":" + FuncInfo->MBB->getBasicBlock()->getName()).str();
784 }
785 LLVM_DEBUG(dbgs() << "Initial selection DAG: "
786 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
787 << "'\n";
788 CurDAG->dump());
789
790 #ifndef NDEBUG
791 if (TTI.hasBranchDivergence())
792 CurDAG->VerifyDAGDiverence();
793 #endif
794
795 if (ViewDAGCombine1 && MatchFilterBB)
796 CurDAG->viewGraph("dag-combine1 input for " + BlockName);
797
798 // Run the DAG combiner in pre-legalize mode.
799 {
800 NamedRegionTimer T("combine1", "DAG Combining 1", GroupName,
801 GroupDescription, TimePassesIsEnabled);
802 CurDAG->Combine(BeforeLegalizeTypes, AA, OptLevel);
803 }
804
805 LLVM_DEBUG(dbgs() << "Optimized lowered selection DAG: "
806 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
807 << "'\n";
808 CurDAG->dump());
809
810 #ifndef NDEBUG
811 if (TTI.hasBranchDivergence())
812 CurDAG->VerifyDAGDiverence();
813 #endif
814
815 // Second step, hack on the DAG until it only uses operations and types that
816 // the target supports.
817 if (ViewLegalizeTypesDAGs && MatchFilterBB)
818 CurDAG->viewGraph("legalize-types input for " + BlockName);
819
820 bool Changed;
821 {
822 NamedRegionTimer T("legalize_types", "Type Legalization", GroupName,
823 GroupDescription, TimePassesIsEnabled);
824 Changed = CurDAG->LegalizeTypes();
825 }
826
827 LLVM_DEBUG(dbgs() << "Type-legalized selection DAG: "
828 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
829 << "'\n";
830 CurDAG->dump());
831
832 #ifndef NDEBUG
833 if (TTI.hasBranchDivergence())
834 CurDAG->VerifyDAGDiverence();
835 #endif
836
837 // Only allow creation of legal node types.
838 CurDAG->NewNodesMustHaveLegalTypes = true;
839
840 if (Changed) {
841 if (ViewDAGCombineLT && MatchFilterBB)
842 CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
843
844 // Run the DAG combiner in post-type-legalize mode.
845 {
846 NamedRegionTimer T("combine_lt", "DAG Combining after legalize types",
847 GroupName, GroupDescription, TimePassesIsEnabled);
848 CurDAG->Combine(AfterLegalizeTypes, AA, OptLevel);
849 }
850
851 LLVM_DEBUG(dbgs() << "Optimized type-legalized selection DAG: "
852 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
853 << "'\n";
854 CurDAG->dump());
855
856 #ifndef NDEBUG
857 if (TTI.hasBranchDivergence())
858 CurDAG->VerifyDAGDiverence();
859 #endif
860 }
861
862 {
863 NamedRegionTimer T("legalize_vec", "Vector Legalization", GroupName,
864 GroupDescription, TimePassesIsEnabled);
865 Changed = CurDAG->LegalizeVectors();
866 }
867
868 if (Changed) {
869 LLVM_DEBUG(dbgs() << "Vector-legalized selection DAG: "
870 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
871 << "'\n";
872 CurDAG->dump());
873
874 #ifndef NDEBUG
875 if (TTI.hasBranchDivergence())
876 CurDAG->VerifyDAGDiverence();
877 #endif
878
879 {
880 NamedRegionTimer T("legalize_types2", "Type Legalization 2", GroupName,
881 GroupDescription, TimePassesIsEnabled);
882 CurDAG->LegalizeTypes();
883 }
884
885 LLVM_DEBUG(dbgs() << "Vector/type-legalized selection DAG: "
886 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
887 << "'\n";
888 CurDAG->dump());
889
890 #ifndef NDEBUG
891 if (TTI.hasBranchDivergence())
892 CurDAG->VerifyDAGDiverence();
893 #endif
894
895 if (ViewDAGCombineLT && MatchFilterBB)
896 CurDAG->viewGraph("dag-combine-lv input for " + BlockName);
897
898 // Run the DAG combiner in post-type-legalize mode.
899 {
900 NamedRegionTimer T("combine_lv", "DAG Combining after legalize vectors",
901 GroupName, GroupDescription, TimePassesIsEnabled);
902 CurDAG->Combine(AfterLegalizeVectorOps, AA, OptLevel);
903 }
904
905 LLVM_DEBUG(dbgs() << "Optimized vector-legalized selection DAG: "
906 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
907 << "'\n";
908 CurDAG->dump());
909
910 #ifndef NDEBUG
911 if (TTI.hasBranchDivergence())
912 CurDAG->VerifyDAGDiverence();
913 #endif
914 }
915
916 if (ViewLegalizeDAGs && MatchFilterBB)
917 CurDAG->viewGraph("legalize input for " + BlockName);
918
919 {
920 NamedRegionTimer T("legalize", "DAG Legalization", GroupName,
921 GroupDescription, TimePassesIsEnabled);
922 CurDAG->Legalize();
923 }
924
925 LLVM_DEBUG(dbgs() << "Legalized selection DAG: "
926 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
927 << "'\n";
928 CurDAG->dump());
929
930 #ifndef NDEBUG
931 if (TTI.hasBranchDivergence())
932 CurDAG->VerifyDAGDiverence();
933 #endif
934
935 if (ViewDAGCombine2 && MatchFilterBB)
936 CurDAG->viewGraph("dag-combine2 input for " + BlockName);
937
938 // Run the DAG combiner in post-legalize mode.
939 {
940 NamedRegionTimer T("combine2", "DAG Combining 2", GroupName,
941 GroupDescription, TimePassesIsEnabled);
942 CurDAG->Combine(AfterLegalizeDAG, AA, OptLevel);
943 }
944
945 LLVM_DEBUG(dbgs() << "Optimized legalized selection DAG: "
946 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
947 << "'\n";
948 CurDAG->dump());
949
950 #ifndef NDEBUG
951 if (TTI.hasBranchDivergence())
952 CurDAG->VerifyDAGDiverence();
953 #endif
954
955 if (OptLevel != CodeGenOpt::None)
956 ComputeLiveOutVRegInfo();
957
958 if (ViewISelDAGs && MatchFilterBB)
959 CurDAG->viewGraph("isel input for " + BlockName);
960
961 // Third, instruction select all of the operations to machine code, adding the
962 // code to the MachineBasicBlock.
963 {
964 NamedRegionTimer T("isel", "Instruction Selection", GroupName,
965 GroupDescription, TimePassesIsEnabled);
966 DoInstructionSelection();
967 }
968
969 LLVM_DEBUG(dbgs() << "Selected selection DAG: "
970 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName
971 << "'\n";
972 CurDAG->dump());
973
974 if (ViewSchedDAGs && MatchFilterBB)
975 CurDAG->viewGraph("scheduler input for " + BlockName);
976
977 // Schedule machine code.
978 ScheduleDAGSDNodes *Scheduler = CreateScheduler();
979 {
980 NamedRegionTimer T("sched", "Instruction Scheduling", GroupName,
981 GroupDescription, TimePassesIsEnabled);
982 Scheduler->Run(CurDAG, FuncInfo->MBB);
983 }
984
985 if (ViewSUnitDAGs && MatchFilterBB)
986 Scheduler->viewGraph();
987
988 // Emit machine code to BB. This can change 'BB' to the last block being
989 // inserted into.
990 MachineBasicBlock *FirstMBB = FuncInfo->MBB, *LastMBB;
991 {
992 NamedRegionTimer T("emit", "Instruction Creation", GroupName,
993 GroupDescription, TimePassesIsEnabled);
994
995 // FuncInfo->InsertPt is passed by reference and set to the end of the
996 // scheduled instructions.
997 LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(FuncInfo->InsertPt);
998 }
999
1000 // If the block was split, make sure we update any references that are used to
1001 // update PHI nodes later on.
1002 if (FirstMBB != LastMBB)
1003 SDB->UpdateSplitBlock(FirstMBB, LastMBB);
1004
1005 // Free the scheduler state.
1006 {
1007 NamedRegionTimer T("cleanup", "Instruction Scheduling Cleanup", GroupName,
1008 GroupDescription, TimePassesIsEnabled);
1009 delete Scheduler;
1010 }
1011
1012 // Free the SelectionDAG state, now that we're finished with it.
1013 CurDAG->clear();
1014 }
1015
1016 namespace {
1017
1018 /// ISelUpdater - helper class to handle updates of the instruction selection
1019 /// graph.
1020 class ISelUpdater : public SelectionDAG::DAGUpdateListener {
1021 SelectionDAG::allnodes_iterator &ISelPosition;
1022
1023 public:
ISelUpdater(SelectionDAG & DAG,SelectionDAG::allnodes_iterator & isp)1024 ISelUpdater(SelectionDAG &DAG, SelectionDAG::allnodes_iterator &isp)
1025 : SelectionDAG::DAGUpdateListener(DAG), ISelPosition(isp) {}
1026
1027 /// NodeDeleted - Handle nodes deleted from the graph. If the node being
1028 /// deleted is the current ISelPosition node, update ISelPosition.
1029 ///
NodeDeleted(SDNode * N,SDNode * E)1030 void NodeDeleted(SDNode *N, SDNode *E) override {
1031 if (ISelPosition == SelectionDAG::allnodes_iterator(N))
1032 ++ISelPosition;
1033 }
1034 };
1035
1036 } // end anonymous namespace
1037
1038 // This function is used to enforce the topological node id property
1039 // property leveraged during Instruction selection. Before selection all
1040 // nodes are given a non-negative id such that all nodes have a larger id than
1041 // their operands. As this holds transitively we can prune checks that a node N
1042 // is a predecessor of M another by not recursively checking through M's
1043 // operands if N's ID is larger than M's ID. This is significantly improves
1044 // performance of for various legality checks (e.g. IsLegalToFold /
1045 // UpdateChains).
1046
1047 // However, when we fuse multiple nodes into a single node
1048 // during selection we may induce a predecessor relationship between inputs and
1049 // outputs of distinct nodes being merged violating the topological property.
1050 // Should a fused node have a successor which has yet to be selected, our
1051 // legality checks would be incorrect. To avoid this we mark all unselected
1052 // sucessor nodes, i.e. id != -1 as invalid for pruning by bit-negating (x =>
1053 // (-(x+1))) the ids and modify our pruning check to ignore negative Ids of M.
1054 // We use bit-negation to more clearly enforce that node id -1 can only be
1055 // achieved by selected nodes). As the conversion is reversable the original Id,
1056 // topological pruning can still be leveraged when looking for unselected nodes.
1057 // This method is call internally in all ISel replacement calls.
EnforceNodeIdInvariant(SDNode * Node)1058 void SelectionDAGISel::EnforceNodeIdInvariant(SDNode *Node) {
1059 SmallVector<SDNode *, 4> Nodes;
1060 Nodes.push_back(Node);
1061
1062 while (!Nodes.empty()) {
1063 SDNode *N = Nodes.pop_back_val();
1064 for (auto *U : N->uses()) {
1065 auto UId = U->getNodeId();
1066 if (UId > 0) {
1067 InvalidateNodeId(U);
1068 Nodes.push_back(U);
1069 }
1070 }
1071 }
1072 }
1073
1074 // InvalidateNodeId - As discusses in EnforceNodeIdInvariant, mark a
1075 // NodeId with the equivalent node id which is invalid for topological
1076 // pruning.
InvalidateNodeId(SDNode * N)1077 void SelectionDAGISel::InvalidateNodeId(SDNode *N) {
1078 int InvalidId = -(N->getNodeId() + 1);
1079 N->setNodeId(InvalidId);
1080 }
1081
1082 // getUninvalidatedNodeId - get original uninvalidated node id.
getUninvalidatedNodeId(SDNode * N)1083 int SelectionDAGISel::getUninvalidatedNodeId(SDNode *N) {
1084 int Id = N->getNodeId();
1085 if (Id < -1)
1086 return -(Id + 1);
1087 return Id;
1088 }
1089
DoInstructionSelection()1090 void SelectionDAGISel::DoInstructionSelection() {
1091 LLVM_DEBUG(dbgs() << "===== Instruction selection begins: "
1092 << printMBBReference(*FuncInfo->MBB) << " '"
1093 << FuncInfo->MBB->getName() << "'\n");
1094
1095 PreprocessISelDAG();
1096
1097 // Select target instructions for the DAG.
1098 {
1099 // Number all nodes with a topological order and set DAGSize.
1100 DAGSize = CurDAG->AssignTopologicalOrder();
1101
1102 // Create a dummy node (which is not added to allnodes), that adds
1103 // a reference to the root node, preventing it from being deleted,
1104 // and tracking any changes of the root.
1105 HandleSDNode Dummy(CurDAG->getRoot());
1106 SelectionDAG::allnodes_iterator ISelPosition (CurDAG->getRoot().getNode());
1107 ++ISelPosition;
1108
1109 // Make sure that ISelPosition gets properly updated when nodes are deleted
1110 // in calls made from this function.
1111 ISelUpdater ISU(*CurDAG, ISelPosition);
1112
1113 // The AllNodes list is now topological-sorted. Visit the
1114 // nodes by starting at the end of the list (the root of the
1115 // graph) and preceding back toward the beginning (the entry
1116 // node).
1117 while (ISelPosition != CurDAG->allnodes_begin()) {
1118 SDNode *Node = &*--ISelPosition;
1119 // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
1120 // but there are currently some corner cases that it misses. Also, this
1121 // makes it theoretically possible to disable the DAGCombiner.
1122 if (Node->use_empty())
1123 continue;
1124
1125 #ifndef NDEBUG
1126 SmallVector<SDNode *, 4> Nodes;
1127 Nodes.push_back(Node);
1128
1129 while (!Nodes.empty()) {
1130 auto N = Nodes.pop_back_val();
1131 if (N->getOpcode() == ISD::TokenFactor || N->getNodeId() < 0)
1132 continue;
1133 for (const SDValue &Op : N->op_values()) {
1134 if (Op->getOpcode() == ISD::TokenFactor)
1135 Nodes.push_back(Op.getNode());
1136 else {
1137 // We rely on topological ordering of node ids for checking for
1138 // cycles when fusing nodes during selection. All unselected nodes
1139 // successors of an already selected node should have a negative id.
1140 // This assertion will catch such cases. If this assertion triggers
1141 // it is likely you using DAG-level Value/Node replacement functions
1142 // (versus equivalent ISEL replacement) in backend-specific
1143 // selections. See comment in EnforceNodeIdInvariant for more
1144 // details.
1145 assert(Op->getNodeId() != -1 &&
1146 "Node has already selected predecessor node");
1147 }
1148 }
1149 }
1150 #endif
1151
1152 // When we are using non-default rounding modes or FP exception behavior
1153 // FP operations are represented by StrictFP pseudo-operations. For
1154 // targets that do not (yet) understand strict FP operations directly,
1155 // we convert them to normal FP opcodes instead at this point. This
1156 // will allow them to be handled by existing target-specific instruction
1157 // selectors.
1158 if (!TLI->isStrictFPEnabled() && Node->isStrictFPOpcode()) {
1159 // For some opcodes, we need to call TLI->getOperationAction using
1160 // the first operand type instead of the result type. Note that this
1161 // must match what SelectionDAGLegalize::LegalizeOp is doing.
1162 EVT ActionVT;
1163 switch (Node->getOpcode()) {
1164 case ISD::STRICT_SINT_TO_FP:
1165 case ISD::STRICT_UINT_TO_FP:
1166 case ISD::STRICT_LRINT:
1167 case ISD::STRICT_LLRINT:
1168 case ISD::STRICT_LROUND:
1169 case ISD::STRICT_LLROUND:
1170 case ISD::STRICT_FSETCC:
1171 case ISD::STRICT_FSETCCS:
1172 ActionVT = Node->getOperand(1).getValueType();
1173 break;
1174 default:
1175 ActionVT = Node->getValueType(0);
1176 break;
1177 }
1178 if (TLI->getOperationAction(Node->getOpcode(), ActionVT)
1179 == TargetLowering::Expand)
1180 Node = CurDAG->mutateStrictFPToFP(Node);
1181 }
1182
1183 LLVM_DEBUG(dbgs() << "\nISEL: Starting selection on root node: ";
1184 Node->dump(CurDAG));
1185
1186 Select(Node);
1187 }
1188
1189 CurDAG->setRoot(Dummy.getValue());
1190 }
1191
1192 LLVM_DEBUG(dbgs() << "\n===== Instruction selection ends:\n");
1193
1194 PostprocessISelDAG();
1195 }
1196
hasExceptionPointerOrCodeUser(const CatchPadInst * CPI)1197 static bool hasExceptionPointerOrCodeUser(const CatchPadInst *CPI) {
1198 for (const User *U : CPI->users()) {
1199 if (const IntrinsicInst *EHPtrCall = dyn_cast<IntrinsicInst>(U)) {
1200 Intrinsic::ID IID = EHPtrCall->getIntrinsicID();
1201 if (IID == Intrinsic::eh_exceptionpointer ||
1202 IID == Intrinsic::eh_exceptioncode)
1203 return true;
1204 }
1205 }
1206 return false;
1207 }
1208
1209 // wasm.landingpad.index intrinsic is for associating a landing pad index number
1210 // with a catchpad instruction. Retrieve the landing pad index in the intrinsic
1211 // and store the mapping in the function.
mapWasmLandingPadIndex(MachineBasicBlock * MBB,const CatchPadInst * CPI)1212 static void mapWasmLandingPadIndex(MachineBasicBlock *MBB,
1213 const CatchPadInst *CPI) {
1214 MachineFunction *MF = MBB->getParent();
1215 // In case of single catch (...), we don't emit LSDA, so we don't need
1216 // this information.
1217 bool IsSingleCatchAllClause =
1218 CPI->getNumArgOperands() == 1 &&
1219 cast<Constant>(CPI->getArgOperand(0))->isNullValue();
1220 if (!IsSingleCatchAllClause) {
1221 // Create a mapping from landing pad label to landing pad index.
1222 bool IntrFound = false;
1223 for (const User *U : CPI->users()) {
1224 if (const auto *Call = dyn_cast<IntrinsicInst>(U)) {
1225 Intrinsic::ID IID = Call->getIntrinsicID();
1226 if (IID == Intrinsic::wasm_landingpad_index) {
1227 Value *IndexArg = Call->getArgOperand(1);
1228 int Index = cast<ConstantInt>(IndexArg)->getZExtValue();
1229 MF->setWasmLandingPadIndex(MBB, Index);
1230 IntrFound = true;
1231 break;
1232 }
1233 }
1234 }
1235 assert(IntrFound && "wasm.landingpad.index intrinsic not found!");
1236 (void)IntrFound;
1237 }
1238 }
1239
1240 /// PrepareEHLandingPad - Emit an EH_LABEL, set up live-in registers, and
1241 /// do other setup for EH landing-pad blocks.
PrepareEHLandingPad()1242 bool SelectionDAGISel::PrepareEHLandingPad() {
1243 MachineBasicBlock *MBB = FuncInfo->MBB;
1244 const Constant *PersonalityFn = FuncInfo->Fn->getPersonalityFn();
1245 const BasicBlock *LLVMBB = MBB->getBasicBlock();
1246 const TargetRegisterClass *PtrRC =
1247 TLI->getRegClassFor(TLI->getPointerTy(CurDAG->getDataLayout()));
1248
1249 auto Pers = classifyEHPersonality(PersonalityFn);
1250
1251 // Catchpads have one live-in register, which typically holds the exception
1252 // pointer or code.
1253 if (isFuncletEHPersonality(Pers)) {
1254 if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHI())) {
1255 if (hasExceptionPointerOrCodeUser(CPI)) {
1256 // Get or create the virtual register to hold the pointer or code. Mark
1257 // the live in physreg and copy into the vreg.
1258 MCPhysReg EHPhysReg = TLI->getExceptionPointerRegister(PersonalityFn);
1259 assert(EHPhysReg && "target lacks exception pointer register");
1260 MBB->addLiveIn(EHPhysReg);
1261 unsigned VReg = FuncInfo->getCatchPadExceptionPointerVReg(CPI, PtrRC);
1262 BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(),
1263 TII->get(TargetOpcode::COPY), VReg)
1264 .addReg(EHPhysReg, RegState::Kill);
1265 }
1266 }
1267 return true;
1268 }
1269
1270 // Add a label to mark the beginning of the landing pad. Deletion of the
1271 // landing pad can thus be detected via the MachineModuleInfo.
1272 MCSymbol *Label = MF->addLandingPad(MBB);
1273
1274 const MCInstrDesc &II = TII->get(TargetOpcode::EH_LABEL);
1275 BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II)
1276 .addSym(Label);
1277
1278 // If the unwinder does not preserve all registers, ensure that the
1279 // function marks the clobbered registers as used.
1280 const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();
1281 if (auto *RegMask = TRI.getCustomEHPadPreservedMask(*MF))
1282 MF->getRegInfo().addPhysRegsUsedFromRegMask(RegMask);
1283
1284 if (Pers == EHPersonality::Wasm_CXX) {
1285 if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHI()))
1286 mapWasmLandingPadIndex(MBB, CPI);
1287 } else {
1288 // Assign the call site to the landing pad's begin label.
1289 MF->setCallSiteLandingPad(Label, SDB->LPadToCallSiteMap[MBB]);
1290 // Mark exception register as live in.
1291 if (unsigned Reg = TLI->getExceptionPointerRegister(PersonalityFn))
1292 FuncInfo->ExceptionPointerVirtReg = MBB->addLiveIn(Reg, PtrRC);
1293 // Mark exception selector register as live in.
1294 if (unsigned Reg = TLI->getExceptionSelectorRegister(PersonalityFn))
1295 FuncInfo->ExceptionSelectorVirtReg = MBB->addLiveIn(Reg, PtrRC);
1296 }
1297
1298 return true;
1299 }
1300
1301 /// isFoldedOrDeadInstruction - Return true if the specified instruction is
1302 /// side-effect free and is either dead or folded into a generated instruction.
1303 /// Return false if it needs to be emitted.
isFoldedOrDeadInstruction(const Instruction * I,const FunctionLoweringInfo & FuncInfo)1304 static bool isFoldedOrDeadInstruction(const Instruction *I,
1305 const FunctionLoweringInfo &FuncInfo) {
1306 return !I->mayWriteToMemory() && // Side-effecting instructions aren't folded.
1307 !I->isTerminator() && // Terminators aren't folded.
1308 !isa<DbgInfoIntrinsic>(I) && // Debug instructions aren't folded.
1309 !I->isEHPad() && // EH pad instructions aren't folded.
1310 !FuncInfo.isExportedInst(I); // Exported instrs must be computed.
1311 }
1312
1313 /// Collect llvm.dbg.declare information. This is done after argument lowering
1314 /// in case the declarations refer to arguments.
processDbgDeclares(FunctionLoweringInfo & FuncInfo)1315 static void processDbgDeclares(FunctionLoweringInfo &FuncInfo) {
1316 MachineFunction *MF = FuncInfo.MF;
1317 const DataLayout &DL = MF->getDataLayout();
1318 for (const BasicBlock &BB : *FuncInfo.Fn) {
1319 for (const Instruction &I : BB) {
1320 const DbgDeclareInst *DI = dyn_cast<DbgDeclareInst>(&I);
1321 if (!DI)
1322 continue;
1323
1324 assert(DI->getVariable() && "Missing variable");
1325 assert(DI->getDebugLoc() && "Missing location");
1326 const Value *Address = DI->getAddress();
1327 if (!Address) {
1328 LLVM_DEBUG(dbgs() << "processDbgDeclares skipping " << *DI
1329 << " (bad address)\n");
1330 continue;
1331 }
1332
1333 // Look through casts and constant offset GEPs. These mostly come from
1334 // inalloca.
1335 APInt Offset(DL.getTypeSizeInBits(Address->getType()), 0);
1336 Address = Address->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
1337
1338 // Check if the variable is a static alloca or a byval or inalloca
1339 // argument passed in memory. If it is not, then we will ignore this
1340 // intrinsic and handle this during isel like dbg.value.
1341 int FI = std::numeric_limits<int>::max();
1342 if (const auto *AI = dyn_cast<AllocaInst>(Address)) {
1343 auto SI = FuncInfo.StaticAllocaMap.find(AI);
1344 if (SI != FuncInfo.StaticAllocaMap.end())
1345 FI = SI->second;
1346 } else if (const auto *Arg = dyn_cast<Argument>(Address))
1347 FI = FuncInfo.getArgumentFrameIndex(Arg);
1348
1349 if (FI == std::numeric_limits<int>::max())
1350 continue;
1351
1352 DIExpression *Expr = DI->getExpression();
1353 if (Offset.getBoolValue())
1354 Expr = DIExpression::prepend(Expr, DIExpression::ApplyOffset,
1355 Offset.getZExtValue());
1356 LLVM_DEBUG(dbgs() << "processDbgDeclares: setVariableDbgInfo FI=" << FI
1357 << ", " << *DI << "\n");
1358 MF->setVariableDbgInfo(DI->getVariable(), Expr, FI, DI->getDebugLoc());
1359 }
1360 }
1361 }
1362
SelectAllBasicBlocks(const Function & Fn)1363 void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) {
1364 FastISelFailed = false;
1365 // Initialize the Fast-ISel state, if needed.
1366 FastISel *FastIS = nullptr;
1367 if (TM.Options.EnableFastISel) {
1368 LLVM_DEBUG(dbgs() << "Enabling fast-isel\n");
1369 FastIS = TLI->createFastISel(*FuncInfo, LibInfo);
1370 }
1371
1372 ReversePostOrderTraversal<const Function*> RPOT(&Fn);
1373
1374 // Lower arguments up front. An RPO iteration always visits the entry block
1375 // first.
1376 assert(*RPOT.begin() == &Fn.getEntryBlock());
1377 ++NumEntryBlocks;
1378
1379 // Set up FuncInfo for ISel. Entry blocks never have PHIs.
1380 FuncInfo->MBB = FuncInfo->MBBMap[&Fn.getEntryBlock()];
1381 FuncInfo->InsertPt = FuncInfo->MBB->begin();
1382
1383 CurDAG->setFunctionLoweringInfo(FuncInfo.get());
1384
1385 if (!FastIS) {
1386 LowerArguments(Fn);
1387 } else {
1388 // See if fast isel can lower the arguments.
1389 FastIS->startNewBlock();
1390 if (!FastIS->lowerArguments()) {
1391 FastISelFailed = true;
1392 // Fast isel failed to lower these arguments
1393 ++NumFastIselFailLowerArguments;
1394
1395 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1396 Fn.getSubprogram(),
1397 &Fn.getEntryBlock());
1398 R << "FastISel didn't lower all arguments: "
1399 << ore::NV("Prototype", Fn.getType());
1400 reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 1);
1401
1402 // Use SelectionDAG argument lowering
1403 LowerArguments(Fn);
1404 CurDAG->setRoot(SDB->getControlRoot());
1405 SDB->clear();
1406 CodeGenAndEmitDAG();
1407 }
1408
1409 // If we inserted any instructions at the beginning, make a note of
1410 // where they are, so we can be sure to emit subsequent instructions
1411 // after them.
1412 if (FuncInfo->InsertPt != FuncInfo->MBB->begin())
1413 FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
1414 else
1415 FastIS->setLastLocalValue(nullptr);
1416 }
1417
1418 bool Inserted = SwiftError->createEntriesInEntryBlock(SDB->getCurDebugLoc());
1419
1420 if (FastIS && Inserted)
1421 FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
1422
1423 processDbgDeclares(*FuncInfo);
1424
1425 // Iterate over all basic blocks in the function.
1426 StackProtector &SP = getAnalysis<StackProtector>();
1427 for (const BasicBlock *LLVMBB : RPOT) {
1428 if (OptLevel != CodeGenOpt::None) {
1429 bool AllPredsVisited = true;
1430 for (const BasicBlock *Pred : predecessors(LLVMBB)) {
1431 if (!FuncInfo->VisitedBBs.count(Pred)) {
1432 AllPredsVisited = false;
1433 break;
1434 }
1435 }
1436
1437 if (AllPredsVisited) {
1438 for (const PHINode &PN : LLVMBB->phis())
1439 FuncInfo->ComputePHILiveOutRegInfo(&PN);
1440 } else {
1441 for (const PHINode &PN : LLVMBB->phis())
1442 FuncInfo->InvalidatePHILiveOutRegInfo(&PN);
1443 }
1444
1445 FuncInfo->VisitedBBs.insert(LLVMBB);
1446 }
1447
1448 BasicBlock::const_iterator const Begin =
1449 LLVMBB->getFirstNonPHI()->getIterator();
1450 BasicBlock::const_iterator const End = LLVMBB->end();
1451 BasicBlock::const_iterator BI = End;
1452
1453 FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB];
1454 if (!FuncInfo->MBB)
1455 continue; // Some blocks like catchpads have no code or MBB.
1456
1457 // Insert new instructions after any phi or argument setup code.
1458 FuncInfo->InsertPt = FuncInfo->MBB->end();
1459
1460 // Setup an EH landing-pad block.
1461 FuncInfo->ExceptionPointerVirtReg = 0;
1462 FuncInfo->ExceptionSelectorVirtReg = 0;
1463 if (LLVMBB->isEHPad())
1464 if (!PrepareEHLandingPad())
1465 continue;
1466
1467 // Before doing SelectionDAG ISel, see if FastISel has been requested.
1468 if (FastIS) {
1469 if (LLVMBB != &Fn.getEntryBlock())
1470 FastIS->startNewBlock();
1471
1472 unsigned NumFastIselRemaining = std::distance(Begin, End);
1473
1474 // Pre-assign swifterror vregs.
1475 SwiftError->preassignVRegs(FuncInfo->MBB, Begin, End);
1476
1477 // Do FastISel on as many instructions as possible.
1478 for (; BI != Begin; --BI) {
1479 const Instruction *Inst = &*std::prev(BI);
1480
1481 // If we no longer require this instruction, skip it.
1482 if (isFoldedOrDeadInstruction(Inst, *FuncInfo) ||
1483 ElidedArgCopyInstrs.count(Inst)) {
1484 --NumFastIselRemaining;
1485 continue;
1486 }
1487
1488 // Bottom-up: reset the insert pos at the top, after any local-value
1489 // instructions.
1490 FastIS->recomputeInsertPt();
1491
1492 // Try to select the instruction with FastISel.
1493 if (FastIS->selectInstruction(Inst)) {
1494 --NumFastIselRemaining;
1495 ++NumFastIselSuccess;
1496 // If fast isel succeeded, skip over all the folded instructions, and
1497 // then see if there is a load right before the selected instructions.
1498 // Try to fold the load if so.
1499 const Instruction *BeforeInst = Inst;
1500 while (BeforeInst != &*Begin) {
1501 BeforeInst = &*std::prev(BasicBlock::const_iterator(BeforeInst));
1502 if (!isFoldedOrDeadInstruction(BeforeInst, *FuncInfo))
1503 break;
1504 }
1505 if (BeforeInst != Inst && isa<LoadInst>(BeforeInst) &&
1506 BeforeInst->hasOneUse() &&
1507 FastIS->tryToFoldLoad(cast<LoadInst>(BeforeInst), Inst)) {
1508 // If we succeeded, don't re-select the load.
1509 BI = std::next(BasicBlock::const_iterator(BeforeInst));
1510 --NumFastIselRemaining;
1511 ++NumFastIselSuccess;
1512 }
1513 continue;
1514 }
1515
1516 FastISelFailed = true;
1517
1518 // Then handle certain instructions as single-LLVM-Instruction blocks.
1519 // We cannot separate out GCrelocates to their own blocks since we need
1520 // to keep track of gc-relocates for a particular gc-statepoint. This is
1521 // done by SelectionDAGBuilder::LowerAsSTATEPOINT, called before
1522 // visitGCRelocate.
1523 if (isa<CallInst>(Inst) && !isa<GCStatepointInst>(Inst) &&
1524 !isa<GCRelocateInst>(Inst) && !isa<GCResultInst>(Inst)) {
1525 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1526 Inst->getDebugLoc(), LLVMBB);
1527
1528 R << "FastISel missed call";
1529
1530 if (R.isEnabled() || EnableFastISelAbort) {
1531 std::string InstStrStorage;
1532 raw_string_ostream InstStr(InstStrStorage);
1533 InstStr << *Inst;
1534
1535 R << ": " << InstStr.str();
1536 }
1537
1538 reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 2);
1539
1540 if (!Inst->getType()->isVoidTy() && !Inst->getType()->isTokenTy() &&
1541 !Inst->use_empty()) {
1542 Register &R = FuncInfo->ValueMap[Inst];
1543 if (!R)
1544 R = FuncInfo->CreateRegs(Inst);
1545 }
1546
1547 bool HadTailCall = false;
1548 MachineBasicBlock::iterator SavedInsertPt = FuncInfo->InsertPt;
1549 SelectBasicBlock(Inst->getIterator(), BI, HadTailCall);
1550
1551 // If the call was emitted as a tail call, we're done with the block.
1552 // We also need to delete any previously emitted instructions.
1553 if (HadTailCall) {
1554 FastIS->removeDeadCode(SavedInsertPt, FuncInfo->MBB->end());
1555 --BI;
1556 break;
1557 }
1558
1559 // Recompute NumFastIselRemaining as Selection DAG instruction
1560 // selection may have handled the call, input args, etc.
1561 unsigned RemainingNow = std::distance(Begin, BI);
1562 NumFastIselFailures += NumFastIselRemaining - RemainingNow;
1563 NumFastIselRemaining = RemainingNow;
1564 continue;
1565 }
1566
1567 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1568 Inst->getDebugLoc(), LLVMBB);
1569
1570 bool ShouldAbort = EnableFastISelAbort;
1571 if (Inst->isTerminator()) {
1572 // Use a different message for terminator misses.
1573 R << "FastISel missed terminator";
1574 // Don't abort for terminator unless the level is really high
1575 ShouldAbort = (EnableFastISelAbort > 2);
1576 } else {
1577 R << "FastISel missed";
1578 }
1579
1580 if (R.isEnabled() || EnableFastISelAbort) {
1581 std::string InstStrStorage;
1582 raw_string_ostream InstStr(InstStrStorage);
1583 InstStr << *Inst;
1584 R << ": " << InstStr.str();
1585 }
1586
1587 reportFastISelFailure(*MF, *ORE, R, ShouldAbort);
1588
1589 NumFastIselFailures += NumFastIselRemaining;
1590 break;
1591 }
1592
1593 FastIS->recomputeInsertPt();
1594 }
1595
1596 if (SP.shouldEmitSDCheck(*LLVMBB)) {
1597 bool FunctionBasedInstrumentation =
1598 TLI->getSSPStackGuardCheck(*Fn.getParent());
1599 SDB->SPDescriptor.initialize(LLVMBB, FuncInfo->MBBMap[LLVMBB],
1600 FunctionBasedInstrumentation);
1601 }
1602
1603 if (Begin != BI)
1604 ++NumDAGBlocks;
1605 else
1606 ++NumFastIselBlocks;
1607
1608 if (Begin != BI) {
1609 // Run SelectionDAG instruction selection on the remainder of the block
1610 // not handled by FastISel. If FastISel is not run, this is the entire
1611 // block.
1612 bool HadTailCall;
1613 SelectBasicBlock(Begin, BI, HadTailCall);
1614
1615 // But if FastISel was run, we already selected some of the block.
1616 // If we emitted a tail-call, we need to delete any previously emitted
1617 // instruction that follows it.
1618 if (FastIS && HadTailCall && FuncInfo->InsertPt != FuncInfo->MBB->end())
1619 FastIS->removeDeadCode(FuncInfo->InsertPt, FuncInfo->MBB->end());
1620 }
1621
1622 if (FastIS)
1623 FastIS->finishBasicBlock();
1624 FinishBasicBlock();
1625 FuncInfo->PHINodesToUpdate.clear();
1626 ElidedArgCopyInstrs.clear();
1627 }
1628
1629 SP.copyToMachineFrameInfo(MF->getFrameInfo());
1630
1631 SwiftError->propagateVRegs();
1632
1633 delete FastIS;
1634 SDB->clearDanglingDebugInfo();
1635 SDB->SPDescriptor.resetPerFunctionState();
1636 }
1637
1638 /// Given that the input MI is before a partial terminator sequence TSeq, return
1639 /// true if M + TSeq also a partial terminator sequence.
1640 ///
1641 /// A Terminator sequence is a sequence of MachineInstrs which at this point in
1642 /// lowering copy vregs into physical registers, which are then passed into
1643 /// terminator instructors so we can satisfy ABI constraints. A partial
1644 /// terminator sequence is an improper subset of a terminator sequence (i.e. it
1645 /// may be the whole terminator sequence).
MIIsInTerminatorSequence(const MachineInstr & MI)1646 static bool MIIsInTerminatorSequence(const MachineInstr &MI) {
1647 // If we do not have a copy or an implicit def, we return true if and only if
1648 // MI is a debug value.
1649 if (!MI.isCopy() && !MI.isImplicitDef())
1650 // Sometimes DBG_VALUE MI sneak in between the copies from the vregs to the
1651 // physical registers if there is debug info associated with the terminator
1652 // of our mbb. We want to include said debug info in our terminator
1653 // sequence, so we return true in that case.
1654 return MI.isDebugValue();
1655
1656 // We have left the terminator sequence if we are not doing one of the
1657 // following:
1658 //
1659 // 1. Copying a vreg into a physical register.
1660 // 2. Copying a vreg into a vreg.
1661 // 3. Defining a register via an implicit def.
1662
1663 // OPI should always be a register definition...
1664 MachineInstr::const_mop_iterator OPI = MI.operands_begin();
1665 if (!OPI->isReg() || !OPI->isDef())
1666 return false;
1667
1668 // Defining any register via an implicit def is always ok.
1669 if (MI.isImplicitDef())
1670 return true;
1671
1672 // Grab the copy source...
1673 MachineInstr::const_mop_iterator OPI2 = OPI;
1674 ++OPI2;
1675 assert(OPI2 != MI.operands_end()
1676 && "Should have a copy implying we should have 2 arguments.");
1677
1678 // Make sure that the copy dest is not a vreg when the copy source is a
1679 // physical register.
1680 if (!OPI2->isReg() || (!Register::isPhysicalRegister(OPI->getReg()) &&
1681 Register::isPhysicalRegister(OPI2->getReg())))
1682 return false;
1683
1684 return true;
1685 }
1686
1687 /// Find the split point at which to splice the end of BB into its success stack
1688 /// protector check machine basic block.
1689 ///
1690 /// On many platforms, due to ABI constraints, terminators, even before register
1691 /// allocation, use physical registers. This creates an issue for us since
1692 /// physical registers at this point can not travel across basic
1693 /// blocks. Luckily, selectiondag always moves physical registers into vregs
1694 /// when they enter functions and moves them through a sequence of copies back
1695 /// into the physical registers right before the terminator creating a
1696 /// ``Terminator Sequence''. This function is searching for the beginning of the
1697 /// terminator sequence so that we can ensure that we splice off not just the
1698 /// terminator, but additionally the copies that move the vregs into the
1699 /// physical registers.
1700 static MachineBasicBlock::iterator
FindSplitPointForStackProtector(MachineBasicBlock * BB,const TargetInstrInfo & TII)1701 FindSplitPointForStackProtector(MachineBasicBlock *BB,
1702 const TargetInstrInfo &TII) {
1703 MachineBasicBlock::iterator SplitPoint = BB->getFirstTerminator();
1704 if (SplitPoint == BB->begin())
1705 return SplitPoint;
1706
1707 MachineBasicBlock::iterator Start = BB->begin();
1708 MachineBasicBlock::iterator Previous = SplitPoint;
1709 --Previous;
1710
1711 if (TII.isTailCall(*SplitPoint) &&
1712 Previous->getOpcode() == TII.getCallFrameDestroyOpcode()) {
1713 // call itself, then we must insert before the sequence even starts. For
1714 // example:
1715 // <split point>
1716 // ADJCALLSTACKDOWN ...
1717 // <Moves>
1718 // ADJCALLSTACKUP ...
1719 // TAILJMP somewhere
1720 // On the other hand, it could be an unrelated call in which case this tail call
1721 // has to register moves of its own and should be the split point. For example:
1722 // ADJCALLSTACKDOWN
1723 // CALL something_else
1724 // ADJCALLSTACKUP
1725 // <split point>
1726 // TAILJMP somewhere
1727 do {
1728 --Previous;
1729 if (Previous->isCall())
1730 return SplitPoint;
1731 } while(Previous->getOpcode() != TII.getCallFrameSetupOpcode());
1732
1733 return Previous;
1734 }
1735
1736 while (MIIsInTerminatorSequence(*Previous)) {
1737 SplitPoint = Previous;
1738 if (Previous == Start)
1739 break;
1740 --Previous;
1741 }
1742
1743 return SplitPoint;
1744 }
1745
1746 void
FinishBasicBlock()1747 SelectionDAGISel::FinishBasicBlock() {
1748 LLVM_DEBUG(dbgs() << "Total amount of phi nodes to update: "
1749 << FuncInfo->PHINodesToUpdate.size() << "\n";
1750 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e;
1751 ++i) dbgs()
1752 << "Node " << i << " : (" << FuncInfo->PHINodesToUpdate[i].first
1753 << ", " << FuncInfo->PHINodesToUpdate[i].second << ")\n");
1754
1755 // Next, now that we know what the last MBB the LLVM BB expanded is, update
1756 // PHI nodes in successors.
1757 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) {
1758 MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[i].first);
1759 assert(PHI->isPHI() &&
1760 "This is not a machine PHI node that we are updating!");
1761 if (!FuncInfo->MBB->isSuccessor(PHI->getParent()))
1762 continue;
1763 PHI.addReg(FuncInfo->PHINodesToUpdate[i].second).addMBB(FuncInfo->MBB);
1764 }
1765
1766 // Handle stack protector.
1767 if (SDB->SPDescriptor.shouldEmitFunctionBasedCheckStackProtector()) {
1768 // The target provides a guard check function. There is no need to
1769 // generate error handling code or to split current basic block.
1770 MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
1771
1772 // Add load and check to the basicblock.
1773 FuncInfo->MBB = ParentMBB;
1774 FuncInfo->InsertPt =
1775 FindSplitPointForStackProtector(ParentMBB, *TII);
1776 SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
1777 CurDAG->setRoot(SDB->getRoot());
1778 SDB->clear();
1779 CodeGenAndEmitDAG();
1780
1781 // Clear the Per-BB State.
1782 SDB->SPDescriptor.resetPerBBState();
1783 } else if (SDB->SPDescriptor.shouldEmitStackProtector()) {
1784 MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
1785 MachineBasicBlock *SuccessMBB = SDB->SPDescriptor.getSuccessMBB();
1786
1787 // Find the split point to split the parent mbb. At the same time copy all
1788 // physical registers used in the tail of parent mbb into virtual registers
1789 // before the split point and back into physical registers after the split
1790 // point. This prevents us needing to deal with Live-ins and many other
1791 // register allocation issues caused by us splitting the parent mbb. The
1792 // register allocator will clean up said virtual copies later on.
1793 MachineBasicBlock::iterator SplitPoint =
1794 FindSplitPointForStackProtector(ParentMBB, *TII);
1795
1796 // Splice the terminator of ParentMBB into SuccessMBB.
1797 SuccessMBB->splice(SuccessMBB->end(), ParentMBB,
1798 SplitPoint,
1799 ParentMBB->end());
1800
1801 // Add compare/jump on neq/jump to the parent BB.
1802 FuncInfo->MBB = ParentMBB;
1803 FuncInfo->InsertPt = ParentMBB->end();
1804 SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
1805 CurDAG->setRoot(SDB->getRoot());
1806 SDB->clear();
1807 CodeGenAndEmitDAG();
1808
1809 // CodeGen Failure MBB if we have not codegened it yet.
1810 MachineBasicBlock *FailureMBB = SDB->SPDescriptor.getFailureMBB();
1811 if (FailureMBB->empty()) {
1812 FuncInfo->MBB = FailureMBB;
1813 FuncInfo->InsertPt = FailureMBB->end();
1814 SDB->visitSPDescriptorFailure(SDB->SPDescriptor);
1815 CurDAG->setRoot(SDB->getRoot());
1816 SDB->clear();
1817 CodeGenAndEmitDAG();
1818 }
1819
1820 // Clear the Per-BB State.
1821 SDB->SPDescriptor.resetPerBBState();
1822 }
1823
1824 // Lower each BitTestBlock.
1825 for (auto &BTB : SDB->SL->BitTestCases) {
1826 // Lower header first, if it wasn't already lowered
1827 if (!BTB.Emitted) {
1828 // Set the current basic block to the mbb we wish to insert the code into
1829 FuncInfo->MBB = BTB.Parent;
1830 FuncInfo->InsertPt = FuncInfo->MBB->end();
1831 // Emit the code
1832 SDB->visitBitTestHeader(BTB, FuncInfo->MBB);
1833 CurDAG->setRoot(SDB->getRoot());
1834 SDB->clear();
1835 CodeGenAndEmitDAG();
1836 }
1837
1838 BranchProbability UnhandledProb = BTB.Prob;
1839 for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; ++j) {
1840 UnhandledProb -= BTB.Cases[j].ExtraProb;
1841 // Set the current basic block to the mbb we wish to insert the code into
1842 FuncInfo->MBB = BTB.Cases[j].ThisBB;
1843 FuncInfo->InsertPt = FuncInfo->MBB->end();
1844 // Emit the code
1845
1846 // If all cases cover a contiguous range, it is not necessary to jump to
1847 // the default block after the last bit test fails. This is because the
1848 // range check during bit test header creation has guaranteed that every
1849 // case here doesn't go outside the range. In this case, there is no need
1850 // to perform the last bit test, as it will always be true. Instead, make
1851 // the second-to-last bit-test fall through to the target of the last bit
1852 // test, and delete the last bit test.
1853
1854 MachineBasicBlock *NextMBB;
1855 if (BTB.ContiguousRange && j + 2 == ej) {
1856 // Second-to-last bit-test with contiguous range: fall through to the
1857 // target of the final bit test.
1858 NextMBB = BTB.Cases[j + 1].TargetBB;
1859 } else if (j + 1 == ej) {
1860 // For the last bit test, fall through to Default.
1861 NextMBB = BTB.Default;
1862 } else {
1863 // Otherwise, fall through to the next bit test.
1864 NextMBB = BTB.Cases[j + 1].ThisBB;
1865 }
1866
1867 SDB->visitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j],
1868 FuncInfo->MBB);
1869
1870 CurDAG->setRoot(SDB->getRoot());
1871 SDB->clear();
1872 CodeGenAndEmitDAG();
1873
1874 if (BTB.ContiguousRange && j + 2 == ej) {
1875 // Since we're not going to use the final bit test, remove it.
1876 BTB.Cases.pop_back();
1877 break;
1878 }
1879 }
1880
1881 // Update PHI Nodes
1882 for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
1883 pi != pe; ++pi) {
1884 MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
1885 MachineBasicBlock *PHIBB = PHI->getParent();
1886 assert(PHI->isPHI() &&
1887 "This is not a machine PHI node that we are updating!");
1888 // This is "default" BB. We have two jumps to it. From "header" BB and
1889 // from last "case" BB, unless the latter was skipped.
1890 if (PHIBB == BTB.Default) {
1891 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(BTB.Parent);
1892 if (!BTB.ContiguousRange) {
1893 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)
1894 .addMBB(BTB.Cases.back().ThisBB);
1895 }
1896 }
1897 // One of "cases" BB.
1898 for (unsigned j = 0, ej = BTB.Cases.size();
1899 j != ej; ++j) {
1900 MachineBasicBlock* cBB = BTB.Cases[j].ThisBB;
1901 if (cBB->isSuccessor(PHIBB))
1902 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(cBB);
1903 }
1904 }
1905 }
1906 SDB->SL->BitTestCases.clear();
1907
1908 // If the JumpTable record is filled in, then we need to emit a jump table.
1909 // Updating the PHI nodes is tricky in this case, since we need to determine
1910 // whether the PHI is a successor of the range check MBB or the jump table MBB
1911 for (unsigned i = 0, e = SDB->SL->JTCases.size(); i != e; ++i) {
1912 // Lower header first, if it wasn't already lowered
1913 if (!SDB->SL->JTCases[i].first.Emitted) {
1914 // Set the current basic block to the mbb we wish to insert the code into
1915 FuncInfo->MBB = SDB->SL->JTCases[i].first.HeaderBB;
1916 FuncInfo->InsertPt = FuncInfo->MBB->end();
1917 // Emit the code
1918 SDB->visitJumpTableHeader(SDB->SL->JTCases[i].second,
1919 SDB->SL->JTCases[i].first, FuncInfo->MBB);
1920 CurDAG->setRoot(SDB->getRoot());
1921 SDB->clear();
1922 CodeGenAndEmitDAG();
1923 }
1924
1925 // Set the current basic block to the mbb we wish to insert the code into
1926 FuncInfo->MBB = SDB->SL->JTCases[i].second.MBB;
1927 FuncInfo->InsertPt = FuncInfo->MBB->end();
1928 // Emit the code
1929 SDB->visitJumpTable(SDB->SL->JTCases[i].second);
1930 CurDAG->setRoot(SDB->getRoot());
1931 SDB->clear();
1932 CodeGenAndEmitDAG();
1933
1934 // Update PHI Nodes
1935 for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
1936 pi != pe; ++pi) {
1937 MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
1938 MachineBasicBlock *PHIBB = PHI->getParent();
1939 assert(PHI->isPHI() &&
1940 "This is not a machine PHI node that we are updating!");
1941 // "default" BB. We can go there only from header BB.
1942 if (PHIBB == SDB->SL->JTCases[i].second.Default)
1943 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)
1944 .addMBB(SDB->SL->JTCases[i].first.HeaderBB);
1945 // JT BB. Just iterate over successors here
1946 if (FuncInfo->MBB->isSuccessor(PHIBB))
1947 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(FuncInfo->MBB);
1948 }
1949 }
1950 SDB->SL->JTCases.clear();
1951
1952 // If we generated any switch lowering information, build and codegen any
1953 // additional DAGs necessary.
1954 for (unsigned i = 0, e = SDB->SL->SwitchCases.size(); i != e; ++i) {
1955 // Set the current basic block to the mbb we wish to insert the code into
1956 FuncInfo->MBB = SDB->SL->SwitchCases[i].ThisBB;
1957 FuncInfo->InsertPt = FuncInfo->MBB->end();
1958
1959 // Determine the unique successors.
1960 SmallVector<MachineBasicBlock *, 2> Succs;
1961 Succs.push_back(SDB->SL->SwitchCases[i].TrueBB);
1962 if (SDB->SL->SwitchCases[i].TrueBB != SDB->SL->SwitchCases[i].FalseBB)
1963 Succs.push_back(SDB->SL->SwitchCases[i].FalseBB);
1964
1965 // Emit the code. Note that this could result in FuncInfo->MBB being split.
1966 SDB->visitSwitchCase(SDB->SL->SwitchCases[i], FuncInfo->MBB);
1967 CurDAG->setRoot(SDB->getRoot());
1968 SDB->clear();
1969 CodeGenAndEmitDAG();
1970
1971 // Remember the last block, now that any splitting is done, for use in
1972 // populating PHI nodes in successors.
1973 MachineBasicBlock *ThisBB = FuncInfo->MBB;
1974
1975 // Handle any PHI nodes in successors of this chunk, as if we were coming
1976 // from the original BB before switch expansion. Note that PHI nodes can
1977 // occur multiple times in PHINodesToUpdate. We have to be very careful to
1978 // handle them the right number of times.
1979 for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1980 FuncInfo->MBB = Succs[i];
1981 FuncInfo->InsertPt = FuncInfo->MBB->end();
1982 // FuncInfo->MBB may have been removed from the CFG if a branch was
1983 // constant folded.
1984 if (ThisBB->isSuccessor(FuncInfo->MBB)) {
1985 for (MachineBasicBlock::iterator
1986 MBBI = FuncInfo->MBB->begin(), MBBE = FuncInfo->MBB->end();
1987 MBBI != MBBE && MBBI->isPHI(); ++MBBI) {
1988 MachineInstrBuilder PHI(*MF, MBBI);
1989 // This value for this PHI node is recorded in PHINodesToUpdate.
1990 for (unsigned pn = 0; ; ++pn) {
1991 assert(pn != FuncInfo->PHINodesToUpdate.size() &&
1992 "Didn't find PHI entry!");
1993 if (FuncInfo->PHINodesToUpdate[pn].first == PHI) {
1994 PHI.addReg(FuncInfo->PHINodesToUpdate[pn].second).addMBB(ThisBB);
1995 break;
1996 }
1997 }
1998 }
1999 }
2000 }
2001 }
2002 SDB->SL->SwitchCases.clear();
2003 }
2004
2005 /// Create the scheduler. If a specific scheduler was specified
2006 /// via the SchedulerRegistry, use it, otherwise select the
2007 /// one preferred by the target.
2008 ///
CreateScheduler()2009 ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {
2010 return ISHeuristic(this, OptLevel);
2011 }
2012
2013 //===----------------------------------------------------------------------===//
2014 // Helper functions used by the generated instruction selector.
2015 //===----------------------------------------------------------------------===//
2016 // Calls to these methods are generated by tblgen.
2017
2018 /// CheckAndMask - The isel is trying to match something like (and X, 255). If
2019 /// the dag combiner simplified the 255, we still want to match. RHS is the
2020 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
2021 /// specified in the .td file (e.g. 255).
CheckAndMask(SDValue LHS,ConstantSDNode * RHS,int64_t DesiredMaskS) const2022 bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
2023 int64_t DesiredMaskS) const {
2024 const APInt &ActualMask = RHS->getAPIntValue();
2025 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
2026
2027 // If the actual mask exactly matches, success!
2028 if (ActualMask == DesiredMask)
2029 return true;
2030
2031 // If the actual AND mask is allowing unallowed bits, this doesn't match.
2032 if (!ActualMask.isSubsetOf(DesiredMask))
2033 return false;
2034
2035 // Otherwise, the DAG Combiner may have proven that the value coming in is
2036 // either already zero or is not demanded. Check for known zero input bits.
2037 APInt NeededMask = DesiredMask & ~ActualMask;
2038 if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
2039 return true;
2040
2041 // TODO: check to see if missing bits are just not demanded.
2042
2043 // Otherwise, this pattern doesn't match.
2044 return false;
2045 }
2046
2047 /// CheckOrMask - The isel is trying to match something like (or X, 255). If
2048 /// the dag combiner simplified the 255, we still want to match. RHS is the
2049 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
2050 /// specified in the .td file (e.g. 255).
CheckOrMask(SDValue LHS,ConstantSDNode * RHS,int64_t DesiredMaskS) const2051 bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
2052 int64_t DesiredMaskS) const {
2053 const APInt &ActualMask = RHS->getAPIntValue();
2054 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
2055
2056 // If the actual mask exactly matches, success!
2057 if (ActualMask == DesiredMask)
2058 return true;
2059
2060 // If the actual AND mask is allowing unallowed bits, this doesn't match.
2061 if (!ActualMask.isSubsetOf(DesiredMask))
2062 return false;
2063
2064 // Otherwise, the DAG Combiner may have proven that the value coming in is
2065 // either already zero or is not demanded. Check for known zero input bits.
2066 APInt NeededMask = DesiredMask & ~ActualMask;
2067 KnownBits Known = CurDAG->computeKnownBits(LHS);
2068
2069 // If all the missing bits in the or are already known to be set, match!
2070 if (NeededMask.isSubsetOf(Known.One))
2071 return true;
2072
2073 // TODO: check to see if missing bits are just not demanded.
2074
2075 // Otherwise, this pattern doesn't match.
2076 return false;
2077 }
2078
2079 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
2080 /// by tblgen. Others should not call it.
SelectInlineAsmMemoryOperands(std::vector<SDValue> & Ops,const SDLoc & DL)2081 void SelectionDAGISel::SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
2082 const SDLoc &DL) {
2083 std::vector<SDValue> InOps;
2084 std::swap(InOps, Ops);
2085
2086 Ops.push_back(InOps[InlineAsm::Op_InputChain]); // 0
2087 Ops.push_back(InOps[InlineAsm::Op_AsmString]); // 1
2088 Ops.push_back(InOps[InlineAsm::Op_MDNode]); // 2, !srcloc
2089 Ops.push_back(InOps[InlineAsm::Op_ExtraInfo]); // 3 (SideEffect, AlignStack)
2090
2091 unsigned i = InlineAsm::Op_FirstOperand, e = InOps.size();
2092 if (InOps[e-1].getValueType() == MVT::Glue)
2093 --e; // Don't process a glue operand if it is here.
2094
2095 while (i != e) {
2096 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue();
2097 if (!InlineAsm::isMemKind(Flags)) {
2098 // Just skip over this operand, copying the operands verbatim.
2099 Ops.insert(Ops.end(), InOps.begin()+i,
2100 InOps.begin()+i+InlineAsm::getNumOperandRegisters(Flags) + 1);
2101 i += InlineAsm::getNumOperandRegisters(Flags) + 1;
2102 } else {
2103 assert(InlineAsm::getNumOperandRegisters(Flags) == 1 &&
2104 "Memory operand with multiple values?");
2105
2106 unsigned TiedToOperand;
2107 if (InlineAsm::isUseOperandTiedToDef(Flags, TiedToOperand)) {
2108 // We need the constraint ID from the operand this is tied to.
2109 unsigned CurOp = InlineAsm::Op_FirstOperand;
2110 Flags = cast<ConstantSDNode>(InOps[CurOp])->getZExtValue();
2111 for (; TiedToOperand; --TiedToOperand) {
2112 CurOp += InlineAsm::getNumOperandRegisters(Flags)+1;
2113 Flags = cast<ConstantSDNode>(InOps[CurOp])->getZExtValue();
2114 }
2115 }
2116
2117 // Otherwise, this is a memory operand. Ask the target to select it.
2118 std::vector<SDValue> SelOps;
2119 unsigned ConstraintID = InlineAsm::getMemoryConstraintID(Flags);
2120 if (SelectInlineAsmMemoryOperand(InOps[i+1], ConstraintID, SelOps))
2121 report_fatal_error("Could not match memory address. Inline asm"
2122 " failure!");
2123
2124 // Add this to the output node.
2125 unsigned NewFlags =
2126 InlineAsm::getFlagWord(InlineAsm::Kind_Mem, SelOps.size());
2127 NewFlags = InlineAsm::getFlagWordForMem(NewFlags, ConstraintID);
2128 Ops.push_back(CurDAG->getTargetConstant(NewFlags, DL, MVT::i32));
2129 llvm::append_range(Ops, SelOps);
2130 i += 2;
2131 }
2132 }
2133
2134 // Add the glue input back if present.
2135 if (e != InOps.size())
2136 Ops.push_back(InOps.back());
2137 }
2138
2139 /// findGlueUse - Return use of MVT::Glue value produced by the specified
2140 /// SDNode.
2141 ///
findGlueUse(SDNode * N)2142 static SDNode *findGlueUse(SDNode *N) {
2143 unsigned FlagResNo = N->getNumValues()-1;
2144 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
2145 SDUse &Use = I.getUse();
2146 if (Use.getResNo() == FlagResNo)
2147 return Use.getUser();
2148 }
2149 return nullptr;
2150 }
2151
2152 /// findNonImmUse - Return true if "Def" is a predecessor of "Root" via a path
2153 /// beyond "ImmedUse". We may ignore chains as they are checked separately.
findNonImmUse(SDNode * Root,SDNode * Def,SDNode * ImmedUse,bool IgnoreChains)2154 static bool findNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse,
2155 bool IgnoreChains) {
2156 SmallPtrSet<const SDNode *, 16> Visited;
2157 SmallVector<const SDNode *, 16> WorkList;
2158 // Only check if we have non-immediate uses of Def.
2159 if (ImmedUse->isOnlyUserOf(Def))
2160 return false;
2161
2162 // We don't care about paths to Def that go through ImmedUse so mark it
2163 // visited and mark non-def operands as used.
2164 Visited.insert(ImmedUse);
2165 for (const SDValue &Op : ImmedUse->op_values()) {
2166 SDNode *N = Op.getNode();
2167 // Ignore chain deps (they are validated by
2168 // HandleMergeInputChains) and immediate uses
2169 if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)
2170 continue;
2171 if (!Visited.insert(N).second)
2172 continue;
2173 WorkList.push_back(N);
2174 }
2175
2176 // Initialize worklist to operands of Root.
2177 if (Root != ImmedUse) {
2178 for (const SDValue &Op : Root->op_values()) {
2179 SDNode *N = Op.getNode();
2180 // Ignore chains (they are validated by HandleMergeInputChains)
2181 if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)
2182 continue;
2183 if (!Visited.insert(N).second)
2184 continue;
2185 WorkList.push_back(N);
2186 }
2187 }
2188
2189 return SDNode::hasPredecessorHelper(Def, Visited, WorkList, 0, true);
2190 }
2191
2192 /// IsProfitableToFold - Returns true if it's profitable to fold the specific
2193 /// operand node N of U during instruction selection that starts at Root.
IsProfitableToFold(SDValue N,SDNode * U,SDNode * Root) const2194 bool SelectionDAGISel::IsProfitableToFold(SDValue N, SDNode *U,
2195 SDNode *Root) const {
2196 if (OptLevel == CodeGenOpt::None) return false;
2197 return N.hasOneUse();
2198 }
2199
2200 /// IsLegalToFold - Returns true if the specific operand node N of
2201 /// U can be folded during instruction selection that starts at Root.
IsLegalToFold(SDValue N,SDNode * U,SDNode * Root,CodeGenOpt::Level OptLevel,bool IgnoreChains)2202 bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
2203 CodeGenOpt::Level OptLevel,
2204 bool IgnoreChains) {
2205 if (OptLevel == CodeGenOpt::None) return false;
2206
2207 // If Root use can somehow reach N through a path that that doesn't contain
2208 // U then folding N would create a cycle. e.g. In the following
2209 // diagram, Root can reach N through X. If N is folded into Root, then
2210 // X is both a predecessor and a successor of U.
2211 //
2212 // [N*] //
2213 // ^ ^ //
2214 // / \ //
2215 // [U*] [X]? //
2216 // ^ ^ //
2217 // \ / //
2218 // \ / //
2219 // [Root*] //
2220 //
2221 // * indicates nodes to be folded together.
2222 //
2223 // If Root produces glue, then it gets (even more) interesting. Since it
2224 // will be "glued" together with its glue use in the scheduler, we need to
2225 // check if it might reach N.
2226 //
2227 // [N*] //
2228 // ^ ^ //
2229 // / \ //
2230 // [U*] [X]? //
2231 // ^ ^ //
2232 // \ \ //
2233 // \ | //
2234 // [Root*] | //
2235 // ^ | //
2236 // f | //
2237 // | / //
2238 // [Y] / //
2239 // ^ / //
2240 // f / //
2241 // | / //
2242 // [GU] //
2243 //
2244 // If GU (glue use) indirectly reaches N (the load), and Root folds N
2245 // (call it Fold), then X is a predecessor of GU and a successor of
2246 // Fold. But since Fold and GU are glued together, this will create
2247 // a cycle in the scheduling graph.
2248
2249 // If the node has glue, walk down the graph to the "lowest" node in the
2250 // glueged set.
2251 EVT VT = Root->getValueType(Root->getNumValues()-1);
2252 while (VT == MVT::Glue) {
2253 SDNode *GU = findGlueUse(Root);
2254 if (!GU)
2255 break;
2256 Root = GU;
2257 VT = Root->getValueType(Root->getNumValues()-1);
2258
2259 // If our query node has a glue result with a use, we've walked up it. If
2260 // the user (which has already been selected) has a chain or indirectly uses
2261 // the chain, HandleMergeInputChains will not consider it. Because of
2262 // this, we cannot ignore chains in this predicate.
2263 IgnoreChains = false;
2264 }
2265
2266 return !findNonImmUse(Root, N.getNode(), U, IgnoreChains);
2267 }
2268
Select_INLINEASM(SDNode * N)2269 void SelectionDAGISel::Select_INLINEASM(SDNode *N) {
2270 SDLoc DL(N);
2271
2272 std::vector<SDValue> Ops(N->op_begin(), N->op_end());
2273 SelectInlineAsmMemoryOperands(Ops, DL);
2274
2275 const EVT VTs[] = {MVT::Other, MVT::Glue};
2276 SDValue New = CurDAG->getNode(N->getOpcode(), DL, VTs, Ops);
2277 New->setNodeId(-1);
2278 ReplaceUses(N, New.getNode());
2279 CurDAG->RemoveDeadNode(N);
2280 }
2281
Select_READ_REGISTER(SDNode * Op)2282 void SelectionDAGISel::Select_READ_REGISTER(SDNode *Op) {
2283 SDLoc dl(Op);
2284 MDNodeSDNode *MD = cast<MDNodeSDNode>(Op->getOperand(1));
2285 const MDString *RegStr = cast<MDString>(MD->getMD()->getOperand(0));
2286
2287 EVT VT = Op->getValueType(0);
2288 LLT Ty = VT.isSimple() ? getLLTForMVT(VT.getSimpleVT()) : LLT();
2289 Register Reg =
2290 TLI->getRegisterByName(RegStr->getString().data(), Ty,
2291 CurDAG->getMachineFunction());
2292 SDValue New = CurDAG->getCopyFromReg(
2293 Op->getOperand(0), dl, Reg, Op->getValueType(0));
2294 New->setNodeId(-1);
2295 ReplaceUses(Op, New.getNode());
2296 CurDAG->RemoveDeadNode(Op);
2297 }
2298
Select_WRITE_REGISTER(SDNode * Op)2299 void SelectionDAGISel::Select_WRITE_REGISTER(SDNode *Op) {
2300 SDLoc dl(Op);
2301 MDNodeSDNode *MD = cast<MDNodeSDNode>(Op->getOperand(1));
2302 const MDString *RegStr = cast<MDString>(MD->getMD()->getOperand(0));
2303
2304 EVT VT = Op->getOperand(2).getValueType();
2305 LLT Ty = VT.isSimple() ? getLLTForMVT(VT.getSimpleVT()) : LLT();
2306
2307 Register Reg = TLI->getRegisterByName(RegStr->getString().data(), Ty,
2308 CurDAG->getMachineFunction());
2309 SDValue New = CurDAG->getCopyToReg(
2310 Op->getOperand(0), dl, Reg, Op->getOperand(2));
2311 New->setNodeId(-1);
2312 ReplaceUses(Op, New.getNode());
2313 CurDAG->RemoveDeadNode(Op);
2314 }
2315
Select_UNDEF(SDNode * N)2316 void SelectionDAGISel::Select_UNDEF(SDNode *N) {
2317 CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF, N->getValueType(0));
2318 }
2319
Select_FREEZE(SDNode * N)2320 void SelectionDAGISel::Select_FREEZE(SDNode *N) {
2321 // TODO: We don't have FREEZE pseudo-instruction in MachineInstr-level now.
2322 // If FREEZE instruction is added later, the code below must be changed as
2323 // well.
2324 CurDAG->SelectNodeTo(N, TargetOpcode::COPY, N->getValueType(0),
2325 N->getOperand(0));
2326 }
2327
2328 /// GetVBR - decode a vbr encoding whose top bit is set.
2329 LLVM_ATTRIBUTE_ALWAYS_INLINE static uint64_t
GetVBR(uint64_t Val,const unsigned char * MatcherTable,unsigned & Idx)2330 GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {
2331 assert(Val >= 128 && "Not a VBR");
2332 Val &= 127; // Remove first vbr bit.
2333
2334 unsigned Shift = 7;
2335 uint64_t NextBits;
2336 do {
2337 NextBits = MatcherTable[Idx++];
2338 Val |= (NextBits&127) << Shift;
2339 Shift += 7;
2340 } while (NextBits & 128);
2341
2342 return Val;
2343 }
2344
2345 /// When a match is complete, this method updates uses of interior chain results
2346 /// to use the new results.
UpdateChains(SDNode * NodeToMatch,SDValue InputChain,SmallVectorImpl<SDNode * > & ChainNodesMatched,bool isMorphNodeTo)2347 void SelectionDAGISel::UpdateChains(
2348 SDNode *NodeToMatch, SDValue InputChain,
2349 SmallVectorImpl<SDNode *> &ChainNodesMatched, bool isMorphNodeTo) {
2350 SmallVector<SDNode*, 4> NowDeadNodes;
2351
2352 // Now that all the normal results are replaced, we replace the chain and
2353 // glue results if present.
2354 if (!ChainNodesMatched.empty()) {
2355 assert(InputChain.getNode() &&
2356 "Matched input chains but didn't produce a chain");
2357 // Loop over all of the nodes we matched that produced a chain result.
2358 // Replace all the chain results with the final chain we ended up with.
2359 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2360 SDNode *ChainNode = ChainNodesMatched[i];
2361 // If ChainNode is null, it's because we replaced it on a previous
2362 // iteration and we cleared it out of the map. Just skip it.
2363 if (!ChainNode)
2364 continue;
2365
2366 assert(ChainNode->getOpcode() != ISD::DELETED_NODE &&
2367 "Deleted node left in chain");
2368
2369 // Don't replace the results of the root node if we're doing a
2370 // MorphNodeTo.
2371 if (ChainNode == NodeToMatch && isMorphNodeTo)
2372 continue;
2373
2374 SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);
2375 if (ChainVal.getValueType() == MVT::Glue)
2376 ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
2377 assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
2378 SelectionDAG::DAGNodeDeletedListener NDL(
2379 *CurDAG, [&](SDNode *N, SDNode *E) {
2380 std::replace(ChainNodesMatched.begin(), ChainNodesMatched.end(), N,
2381 static_cast<SDNode *>(nullptr));
2382 });
2383 if (ChainNode->getOpcode() != ISD::TokenFactor)
2384 ReplaceUses(ChainVal, InputChain);
2385
2386 // If the node became dead and we haven't already seen it, delete it.
2387 if (ChainNode != NodeToMatch && ChainNode->use_empty() &&
2388 !llvm::is_contained(NowDeadNodes, ChainNode))
2389 NowDeadNodes.push_back(ChainNode);
2390 }
2391 }
2392
2393 if (!NowDeadNodes.empty())
2394 CurDAG->RemoveDeadNodes(NowDeadNodes);
2395
2396 LLVM_DEBUG(dbgs() << "ISEL: Match complete!\n");
2397 }
2398
2399 /// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
2400 /// operation for when the pattern matched at least one node with a chains. The
2401 /// input vector contains a list of all of the chained nodes that we match. We
2402 /// must determine if this is a valid thing to cover (i.e. matching it won't
2403 /// induce cycles in the DAG) and if so, creating a TokenFactor node. that will
2404 /// be used as the input node chain for the generated nodes.
2405 static SDValue
HandleMergeInputChains(SmallVectorImpl<SDNode * > & ChainNodesMatched,SelectionDAG * CurDAG)2406 HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched,
2407 SelectionDAG *CurDAG) {
2408
2409 SmallPtrSet<const SDNode *, 16> Visited;
2410 SmallVector<const SDNode *, 8> Worklist;
2411 SmallVector<SDValue, 3> InputChains;
2412 unsigned int Max = 8192;
2413
2414 // Quick exit on trivial merge.
2415 if (ChainNodesMatched.size() == 1)
2416 return ChainNodesMatched[0]->getOperand(0);
2417
2418 // Add chains that aren't already added (internal). Peek through
2419 // token factors.
2420 std::function<void(const SDValue)> AddChains = [&](const SDValue V) {
2421 if (V.getValueType() != MVT::Other)
2422 return;
2423 if (V->getOpcode() == ISD::EntryToken)
2424 return;
2425 if (!Visited.insert(V.getNode()).second)
2426 return;
2427 if (V->getOpcode() == ISD::TokenFactor) {
2428 for (const SDValue &Op : V->op_values())
2429 AddChains(Op);
2430 } else
2431 InputChains.push_back(V);
2432 };
2433
2434 for (auto *N : ChainNodesMatched) {
2435 Worklist.push_back(N);
2436 Visited.insert(N);
2437 }
2438
2439 while (!Worklist.empty())
2440 AddChains(Worklist.pop_back_val()->getOperand(0));
2441
2442 // Skip the search if there are no chain dependencies.
2443 if (InputChains.size() == 0)
2444 return CurDAG->getEntryNode();
2445
2446 // If one of these chains is a successor of input, we must have a
2447 // node that is both the predecessor and successor of the
2448 // to-be-merged nodes. Fail.
2449 Visited.clear();
2450 for (SDValue V : InputChains)
2451 Worklist.push_back(V.getNode());
2452
2453 for (auto *N : ChainNodesMatched)
2454 if (SDNode::hasPredecessorHelper(N, Visited, Worklist, Max, true))
2455 return SDValue();
2456
2457 // Return merged chain.
2458 if (InputChains.size() == 1)
2459 return InputChains[0];
2460 return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]),
2461 MVT::Other, InputChains);
2462 }
2463
2464 /// MorphNode - Handle morphing a node in place for the selector.
2465 SDNode *SelectionDAGISel::
MorphNode(SDNode * Node,unsigned TargetOpc,SDVTList VTList,ArrayRef<SDValue> Ops,unsigned EmitNodeInfo)2466 MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
2467 ArrayRef<SDValue> Ops, unsigned EmitNodeInfo) {
2468 // It is possible we're using MorphNodeTo to replace a node with no
2469 // normal results with one that has a normal result (or we could be
2470 // adding a chain) and the input could have glue and chains as well.
2471 // In this case we need to shift the operands down.
2472 // FIXME: This is a horrible hack and broken in obscure cases, no worse
2473 // than the old isel though.
2474 int OldGlueResultNo = -1, OldChainResultNo = -1;
2475
2476 unsigned NTMNumResults = Node->getNumValues();
2477 if (Node->getValueType(NTMNumResults-1) == MVT::Glue) {
2478 OldGlueResultNo = NTMNumResults-1;
2479 if (NTMNumResults != 1 &&
2480 Node->getValueType(NTMNumResults-2) == MVT::Other)
2481 OldChainResultNo = NTMNumResults-2;
2482 } else if (Node->getValueType(NTMNumResults-1) == MVT::Other)
2483 OldChainResultNo = NTMNumResults-1;
2484
2485 // Call the underlying SelectionDAG routine to do the transmogrification. Note
2486 // that this deletes operands of the old node that become dead.
2487 SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops);
2488
2489 // MorphNodeTo can operate in two ways: if an existing node with the
2490 // specified operands exists, it can just return it. Otherwise, it
2491 // updates the node in place to have the requested operands.
2492 if (Res == Node) {
2493 // If we updated the node in place, reset the node ID. To the isel,
2494 // this should be just like a newly allocated machine node.
2495 Res->setNodeId(-1);
2496 }
2497
2498 unsigned ResNumResults = Res->getNumValues();
2499 // Move the glue if needed.
2500 if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 &&
2501 (unsigned)OldGlueResultNo != ResNumResults-1)
2502 ReplaceUses(SDValue(Node, OldGlueResultNo),
2503 SDValue(Res, ResNumResults - 1));
2504
2505 if ((EmitNodeInfo & OPFL_GlueOutput) != 0)
2506 --ResNumResults;
2507
2508 // Move the chain reference if needed.
2509 if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
2510 (unsigned)OldChainResultNo != ResNumResults-1)
2511 ReplaceUses(SDValue(Node, OldChainResultNo),
2512 SDValue(Res, ResNumResults - 1));
2513
2514 // Otherwise, no replacement happened because the node already exists. Replace
2515 // Uses of the old node with the new one.
2516 if (Res != Node) {
2517 ReplaceNode(Node, Res);
2518 } else {
2519 EnforceNodeIdInvariant(Res);
2520 }
2521
2522 return Res;
2523 }
2524
2525 /// CheckSame - Implements OP_CheckSame.
2526 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckSame(const unsigned char * MatcherTable,unsigned & MatcherIndex,SDValue N,const SmallVectorImpl<std::pair<SDValue,SDNode * >> & RecordedNodes)2527 CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2528 const SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes) {
2529 // Accept if it is exactly the same as a previously recorded node.
2530 unsigned RecNo = MatcherTable[MatcherIndex++];
2531 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2532 return N == RecordedNodes[RecNo].first;
2533 }
2534
2535 /// CheckChildSame - Implements OP_CheckChildXSame.
CheckChildSame(const unsigned char * MatcherTable,unsigned & MatcherIndex,SDValue N,const SmallVectorImpl<std::pair<SDValue,SDNode * >> & RecordedNodes,unsigned ChildNo)2536 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool CheckChildSame(
2537 const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2538 const SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes,
2539 unsigned ChildNo) {
2540 if (ChildNo >= N.getNumOperands())
2541 return false; // Match fails if out of range child #.
2542 return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo),
2543 RecordedNodes);
2544 }
2545
2546 /// CheckPatternPredicate - Implements OP_CheckPatternPredicate.
2547 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckPatternPredicate(const unsigned char * MatcherTable,unsigned & MatcherIndex,const SelectionDAGISel & SDISel)2548 CheckPatternPredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2549 const SelectionDAGISel &SDISel) {
2550 return SDISel.CheckPatternPredicate(MatcherTable[MatcherIndex++]);
2551 }
2552
2553 /// CheckNodePredicate - Implements OP_CheckNodePredicate.
2554 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckNodePredicate(const unsigned char * MatcherTable,unsigned & MatcherIndex,const SelectionDAGISel & SDISel,SDNode * N)2555 CheckNodePredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2556 const SelectionDAGISel &SDISel, SDNode *N) {
2557 return SDISel.CheckNodePredicate(N, MatcherTable[MatcherIndex++]);
2558 }
2559
2560 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckOpcode(const unsigned char * MatcherTable,unsigned & MatcherIndex,SDNode * N)2561 CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2562 SDNode *N) {
2563 uint16_t Opc = MatcherTable[MatcherIndex++];
2564 Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
2565 return N->getOpcode() == Opc;
2566 }
2567
2568 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckType(const unsigned char * MatcherTable,unsigned & MatcherIndex,SDValue N,const TargetLowering * TLI,const DataLayout & DL)2569 CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2570 const TargetLowering *TLI, const DataLayout &DL) {
2571 MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2572 if (N.getValueType() == VT) return true;
2573
2574 // Handle the case when VT is iPTR.
2575 return VT == MVT::iPTR && N.getValueType() == TLI->getPointerTy(DL);
2576 }
2577
2578 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckChildType(const unsigned char * MatcherTable,unsigned & MatcherIndex,SDValue N,const TargetLowering * TLI,const DataLayout & DL,unsigned ChildNo)2579 CheckChildType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2580 SDValue N, const TargetLowering *TLI, const DataLayout &DL,
2581 unsigned ChildNo) {
2582 if (ChildNo >= N.getNumOperands())
2583 return false; // Match fails if out of range child #.
2584 return ::CheckType(MatcherTable, MatcherIndex, N.getOperand(ChildNo), TLI,
2585 DL);
2586 }
2587
2588 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckCondCode(const unsigned char * MatcherTable,unsigned & MatcherIndex,SDValue N)2589 CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2590 SDValue N) {
2591 return cast<CondCodeSDNode>(N)->get() ==
2592 (ISD::CondCode)MatcherTable[MatcherIndex++];
2593 }
2594
2595 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckChild2CondCode(const unsigned char * MatcherTable,unsigned & MatcherIndex,SDValue N)2596 CheckChild2CondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2597 SDValue N) {
2598 if (2 >= N.getNumOperands())
2599 return false;
2600 return ::CheckCondCode(MatcherTable, MatcherIndex, N.getOperand(2));
2601 }
2602
2603 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckValueType(const unsigned char * MatcherTable,unsigned & MatcherIndex,SDValue N,const TargetLowering * TLI,const DataLayout & DL)2604 CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2605 SDValue N, const TargetLowering *TLI, const DataLayout &DL) {
2606 MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2607 if (cast<VTSDNode>(N)->getVT() == VT)
2608 return true;
2609
2610 // Handle the case when VT is iPTR.
2611 return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI->getPointerTy(DL);
2612 }
2613
2614 // Bit 0 stores the sign of the immediate. The upper bits contain the magnitude
2615 // shifted left by 1.
decodeSignRotatedValue(uint64_t V)2616 static uint64_t decodeSignRotatedValue(uint64_t V) {
2617 if ((V & 1) == 0)
2618 return V >> 1;
2619 if (V != 1)
2620 return -(V >> 1);
2621 // There is no such thing as -0 with integers. "-0" really means MININT.
2622 return 1ULL << 63;
2623 }
2624
2625 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckInteger(const unsigned char * MatcherTable,unsigned & MatcherIndex,SDValue N)2626 CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2627 SDValue N) {
2628 int64_t Val = MatcherTable[MatcherIndex++];
2629 if (Val & 128)
2630 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2631
2632 Val = decodeSignRotatedValue(Val);
2633
2634 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N);
2635 return C && C->getSExtValue() == Val;
2636 }
2637
2638 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckChildInteger(const unsigned char * MatcherTable,unsigned & MatcherIndex,SDValue N,unsigned ChildNo)2639 CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2640 SDValue N, unsigned ChildNo) {
2641 if (ChildNo >= N.getNumOperands())
2642 return false; // Match fails if out of range child #.
2643 return ::CheckInteger(MatcherTable, MatcherIndex, N.getOperand(ChildNo));
2644 }
2645
2646 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckAndImm(const unsigned char * MatcherTable,unsigned & MatcherIndex,SDValue N,const SelectionDAGISel & SDISel)2647 CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2648 SDValue N, const SelectionDAGISel &SDISel) {
2649 int64_t Val = MatcherTable[MatcherIndex++];
2650 if (Val & 128)
2651 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2652
2653 if (N->getOpcode() != ISD::AND) return false;
2654
2655 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
2656 return C && SDISel.CheckAndMask(N.getOperand(0), C, Val);
2657 }
2658
2659 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
CheckOrImm(const unsigned char * MatcherTable,unsigned & MatcherIndex,SDValue N,const SelectionDAGISel & SDISel)2660 CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2661 const SelectionDAGISel &SDISel) {
2662 int64_t Val = MatcherTable[MatcherIndex++];
2663 if (Val & 128)
2664 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2665
2666 if (N->getOpcode() != ISD::OR) return false;
2667
2668 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
2669 return C && SDISel.CheckOrMask(N.getOperand(0), C, Val);
2670 }
2671
2672 /// IsPredicateKnownToFail - If we know how and can do so without pushing a
2673 /// scope, evaluate the current node. If the current predicate is known to
2674 /// fail, set Result=true and return anything. If the current predicate is
2675 /// known to pass, set Result=false and return the MatcherIndex to continue
2676 /// with. If the current predicate is unknown, set Result=false and return the
2677 /// MatcherIndex to continue with.
IsPredicateKnownToFail(const unsigned char * Table,unsigned Index,SDValue N,bool & Result,const SelectionDAGISel & SDISel,SmallVectorImpl<std::pair<SDValue,SDNode * >> & RecordedNodes)2678 static unsigned IsPredicateKnownToFail(const unsigned char *Table,
2679 unsigned Index, SDValue N,
2680 bool &Result,
2681 const SelectionDAGISel &SDISel,
2682 SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) {
2683 switch (Table[Index++]) {
2684 default:
2685 Result = false;
2686 return Index-1; // Could not evaluate this predicate.
2687 case SelectionDAGISel::OPC_CheckSame:
2688 Result = !::CheckSame(Table, Index, N, RecordedNodes);
2689 return Index;
2690 case SelectionDAGISel::OPC_CheckChild0Same:
2691 case SelectionDAGISel::OPC_CheckChild1Same:
2692 case SelectionDAGISel::OPC_CheckChild2Same:
2693 case SelectionDAGISel::OPC_CheckChild3Same:
2694 Result = !::CheckChildSame(Table, Index, N, RecordedNodes,
2695 Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Same);
2696 return Index;
2697 case SelectionDAGISel::OPC_CheckPatternPredicate:
2698 Result = !::CheckPatternPredicate(Table, Index, SDISel);
2699 return Index;
2700 case SelectionDAGISel::OPC_CheckPredicate:
2701 Result = !::CheckNodePredicate(Table, Index, SDISel, N.getNode());
2702 return Index;
2703 case SelectionDAGISel::OPC_CheckOpcode:
2704 Result = !::CheckOpcode(Table, Index, N.getNode());
2705 return Index;
2706 case SelectionDAGISel::OPC_CheckType:
2707 Result = !::CheckType(Table, Index, N, SDISel.TLI,
2708 SDISel.CurDAG->getDataLayout());
2709 return Index;
2710 case SelectionDAGISel::OPC_CheckTypeRes: {
2711 unsigned Res = Table[Index++];
2712 Result = !::CheckType(Table, Index, N.getValue(Res), SDISel.TLI,
2713 SDISel.CurDAG->getDataLayout());
2714 return Index;
2715 }
2716 case SelectionDAGISel::OPC_CheckChild0Type:
2717 case SelectionDAGISel::OPC_CheckChild1Type:
2718 case SelectionDAGISel::OPC_CheckChild2Type:
2719 case SelectionDAGISel::OPC_CheckChild3Type:
2720 case SelectionDAGISel::OPC_CheckChild4Type:
2721 case SelectionDAGISel::OPC_CheckChild5Type:
2722 case SelectionDAGISel::OPC_CheckChild6Type:
2723 case SelectionDAGISel::OPC_CheckChild7Type:
2724 Result = !::CheckChildType(
2725 Table, Index, N, SDISel.TLI, SDISel.CurDAG->getDataLayout(),
2726 Table[Index - 1] - SelectionDAGISel::OPC_CheckChild0Type);
2727 return Index;
2728 case SelectionDAGISel::OPC_CheckCondCode:
2729 Result = !::CheckCondCode(Table, Index, N);
2730 return Index;
2731 case SelectionDAGISel::OPC_CheckChild2CondCode:
2732 Result = !::CheckChild2CondCode(Table, Index, N);
2733 return Index;
2734 case SelectionDAGISel::OPC_CheckValueType:
2735 Result = !::CheckValueType(Table, Index, N, SDISel.TLI,
2736 SDISel.CurDAG->getDataLayout());
2737 return Index;
2738 case SelectionDAGISel::OPC_CheckInteger:
2739 Result = !::CheckInteger(Table, Index, N);
2740 return Index;
2741 case SelectionDAGISel::OPC_CheckChild0Integer:
2742 case SelectionDAGISel::OPC_CheckChild1Integer:
2743 case SelectionDAGISel::OPC_CheckChild2Integer:
2744 case SelectionDAGISel::OPC_CheckChild3Integer:
2745 case SelectionDAGISel::OPC_CheckChild4Integer:
2746 Result = !::CheckChildInteger(Table, Index, N,
2747 Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Integer);
2748 return Index;
2749 case SelectionDAGISel::OPC_CheckAndImm:
2750 Result = !::CheckAndImm(Table, Index, N, SDISel);
2751 return Index;
2752 case SelectionDAGISel::OPC_CheckOrImm:
2753 Result = !::CheckOrImm(Table, Index, N, SDISel);
2754 return Index;
2755 }
2756 }
2757
2758 namespace {
2759
2760 struct MatchScope {
2761 /// FailIndex - If this match fails, this is the index to continue with.
2762 unsigned FailIndex;
2763
2764 /// NodeStack - The node stack when the scope was formed.
2765 SmallVector<SDValue, 4> NodeStack;
2766
2767 /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
2768 unsigned NumRecordedNodes;
2769
2770 /// NumMatchedMemRefs - The number of matched memref entries.
2771 unsigned NumMatchedMemRefs;
2772
2773 /// InputChain/InputGlue - The current chain/glue
2774 SDValue InputChain, InputGlue;
2775
2776 /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.
2777 bool HasChainNodesMatched;
2778 };
2779
2780 /// \A DAG update listener to keep the matching state
2781 /// (i.e. RecordedNodes and MatchScope) uptodate if the target is allowed to
2782 /// change the DAG while matching. X86 addressing mode matcher is an example
2783 /// for this.
2784 class MatchStateUpdater : public SelectionDAG::DAGUpdateListener
2785 {
2786 SDNode **NodeToMatch;
2787 SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes;
2788 SmallVectorImpl<MatchScope> &MatchScopes;
2789
2790 public:
MatchStateUpdater(SelectionDAG & DAG,SDNode ** NodeToMatch,SmallVectorImpl<std::pair<SDValue,SDNode * >> & RN,SmallVectorImpl<MatchScope> & MS)2791 MatchStateUpdater(SelectionDAG &DAG, SDNode **NodeToMatch,
2792 SmallVectorImpl<std::pair<SDValue, SDNode *>> &RN,
2793 SmallVectorImpl<MatchScope> &MS)
2794 : SelectionDAG::DAGUpdateListener(DAG), NodeToMatch(NodeToMatch),
2795 RecordedNodes(RN), MatchScopes(MS) {}
2796
NodeDeleted(SDNode * N,SDNode * E)2797 void NodeDeleted(SDNode *N, SDNode *E) override {
2798 // Some early-returns here to avoid the search if we deleted the node or
2799 // if the update comes from MorphNodeTo (MorphNodeTo is the last thing we
2800 // do, so it's unnecessary to update matching state at that point).
2801 // Neither of these can occur currently because we only install this
2802 // update listener during matching a complex patterns.
2803 if (!E || E->isMachineOpcode())
2804 return;
2805 // Check if NodeToMatch was updated.
2806 if (N == *NodeToMatch)
2807 *NodeToMatch = E;
2808 // Performing linear search here does not matter because we almost never
2809 // run this code. You'd have to have a CSE during complex pattern
2810 // matching.
2811 for (auto &I : RecordedNodes)
2812 if (I.first.getNode() == N)
2813 I.first.setNode(E);
2814
2815 for (auto &I : MatchScopes)
2816 for (auto &J : I.NodeStack)
2817 if (J.getNode() == N)
2818 J.setNode(E);
2819 }
2820 };
2821
2822 } // end anonymous namespace
2823
SelectCodeCommon(SDNode * NodeToMatch,const unsigned char * MatcherTable,unsigned TableSize)2824 void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch,
2825 const unsigned char *MatcherTable,
2826 unsigned TableSize) {
2827 // FIXME: Should these even be selected? Handle these cases in the caller?
2828 switch (NodeToMatch->getOpcode()) {
2829 default:
2830 break;
2831 case ISD::EntryToken: // These nodes remain the same.
2832 case ISD::BasicBlock:
2833 case ISD::Register:
2834 case ISD::RegisterMask:
2835 case ISD::HANDLENODE:
2836 case ISD::MDNODE_SDNODE:
2837 case ISD::TargetConstant:
2838 case ISD::TargetConstantFP:
2839 case ISD::TargetConstantPool:
2840 case ISD::TargetFrameIndex:
2841 case ISD::TargetExternalSymbol:
2842 case ISD::MCSymbol:
2843 case ISD::TargetBlockAddress:
2844 case ISD::TargetJumpTable:
2845 case ISD::TargetGlobalTLSAddress:
2846 case ISD::TargetGlobalAddress:
2847 case ISD::TokenFactor:
2848 case ISD::CopyFromReg:
2849 case ISD::CopyToReg:
2850 case ISD::EH_LABEL:
2851 case ISD::ANNOTATION_LABEL:
2852 case ISD::LIFETIME_START:
2853 case ISD::LIFETIME_END:
2854 case ISD::PSEUDO_PROBE:
2855 NodeToMatch->setNodeId(-1); // Mark selected.
2856 return;
2857 case ISD::AssertSext:
2858 case ISD::AssertZext:
2859 case ISD::AssertAlign:
2860 ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
2861 CurDAG->RemoveDeadNode(NodeToMatch);
2862 return;
2863 case ISD::INLINEASM:
2864 case ISD::INLINEASM_BR:
2865 Select_INLINEASM(NodeToMatch);
2866 return;
2867 case ISD::READ_REGISTER:
2868 Select_READ_REGISTER(NodeToMatch);
2869 return;
2870 case ISD::WRITE_REGISTER:
2871 Select_WRITE_REGISTER(NodeToMatch);
2872 return;
2873 case ISD::UNDEF:
2874 Select_UNDEF(NodeToMatch);
2875 return;
2876 case ISD::FREEZE:
2877 Select_FREEZE(NodeToMatch);
2878 return;
2879 }
2880
2881 assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
2882
2883 // Set up the node stack with NodeToMatch as the only node on the stack.
2884 SmallVector<SDValue, 8> NodeStack;
2885 SDValue N = SDValue(NodeToMatch, 0);
2886 NodeStack.push_back(N);
2887
2888 // MatchScopes - Scopes used when matching, if a match failure happens, this
2889 // indicates where to continue checking.
2890 SmallVector<MatchScope, 8> MatchScopes;
2891
2892 // RecordedNodes - This is the set of nodes that have been recorded by the
2893 // state machine. The second value is the parent of the node, or null if the
2894 // root is recorded.
2895 SmallVector<std::pair<SDValue, SDNode*>, 8> RecordedNodes;
2896
2897 // MatchedMemRefs - This is the set of MemRef's we've seen in the input
2898 // pattern.
2899 SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
2900
2901 // These are the current input chain and glue for use when generating nodes.
2902 // Various Emit operations change these. For example, emitting a copytoreg
2903 // uses and updates these.
2904 SDValue InputChain, InputGlue;
2905
2906 // ChainNodesMatched - If a pattern matches nodes that have input/output
2907 // chains, the OPC_EmitMergeInputChains operation is emitted which indicates
2908 // which ones they are. The result is captured into this list so that we can
2909 // update the chain results when the pattern is complete.
2910 SmallVector<SDNode*, 3> ChainNodesMatched;
2911
2912 LLVM_DEBUG(dbgs() << "ISEL: Starting pattern match\n");
2913
2914 // Determine where to start the interpreter. Normally we start at opcode #0,
2915 // but if the state machine starts with an OPC_SwitchOpcode, then we
2916 // accelerate the first lookup (which is guaranteed to be hot) with the
2917 // OpcodeOffset table.
2918 unsigned MatcherIndex = 0;
2919
2920 if (!OpcodeOffset.empty()) {
2921 // Already computed the OpcodeOffset table, just index into it.
2922 if (N.getOpcode() < OpcodeOffset.size())
2923 MatcherIndex = OpcodeOffset[N.getOpcode()];
2924 LLVM_DEBUG(dbgs() << " Initial Opcode index to " << MatcherIndex << "\n");
2925
2926 } else if (MatcherTable[0] == OPC_SwitchOpcode) {
2927 // Otherwise, the table isn't computed, but the state machine does start
2928 // with an OPC_SwitchOpcode instruction. Populate the table now, since this
2929 // is the first time we're selecting an instruction.
2930 unsigned Idx = 1;
2931 while (true) {
2932 // Get the size of this case.
2933 unsigned CaseSize = MatcherTable[Idx++];
2934 if (CaseSize & 128)
2935 CaseSize = GetVBR(CaseSize, MatcherTable, Idx);
2936 if (CaseSize == 0) break;
2937
2938 // Get the opcode, add the index to the table.
2939 uint16_t Opc = MatcherTable[Idx++];
2940 Opc |= (unsigned short)MatcherTable[Idx++] << 8;
2941 if (Opc >= OpcodeOffset.size())
2942 OpcodeOffset.resize((Opc+1)*2);
2943 OpcodeOffset[Opc] = Idx;
2944 Idx += CaseSize;
2945 }
2946
2947 // Okay, do the lookup for the first opcode.
2948 if (N.getOpcode() < OpcodeOffset.size())
2949 MatcherIndex = OpcodeOffset[N.getOpcode()];
2950 }
2951
2952 while (true) {
2953 assert(MatcherIndex < TableSize && "Invalid index");
2954 #ifndef NDEBUG
2955 unsigned CurrentOpcodeIndex = MatcherIndex;
2956 #endif
2957 BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++];
2958 switch (Opcode) {
2959 case OPC_Scope: {
2960 // Okay, the semantics of this operation are that we should push a scope
2961 // then evaluate the first child. However, pushing a scope only to have
2962 // the first check fail (which then pops it) is inefficient. If we can
2963 // determine immediately that the first check (or first several) will
2964 // immediately fail, don't even bother pushing a scope for them.
2965 unsigned FailIndex;
2966
2967 while (true) {
2968 unsigned NumToSkip = MatcherTable[MatcherIndex++];
2969 if (NumToSkip & 128)
2970 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
2971 // Found the end of the scope with no match.
2972 if (NumToSkip == 0) {
2973 FailIndex = 0;
2974 break;
2975 }
2976
2977 FailIndex = MatcherIndex+NumToSkip;
2978
2979 unsigned MatcherIndexOfPredicate = MatcherIndex;
2980 (void)MatcherIndexOfPredicate; // silence warning.
2981
2982 // If we can't evaluate this predicate without pushing a scope (e.g. if
2983 // it is a 'MoveParent') or if the predicate succeeds on this node, we
2984 // push the scope and evaluate the full predicate chain.
2985 bool Result;
2986 MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,
2987 Result, *this, RecordedNodes);
2988 if (!Result)
2989 break;
2990
2991 LLVM_DEBUG(
2992 dbgs() << " Skipped scope entry (due to false predicate) at "
2993 << "index " << MatcherIndexOfPredicate << ", continuing at "
2994 << FailIndex << "\n");
2995 ++NumDAGIselRetries;
2996
2997 // Otherwise, we know that this case of the Scope is guaranteed to fail,
2998 // move to the next case.
2999 MatcherIndex = FailIndex;
3000 }
3001
3002 // If the whole scope failed to match, bail.
3003 if (FailIndex == 0) break;
3004
3005 // Push a MatchScope which indicates where to go if the first child fails
3006 // to match.
3007 MatchScope NewEntry;
3008 NewEntry.FailIndex = FailIndex;
3009 NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
3010 NewEntry.NumRecordedNodes = RecordedNodes.size();
3011 NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
3012 NewEntry.InputChain = InputChain;
3013 NewEntry.InputGlue = InputGlue;
3014 NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
3015 MatchScopes.push_back(NewEntry);
3016 continue;
3017 }
3018 case OPC_RecordNode: {
3019 // Remember this node, it may end up being an operand in the pattern.
3020 SDNode *Parent = nullptr;
3021 if (NodeStack.size() > 1)
3022 Parent = NodeStack[NodeStack.size()-2].getNode();
3023 RecordedNodes.push_back(std::make_pair(N, Parent));
3024 continue;
3025 }
3026
3027 case OPC_RecordChild0: case OPC_RecordChild1:
3028 case OPC_RecordChild2: case OPC_RecordChild3:
3029 case OPC_RecordChild4: case OPC_RecordChild5:
3030 case OPC_RecordChild6: case OPC_RecordChild7: {
3031 unsigned ChildNo = Opcode-OPC_RecordChild0;
3032 if (ChildNo >= N.getNumOperands())
3033 break; // Match fails if out of range child #.
3034
3035 RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo),
3036 N.getNode()));
3037 continue;
3038 }
3039 case OPC_RecordMemRef:
3040 if (auto *MN = dyn_cast<MemSDNode>(N))
3041 MatchedMemRefs.push_back(MN->getMemOperand());
3042 else {
3043 LLVM_DEBUG(dbgs() << "Expected MemSDNode "; N->dump(CurDAG);
3044 dbgs() << '\n');
3045 }
3046
3047 continue;
3048
3049 case OPC_CaptureGlueInput:
3050 // If the current node has an input glue, capture it in InputGlue.
3051 if (N->getNumOperands() != 0 &&
3052 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue)
3053 InputGlue = N->getOperand(N->getNumOperands()-1);
3054 continue;
3055
3056 case OPC_MoveChild: {
3057 unsigned ChildNo = MatcherTable[MatcherIndex++];
3058 if (ChildNo >= N.getNumOperands())
3059 break; // Match fails if out of range child #.
3060 N = N.getOperand(ChildNo);
3061 NodeStack.push_back(N);
3062 continue;
3063 }
3064
3065 case OPC_MoveChild0: case OPC_MoveChild1:
3066 case OPC_MoveChild2: case OPC_MoveChild3:
3067 case OPC_MoveChild4: case OPC_MoveChild5:
3068 case OPC_MoveChild6: case OPC_MoveChild7: {
3069 unsigned ChildNo = Opcode-OPC_MoveChild0;
3070 if (ChildNo >= N.getNumOperands())
3071 break; // Match fails if out of range child #.
3072 N = N.getOperand(ChildNo);
3073 NodeStack.push_back(N);
3074 continue;
3075 }
3076
3077 case OPC_MoveParent:
3078 // Pop the current node off the NodeStack.
3079 NodeStack.pop_back();
3080 assert(!NodeStack.empty() && "Node stack imbalance!");
3081 N = NodeStack.back();
3082 continue;
3083
3084 case OPC_CheckSame:
3085 if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break;
3086 continue;
3087
3088 case OPC_CheckChild0Same: case OPC_CheckChild1Same:
3089 case OPC_CheckChild2Same: case OPC_CheckChild3Same:
3090 if (!::CheckChildSame(MatcherTable, MatcherIndex, N, RecordedNodes,
3091 Opcode-OPC_CheckChild0Same))
3092 break;
3093 continue;
3094
3095 case OPC_CheckPatternPredicate:
3096 if (!::CheckPatternPredicate(MatcherTable, MatcherIndex, *this)) break;
3097 continue;
3098 case OPC_CheckPredicate:
3099 if (!::CheckNodePredicate(MatcherTable, MatcherIndex, *this,
3100 N.getNode()))
3101 break;
3102 continue;
3103 case OPC_CheckPredicateWithOperands: {
3104 unsigned OpNum = MatcherTable[MatcherIndex++];
3105 SmallVector<SDValue, 8> Operands;
3106
3107 for (unsigned i = 0; i < OpNum; ++i)
3108 Operands.push_back(RecordedNodes[MatcherTable[MatcherIndex++]].first);
3109
3110 unsigned PredNo = MatcherTable[MatcherIndex++];
3111 if (!CheckNodePredicateWithOperands(N.getNode(), PredNo, Operands))
3112 break;
3113 continue;
3114 }
3115 case OPC_CheckComplexPat: {
3116 unsigned CPNum = MatcherTable[MatcherIndex++];
3117 unsigned RecNo = MatcherTable[MatcherIndex++];
3118 assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat");
3119
3120 // If target can modify DAG during matching, keep the matching state
3121 // consistent.
3122 std::unique_ptr<MatchStateUpdater> MSU;
3123 if (ComplexPatternFuncMutatesDAG())
3124 MSU.reset(new MatchStateUpdater(*CurDAG, &NodeToMatch, RecordedNodes,
3125 MatchScopes));
3126
3127 if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second,
3128 RecordedNodes[RecNo].first, CPNum,
3129 RecordedNodes))
3130 break;
3131 continue;
3132 }
3133 case OPC_CheckOpcode:
3134 if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break;
3135 continue;
3136
3137 case OPC_CheckType:
3138 if (!::CheckType(MatcherTable, MatcherIndex, N, TLI,
3139 CurDAG->getDataLayout()))
3140 break;
3141 continue;
3142
3143 case OPC_CheckTypeRes: {
3144 unsigned Res = MatcherTable[MatcherIndex++];
3145 if (!::CheckType(MatcherTable, MatcherIndex, N.getValue(Res), TLI,
3146 CurDAG->getDataLayout()))
3147 break;
3148 continue;
3149 }
3150
3151 case OPC_SwitchOpcode: {
3152 unsigned CurNodeOpcode = N.getOpcode();
3153 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3154 unsigned CaseSize;
3155 while (true) {
3156 // Get the size of this case.
3157 CaseSize = MatcherTable[MatcherIndex++];
3158 if (CaseSize & 128)
3159 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3160 if (CaseSize == 0) break;
3161
3162 uint16_t Opc = MatcherTable[MatcherIndex++];
3163 Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
3164
3165 // If the opcode matches, then we will execute this case.
3166 if (CurNodeOpcode == Opc)
3167 break;
3168
3169 // Otherwise, skip over this case.
3170 MatcherIndex += CaseSize;
3171 }
3172
3173 // If no cases matched, bail out.
3174 if (CaseSize == 0) break;
3175
3176 // Otherwise, execute the case we found.
3177 LLVM_DEBUG(dbgs() << " OpcodeSwitch from " << SwitchStart << " to "
3178 << MatcherIndex << "\n");
3179 continue;
3180 }
3181
3182 case OPC_SwitchType: {
3183 MVT CurNodeVT = N.getSimpleValueType();
3184 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3185 unsigned CaseSize;
3186 while (true) {
3187 // Get the size of this case.
3188 CaseSize = MatcherTable[MatcherIndex++];
3189 if (CaseSize & 128)
3190 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3191 if (CaseSize == 0) break;
3192
3193 MVT CaseVT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3194 if (CaseVT == MVT::iPTR)
3195 CaseVT = TLI->getPointerTy(CurDAG->getDataLayout());
3196
3197 // If the VT matches, then we will execute this case.
3198 if (CurNodeVT == CaseVT)
3199 break;
3200
3201 // Otherwise, skip over this case.
3202 MatcherIndex += CaseSize;
3203 }
3204
3205 // If no cases matched, bail out.
3206 if (CaseSize == 0) break;
3207
3208 // Otherwise, execute the case we found.
3209 LLVM_DEBUG(dbgs() << " TypeSwitch[" << EVT(CurNodeVT).getEVTString()
3210 << "] from " << SwitchStart << " to " << MatcherIndex
3211 << '\n');
3212 continue;
3213 }
3214 case OPC_CheckChild0Type: case OPC_CheckChild1Type:
3215 case OPC_CheckChild2Type: case OPC_CheckChild3Type:
3216 case OPC_CheckChild4Type: case OPC_CheckChild5Type:
3217 case OPC_CheckChild6Type: case OPC_CheckChild7Type:
3218 if (!::CheckChildType(MatcherTable, MatcherIndex, N, TLI,
3219 CurDAG->getDataLayout(),
3220 Opcode - OPC_CheckChild0Type))
3221 break;
3222 continue;
3223 case OPC_CheckCondCode:
3224 if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break;
3225 continue;
3226 case OPC_CheckChild2CondCode:
3227 if (!::CheckChild2CondCode(MatcherTable, MatcherIndex, N)) break;
3228 continue;
3229 case OPC_CheckValueType:
3230 if (!::CheckValueType(MatcherTable, MatcherIndex, N, TLI,
3231 CurDAG->getDataLayout()))
3232 break;
3233 continue;
3234 case OPC_CheckInteger:
3235 if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break;
3236 continue;
3237 case OPC_CheckChild0Integer: case OPC_CheckChild1Integer:
3238 case OPC_CheckChild2Integer: case OPC_CheckChild3Integer:
3239 case OPC_CheckChild4Integer:
3240 if (!::CheckChildInteger(MatcherTable, MatcherIndex, N,
3241 Opcode-OPC_CheckChild0Integer)) break;
3242 continue;
3243 case OPC_CheckAndImm:
3244 if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break;
3245 continue;
3246 case OPC_CheckOrImm:
3247 if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break;
3248 continue;
3249 case OPC_CheckImmAllOnesV:
3250 if (!ISD::isConstantSplatVectorAllOnes(N.getNode()))
3251 break;
3252 continue;
3253 case OPC_CheckImmAllZerosV:
3254 if (!ISD::isConstantSplatVectorAllZeros(N.getNode()))
3255 break;
3256 continue;
3257
3258 case OPC_CheckFoldableChainNode: {
3259 assert(NodeStack.size() != 1 && "No parent node");
3260 // Verify that all intermediate nodes between the root and this one have
3261 // a single use (ignoring chains, which are handled in UpdateChains).
3262 bool HasMultipleUses = false;
3263 for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i) {
3264 unsigned NNonChainUses = 0;
3265 SDNode *NS = NodeStack[i].getNode();
3266 for (auto UI = NS->use_begin(), UE = NS->use_end(); UI != UE; ++UI)
3267 if (UI.getUse().getValueType() != MVT::Other)
3268 if (++NNonChainUses > 1) {
3269 HasMultipleUses = true;
3270 break;
3271 }
3272 if (HasMultipleUses) break;
3273 }
3274 if (HasMultipleUses) break;
3275
3276 // Check to see that the target thinks this is profitable to fold and that
3277 // we can fold it without inducing cycles in the graph.
3278 if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3279 NodeToMatch) ||
3280 !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3281 NodeToMatch, OptLevel,
3282 true/*We validate our own chains*/))
3283 break;
3284
3285 continue;
3286 }
3287 case OPC_EmitInteger:
3288 case OPC_EmitStringInteger: {
3289 MVT::SimpleValueType VT =
3290 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3291 int64_t Val = MatcherTable[MatcherIndex++];
3292 if (Val & 128)
3293 Val = GetVBR(Val, MatcherTable, MatcherIndex);
3294 if (Opcode == OPC_EmitInteger)
3295 Val = decodeSignRotatedValue(Val);
3296 RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3297 CurDAG->getTargetConstant(Val, SDLoc(NodeToMatch),
3298 VT), nullptr));
3299 continue;
3300 }
3301 case OPC_EmitRegister: {
3302 MVT::SimpleValueType VT =
3303 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3304 unsigned RegNo = MatcherTable[MatcherIndex++];
3305 RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3306 CurDAG->getRegister(RegNo, VT), nullptr));
3307 continue;
3308 }
3309 case OPC_EmitRegister2: {
3310 // For targets w/ more than 256 register names, the register enum
3311 // values are stored in two bytes in the matcher table (just like
3312 // opcodes).
3313 MVT::SimpleValueType VT =
3314 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3315 unsigned RegNo = MatcherTable[MatcherIndex++];
3316 RegNo |= MatcherTable[MatcherIndex++] << 8;
3317 RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3318 CurDAG->getRegister(RegNo, VT), nullptr));
3319 continue;
3320 }
3321
3322 case OPC_EmitConvertToTarget: {
3323 // Convert from IMM/FPIMM to target version.
3324 unsigned RecNo = MatcherTable[MatcherIndex++];
3325 assert(RecNo < RecordedNodes.size() && "Invalid EmitConvertToTarget");
3326 SDValue Imm = RecordedNodes[RecNo].first;
3327
3328 if (Imm->getOpcode() == ISD::Constant) {
3329 const ConstantInt *Val=cast<ConstantSDNode>(Imm)->getConstantIntValue();
3330 Imm = CurDAG->getTargetConstant(*Val, SDLoc(NodeToMatch),
3331 Imm.getValueType());
3332 } else if (Imm->getOpcode() == ISD::ConstantFP) {
3333 const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
3334 Imm = CurDAG->getTargetConstantFP(*Val, SDLoc(NodeToMatch),
3335 Imm.getValueType());
3336 }
3337
3338 RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second));
3339 continue;
3340 }
3341
3342 case OPC_EmitMergeInputChains1_0: // OPC_EmitMergeInputChains, 1, 0
3343 case OPC_EmitMergeInputChains1_1: // OPC_EmitMergeInputChains, 1, 1
3344 case OPC_EmitMergeInputChains1_2: { // OPC_EmitMergeInputChains, 1, 2
3345 // These are space-optimized forms of OPC_EmitMergeInputChains.
3346 assert(!InputChain.getNode() &&
3347 "EmitMergeInputChains should be the first chain producing node");
3348 assert(ChainNodesMatched.empty() &&
3349 "Should only have one EmitMergeInputChains per match");
3350
3351 // Read all of the chained nodes.
3352 unsigned RecNo = Opcode - OPC_EmitMergeInputChains1_0;
3353 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3354 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3355
3356 // FIXME: What if other value results of the node have uses not matched
3357 // by this pattern?
3358 if (ChainNodesMatched.back() != NodeToMatch &&
3359 !RecordedNodes[RecNo].first.hasOneUse()) {
3360 ChainNodesMatched.clear();
3361 break;
3362 }
3363
3364 // Merge the input chains if they are not intra-pattern references.
3365 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3366
3367 if (!InputChain.getNode())
3368 break; // Failed to merge.
3369 continue;
3370 }
3371
3372 case OPC_EmitMergeInputChains: {
3373 assert(!InputChain.getNode() &&
3374 "EmitMergeInputChains should be the first chain producing node");
3375 // This node gets a list of nodes we matched in the input that have
3376 // chains. We want to token factor all of the input chains to these nodes
3377 // together. However, if any of the input chains is actually one of the
3378 // nodes matched in this pattern, then we have an intra-match reference.
3379 // Ignore these because the newly token factored chain should not refer to
3380 // the old nodes.
3381 unsigned NumChains = MatcherTable[MatcherIndex++];
3382 assert(NumChains != 0 && "Can't TF zero chains");
3383
3384 assert(ChainNodesMatched.empty() &&
3385 "Should only have one EmitMergeInputChains per match");
3386
3387 // Read all of the chained nodes.
3388 for (unsigned i = 0; i != NumChains; ++i) {
3389 unsigned RecNo = MatcherTable[MatcherIndex++];
3390 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3391 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3392
3393 // FIXME: What if other value results of the node have uses not matched
3394 // by this pattern?
3395 if (ChainNodesMatched.back() != NodeToMatch &&
3396 !RecordedNodes[RecNo].first.hasOneUse()) {
3397 ChainNodesMatched.clear();
3398 break;
3399 }
3400 }
3401
3402 // If the inner loop broke out, the match fails.
3403 if (ChainNodesMatched.empty())
3404 break;
3405
3406 // Merge the input chains if they are not intra-pattern references.
3407 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3408
3409 if (!InputChain.getNode())
3410 break; // Failed to merge.
3411
3412 continue;
3413 }
3414
3415 case OPC_EmitCopyToReg:
3416 case OPC_EmitCopyToReg2: {
3417 unsigned RecNo = MatcherTable[MatcherIndex++];
3418 assert(RecNo < RecordedNodes.size() && "Invalid EmitCopyToReg");
3419 unsigned DestPhysReg = MatcherTable[MatcherIndex++];
3420 if (Opcode == OPC_EmitCopyToReg2)
3421 DestPhysReg |= MatcherTable[MatcherIndex++] << 8;
3422
3423 if (!InputChain.getNode())
3424 InputChain = CurDAG->getEntryNode();
3425
3426 InputChain = CurDAG->getCopyToReg(InputChain, SDLoc(NodeToMatch),
3427 DestPhysReg, RecordedNodes[RecNo].first,
3428 InputGlue);
3429
3430 InputGlue = InputChain.getValue(1);
3431 continue;
3432 }
3433
3434 case OPC_EmitNodeXForm: {
3435 unsigned XFormNo = MatcherTable[MatcherIndex++];
3436 unsigned RecNo = MatcherTable[MatcherIndex++];
3437 assert(RecNo < RecordedNodes.size() && "Invalid EmitNodeXForm");
3438 SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo);
3439 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, nullptr));
3440 continue;
3441 }
3442 case OPC_Coverage: {
3443 // This is emitted right before MorphNode/EmitNode.
3444 // So it should be safe to assume that this node has been selected
3445 unsigned index = MatcherTable[MatcherIndex++];
3446 index |= (MatcherTable[MatcherIndex++] << 8);
3447 dbgs() << "COVERED: " << getPatternForIndex(index) << "\n";
3448 dbgs() << "INCLUDED: " << getIncludePathForIndex(index) << "\n";
3449 continue;
3450 }
3451
3452 case OPC_EmitNode: case OPC_MorphNodeTo:
3453 case OPC_EmitNode0: case OPC_EmitNode1: case OPC_EmitNode2:
3454 case OPC_MorphNodeTo0: case OPC_MorphNodeTo1: case OPC_MorphNodeTo2: {
3455 uint16_t TargetOpc = MatcherTable[MatcherIndex++];
3456 TargetOpc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
3457 unsigned EmitNodeInfo = MatcherTable[MatcherIndex++];
3458 // Get the result VT list.
3459 unsigned NumVTs;
3460 // If this is one of the compressed forms, get the number of VTs based
3461 // on the Opcode. Otherwise read the next byte from the table.
3462 if (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2)
3463 NumVTs = Opcode - OPC_MorphNodeTo0;
3464 else if (Opcode >= OPC_EmitNode0 && Opcode <= OPC_EmitNode2)
3465 NumVTs = Opcode - OPC_EmitNode0;
3466 else
3467 NumVTs = MatcherTable[MatcherIndex++];
3468 SmallVector<EVT, 4> VTs;
3469 for (unsigned i = 0; i != NumVTs; ++i) {
3470 MVT::SimpleValueType VT =
3471 (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3472 if (VT == MVT::iPTR)
3473 VT = TLI->getPointerTy(CurDAG->getDataLayout()).SimpleTy;
3474 VTs.push_back(VT);
3475 }
3476
3477 if (EmitNodeInfo & OPFL_Chain)
3478 VTs.push_back(MVT::Other);
3479 if (EmitNodeInfo & OPFL_GlueOutput)
3480 VTs.push_back(MVT::Glue);
3481
3482 // This is hot code, so optimize the two most common cases of 1 and 2
3483 // results.
3484 SDVTList VTList;
3485 if (VTs.size() == 1)
3486 VTList = CurDAG->getVTList(VTs[0]);
3487 else if (VTs.size() == 2)
3488 VTList = CurDAG->getVTList(VTs[0], VTs[1]);
3489 else
3490 VTList = CurDAG->getVTList(VTs);
3491
3492 // Get the operand list.
3493 unsigned NumOps = MatcherTable[MatcherIndex++];
3494 SmallVector<SDValue, 8> Ops;
3495 for (unsigned i = 0; i != NumOps; ++i) {
3496 unsigned RecNo = MatcherTable[MatcherIndex++];
3497 if (RecNo & 128)
3498 RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
3499
3500 assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");
3501 Ops.push_back(RecordedNodes[RecNo].first);
3502 }
3503
3504 // If there are variadic operands to add, handle them now.
3505 if (EmitNodeInfo & OPFL_VariadicInfo) {
3506 // Determine the start index to copy from.
3507 unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
3508 FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
3509 assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
3510 "Invalid variadic node");
3511 // Copy all of the variadic operands, not including a potential glue
3512 // input.
3513 for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
3514 i != e; ++i) {
3515 SDValue V = NodeToMatch->getOperand(i);
3516 if (V.getValueType() == MVT::Glue) break;
3517 Ops.push_back(V);
3518 }
3519 }
3520
3521 // If this has chain/glue inputs, add them.
3522 if (EmitNodeInfo & OPFL_Chain)
3523 Ops.push_back(InputChain);
3524 if ((EmitNodeInfo & OPFL_GlueInput) && InputGlue.getNode() != nullptr)
3525 Ops.push_back(InputGlue);
3526
3527 // Check whether any matched node could raise an FP exception. Since all
3528 // such nodes must have a chain, it suffices to check ChainNodesMatched.
3529 // We need to perform this check before potentially modifying one of the
3530 // nodes via MorphNode.
3531 bool MayRaiseFPException = false;
3532 for (auto *N : ChainNodesMatched)
3533 if (mayRaiseFPException(N) && !N->getFlags().hasNoFPExcept()) {
3534 MayRaiseFPException = true;
3535 break;
3536 }
3537
3538 // Create the node.
3539 MachineSDNode *Res = nullptr;
3540 bool IsMorphNodeTo = Opcode == OPC_MorphNodeTo ||
3541 (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2);
3542 if (!IsMorphNodeTo) {
3543 // If this is a normal EmitNode command, just create the new node and
3544 // add the results to the RecordedNodes list.
3545 Res = CurDAG->getMachineNode(TargetOpc, SDLoc(NodeToMatch),
3546 VTList, Ops);
3547
3548 // Add all the non-glue/non-chain results to the RecordedNodes list.
3549 for (unsigned i = 0, e = VTs.size(); i != e; ++i) {
3550 if (VTs[i] == MVT::Other || VTs[i] == MVT::Glue) break;
3551 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i),
3552 nullptr));
3553 }
3554 } else {
3555 assert(NodeToMatch->getOpcode() != ISD::DELETED_NODE &&
3556 "NodeToMatch was removed partway through selection");
3557 SelectionDAG::DAGNodeDeletedListener NDL(*CurDAG, [&](SDNode *N,
3558 SDNode *E) {
3559 CurDAG->salvageDebugInfo(*N);
3560 auto &Chain = ChainNodesMatched;
3561 assert((!E || !is_contained(Chain, N)) &&
3562 "Chain node replaced during MorphNode");
3563 llvm::erase_value(Chain, N);
3564 });
3565 Res = cast<MachineSDNode>(MorphNode(NodeToMatch, TargetOpc, VTList,
3566 Ops, EmitNodeInfo));
3567 }
3568
3569 // Set the NoFPExcept flag when no original matched node could
3570 // raise an FP exception, but the new node potentially might.
3571 if (!MayRaiseFPException && mayRaiseFPException(Res)) {
3572 SDNodeFlags Flags = Res->getFlags();
3573 Flags.setNoFPExcept(true);
3574 Res->setFlags(Flags);
3575 }
3576
3577 // If the node had chain/glue results, update our notion of the current
3578 // chain and glue.
3579 if (EmitNodeInfo & OPFL_GlueOutput) {
3580 InputGlue = SDValue(Res, VTs.size()-1);
3581 if (EmitNodeInfo & OPFL_Chain)
3582 InputChain = SDValue(Res, VTs.size()-2);
3583 } else if (EmitNodeInfo & OPFL_Chain)
3584 InputChain = SDValue(Res, VTs.size()-1);
3585
3586 // If the OPFL_MemRefs glue is set on this node, slap all of the
3587 // accumulated memrefs onto it.
3588 //
3589 // FIXME: This is vastly incorrect for patterns with multiple outputs
3590 // instructions that access memory and for ComplexPatterns that match
3591 // loads.
3592 if (EmitNodeInfo & OPFL_MemRefs) {
3593 // Only attach load or store memory operands if the generated
3594 // instruction may load or store.
3595 const MCInstrDesc &MCID = TII->get(TargetOpc);
3596 bool mayLoad = MCID.mayLoad();
3597 bool mayStore = MCID.mayStore();
3598
3599 // We expect to have relatively few of these so just filter them into a
3600 // temporary buffer so that we can easily add them to the instruction.
3601 SmallVector<MachineMemOperand *, 4> FilteredMemRefs;
3602 for (MachineMemOperand *MMO : MatchedMemRefs) {
3603 if (MMO->isLoad()) {
3604 if (mayLoad)
3605 FilteredMemRefs.push_back(MMO);
3606 } else if (MMO->isStore()) {
3607 if (mayStore)
3608 FilteredMemRefs.push_back(MMO);
3609 } else {
3610 FilteredMemRefs.push_back(MMO);
3611 }
3612 }
3613
3614 CurDAG->setNodeMemRefs(Res, FilteredMemRefs);
3615 }
3616
3617 LLVM_DEBUG(if (!MatchedMemRefs.empty() && Res->memoperands_empty()) dbgs()
3618 << " Dropping mem operands\n";
3619 dbgs() << " " << (IsMorphNodeTo ? "Morphed" : "Created")
3620 << " node: ";
3621 Res->dump(CurDAG););
3622
3623 // If this was a MorphNodeTo then we're completely done!
3624 if (IsMorphNodeTo) {
3625 // Update chain uses.
3626 UpdateChains(Res, InputChain, ChainNodesMatched, true);
3627 return;
3628 }
3629 continue;
3630 }
3631
3632 case OPC_CompleteMatch: {
3633 // The match has been completed, and any new nodes (if any) have been
3634 // created. Patch up references to the matched dag to use the newly
3635 // created nodes.
3636 unsigned NumResults = MatcherTable[MatcherIndex++];
3637
3638 for (unsigned i = 0; i != NumResults; ++i) {
3639 unsigned ResSlot = MatcherTable[MatcherIndex++];
3640 if (ResSlot & 128)
3641 ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);
3642
3643 assert(ResSlot < RecordedNodes.size() && "Invalid CompleteMatch");
3644 SDValue Res = RecordedNodes[ResSlot].first;
3645
3646 assert(i < NodeToMatch->getNumValues() &&
3647 NodeToMatch->getValueType(i) != MVT::Other &&
3648 NodeToMatch->getValueType(i) != MVT::Glue &&
3649 "Invalid number of results to complete!");
3650 assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
3651 NodeToMatch->getValueType(i) == MVT::iPTR ||
3652 Res.getValueType() == MVT::iPTR ||
3653 NodeToMatch->getValueType(i).getSizeInBits() ==
3654 Res.getValueSizeInBits()) &&
3655 "invalid replacement");
3656 ReplaceUses(SDValue(NodeToMatch, i), Res);
3657 }
3658
3659 // Update chain uses.
3660 UpdateChains(NodeToMatch, InputChain, ChainNodesMatched, false);
3661
3662 // If the root node defines glue, we need to update it to the glue result.
3663 // TODO: This never happens in our tests and I think it can be removed /
3664 // replaced with an assert, but if we do it this the way the change is
3665 // NFC.
3666 if (NodeToMatch->getValueType(NodeToMatch->getNumValues() - 1) ==
3667 MVT::Glue &&
3668 InputGlue.getNode())
3669 ReplaceUses(SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1),
3670 InputGlue);
3671
3672 assert(NodeToMatch->use_empty() &&
3673 "Didn't replace all uses of the node?");
3674 CurDAG->RemoveDeadNode(NodeToMatch);
3675
3676 return;
3677 }
3678 }
3679
3680 // If the code reached this point, then the match failed. See if there is
3681 // another child to try in the current 'Scope', otherwise pop it until we
3682 // find a case to check.
3683 LLVM_DEBUG(dbgs() << " Match failed at index " << CurrentOpcodeIndex
3684 << "\n");
3685 ++NumDAGIselRetries;
3686 while (true) {
3687 if (MatchScopes.empty()) {
3688 CannotYetSelect(NodeToMatch);
3689 return;
3690 }
3691
3692 // Restore the interpreter state back to the point where the scope was
3693 // formed.
3694 MatchScope &LastScope = MatchScopes.back();
3695 RecordedNodes.resize(LastScope.NumRecordedNodes);
3696 NodeStack.clear();
3697 NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());
3698 N = NodeStack.back();
3699
3700 if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
3701 MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
3702 MatcherIndex = LastScope.FailIndex;
3703
3704 LLVM_DEBUG(dbgs() << " Continuing at " << MatcherIndex << "\n");
3705
3706 InputChain = LastScope.InputChain;
3707 InputGlue = LastScope.InputGlue;
3708 if (!LastScope.HasChainNodesMatched)
3709 ChainNodesMatched.clear();
3710
3711 // Check to see what the offset is at the new MatcherIndex. If it is zero
3712 // we have reached the end of this scope, otherwise we have another child
3713 // in the current scope to try.
3714 unsigned NumToSkip = MatcherTable[MatcherIndex++];
3715 if (NumToSkip & 128)
3716 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
3717
3718 // If we have another child in this scope to match, update FailIndex and
3719 // try it.
3720 if (NumToSkip != 0) {
3721 LastScope.FailIndex = MatcherIndex+NumToSkip;
3722 break;
3723 }
3724
3725 // End of this scope, pop it and try the next child in the containing
3726 // scope.
3727 MatchScopes.pop_back();
3728 }
3729 }
3730 }
3731
3732 /// Return whether the node may raise an FP exception.
mayRaiseFPException(SDNode * N) const3733 bool SelectionDAGISel::mayRaiseFPException(SDNode *N) const {
3734 // For machine opcodes, consult the MCID flag.
3735 if (N->isMachineOpcode()) {
3736 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
3737 return MCID.mayRaiseFPException();
3738 }
3739
3740 // For ISD opcodes, only StrictFP opcodes may raise an FP
3741 // exception.
3742 if (N->isTargetOpcode())
3743 return N->isTargetStrictFPOpcode();
3744 return N->isStrictFPOpcode();
3745 }
3746
isOrEquivalentToAdd(const SDNode * N) const3747 bool SelectionDAGISel::isOrEquivalentToAdd(const SDNode *N) const {
3748 assert(N->getOpcode() == ISD::OR && "Unexpected opcode");
3749 auto *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
3750 if (!C)
3751 return false;
3752
3753 // Detect when "or" is used to add an offset to a stack object.
3754 if (auto *FN = dyn_cast<FrameIndexSDNode>(N->getOperand(0))) {
3755 MachineFrameInfo &MFI = MF->getFrameInfo();
3756 Align A = MFI.getObjectAlign(FN->getIndex());
3757 int32_t Off = C->getSExtValue();
3758 // If the alleged offset fits in the zero bits guaranteed by
3759 // the alignment, then this or is really an add.
3760 return (Off >= 0) && (((A.value() - 1) & Off) == unsigned(Off));
3761 }
3762 return false;
3763 }
3764
CannotYetSelect(SDNode * N)3765 void SelectionDAGISel::CannotYetSelect(SDNode *N) {
3766 std::string msg;
3767 raw_string_ostream Msg(msg);
3768 Msg << "Cannot select: ";
3769
3770 if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&
3771 N->getOpcode() != ISD::INTRINSIC_WO_CHAIN &&
3772 N->getOpcode() != ISD::INTRINSIC_VOID) {
3773 N->printrFull(Msg, CurDAG);
3774 Msg << "\nIn function: " << MF->getName();
3775 } else {
3776 bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other;
3777 unsigned iid =
3778 cast<ConstantSDNode>(N->getOperand(HasInputChain))->getZExtValue();
3779 if (iid < Intrinsic::num_intrinsics)
3780 Msg << "intrinsic %" << Intrinsic::getName((Intrinsic::ID)iid, None);
3781 else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo())
3782 Msg << "target intrinsic %" << TII->getName(iid);
3783 else
3784 Msg << "unknown intrinsic #" << iid;
3785 }
3786 report_fatal_error(Msg.str());
3787 }
3788
3789 char SelectionDAGISel::ID = 0;
3790