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