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