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