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