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 DPValue &DPV : DPValue::filter(I.getDbgValueRange())) {
1465 if (DPV.Type == DPValue::LocationType::Declare &&
1466 processDbgDeclare(FuncInfo, DPV.getVariableLocationOp(0),
1467 DPV.getExpression(), DPV.getVariable(),
1468 DPV.getDebugLoc()))
1469 FuncInfo.PreprocessedDPVDeclares.insert(&DPV);
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::pushStackMapLiveVariable(SmallVectorImpl<SDValue> &Ops,
2374 SDValue OpVal, SDLoc DL) {
2375 SDNode *OpNode = OpVal.getNode();
2376
2377 // FrameIndex nodes should have been directly emitted to TargetFrameIndex
2378 // nodes at DAG-construction time.
2379 assert(OpNode->getOpcode() != ISD::FrameIndex);
2380
2381 if (OpNode->getOpcode() == ISD::Constant) {
2382 Ops.push_back(
2383 CurDAG->getTargetConstant(StackMaps::ConstantOp, DL, MVT::i64));
2385 OpVal.getValueType()));
2386 } else {
2387 Ops.push_back(OpVal);
2388 }
2389}
2390
2391void SelectionDAGISel::Select_STACKMAP(SDNode *N) {
2393 auto *It = N->op_begin();
2394 SDLoc DL(N);
2395
2396 // Stash the chain and glue operands so we can move them to the end.
2397 SDValue Chain = *It++;
2398 SDValue InGlue = *It++;
2399
2400 // <id> operand.
2401 SDValue ID = *It++;
2402 assert(ID.getValueType() == MVT::i64);
2403 Ops.push_back(ID);
2404
2405 // <numShadowBytes> operand.
2406 SDValue Shad = *It++;
2407 assert(Shad.getValueType() == MVT::i32);
2408 Ops.push_back(Shad);
2409
2410 // Live variable operands.
2411 for (; It != N->op_end(); It++)
2412 pushStackMapLiveVariable(Ops, *It, DL);
2413
2414 Ops.push_back(Chain);
2415 Ops.push_back(InGlue);
2416
2417 SDVTList NodeTys = CurDAG->getVTList(MVT::Other, MVT::Glue);
2418 CurDAG->SelectNodeTo(N, TargetOpcode::STACKMAP, NodeTys, Ops);
2419}
2420
2421void SelectionDAGISel::Select_PATCHPOINT(SDNode *N) {
2423 auto *It = N->op_begin();
2424 SDLoc DL(N);
2425
2426 // Cache arguments that will be moved to the end in the target node.
2427 SDValue Chain = *It++;
2428 std::optional<SDValue> Glue;
2429 if (It->getValueType() == MVT::Glue)
2430 Glue = *It++;
2431 SDValue RegMask = *It++;
2432
2433 // <id> operand.
2434 SDValue ID = *It++;
2435 assert(ID.getValueType() == MVT::i64);
2436 Ops.push_back(ID);
2437
2438 // <numShadowBytes> operand.
2439 SDValue Shad = *It++;
2440 assert(Shad.getValueType() == MVT::i32);
2441 Ops.push_back(Shad);
2442
2443 // Add the callee.
2444 Ops.push_back(*It++);
2445
2446 // Add <numArgs>.
2447 SDValue NumArgs = *It++;
2448 assert(NumArgs.getValueType() == MVT::i32);
2449 Ops.push_back(NumArgs);
2450
2451 // Calling convention.
2452 Ops.push_back(*It++);
2453
2454 // Push the args for the call.
2455 for (uint64_t I = NumArgs->getAsZExtVal(); I != 0; I--)
2456 Ops.push_back(*It++);
2457
2458 // Now push the live variables.
2459 for (; It != N->op_end(); It++)
2460 pushStackMapLiveVariable(Ops, *It, DL);
2461
2462 // Finally, the regmask, chain and (if present) glue are moved to the end.
2463 Ops.push_back(RegMask);
2464 Ops.push_back(Chain);
2465 if (Glue.has_value())
2466 Ops.push_back(*Glue);
2467
2468 SDVTList NodeTys = N->getVTList();
2469 CurDAG->SelectNodeTo(N, TargetOpcode::PATCHPOINT, NodeTys, Ops);
2470}
2471
2472/// GetVBR - decode a vbr encoding whose top bit is set.
2474GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {
2475 assert(Val >= 128 && "Not a VBR");
2476 Val &= 127; // Remove first vbr bit.
2477
2478 unsigned Shift = 7;
2479 uint64_t NextBits;
2480 do {
2481 NextBits = MatcherTable[Idx++];
2482 Val |= (NextBits&127) << Shift;
2483 Shift += 7;
2484 } while (NextBits & 128);
2485
2486 return Val;
2487}
2488
2489void SelectionDAGISel::Select_JUMP_TABLE_DEBUG_INFO(SDNode *N) {
2490 SDLoc dl(N);
2491 CurDAG->SelectNodeTo(N, TargetOpcode::JUMP_TABLE_DEBUG_INFO, MVT::Glue,
2492 CurDAG->getTargetConstant(N->getConstantOperandVal(1),
2493 dl, MVT::i64, true));
2494}
2495
2496/// When a match is complete, this method updates uses of interior chain results
2497/// to use the new results.
2498void SelectionDAGISel::UpdateChains(
2499 SDNode *NodeToMatch, SDValue InputChain,
2500 SmallVectorImpl<SDNode *> &ChainNodesMatched, bool isMorphNodeTo) {
2501 SmallVector<SDNode*, 4> NowDeadNodes;
2502
2503 // Now that all the normal results are replaced, we replace the chain and
2504 // glue results if present.
2505 if (!ChainNodesMatched.empty()) {
2506 assert(InputChain.getNode() &&
2507 "Matched input chains but didn't produce a chain");
2508 // Loop over all of the nodes we matched that produced a chain result.
2509 // Replace all the chain results with the final chain we ended up with.
2510 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2511 SDNode *ChainNode = ChainNodesMatched[i];
2512 // If ChainNode is null, it's because we replaced it on a previous
2513 // iteration and we cleared it out of the map. Just skip it.
2514 if (!ChainNode)
2515 continue;
2516
2517 assert(ChainNode->getOpcode() != ISD::DELETED_NODE &&
2518 "Deleted node left in chain");
2519
2520 // Don't replace the results of the root node if we're doing a
2521 // MorphNodeTo.
2522 if (ChainNode == NodeToMatch && isMorphNodeTo)
2523 continue;
2524
2525 SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);
2526 if (ChainVal.getValueType() == MVT::Glue)
2527 ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
2528 assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
2530 *CurDAG, [&](SDNode *N, SDNode *E) {
2531 std::replace(ChainNodesMatched.begin(), ChainNodesMatched.end(), N,
2532 static_cast<SDNode *>(nullptr));
2533 });
2534 if (ChainNode->getOpcode() != ISD::TokenFactor)
2535 ReplaceUses(ChainVal, InputChain);
2536
2537 // If the node became dead and we haven't already seen it, delete it.
2538 if (ChainNode != NodeToMatch && ChainNode->use_empty() &&
2539 !llvm::is_contained(NowDeadNodes, ChainNode))
2540 NowDeadNodes.push_back(ChainNode);
2541 }
2542 }
2543
2544 if (!NowDeadNodes.empty())
2545 CurDAG->RemoveDeadNodes(NowDeadNodes);
2546
2547 LLVM_DEBUG(dbgs() << "ISEL: Match complete!\n");
2548}
2549
2550/// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
2551/// operation for when the pattern matched at least one node with a chains. The
2552/// input vector contains a list of all of the chained nodes that we match. We
2553/// must determine if this is a valid thing to cover (i.e. matching it won't
2554/// induce cycles in the DAG) and if so, creating a TokenFactor node. that will
2555/// be used as the input node chain for the generated nodes.
2556static SDValue
2558 SelectionDAG *CurDAG) {
2559
2562 SmallVector<SDValue, 3> InputChains;
2563 unsigned int Max = 8192;
2564
2565 // Quick exit on trivial merge.
2566 if (ChainNodesMatched.size() == 1)
2567 return ChainNodesMatched[0]->getOperand(0);
2568
2569 // Add chains that aren't already added (internal). Peek through
2570 // token factors.
2571 std::function<void(const SDValue)> AddChains = [&](const SDValue V) {
2572 if (V.getValueType() != MVT::Other)
2573 return;
2574 if (V->getOpcode() == ISD::EntryToken)
2575 return;
2576 if (!Visited.insert(V.getNode()).second)
2577 return;
2578 if (V->getOpcode() == ISD::TokenFactor) {
2579 for (const SDValue &Op : V->op_values())
2580 AddChains(Op);
2581 } else
2582 InputChains.push_back(V);
2583 };
2584
2585 for (auto *N : ChainNodesMatched) {
2586 Worklist.push_back(N);
2587 Visited.insert(N);
2588 }
2589
2590 while (!Worklist.empty())
2591 AddChains(Worklist.pop_back_val()->getOperand(0));
2592
2593 // Skip the search if there are no chain dependencies.
2594 if (InputChains.size() == 0)
2595 return CurDAG->getEntryNode();
2596
2597 // If one of these chains is a successor of input, we must have a
2598 // node that is both the predecessor and successor of the
2599 // to-be-merged nodes. Fail.
2600 Visited.clear();
2601 for (SDValue V : InputChains)
2602 Worklist.push_back(V.getNode());
2603
2604 for (auto *N : ChainNodesMatched)
2605 if (SDNode::hasPredecessorHelper(N, Visited, Worklist, Max, true))
2606 return SDValue();
2607
2608 // Return merged chain.
2609 if (InputChains.size() == 1)
2610 return InputChains[0];
2611 return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]),
2612 MVT::Other, InputChains);
2613}
2614
2615/// MorphNode - Handle morphing a node in place for the selector.
2616SDNode *SelectionDAGISel::
2617MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
2618 ArrayRef<SDValue> Ops, unsigned EmitNodeInfo) {
2619 // It is possible we're using MorphNodeTo to replace a node with no
2620 // normal results with one that has a normal result (or we could be
2621 // adding a chain) and the input could have glue and chains as well.
2622 // In this case we need to shift the operands down.
2623 // FIXME: This is a horrible hack and broken in obscure cases, no worse
2624 // than the old isel though.
2625 int OldGlueResultNo = -1, OldChainResultNo = -1;
2626
2627 unsigned NTMNumResults = Node->getNumValues();
2628 if (Node->getValueType(NTMNumResults-1) == MVT::Glue) {
2629 OldGlueResultNo = NTMNumResults-1;
2630 if (NTMNumResults != 1 &&
2631 Node->getValueType(NTMNumResults-2) == MVT::Other)
2632 OldChainResultNo = NTMNumResults-2;
2633 } else if (Node->getValueType(NTMNumResults-1) == MVT::Other)
2634 OldChainResultNo = NTMNumResults-1;
2635
2636 // Call the underlying SelectionDAG routine to do the transmogrification. Note
2637 // that this deletes operands of the old node that become dead.
2638 SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops);
2639
2640 // MorphNodeTo can operate in two ways: if an existing node with the
2641 // specified operands exists, it can just return it. Otherwise, it
2642 // updates the node in place to have the requested operands.
2643 if (Res == Node) {
2644 // If we updated the node in place, reset the node ID. To the isel,
2645 // this should be just like a newly allocated machine node.
2646 Res->setNodeId(-1);
2647 }
2648
2649 unsigned ResNumResults = Res->getNumValues();
2650 // Move the glue if needed.
2651 if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 &&
2652 static_cast<unsigned>(OldGlueResultNo) != ResNumResults - 1)
2653 ReplaceUses(SDValue(Node, OldGlueResultNo),
2654 SDValue(Res, ResNumResults - 1));
2655
2656 if ((EmitNodeInfo & OPFL_GlueOutput) != 0)
2657 --ResNumResults;
2658
2659 // Move the chain reference if needed.
2660 if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
2661 static_cast<unsigned>(OldChainResultNo) != ResNumResults - 1)
2662 ReplaceUses(SDValue(Node, OldChainResultNo),
2663 SDValue(Res, ResNumResults - 1));
2664
2665 // Otherwise, no replacement happened because the node already exists. Replace
2666 // Uses of the old node with the new one.
2667 if (Res != Node) {
2668 ReplaceNode(Node, Res);
2669 } else {
2671 }
2672
2673 return Res;
2674}
2675
2676/// CheckSame - Implements OP_CheckSame.
2678CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2679 const SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes) {
2680 // Accept if it is exactly the same as a previously recorded node.
2681 unsigned RecNo = MatcherTable[MatcherIndex++];
2682 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2683 return N == RecordedNodes[RecNo].first;
2684}
2685
2686/// CheckChildSame - Implements OP_CheckChildXSame.
2688 const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2689 const SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes,
2690 unsigned ChildNo) {
2691 if (ChildNo >= N.getNumOperands())
2692 return false; // Match fails if out of range child #.
2693 return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo),
2694 RecordedNodes);
2695}
2696
2697/// CheckPatternPredicate - Implements OP_CheckPatternPredicate.
2699CheckPatternPredicate(unsigned Opcode, const unsigned char *MatcherTable,
2700 unsigned &MatcherIndex, const SelectionDAGISel &SDISel) {
2701 bool TwoBytePredNo =
2703 unsigned PredNo =
2704 TwoBytePredNo || Opcode == SelectionDAGISel::OPC_CheckPatternPredicate
2705 ? MatcherTable[MatcherIndex++]
2707 if (TwoBytePredNo)
2708 PredNo |= MatcherTable[MatcherIndex++] << 8;
2709 return SDISel.CheckPatternPredicate(PredNo);
2710}
2711
2712/// CheckNodePredicate - Implements OP_CheckNodePredicate.
2714CheckNodePredicate(unsigned Opcode, const unsigned char *MatcherTable,
2715 unsigned &MatcherIndex, const SelectionDAGISel &SDISel,
2716 SDNode *N) {
2717 unsigned PredNo = Opcode == SelectionDAGISel::OPC_CheckPredicate
2718 ? MatcherTable[MatcherIndex++]
2720 return SDISel.CheckNodePredicate(N, PredNo);
2721}
2722
2724CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2725 SDNode *N) {
2726 uint16_t Opc = MatcherTable[MatcherIndex++];
2727 Opc |= static_cast<uint16_t>(MatcherTable[MatcherIndex++]) << 8;
2728 return N->getOpcode() == Opc;
2729}
2730
2732 SDValue N,
2733 const TargetLowering *TLI,
2734 const DataLayout &DL) {
2735 if (N.getValueType() == VT)
2736 return true;
2737
2738 // Handle the case when VT is iPTR.
2739 return VT == MVT::iPTR && N.getValueType() == TLI->getPointerTy(DL);
2740}
2741
2744 const DataLayout &DL, unsigned ChildNo) {
2745 if (ChildNo >= N.getNumOperands())
2746 return false; // Match fails if out of range child #.
2747 return ::CheckType(VT, N.getOperand(ChildNo), TLI, DL);
2748}
2749
2751CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2752 SDValue N) {
2753 return cast<CondCodeSDNode>(N)->get() ==
2754 static_cast<ISD::CondCode>(MatcherTable[MatcherIndex++]);
2755}
2756
2758CheckChild2CondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2759 SDValue N) {
2760 if (2 >= N.getNumOperands())
2761 return false;
2762 return ::CheckCondCode(MatcherTable, MatcherIndex, N.getOperand(2));
2763}
2764
2766CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2767 SDValue N, const TargetLowering *TLI, const DataLayout &DL) {
2769 static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
2770 if (cast<VTSDNode>(N)->getVT() == VT)
2771 return true;
2772
2773 // Handle the case when VT is iPTR.
2774 return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI->getPointerTy(DL);
2775}
2776
2777// Bit 0 stores the sign of the immediate. The upper bits contain the magnitude
2778// shifted left by 1.
2780 if ((V & 1) == 0)
2781 return V >> 1;
2782 if (V != 1)
2783 return -(V >> 1);
2784 // There is no such thing as -0 with integers. "-0" really means MININT.
2785 return 1ULL << 63;
2786}
2787
2789CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2790 SDValue N) {
2791 int64_t Val = MatcherTable[MatcherIndex++];
2792 if (Val & 128)
2793 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2794
2795 Val = decodeSignRotatedValue(Val);
2796
2797 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N);
2798 return C && C->getAPIntValue().trySExtValue() == Val;
2799}
2800
2802CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2803 SDValue N, unsigned ChildNo) {
2804 if (ChildNo >= N.getNumOperands())
2805 return false; // Match fails if out of range child #.
2806 return ::CheckInteger(MatcherTable, MatcherIndex, N.getOperand(ChildNo));
2807}
2808
2810CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2811 SDValue N, const SelectionDAGISel &SDISel) {
2812 int64_t Val = MatcherTable[MatcherIndex++];
2813 if (Val & 128)
2814 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2815
2816 if (N->getOpcode() != ISD::AND) return false;
2817
2818 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
2819 return C && SDISel.CheckAndMask(N.getOperand(0), C, Val);
2820}
2821
2823CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2824 const SelectionDAGISel &SDISel) {
2825 int64_t Val = MatcherTable[MatcherIndex++];
2826 if (Val & 128)
2827 Val = GetVBR(Val, MatcherTable, MatcherIndex);
2828
2829 if (N->getOpcode() != ISD::OR) return false;
2830
2831 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
2832 return C && SDISel.CheckOrMask(N.getOperand(0), C, Val);
2833}
2834
2835/// IsPredicateKnownToFail - If we know how and can do so without pushing a
2836/// scope, evaluate the current node. If the current predicate is known to
2837/// fail, set Result=true and return anything. If the current predicate is
2838/// known to pass, set Result=false and return the MatcherIndex to continue
2839/// with. If the current predicate is unknown, set Result=false and return the
2840/// MatcherIndex to continue with.
2841static unsigned IsPredicateKnownToFail(const unsigned char *Table,
2842 unsigned Index, SDValue N,
2843 bool &Result,
2844 const SelectionDAGISel &SDISel,
2845 SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) {
2846 unsigned Opcode = Table[Index++];
2847 switch (Opcode) {
2848 default:
2849 Result = false;
2850 return Index-1; // Could not evaluate this predicate.
2852 Result = !::CheckSame(Table, Index, N, RecordedNodes);
2853 return Index;
2858 Result = !::CheckChildSame(Table, Index, N, RecordedNodes,
2860 return Index;
2871 Result = !::CheckPatternPredicate(Opcode, Table, Index, SDISel);
2872 return Index;
2882 Result = !::CheckNodePredicate(Opcode, Table, Index, SDISel, N.getNode());
2883 return Index;
2885 Result = !::CheckOpcode(Table, Index, N.getNode());
2886 return Index;
2891 switch (Opcode) {
2893 VT = MVT::i32;
2894 break;
2896 VT = MVT::i64;
2897 break;
2898 default:
2899 VT = static_cast<MVT::SimpleValueType>(Table[Index++]);
2900 break;
2901 }
2902 Result = !::CheckType(VT, N, SDISel.TLI, SDISel.CurDAG->getDataLayout());
2903 return Index;
2904 }
2906 unsigned Res = Table[Index++];
2907 Result = !::CheckType(static_cast<MVT::SimpleValueType>(Table[Index++]),
2908 N.getValue(Res), SDISel.TLI,
2909 SDISel.CurDAG->getDataLayout());
2910 return Index;
2911 }
2937 unsigned ChildNo;
2940 VT = MVT::i32;
2942 } else if (Opcode >= SelectionDAGISel::OPC_CheckChild0TypeI64 &&
2944 VT = MVT::i64;
2946 } else {
2947 VT = static_cast<MVT::SimpleValueType>(Table[Index++]);
2948 ChildNo = Opcode - SelectionDAGISel::OPC_CheckChild0Type;
2949 }
2950 Result = !::CheckChildType(VT, N, SDISel.TLI,
2951 SDISel.CurDAG->getDataLayout(), ChildNo);
2952 return Index;
2953 }
2955 Result = !::CheckCondCode(Table, Index, N);
2956 return Index;
2958 Result = !::CheckChild2CondCode(Table, Index, N);
2959 return Index;
2961 Result = !::CheckValueType(Table, Index, N, SDISel.TLI,
2962 SDISel.CurDAG->getDataLayout());
2963 return Index;
2965 Result = !::CheckInteger(Table, Index, N);
2966 return Index;
2972 Result = !::CheckChildInteger(Table, Index, N,
2974 return Index;
2976 Result = !::CheckAndImm(Table, Index, N, SDISel);
2977 return Index;
2979 Result = !::CheckOrImm(Table, Index, N, SDISel);
2980 return Index;
2981 }
2982}
2983
2984namespace {
2985
2986struct MatchScope {
2987 /// FailIndex - If this match fails, this is the index to continue with.
2988 unsigned FailIndex;
2989
2990 /// NodeStack - The node stack when the scope was formed.
2991 SmallVector<SDValue, 4> NodeStack;
2992
2993 /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
2994 unsigned NumRecordedNodes;
2995
2996 /// NumMatchedMemRefs - The number of matched memref entries.
2997 unsigned NumMatchedMemRefs;
2998
2999 /// InputChain/InputGlue - The current chain/glue
3000 SDValue InputChain, InputGlue;
3001
3002 /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.
3003 bool HasChainNodesMatched;
3004};
3005
3006/// \A DAG update listener to keep the matching state
3007/// (i.e. RecordedNodes and MatchScope) uptodate if the target is allowed to
3008/// change the DAG while matching. X86 addressing mode matcher is an example
3009/// for this.
3010class MatchStateUpdater : public SelectionDAG::DAGUpdateListener
3011{
3012 SDNode **NodeToMatch;
3014 SmallVectorImpl<MatchScope> &MatchScopes;
3015
3016public:
3017 MatchStateUpdater(SelectionDAG &DAG, SDNode **NodeToMatch,
3018 SmallVectorImpl<std::pair<SDValue, SDNode *>> &RN,
3020 : SelectionDAG::DAGUpdateListener(DAG), NodeToMatch(NodeToMatch),
3021 RecordedNodes(RN), MatchScopes(MS) {}
3022
3023 void NodeDeleted(SDNode *N, SDNode *E) override {
3024 // Some early-returns here to avoid the search if we deleted the node or
3025 // if the update comes from MorphNodeTo (MorphNodeTo is the last thing we
3026 // do, so it's unnecessary to update matching state at that point).
3027 // Neither of these can occur currently because we only install this
3028 // update listener during matching a complex patterns.
3029 if (!E || E->isMachineOpcode())
3030 return;
3031 // Check if NodeToMatch was updated.
3032 if (N == *NodeToMatch)
3033 *NodeToMatch = E;
3034 // Performing linear search here does not matter because we almost never
3035 // run this code. You'd have to have a CSE during complex pattern
3036 // matching.
3037 for (auto &I : RecordedNodes)
3038 if (I.first.getNode() == N)
3039 I.first.setNode(E);
3040
3041 for (auto &I : MatchScopes)
3042 for (auto &J : I.NodeStack)
3043 if (J.getNode() == N)
3044 J.setNode(E);
3045 }
3046};
3047
3048} // end anonymous namespace
3049
3051 const unsigned char *MatcherTable,
3052 unsigned TableSize) {
3053 // FIXME: Should these even be selected? Handle these cases in the caller?
3054 switch (NodeToMatch->getOpcode()) {
3055 default:
3056 break;
3057 case ISD::EntryToken: // These nodes remain the same.
3058 case ISD::BasicBlock:
3059 case ISD::Register:
3060 case ISD::RegisterMask:
3061 case ISD::HANDLENODE:
3062 case ISD::MDNODE_SDNODE:
3068 case ISD::MCSymbol:
3073 case ISD::TokenFactor:
3074 case ISD::CopyFromReg:
3075 case ISD::CopyToReg:
3076 case ISD::EH_LABEL:
3079 case ISD::LIFETIME_END:
3080 case ISD::PSEUDO_PROBE:
3081 NodeToMatch->setNodeId(-1); // Mark selected.
3082 return;
3083 case ISD::AssertSext:
3084 case ISD::AssertZext:
3085 case ISD::AssertAlign:
3086 ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));
3087 CurDAG->RemoveDeadNode(NodeToMatch);
3088 return;
3089 case ISD::INLINEASM:
3090 case ISD::INLINEASM_BR:
3091 Select_INLINEASM(NodeToMatch);
3092 return;
3093 case ISD::READ_REGISTER:
3094 Select_READ_REGISTER(NodeToMatch);
3095 return;
3097 Select_WRITE_REGISTER(NodeToMatch);
3098 return;
3099 case ISD::UNDEF:
3100 Select_UNDEF(NodeToMatch);
3101 return;
3102 case ISD::FREEZE:
3103 Select_FREEZE(NodeToMatch);
3104 return;
3105 case ISD::ARITH_FENCE:
3106 Select_ARITH_FENCE(NodeToMatch);
3107 return;
3108 case ISD::MEMBARRIER:
3109 Select_MEMBARRIER(NodeToMatch);
3110 return;
3111 case ISD::STACKMAP:
3112 Select_STACKMAP(NodeToMatch);
3113 return;
3114 case ISD::PATCHPOINT:
3115 Select_PATCHPOINT(NodeToMatch);
3116 return;
3118 Select_JUMP_TABLE_DEBUG_INFO(NodeToMatch);
3119 return;
3120 }
3121
3122 assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
3123
3124 // Set up the node stack with NodeToMatch as the only node on the stack.
3125 SmallVector<SDValue, 8> NodeStack;
3126 SDValue N = SDValue(NodeToMatch, 0);
3127 NodeStack.push_back(N);
3128
3129 // MatchScopes - Scopes used when matching, if a match failure happens, this
3130 // indicates where to continue checking.
3131 SmallVector<MatchScope, 8> MatchScopes;
3132
3133 // RecordedNodes - This is the set of nodes that have been recorded by the
3134 // state machine. The second value is the parent of the node, or null if the
3135 // root is recorded.
3137
3138 // MatchedMemRefs - This is the set of MemRef's we've seen in the input
3139 // pattern.
3141
3142 // These are the current input chain and glue for use when generating nodes.
3143 // Various Emit operations change these. For example, emitting a copytoreg
3144 // uses and updates these.
3145 SDValue InputChain, InputGlue;
3146
3147 // ChainNodesMatched - If a pattern matches nodes that have input/output
3148 // chains, the OPC_EmitMergeInputChains operation is emitted which indicates
3149 // which ones they are. The result is captured into this list so that we can
3150 // update the chain results when the pattern is complete.
3151 SmallVector<SDNode*, 3> ChainNodesMatched;
3152
3153 LLVM_DEBUG(dbgs() << "ISEL: Starting pattern match\n");
3154
3155 // Determine where to start the interpreter. Normally we start at opcode #0,
3156 // but if the state machine starts with an OPC_SwitchOpcode, then we
3157 // accelerate the first lookup (which is guaranteed to be hot) with the
3158 // OpcodeOffset table.
3159 unsigned MatcherIndex = 0;
3160
3161 if (!OpcodeOffset.empty()) {
3162 // Already computed the OpcodeOffset table, just index into it.
3163 if (N.getOpcode() < OpcodeOffset.size())
3164 MatcherIndex = OpcodeOffset[N.getOpcode()];
3165 LLVM_DEBUG(dbgs() << " Initial Opcode index to " << MatcherIndex << "\n");
3166
3167 } else if (MatcherTable[0] == OPC_SwitchOpcode) {
3168 // Otherwise, the table isn't computed, but the state machine does start
3169 // with an OPC_SwitchOpcode instruction. Populate the table now, since this
3170 // is the first time we're selecting an instruction.
3171 unsigned Idx = 1;
3172 while (true) {
3173 // Get the size of this case.
3174 unsigned CaseSize = MatcherTable[Idx++];
3175 if (CaseSize & 128)
3176 CaseSize = GetVBR(CaseSize, MatcherTable, Idx);
3177 if (CaseSize == 0) break;
3178
3179 // Get the opcode, add the index to the table.
3180 uint16_t Opc = MatcherTable[Idx++];
3181 Opc |= static_cast<uint16_t>(MatcherTable[Idx++]) << 8;
3182 if (Opc >= OpcodeOffset.size())
3183 OpcodeOffset.resize((Opc+1)*2);
3184 OpcodeOffset[Opc] = Idx;
3185 Idx += CaseSize;
3186 }
3187
3188 // Okay, do the lookup for the first opcode.
3189 if (N.getOpcode() < OpcodeOffset.size())
3190 MatcherIndex = OpcodeOffset[N.getOpcode()];
3191 }
3192
3193 while (true) {
3194 assert(MatcherIndex < TableSize && "Invalid index");
3195#ifndef NDEBUG
3196 unsigned CurrentOpcodeIndex = MatcherIndex;
3197#endif
3198 BuiltinOpcodes Opcode =
3199 static_cast<BuiltinOpcodes>(MatcherTable[MatcherIndex++]);
3200 switch (Opcode) {
3201 case OPC_Scope: {
3202 // Okay, the semantics of this operation are that we should push a scope
3203 // then evaluate the first child. However, pushing a scope only to have
3204 // the first check fail (which then pops it) is inefficient. If we can
3205 // determine immediately that the first check (or first several) will
3206 // immediately fail, don't even bother pushing a scope for them.
3207 unsigned FailIndex;
3208
3209 while (true) {
3210 unsigned NumToSkip = MatcherTable[MatcherIndex++];
3211 if (NumToSkip & 128)
3212 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
3213 // Found the end of the scope with no match.
3214 if (NumToSkip == 0) {
3215 FailIndex = 0;
3216 break;
3217 }
3218
3219 FailIndex = MatcherIndex+NumToSkip;
3220
3221 unsigned MatcherIndexOfPredicate = MatcherIndex;
3222 (void)MatcherIndexOfPredicate; // silence warning.
3223
3224 // If we can't evaluate this predicate without pushing a scope (e.g. if
3225 // it is a 'MoveParent') or if the predicate succeeds on this node, we
3226 // push the scope and evaluate the full predicate chain.
3227 bool Result;
3228 MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,
3229 Result, *this, RecordedNodes);
3230 if (!Result)
3231 break;
3232
3233 LLVM_DEBUG(
3234 dbgs() << " Skipped scope entry (due to false predicate) at "
3235 << "index " << MatcherIndexOfPredicate << ", continuing at "
3236 << FailIndex << "\n");
3237 ++NumDAGIselRetries;
3238
3239 // Otherwise, we know that this case of the Scope is guaranteed to fail,
3240 // move to the next case.
3241 MatcherIndex = FailIndex;
3242 }
3243
3244 // If the whole scope failed to match, bail.
3245 if (FailIndex == 0) break;
3246
3247 // Push a MatchScope which indicates where to go if the first child fails
3248 // to match.
3249 MatchScope NewEntry;
3250 NewEntry.FailIndex = FailIndex;
3251 NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
3252 NewEntry.NumRecordedNodes = RecordedNodes.size();
3253 NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
3254 NewEntry.InputChain = InputChain;
3255 NewEntry.InputGlue = InputGlue;
3256 NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
3257 MatchScopes.push_back(NewEntry);
3258 continue;
3259 }
3260 case OPC_RecordNode: {
3261 // Remember this node, it may end up being an operand in the pattern.
3262 SDNode *Parent = nullptr;
3263 if (NodeStack.size() > 1)
3264 Parent = NodeStack[NodeStack.size()-2].getNode();
3265 RecordedNodes.push_back(std::make_pair(N, Parent));
3266 continue;
3267 }
3268
3273 unsigned ChildNo = Opcode-OPC_RecordChild0;
3274 if (ChildNo >= N.getNumOperands())
3275 break; // Match fails if out of range child #.
3276
3277 RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo),
3278 N.getNode()));
3279 continue;
3280 }
3281 case OPC_RecordMemRef:
3282 if (auto *MN = dyn_cast<MemSDNode>(N))
3283 MatchedMemRefs.push_back(MN->getMemOperand());
3284 else {
3285 LLVM_DEBUG(dbgs() << "Expected MemSDNode "; N->dump(CurDAG);
3286 dbgs() << '\n');
3287 }
3288
3289 continue;
3290
3292 // If the current node has an input glue, capture it in InputGlue.
3293 if (N->getNumOperands() != 0 &&
3294 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue)
3295 InputGlue = N->getOperand(N->getNumOperands()-1);
3296 continue;
3297
3298 case OPC_MoveChild: {
3299 unsigned ChildNo = MatcherTable[MatcherIndex++];
3300 if (ChildNo >= N.getNumOperands())
3301 break; // Match fails if out of range child #.
3302 N = N.getOperand(ChildNo);
3303 NodeStack.push_back(N);
3304 continue;
3305 }
3306
3307 case OPC_MoveChild0: case OPC_MoveChild1:
3308 case OPC_MoveChild2: case OPC_MoveChild3:
3309 case OPC_MoveChild4: case OPC_MoveChild5:
3310 case OPC_MoveChild6: case OPC_MoveChild7: {
3311 unsigned ChildNo = Opcode-OPC_MoveChild0;
3312 if (ChildNo >= N.getNumOperands())
3313 break; // Match fails if out of range child #.
3314 N = N.getOperand(ChildNo);
3315 NodeStack.push_back(N);
3316 continue;
3317 }
3318
3319 case OPC_MoveSibling:
3320 case OPC_MoveSibling0:
3321 case OPC_MoveSibling1:
3322 case OPC_MoveSibling2:
3323 case OPC_MoveSibling3:
3324 case OPC_MoveSibling4:
3325 case OPC_MoveSibling5:
3326 case OPC_MoveSibling6:
3327 case OPC_MoveSibling7: {
3328 // Pop the current node off the NodeStack.
3329 NodeStack.pop_back();
3330 assert(!NodeStack.empty() && "Node stack imbalance!");
3331 N = NodeStack.back();
3332
3333 unsigned SiblingNo = Opcode == OPC_MoveSibling
3334 ? MatcherTable[MatcherIndex++]
3335 : Opcode - OPC_MoveSibling0;
3336 if (SiblingNo >= N.getNumOperands())
3337 break; // Match fails if out of range sibling #.
3338 N = N.getOperand(SiblingNo);
3339 NodeStack.push_back(N);
3340 continue;
3341 }
3342 case OPC_MoveParent:
3343 // Pop the current node off the NodeStack.
3344 NodeStack.pop_back();
3345 assert(!NodeStack.empty() && "Node stack imbalance!");
3346 N = NodeStack.back();
3347 continue;
3348
3349 case OPC_CheckSame:
3350 if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break;
3351 continue;
3352
3355 if (!::CheckChildSame(MatcherTable, MatcherIndex, N, RecordedNodes,
3356 Opcode-OPC_CheckChild0Same))
3357 break;
3358 continue;
3359
3370 if (!::CheckPatternPredicate(Opcode, MatcherTable, MatcherIndex, *this))
3371 break;
3372 continue;
3381 case OPC_CheckPredicate:
3382 if (!::CheckNodePredicate(Opcode, MatcherTable, MatcherIndex, *this,
3383 N.getNode()))
3384 break;
3385 continue;
3387 unsigned OpNum = MatcherTable[MatcherIndex++];
3389
3390 for (unsigned i = 0; i < OpNum; ++i)
3391 Operands.push_back(RecordedNodes[MatcherTable[MatcherIndex++]].first);
3392
3393 unsigned PredNo = MatcherTable[MatcherIndex++];
3394 if (!CheckNodePredicateWithOperands(N.getNode(), PredNo, Operands))
3395 break;
3396 continue;
3397 }
3406 case OPC_CheckComplexPat7: {
3407 unsigned CPNum = Opcode == OPC_CheckComplexPat
3408 ? MatcherTable[MatcherIndex++]
3409 : Opcode - OPC_CheckComplexPat0;
3410 unsigned RecNo = MatcherTable[MatcherIndex++];
3411 assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat");
3412
3413 // If target can modify DAG during matching, keep the matching state
3414 // consistent.
3415 std::unique_ptr<MatchStateUpdater> MSU;
3417 MSU.reset(new MatchStateUpdater(*CurDAG, &NodeToMatch, RecordedNodes,
3418 MatchScopes));
3419
3420 if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second,
3421 RecordedNodes[RecNo].first, CPNum,
3422 RecordedNodes))
3423 break;
3424 continue;
3425 }
3426 case OPC_CheckOpcode:
3427 if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break;
3428 continue;
3429
3430 case OPC_CheckType:
3431 case OPC_CheckTypeI32:
3432 case OPC_CheckTypeI64:
3434 switch (Opcode) {
3435 case OPC_CheckTypeI32:
3436 VT = MVT::i32;
3437 break;
3438 case OPC_CheckTypeI64:
3439 VT = MVT::i64;
3440 break;
3441 default:
3442 VT = static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
3443 break;
3444 }
3445 if (!::CheckType(VT, N, TLI, CurDAG->getDataLayout()))
3446 break;
3447 continue;
3448
3449 case OPC_CheckTypeRes: {
3450 unsigned Res = MatcherTable[MatcherIndex++];
3451 if (!::CheckType(
3452 static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]),
3453 N.getValue(Res), TLI, CurDAG->getDataLayout()))
3454 break;
3455 continue;
3456 }
3457
3458 case OPC_SwitchOpcode: {
3459 unsigned CurNodeOpcode = N.getOpcode();
3460 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3461 unsigned CaseSize;
3462 while (true) {
3463 // Get the size of this case.
3464 CaseSize = MatcherTable[MatcherIndex++];
3465 if (CaseSize & 128)
3466 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3467 if (CaseSize == 0) break;
3468
3469 uint16_t Opc = MatcherTable[MatcherIndex++];
3470 Opc |= static_cast<uint16_t>(MatcherTable[MatcherIndex++]) << 8;
3471
3472 // If the opcode matches, then we will execute this case.
3473 if (CurNodeOpcode == Opc)
3474 break;
3475
3476 // Otherwise, skip over this case.
3477 MatcherIndex += CaseSize;
3478 }
3479
3480 // If no cases matched, bail out.
3481 if (CaseSize == 0) break;
3482
3483 // Otherwise, execute the case we found.
3484 LLVM_DEBUG(dbgs() << " OpcodeSwitch from " << SwitchStart << " to "
3485 << MatcherIndex << "\n");
3486 continue;
3487 }
3488
3489 case OPC_SwitchType: {
3490 MVT CurNodeVT = N.getSimpleValueType();
3491 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3492 unsigned CaseSize;
3493 while (true) {
3494 // Get the size of this case.
3495 CaseSize = MatcherTable[MatcherIndex++];
3496 if (CaseSize & 128)
3497 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3498 if (CaseSize == 0) break;
3499
3500 MVT CaseVT =
3501 static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
3502 if (CaseVT == MVT::iPTR)
3503 CaseVT = TLI->getPointerTy(CurDAG->getDataLayout());
3504
3505 // If the VT matches, then we will execute this case.
3506 if (CurNodeVT == CaseVT)
3507 break;
3508
3509 // Otherwise, skip over this case.
3510 MatcherIndex += CaseSize;
3511 }
3512
3513 // If no cases matched, bail out.
3514 if (CaseSize == 0) break;
3515
3516 // Otherwise, execute the case we found.
3517 LLVM_DEBUG(dbgs() << " TypeSwitch[" << CurNodeVT
3518 << "] from " << SwitchStart << " to " << MatcherIndex
3519 << '\n');
3520 continue;
3521 }
3547 unsigned ChildNo;
3550 VT = MVT::i32;
3552 } else if (Opcode >= SelectionDAGISel::OPC_CheckChild0TypeI64 &&
3554 VT = MVT::i64;
3556 } else {
3557 VT = static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
3558 ChildNo = Opcode - SelectionDAGISel::OPC_CheckChild0Type;
3559 }
3560 if (!::CheckChildType(VT, N, TLI, CurDAG->getDataLayout(), ChildNo))
3561 break;
3562 continue;
3563 }
3564 case OPC_CheckCondCode:
3565 if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break;
3566 continue;
3568 if (!::CheckChild2CondCode(MatcherTable, MatcherIndex, N)) break;
3569 continue;
3570 case OPC_CheckValueType:
3571 if (!::CheckValueType(MatcherTable, MatcherIndex, N, TLI,
3573 break;
3574 continue;
3575 case OPC_CheckInteger:
3576 if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break;
3577 continue;
3581 if (!::CheckChildInteger(MatcherTable, MatcherIndex, N,
3582 Opcode-OPC_CheckChild0Integer)) break;
3583 continue;
3584 case OPC_CheckAndImm:
3585 if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break;
3586 continue;
3587 case OPC_CheckOrImm:
3588 if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break;
3589 continue;
3591 if (!ISD::isConstantSplatVectorAllOnes(N.getNode()))
3592 break;
3593 continue;
3595 if (!ISD::isConstantSplatVectorAllZeros(N.getNode()))
3596 break;
3597 continue;
3598
3600 assert(NodeStack.size() != 1 && "No parent node");
3601 // Verify that all intermediate nodes between the root and this one have
3602 // a single use (ignoring chains, which are handled in UpdateChains).
3603 bool HasMultipleUses = false;
3604 for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i) {
3605 unsigned NNonChainUses = 0;
3606 SDNode *NS = NodeStack[i].getNode();
3607 for (auto UI = NS->use_begin(), UE = NS->use_end(); UI != UE; ++UI)
3608 if (UI.getUse().getValueType() != MVT::Other)
3609 if (++NNonChainUses > 1) {
3610 HasMultipleUses = true;
3611 break;
3612 }
3613 if (HasMultipleUses) break;
3614 }
3615 if (HasMultipleUses) break;
3616
3617 // Check to see that the target thinks this is profitable to fold and that
3618 // we can fold it without inducing cycles in the graph.
3619 if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3620 NodeToMatch) ||
3621 !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3622 NodeToMatch, OptLevel,
3623 true/*We validate our own chains*/))
3624 break;
3625
3626 continue;
3627 }
3628 case OPC_EmitInteger:
3629 case OPC_EmitInteger8:
3630 case OPC_EmitInteger16:
3631 case OPC_EmitInteger32:
3632 case OPC_EmitInteger64:
3636 switch (Opcode) {
3637 case OPC_EmitInteger8:
3638 VT = MVT::i8;
3639 break;
3640 case OPC_EmitInteger16:
3641 VT = MVT::i16;
3642 break;
3643 case OPC_EmitInteger32:
3645 VT = MVT::i32;
3646 break;
3647 case OPC_EmitInteger64:
3648 VT = MVT::i64;
3649 break;
3650 default:
3651 VT = static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
3652 break;
3653 }
3654 int64_t Val = MatcherTable[MatcherIndex++];
3655 if (Val & 128)
3656 Val = GetVBR(Val, MatcherTable, MatcherIndex);
3657 if (Opcode >= OPC_EmitInteger && Opcode <= OPC_EmitInteger64)
3658 Val = decodeSignRotatedValue(Val);
3659 RecordedNodes.push_back(std::pair<SDValue, SDNode *>(
3660 CurDAG->getTargetConstant(Val, SDLoc(NodeToMatch), VT), nullptr));
3661 continue;
3662 }
3663 case OPC_EmitRegister:
3665 case OPC_EmitRegisterI64: {
3667 switch (Opcode) {
3669 VT = MVT::i32;
3670 break;
3672 VT = MVT::i64;
3673 break;
3674 default:
3675 VT = static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
3676 break;
3677 }
3678 unsigned RegNo = MatcherTable[MatcherIndex++];
3679 RecordedNodes.push_back(std::pair<SDValue, SDNode *>(
3680 CurDAG->getRegister(RegNo, VT), nullptr));
3681 continue;
3682 }
3683 case OPC_EmitRegister2: {
3684 // For targets w/ more than 256 register names, the register enum
3685 // values are stored in two bytes in the matcher table (just like
3686 // opcodes).
3688 static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
3689 unsigned RegNo = MatcherTable[MatcherIndex++];
3690 RegNo |= MatcherTable[MatcherIndex++] << 8;
3691 RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3692 CurDAG->getRegister(RegNo, VT), nullptr));
3693 continue;
3694 }
3695
3705 // Convert from IMM/FPIMM to target version.
3706 unsigned RecNo = Opcode == OPC_EmitConvertToTarget
3707 ? MatcherTable[MatcherIndex++]
3708 : Opcode - OPC_EmitConvertToTarget0;
3709 assert(RecNo < RecordedNodes.size() && "Invalid EmitConvertToTarget");
3710 SDValue Imm = RecordedNodes[RecNo].first;
3711
3712 if (Imm->getOpcode() == ISD::Constant) {
3713 const ConstantInt *Val=cast<ConstantSDNode>(Imm)->getConstantIntValue();
3714 Imm = CurDAG->getTargetConstant(*Val, SDLoc(NodeToMatch),
3715 Imm.getValueType());
3716 } else if (Imm->getOpcode() == ISD::ConstantFP) {
3717 const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
3718 Imm = CurDAG->getTargetConstantFP(*Val, SDLoc(NodeToMatch),
3719 Imm.getValueType());
3720 }
3721
3722 RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second));
3723 continue;
3724 }
3725
3726 case OPC_EmitMergeInputChains1_0: // OPC_EmitMergeInputChains, 1, 0
3727 case OPC_EmitMergeInputChains1_1: // OPC_EmitMergeInputChains, 1, 1
3728 case OPC_EmitMergeInputChains1_2: { // OPC_EmitMergeInputChains, 1, 2
3729 // These are space-optimized forms of OPC_EmitMergeInputChains.
3730 assert(!InputChain.getNode() &&
3731 "EmitMergeInputChains should be the first chain producing node");
3732 assert(ChainNodesMatched.empty() &&
3733 "Should only have one EmitMergeInputChains per match");
3734
3735 // Read all of the chained nodes.
3736 unsigned RecNo = Opcode - OPC_EmitMergeInputChains1_0;
3737 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3738 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3739
3740 // If the chained node is not the root, we can't fold it if it has
3741 // multiple uses.
3742 // FIXME: What if other value results of the node have uses not matched
3743 // by this pattern?
3744 if (ChainNodesMatched.back() != NodeToMatch &&
3745 !RecordedNodes[RecNo].first.hasOneUse()) {
3746 ChainNodesMatched.clear();
3747 break;
3748 }
3749
3750 // Merge the input chains if they are not intra-pattern references.
3751 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3752
3753 if (!InputChain.getNode())
3754 break; // Failed to merge.
3755 continue;
3756 }
3757
3759 assert(!InputChain.getNode() &&
3760 "EmitMergeInputChains should be the first chain producing node");
3761 // This node gets a list of nodes we matched in the input that have
3762 // chains. We want to token factor all of the input chains to these nodes
3763 // together. However, if any of the input chains is actually one of the
3764 // nodes matched in this pattern, then we have an intra-match reference.
3765 // Ignore these because the newly token factored chain should not refer to
3766 // the old nodes.
3767 unsigned NumChains = MatcherTable[MatcherIndex++];
3768 assert(NumChains != 0 && "Can't TF zero chains");
3769
3770 assert(ChainNodesMatched.empty() &&
3771 "Should only have one EmitMergeInputChains per match");
3772
3773 // Read all of the chained nodes.
3774 for (unsigned i = 0; i != NumChains; ++i) {
3775 unsigned RecNo = MatcherTable[MatcherIndex++];
3776 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3777 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3778
3779 // If the chained node is not the root, we can't fold it if it has
3780 // multiple uses.
3781 // FIXME: What if other value results of the node have uses not matched
3782 // by this pattern?
3783 if (ChainNodesMatched.back() != NodeToMatch &&
3784 !RecordedNodes[RecNo].first.hasOneUse()) {
3785 ChainNodesMatched.clear();
3786 break;
3787 }
3788 }
3789
3790 // If the inner loop broke out, the match fails.
3791 if (ChainNodesMatched.empty())
3792 break;
3793
3794 // Merge the input chains if they are not intra-pattern references.
3795 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3796
3797 if (!InputChain.getNode())
3798 break; // Failed to merge.
3799
3800 continue;
3801 }
3802
3803 case OPC_EmitCopyToReg:
3804 case OPC_EmitCopyToReg0:
3805 case OPC_EmitCopyToReg1:
3806 case OPC_EmitCopyToReg2:
3807 case OPC_EmitCopyToReg3:
3808 case OPC_EmitCopyToReg4:
3809 case OPC_EmitCopyToReg5:
3810 case OPC_EmitCopyToReg6:
3811 case OPC_EmitCopyToReg7:
3813 unsigned RecNo =
3814 Opcode >= OPC_EmitCopyToReg0 && Opcode <= OPC_EmitCopyToReg7
3815 ? Opcode - OPC_EmitCopyToReg0
3816 : MatcherTable[MatcherIndex++];
3817 assert(RecNo < RecordedNodes.size() && "Invalid EmitCopyToReg");
3818 unsigned DestPhysReg = MatcherTable[MatcherIndex++];
3819 if (Opcode == OPC_EmitCopyToRegTwoByte)
3820 DestPhysReg |= MatcherTable[MatcherIndex++] << 8;
3821
3822 if (!InputChain.getNode())
3823 InputChain = CurDAG->getEntryNode();
3824
3825 InputChain = CurDAG->getCopyToReg(InputChain, SDLoc(NodeToMatch),
3826 DestPhysReg, RecordedNodes[RecNo].first,
3827 InputGlue);
3828
3829 InputGlue = InputChain.getValue(1);
3830 continue;
3831 }
3832
3833 case OPC_EmitNodeXForm: {
3834 unsigned XFormNo = MatcherTable[MatcherIndex++];
3835 unsigned RecNo = MatcherTable[MatcherIndex++];
3836 assert(RecNo < RecordedNodes.size() && "Invalid EmitNodeXForm");
3837 SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo);
3838 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, nullptr));
3839 continue;
3840 }
3841 case OPC_Coverage: {
3842 // This is emitted right before MorphNode/EmitNode.
3843 // So it should be safe to assume that this node has been selected
3844 unsigned index = MatcherTable[MatcherIndex++];
3845 index |= (MatcherTable[MatcherIndex++] << 8);
3846 dbgs() << "COVERED: " << getPatternForIndex(index) << "\n";
3847 dbgs() << "INCLUDED: " << getIncludePathForIndex(index) << "\n";
3848 continue;
3849 }
3850
3851 case OPC_EmitNode:
3852 case OPC_EmitNode0:
3853 case OPC_EmitNode1:
3854 case OPC_EmitNode2:
3855 case OPC_EmitNode0None:
3856 case OPC_EmitNode1None:
3857 case OPC_EmitNode2None:
3858 case OPC_EmitNode0Chain:
3859 case OPC_EmitNode1Chain:
3860 case OPC_EmitNode2Chain:
3861 case OPC_MorphNodeTo:
3862 case OPC_MorphNodeTo0:
3863 case OPC_MorphNodeTo1:
3864 case OPC_MorphNodeTo2:
3877 uint16_t TargetOpc = MatcherTable[MatcherIndex++];
3878 TargetOpc |= static_cast<uint16_t>(MatcherTable[MatcherIndex++]) << 8;
3879 unsigned EmitNodeInfo;
3880 if (Opcode >= OPC_EmitNode0None && Opcode <= OPC_EmitNode2Chain) {
3881 if (Opcode >= OPC_EmitNode0Chain && Opcode <= OPC_EmitNode2Chain)
3882 EmitNodeInfo = OPFL_Chain;
3883 else
3884 EmitNodeInfo = OPFL_None;
3885 } else if (Opcode >= OPC_MorphNodeTo0None &&
3886 Opcode <= OPC_MorphNodeTo2GlueOutput) {
3887 if (Opcode >= OPC_MorphNodeTo0Chain && Opcode <= OPC_MorphNodeTo2Chain)
3888 EmitNodeInfo = OPFL_Chain;
3889 else if (Opcode >= OPC_MorphNodeTo0GlueInput &&
3890 Opcode <= OPC_MorphNodeTo2GlueInput)
3891 EmitNodeInfo = OPFL_GlueInput;
3892 else if (Opcode >= OPC_MorphNodeTo0GlueOutput &&
3894 EmitNodeInfo = OPFL_GlueOutput;
3895 else
3896 EmitNodeInfo = OPFL_None;
3897 } else
3898 EmitNodeInfo = MatcherTable[MatcherIndex++];
3899 // Get the result VT list.
3900 unsigned NumVTs;
3901 // If this is one of the compressed forms, get the number of VTs based
3902 // on the Opcode. Otherwise read the next byte from the table.
3903 if (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2)
3904 NumVTs = Opcode - OPC_MorphNodeTo0;
3905 else if (Opcode >= OPC_MorphNodeTo0None && Opcode <= OPC_MorphNodeTo2None)
3906 NumVTs = Opcode - OPC_MorphNodeTo0None;
3907 else if (Opcode >= OPC_MorphNodeTo0Chain &&
3908 Opcode <= OPC_MorphNodeTo2Chain)
3909 NumVTs = Opcode - OPC_MorphNodeTo0Chain;
3910 else if (Opcode >= OPC_MorphNodeTo0GlueInput &&
3911 Opcode <= OPC_MorphNodeTo2GlueInput)
3912 NumVTs = Opcode - OPC_MorphNodeTo0GlueInput;
3913 else if (Opcode >= OPC_MorphNodeTo0GlueOutput &&
3915 NumVTs = Opcode - OPC_MorphNodeTo0GlueOutput;
3916 else if (Opcode >= OPC_EmitNode0 && Opcode <= OPC_EmitNode2)
3917 NumVTs = Opcode - OPC_EmitNode0;
3918 else if (Opcode >= OPC_EmitNode0None && Opcode <= OPC_EmitNode2None)
3919 NumVTs = Opcode - OPC_EmitNode0None;
3920 else if (Opcode >= OPC_EmitNode0Chain && Opcode <= OPC_EmitNode2Chain)
3921 NumVTs = Opcode - OPC_EmitNode0Chain;
3922 else
3923 NumVTs = MatcherTable[MatcherIndex++];
3925 for (unsigned i = 0; i != NumVTs; ++i) {
3927 static_cast<MVT::SimpleValueType>(MatcherTable[MatcherIndex++]);
3928 if (VT == MVT::iPTR)
3929 VT = TLI->getPointerTy(CurDAG->getDataLayout()).SimpleTy;
3930 VTs.push_back(VT);
3931 }
3932
3933 if (EmitNodeInfo & OPFL_Chain)
3934 VTs.push_back(MVT::Other);
3935 if (EmitNodeInfo & OPFL_GlueOutput)
3936 VTs.push_back(MVT::Glue);
3937
3938 // This is hot code, so optimize the two most common cases of 1 and 2
3939 // results.
3940 SDVTList VTList;
3941 if (VTs.size() == 1)
3942 VTList = CurDAG->getVTList(VTs[0]);
3943 else if (VTs.size() == 2)
3944 VTList = CurDAG->getVTList(VTs[0], VTs[1]);
3945 else
3946 VTList = CurDAG->getVTList(VTs);
3947
3948 // Get the operand list.
3949 unsigned NumOps = MatcherTable[MatcherIndex++];
3951 for (unsigned i = 0; i != NumOps; ++i) {
3952 unsigned RecNo = MatcherTable[MatcherIndex++];
3953 if (RecNo & 128)
3954 RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
3955
3956 assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");
3957 Ops.push_back(RecordedNodes[RecNo].first);
3958 }
3959
3960 // If there are variadic operands to add, handle them now.
3961 if (EmitNodeInfo & OPFL_VariadicInfo) {
3962 // Determine the start index to copy from.
3963 unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
3964 FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
3965 assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
3966 "Invalid variadic node");
3967 // Copy all of the variadic operands, not including a potential glue
3968 // input.
3969 for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
3970 i != e; ++i) {
3971 SDValue V = NodeToMatch->getOperand(i);
3972 if (V.getValueType() == MVT::Glue) break;
3973 Ops.push_back(V);
3974 }
3975 }
3976
3977 // If this has chain/glue inputs, add them.
3978 if (EmitNodeInfo & OPFL_Chain)
3979 Ops.push_back(InputChain);
3980 if ((EmitNodeInfo & OPFL_GlueInput) && InputGlue.getNode() != nullptr)
3981 Ops.push_back(InputGlue);
3982
3983 // Check whether any matched node could raise an FP exception. Since all
3984 // such nodes must have a chain, it suffices to check ChainNodesMatched.
3985 // We need to perform this check before potentially modifying one of the
3986 // nodes via MorphNode.
3987 bool MayRaiseFPException =
3988 llvm::any_of(ChainNodesMatched, [this](SDNode *N) {
3989 return mayRaiseFPException(N) && !N->getFlags().hasNoFPExcept();
3990 });
3991
3992 // Create the node.
3993 MachineSDNode *Res = nullptr;
3994 bool IsMorphNodeTo =
3995 Opcode == OPC_MorphNodeTo ||
3996 (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2GlueOutput);
3997 if (!IsMorphNodeTo) {
3998 // If this is a normal EmitNode command, just create the new node and
3999 // add the results to the RecordedNodes list.
4000 Res = CurDAG->getMachineNode(TargetOpc, SDLoc(NodeToMatch),
4001 VTList, Ops);
4002
4003 // Add all the non-glue/non-chain results to the RecordedNodes list.
4004 for (unsigned i = 0, e = VTs.size(); i != e; ++i) {
4005 if (VTs[i] == MVT::Other || VTs[i] == MVT::Glue) break;
4006 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i),
4007 nullptr));
4008 }
4009 } else {
4010 assert(NodeToMatch->getOpcode() != ISD::DELETED_NODE &&
4011 "NodeToMatch was removed partway through selection");
4013 SDNode *E) {
4015 auto &Chain = ChainNodesMatched;
4016 assert((!E || !is_contained(Chain, N)) &&
4017 "Chain node replaced during MorphNode");
4018 llvm::erase(Chain, N);
4019 });
4020 Res = cast<MachineSDNode>(MorphNode(NodeToMatch, TargetOpc, VTList,
4021 Ops, EmitNodeInfo));
4022 }
4023
4024 // Set the NoFPExcept flag when no original matched node could
4025 // raise an FP exception, but the new node potentially might.
4026 if (!MayRaiseFPException && mayRaiseFPException(Res)) {
4027 SDNodeFlags Flags = Res->getFlags();
4028 Flags.setNoFPExcept(true);
4029 Res->setFlags(Flags);
4030 }
4031
4032 // If the node had chain/glue results, update our notion of the current
4033 // chain and glue.
4034 if (EmitNodeInfo & OPFL_GlueOutput) {
4035 InputGlue = SDValue(Res, VTs.size()-1);
4036 if (EmitNodeInfo & OPFL_Chain)
4037 InputChain = SDValue(Res, VTs.size()-2);
4038 } else if (EmitNodeInfo & OPFL_Chain)
4039 InputChain = SDValue(Res, VTs.size()-1);
4040
4041 // If the OPFL_MemRefs glue is set on this node, slap all of the
4042 // accumulated memrefs onto it.
4043 //
4044 // FIXME: This is vastly incorrect for patterns with multiple outputs
4045 // instructions that access memory and for ComplexPatterns that match
4046 // loads.
4047 if (EmitNodeInfo & OPFL_MemRefs) {
4048 // Only attach load or store memory operands if the generated
4049 // instruction may load or store.
4050 const MCInstrDesc &MCID = TII->get(TargetOpc);
4051 bool mayLoad = MCID.mayLoad();
4052 bool mayStore = MCID.mayStore();
4053
4054 // We expect to have relatively few of these so just filter them into a
4055 // temporary buffer so that we can easily add them to the instruction.
4057 for (MachineMemOperand *MMO : MatchedMemRefs) {
4058 if (MMO->isLoad()) {
4059 if (mayLoad)
4060 FilteredMemRefs.push_back(MMO);
4061 } else if (MMO->isStore()) {
4062 if (mayStore)
4063 FilteredMemRefs.push_back(MMO);
4064 } else {
4065 FilteredMemRefs.push_back(MMO);
4066 }
4067 }
4068
4069 CurDAG->setNodeMemRefs(Res, FilteredMemRefs);
4070 }
4071
4072 LLVM_DEBUG(if (!MatchedMemRefs.empty() && Res->memoperands_empty()) dbgs()
4073 << " Dropping mem operands\n";
4074 dbgs() << " " << (IsMorphNodeTo ? "Morphed" : "Created")
4075 << " node: ";
4076 Res->dump(CurDAG););
4077
4078 // If this was a MorphNodeTo then we're completely done!
4079 if (IsMorphNodeTo) {
4080 // Update chain uses.
4081 UpdateChains(Res, InputChain, ChainNodesMatched, true);
4082 return;
4083 }
4084 continue;
4085 }
4086
4087 case OPC_CompleteMatch: {
4088 // The match has been completed, and any new nodes (if any) have been
4089 // created. Patch up references to the matched dag to use the newly
4090 // created nodes.
4091 unsigned NumResults = MatcherTable[MatcherIndex++];
4092
4093 for (unsigned i = 0; i != NumResults; ++i) {
4094 unsigned ResSlot = MatcherTable[MatcherIndex++];
4095 if (ResSlot & 128)
4096 ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);
4097
4098 assert(ResSlot < RecordedNodes.size() && "Invalid CompleteMatch");
4099 SDValue Res = RecordedNodes[ResSlot].first;
4100
4101 assert(i < NodeToMatch->getNumValues() &&
4102 NodeToMatch->getValueType(i) != MVT::Other &&
4103 NodeToMatch->getValueType(i) != MVT::Glue &&
4104 "Invalid number of results to complete!");
4105 assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
4106 NodeToMatch->getValueType(i) == MVT::iPTR ||
4107 Res.getValueType() == MVT::iPTR ||
4108 NodeToMatch->getValueType(i).getSizeInBits() ==
4109 Res.getValueSizeInBits()) &&
4110 "invalid replacement");
4111 ReplaceUses(SDValue(NodeToMatch, i), Res);
4112 }
4113
4114 // Update chain uses.
4115 UpdateChains(NodeToMatch, InputChain, ChainNodesMatched, false);
4116
4117 // If the root node defines glue, we need to update it to the glue result.
4118 // TODO: This never happens in our tests and I think it can be removed /
4119 // replaced with an assert, but if we do it this the way the change is
4120 // NFC.
4121 if (NodeToMatch->getValueType(NodeToMatch->getNumValues() - 1) ==
4122 MVT::Glue &&
4123 InputGlue.getNode())
4124 ReplaceUses(SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1),
4125 InputGlue);
4126
4127 assert(NodeToMatch->use_empty() &&
4128 "Didn't replace all uses of the node?");
4129 CurDAG->RemoveDeadNode(NodeToMatch);
4130
4131 return;
4132 }
4133 }
4134
4135 // If the code reached this point, then the match failed. See if there is
4136 // another child to try in the current 'Scope', otherwise pop it until we
4137 // find a case to check.
4138 LLVM_DEBUG(dbgs() << " Match failed at index " << CurrentOpcodeIndex
4139 << "\n");
4140 ++NumDAGIselRetries;
4141 while (true) {
4142 if (MatchScopes.empty()) {
4143 CannotYetSelect(NodeToMatch);
4144 return;
4145 }
4146
4147 // Restore the interpreter state back to the point where the scope was
4148 // formed.
4149 MatchScope &LastScope = MatchScopes.back();
4150 RecordedNodes.resize(LastScope.NumRecordedNodes);
4151 NodeStack.clear();
4152 NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());
4153 N = NodeStack.back();
4154
4155 if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
4156 MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
4157 MatcherIndex = LastScope.FailIndex;
4158
4159 LLVM_DEBUG(dbgs() << " Continuing at " << MatcherIndex << "\n");
4160
4161 InputChain = LastScope.InputChain;
4162 InputGlue = LastScope.InputGlue;
4163 if (!LastScope.HasChainNodesMatched)
4164 ChainNodesMatched.clear();
4165
4166 // Check to see what the offset is at the new MatcherIndex. If it is zero
4167 // we have reached the end of this scope, otherwise we have another child
4168 // in the current scope to try.
4169 unsigned NumToSkip = MatcherTable[MatcherIndex++];
4170 if (NumToSkip & 128)
4171 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
4172
4173 // If we have another child in this scope to match, update FailIndex and
4174 // try it.
4175 if (NumToSkip != 0) {
4176 LastScope.FailIndex = MatcherIndex+NumToSkip;
4177 break;
4178 }
4179
4180 // End of this scope, pop it and try the next child in the containing
4181 // scope.
4182 MatchScopes.pop_back();
4183 }
4184 }
4185}
4186
4187/// Return whether the node may raise an FP exception.
4189 // For machine opcodes, consult the MCID flag.
4190 if (N->isMachineOpcode()) {
4191 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
4192 return MCID.mayRaiseFPException();
4193 }
4194
4195 // For ISD opcodes, only StrictFP opcodes may raise an FP
4196 // exception.
4197 if (N->isTargetOpcode())
4198 return N->isTargetStrictFPOpcode();
4199 return N->isStrictFPOpcode();
4200}
4201
4203 assert(N->getOpcode() == ISD::OR && "Unexpected opcode");
4204 auto *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
4205 if (!C)
4206 return false;
4207
4208 // Detect when "or" is used to add an offset to a stack object.
4209 if (auto *FN = dyn_cast<FrameIndexSDNode>(N->getOperand(0))) {
4211 Align A = MFI.getObjectAlign(FN->getIndex());
4212 int32_t Off = C->getSExtValue();
4213 // If the alleged offset fits in the zero bits guaranteed by
4214 // the alignment, then this or is really an add.
4215 return (Off >= 0) && (((A.value() - 1) & Off) == unsigned(Off));
4216 }
4217 return false;
4218}
4219
4220void SelectionDAGISel::CannotYetSelect(SDNode *N) {
4221 std::string msg;
4222 raw_string_ostream Msg(msg);
4223 Msg << "Cannot select: ";
4224
4225 if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&
4226 N->getOpcode() != ISD::INTRINSIC_WO_CHAIN &&
4227 N->getOpcode() != ISD::INTRINSIC_VOID) {
4228 N->printrFull(Msg, CurDAG);
4229 Msg << "\nIn function: " << MF->getName();
4230 } else {
4231 bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other;
4232 unsigned iid = N->getConstantOperandVal(HasInputChain);
4233 if (iid < Intrinsic::num_intrinsics)
4234 Msg << "intrinsic %" << Intrinsic::getBaseName((Intrinsic::ID)iid);
4235 else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo())
4236 Msg << "target intrinsic %" << TII->getName(iid);
4237 else
4238 Msg << "unknown intrinsic #" << iid;
4239 }
4241}
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...
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
Select target instructions out of generic instructions
#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:1229
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:28
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:451
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
Definition: BasicBlock.h:507
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:174
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
Definition: BasicBlock.cpp:405
bool isEHPad() const
Return true if this basic block is an exception handling block.
Definition: BasicBlock.h:665
const Instruction * getFirstMayFaultInst() const
Returns the first potential AsynchEH faulty instruction currently it checks for loads/stores (which m...
Definition: BasicBlock.cpp:396
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:267
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
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 ...
Record of a variable value-assignment, aka a non instruction representation of the dbg....
static auto filter(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DPValue types only and downcast.
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
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:1183
bool tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst)
We're checking to see if we can fold LI into FoldInst.
Definition: FastISel.cpp:2297
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:1579
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:2417
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th funcletpad argument.
Definition: InstrTypes.h:2433
FunctionLoweringInfo - This contains information that is global to a function that is used when lower...
DenseMap< const AllocaInst *, int > StaticAllocaMap
StaticAllocaMap - Keep track of frame indices for fixed sized allocas in the entry block.
int getArgumentFrameIndex(const Argument *A)
getArgumentFrameIndex - Get frame index for the byval argument.
SmallPtrSet< const DPValue *, 8 > PreprocessedDPVDeclares
bool isExportedInst(const Value *V) const
isExportedInst - Return true if the specified value is an instruction exported from its block.
SmallPtrSet< const DbgDeclareInst *, 8 > PreprocessedDbgDeclares
Collection of dbg.declare instructions handled after argument lowering and before ISel proper.
DenseMap< const Value *, Register > ValueMap
ValueMap - Since we emit code for the function a basic block at a time, we must remember which virtua...
Definition: