LLVM 19.0.0git
SelectionDAGBuilder.h
Go to the documentation of this file.
1//===- SelectionDAGBuilder.h - Selection-DAG building -----------*- C++ -*-===//
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 routines for translating from LLVM IR into SelectionDAG IR.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_LIB_CODEGEN_SELECTIONDAG_SELECTIONDAGBUILDER_H
14#define LLVM_LIB_CODEGEN_SELECTIONDAG_SELECTIONDAGBUILDER_H
15
16#include "StatepointLowering.h"
17#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/ADT/MapVector.h"
29#include "llvm/IR/DebugLoc.h"
30#include "llvm/IR/Instruction.h"
34#include <algorithm>
35#include <cassert>
36#include <cstdint>
37#include <optional>
38#include <utility>
39#include <vector>
40
41namespace llvm {
42
43class AAResults;
44class AllocaInst;
45class AtomicCmpXchgInst;
46class AtomicRMWInst;
47class AssumptionCache;
48class BasicBlock;
49class BranchInst;
50class CallInst;
51class CallBrInst;
52class CatchPadInst;
53class CatchReturnInst;
54class CatchSwitchInst;
55class CleanupPadInst;
56class CleanupReturnInst;
57class Constant;
58class ConstrainedFPIntrinsic;
59class DbgValueInst;
60class DataLayout;
61class DIExpression;
62class DILocalVariable;
63class DILocation;
64class FenceInst;
65class FunctionLoweringInfo;
66class GCFunctionInfo;
67class GCRelocateInst;
68class GCResultInst;
69class GCStatepointInst;
70class IndirectBrInst;
71class InvokeInst;
72class LandingPadInst;
73class LLVMContext;
74class LoadInst;
75class MachineBasicBlock;
76class PHINode;
77class ResumeInst;
78class ReturnInst;
79class SDDbgValue;
80class SelectionDAG;
81class StoreInst;
82class SwiftErrorValueTracking;
83class SwitchInst;
84class TargetLibraryInfo;
85class TargetMachine;
86class Type;
87class VAArgInst;
88class UnreachableInst;
89class Use;
90class User;
91class Value;
92
93//===----------------------------------------------------------------------===//
94/// SelectionDAGBuilder - This is the common target-independent lowering
95/// implementation that is parameterized by a TargetLowering object.
96///
98 /// The current instruction being visited.
99 const Instruction *CurInst = nullptr;
100
102
103 /// Maps argument value for unused arguments. This is used
104 /// to preserve debug information for incoming arguments.
105 DenseMap<const Value*, SDValue> UnusedArgNodeMap;
106
107 /// Helper type for DanglingDebugInfoMap.
108 class DanglingDebugInfo {
109 unsigned SDNodeOrder = 0;
110
111 public:
112 DILocalVariable *Variable;
114 DebugLoc dl;
115 DanglingDebugInfo() = default;
116 DanglingDebugInfo(DILocalVariable *Var, DIExpression *Expr, DebugLoc DL,
117 unsigned SDNO)
118 : SDNodeOrder(SDNO), Variable(Var), Expression(Expr),
119 dl(std::move(DL)) {}
120
121 DILocalVariable *getVariable() const { return Variable; }
122 DIExpression *getExpression() const { return Expression; }
123 DebugLoc getDebugLoc() const { return dl; }
124 unsigned getSDNodeOrder() const { return SDNodeOrder; }
125
126 /// Helper for printing DanglingDebugInfo. This hoop-jumping is to
127 /// store a Value pointer, so that we can print a whole DDI as one object.
128 /// Call SelectionDAGBuilder::printDDI instead of using directly.
129 struct Print {
130 Print(const Value *V, const DanglingDebugInfo &DDI) : V(V), DDI(DDI) {}
131 const Value *V;
132 const DanglingDebugInfo &DDI;
135 OS << "DDI(var=" << *P.DDI.getVariable();
136 if (P.V)
137 OS << ", val=" << *P.V;
138 else
139 OS << ", val=nullptr";
140
141 OS << ", expr=" << *P.DDI.getExpression()
142 << ", order=" << P.DDI.getSDNodeOrder()
143 << ", loc=" << P.DDI.getDebugLoc() << ")";
144 return OS;
145 }
146 };
147 };
148
149 /// Returns an object that defines `raw_ostream &operator<<` for printing.
150 /// Usage example:
151 //// errs() << printDDI(MyDanglingInfo) << " is dangling\n";
152 DanglingDebugInfo::Print printDDI(const Value *V,
153 const DanglingDebugInfo &DDI) {
154 return DanglingDebugInfo::Print(V, DDI);
155 }
156
157 /// Helper type for DanglingDebugInfoMap.
158 typedef std::vector<DanglingDebugInfo> DanglingDebugInfoVector;
159
160 /// Keeps track of dbg_values for which we have not yet seen the referent.
161 /// We defer handling these until we do see it.
162 MapVector<const Value*, DanglingDebugInfoVector> DanglingDebugInfoMap;
163
164 /// Cache the module flag for whether we should use debug-info assignment
165 /// tracking.
166 bool AssignmentTrackingEnabled = false;
167
168public:
169 /// Loads are not emitted to the program immediately. We bunch them up and
170 /// then emit token factor nodes when possible. This allows us to get simple
171 /// disambiguation between loads without worrying about alias analysis.
173
174 /// State used while lowering a statepoint sequence (gc_statepoint,
175 /// gc_relocate, and gc_result). See StatepointLowering.hpp/cpp for details.
177
178private:
179 /// CopyToReg nodes that copy values to virtual registers for export to other
180 /// blocks need to be emitted before any terminator instruction, but they have
181 /// no other ordering requirements. We bunch them up and the emit a single
182 /// tokenfactor for them just before terminator instructions.
183 SmallVector<SDValue, 8> PendingExports;
184
185 /// Similar to loads, nodes corresponding to constrained FP intrinsics are
186 /// bunched up and emitted when necessary. These can be moved across each
187 /// other and any (normal) memory operation (load or store), but not across
188 /// calls or instructions having unspecified side effects. As a special
189 /// case, constrained FP intrinsics using fpexcept.strict may not be deleted
190 /// even if otherwise unused, so they need to be chained before any
191 /// terminator instruction (like PendingExports). We track the latter
192 /// set of nodes in a separate list.
193 SmallVector<SDValue, 8> PendingConstrainedFP;
194 SmallVector<SDValue, 8> PendingConstrainedFPStrict;
195
196 /// Update root to include all chains from the Pending list.
197 SDValue updateRoot(SmallVectorImpl<SDValue> &Pending);
198
199 /// A unique monotonically increasing number used to order the SDNodes we
200 /// create.
201 unsigned SDNodeOrder;
202
203 /// Emit comparison and split W into two subtrees.
204 void splitWorkItem(SwitchCG::SwitchWorkList &WorkList,
206 MachineBasicBlock *SwitchMBB);
207
208 /// Lower W.
209 void lowerWorkItem(SwitchCG::SwitchWorkListItem W, Value *Cond,
210 MachineBasicBlock *SwitchMBB,
211 MachineBasicBlock *DefaultMBB);
212
213 /// Peel the top probability case if it exceeds the threshold
215 peelDominantCaseCluster(const SwitchInst &SI,
217 BranchProbability &PeeledCaseProb);
218
219private:
220 const TargetMachine &TM;
221
222public:
223 /// Lowest valid SDNodeOrder. The special case 0 is reserved for scheduling
224 /// nodes without a corresponding SDNode.
225 static const unsigned LowestSDNodeOrder = 1;
226
228 AAResults *AA = nullptr;
229 AssumptionCache *AC = nullptr;
230 const TargetLibraryInfo *LibInfo = nullptr;
231
233 public:
235 : SwitchCG::SwitchLowering(funcinfo), SDB(sdb) {}
236
240 SDB->addSuccessorWithProb(Src, Dst, Prob);
241 }
242
243 private:
244 SelectionDAGBuilder *SDB = nullptr;
245 };
246
247 // Data related to deferred switch lowerings. Used to construct additional
248 // Basic Blocks in SelectionDAGISel::FinishBasicBlock.
249 std::unique_ptr<SDAGSwitchLowering> SL;
250
251 /// A StackProtectorDescriptor structure used to communicate stack protector
252 /// information in between SelectBasicBlock and FinishBasicBlock.
254
255 // Emit PHI-node-operand constants only once even if used by multiple
256 // PHI nodes.
258
259 /// Information about the function as a whole.
261
262 /// Information about the swifterror values used throughout the function.
264
265 /// Garbage collection metadata for the function.
266 GCFunctionInfo *GFI = nullptr;
267
268 /// Map a landing pad to the call site indexes.
270
271 /// This is set to true if a call in the current block has been translated as
272 /// a tail call. In this case, no subsequent DAG nodes should be created.
273 bool HasTailCall = false;
274
276
279 : SDNodeOrder(LowestSDNodeOrder), TM(dag.getTarget()), DAG(dag),
280 SL(std::make_unique<SDAGSwitchLowering>(this, funcinfo)),
281 FuncInfo(funcinfo), SwiftError(swifterror) {}
282
284 const TargetLibraryInfo *li);
285
286 /// Clear out the current SelectionDAG and the associated state and prepare
287 /// this SelectionDAGBuilder object to be used for a new block. This doesn't
288 /// clear out information about additional blocks that are needed to complete
289 /// switch lowering or PHI node updating; that information is cleared out as
290 /// it is consumed.
291 void clear();
292
293 /// Clear the dangling debug information map. This function is separated from
294 /// the clear so that debug information that is dangling in a basic block can
295 /// be properly resolved in a different basic block. This allows the
296 /// SelectionDAG to resolve dangling debug information attached to PHI nodes.
298
299 /// Return the current virtual root of the Selection DAG, flushing any
300 /// PendingLoad items. This must be done before emitting a store or any other
301 /// memory node that may need to be ordered after any prior load instructions.
303
304 /// Similar to getMemoryRoot, but also flushes PendingConstrainedFP(Strict)
305 /// items. This must be done before emitting any call other any other node
306 /// that may need to be ordered after FP instructions due to other side
307 /// effects.
309
310 /// Similar to getRoot, but instead of flushing all the PendingLoad items,
311 /// flush all the PendingExports (and PendingConstrainedFPStrict) items.
312 /// It is necessary to do this before emitting a terminator instruction.
314
316 return SDLoc(CurInst, SDNodeOrder);
317 }
318
320 return CurInst ? CurInst->getDebugLoc() : DebugLoc();
321 }
322
323 void CopyValueToVirtualRegister(const Value *V, unsigned Reg,
324 ISD::NodeType ExtendType = ISD::ANY_EXTEND);
325
326 void visit(const Instruction &I);
327 void visitDbgInfo(const Instruction &I);
328
329 void visit(unsigned Opcode, const User &I);
330
331 /// If there was virtual register allocated for the value V emit CopyFromReg
332 /// of the specified type Ty. Return empty SDValue() otherwise.
333 SDValue getCopyFromRegs(const Value *V, Type *Ty);
334
335 /// Register a dbg_value which relies on a Value which we have not yet seen.
337 DILocalVariable *Var, DIExpression *Expr,
338 bool IsVariadic, DebugLoc DL, unsigned Order);
339
340 /// If we have dangling debug info that describes \p Variable, or an
341 /// overlapping part of variable considering the \p Expr, then this method
342 /// will drop that debug info as it isn't valid any longer.
343 void dropDanglingDebugInfo(const DILocalVariable *Variable,
344 const DIExpression *Expr);
345
346 /// If we saw an earlier dbg_value referring to V, generate the debug data
347 /// structures now that we've seen its definition.
348 void resolveDanglingDebugInfo(const Value *V, SDValue Val);
349
350 /// For the given dangling debuginfo record, perform last-ditch efforts to
351 /// resolve the debuginfo to something that is represented in this DAG. If
352 /// this cannot be done, produce an Undef debug value record.
353 void salvageUnresolvedDbgValue(const Value *V, DanglingDebugInfo &DDI);
354
355 /// For a given list of Values, attempt to create and record a SDDbgValue in
356 /// the SelectionDAG.
358 DIExpression *Expr, DebugLoc DbgLoc, unsigned Order,
359 bool IsVariadic);
360
361 /// Create a record for a kill location debug intrinsic.
363 DebugLoc DbgLoc, unsigned Order);
364
367
368 /// Evict any dangling debug information, attempting to salvage it first.
370
371 SDValue getValue(const Value *V);
372
374 SDValue getValueImpl(const Value *V);
375
376 void setValue(const Value *V, SDValue NewN) {
377 SDValue &N = NodeMap[V];
378 assert(!N.getNode() && "Already set a value for this node!");
379 N = NewN;
380 }
381
382 void setUnusedArgValue(const Value *V, SDValue NewN) {
383 SDValue &N = UnusedArgNodeMap[V];
384 assert(!N.getNode() && "Already set a value for this node!");
385 N = NewN;
386 }
387
390 Instruction::BinaryOps Opc, const Value *Lhs, const Value *Rhs,
392
395 MachineBasicBlock *SwitchBB,
397 BranchProbability FProb, bool InvertCond);
400 MachineBasicBlock *CurBB,
401 MachineBasicBlock *SwitchBB,
403 bool InvertCond);
404 bool ShouldEmitAsBranches(const std::vector<SwitchCG::CaseBlock> &Cases);
405 bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB);
406 void CopyToExportRegsIfNeeded(const Value *V);
407 void ExportFromCurrentBlock(const Value *V);
408 void LowerCallTo(const CallBase &CB, SDValue Callee, bool IsTailCall,
409 bool IsMustTailCall, const BasicBlock *EHPadBB = nullptr,
410 const TargetLowering::PtrAuthInfo *PAI = nullptr);
411
412 // Lower range metadata from 0 to N to assert zext to an integer of nearest
413 // floor power of two.
415 SDValue Op);
416
418 const CallBase *Call, unsigned ArgIdx,
419 unsigned NumArgs, SDValue Callee,
420 Type *ReturnTy, AttributeSet RetAttrs,
421 bool IsPatchPoint);
422
423 std::pair<SDValue, SDValue>
425 const BasicBlock *EHPadBB = nullptr);
426
427 /// When an MBB was split during scheduling, update the
428 /// references that need to refer to the last resulting block.
430
431 /// Describes a gc.statepoint or a gc.statepoint like thing for the purposes
432 /// of lowering into a STATEPOINT node.
434 /// Bases[i] is the base pointer for Ptrs[i]. Together they denote the set
435 /// of gc pointers this STATEPOINT has to relocate.
438
439 /// The set of gc.relocate calls associated with this gc.statepoint.
441
442 /// The full list of gc arguments to the gc.statepoint being lowered.
444
445 /// The gc.statepoint instruction.
446 const Instruction *StatepointInstr = nullptr;
447
448 /// The list of gc transition arguments present in the gc.statepoint being
449 /// lowered.
451
452 /// The ID that the resulting STATEPOINT instruction has to report.
454
455 /// Information regarding the underlying call instruction.
457
458 /// The deoptimization state associated with this gc.statepoint call, if
459 /// any.
461
462 /// Flags associated with the meta arguments being lowered.
464
465 /// The number of patchable bytes the call needs to get lowered into.
466 unsigned NumPatchBytes = -1;
467
468 /// The exception handling unwind destination, in case this represents an
469 /// invoke of gc.statepoint.
470 const BasicBlock *EHPadBB = nullptr;
471
473 };
474
475 /// Lower \p SLI into a STATEPOINT instruction.
476 SDValue LowerAsSTATEPOINT(StatepointLoweringInfo &SI);
477
478 // This function is responsible for the whole statepoint lowering process.
479 // It uniformly handles invoke and call statepoints.
481 const BasicBlock *EHPadBB = nullptr);
482
483 void LowerCallSiteWithDeoptBundle(const CallBase *Call, SDValue Callee,
484 const BasicBlock *EHPadBB);
485
486 void LowerDeoptimizeCall(const CallInst *CI);
488
489 void LowerCallSiteWithDeoptBundleImpl(const CallBase *Call, SDValue Callee,
490 const BasicBlock *EHPadBB,
491 bool VarArgDisallowed,
492 bool ForceVoidReturnTy);
493
495 const BasicBlock *EHPadBB);
496
497 /// Returns the type of FrameIndex and TargetFrameIndex nodes.
500 }
501
502private:
503 // Terminator instructions.
504 void visitRet(const ReturnInst &I);
505 void visitBr(const BranchInst &I);
506 void visitSwitch(const SwitchInst &I);
507 void visitIndirectBr(const IndirectBrInst &I);
508 void visitUnreachable(const UnreachableInst &I);
509 void visitCleanupRet(const CleanupReturnInst &I);
510 void visitCatchSwitch(const CatchSwitchInst &I);
511 void visitCatchRet(const CatchReturnInst &I);
512 void visitCatchPad(const CatchPadInst &I);
513 void visitCleanupPad(const CleanupPadInst &CPI);
514
515 BranchProbability getEdgeProbability(const MachineBasicBlock *Src,
516 const MachineBasicBlock *Dst) const;
517 void addSuccessorWithProb(
520
521public:
524 MachineBasicBlock *ParentBB);
527 MachineBasicBlock *SwitchBB);
529 BranchProbability BranchProbToNext, unsigned Reg,
534 MachineBasicBlock *SwitchBB);
535
536private:
537 // These all get lowered before this pass.
538 void visitInvoke(const InvokeInst &I);
539 void visitCallBr(const CallBrInst &I);
540 void visitCallBrLandingPad(const CallInst &I);
541 void visitResume(const ResumeInst &I);
542
543 void visitUnary(const User &I, unsigned Opcode);
544 void visitFNeg(const User &I) { visitUnary(I, ISD::FNEG); }
545
546 void visitBinary(const User &I, unsigned Opcode);
547 void visitShift(const User &I, unsigned Opcode);
548 void visitAdd(const User &I) { visitBinary(I, ISD::ADD); }
549 void visitFAdd(const User &I) { visitBinary(I, ISD::FADD); }
550 void visitSub(const User &I) { visitBinary(I, ISD::SUB); }
551 void visitFSub(const User &I) { visitBinary(I, ISD::FSUB); }
552 void visitMul(const User &I) { visitBinary(I, ISD::MUL); }
553 void visitFMul(const User &I) { visitBinary(I, ISD::FMUL); }
554 void visitURem(const User &I) { visitBinary(I, ISD::UREM); }
555 void visitSRem(const User &I) { visitBinary(I, ISD::SREM); }
556 void visitFRem(const User &I) { visitBinary(I, ISD::FREM); }
557 void visitUDiv(const User &I) { visitBinary(I, ISD::UDIV); }
558 void visitSDiv(const User &I);
559 void visitFDiv(const User &I) { visitBinary(I, ISD::FDIV); }
560 void visitAnd (const User &I) { visitBinary(I, ISD::AND); }
561 void visitOr (const User &I) { visitBinary(I, ISD::OR); }
562 void visitXor (const User &I) { visitBinary(I, ISD::XOR); }
563 void visitShl (const User &I) { visitShift(I, ISD::SHL); }
564 void visitLShr(const User &I) { visitShift(I, ISD::SRL); }
565 void visitAShr(const User &I) { visitShift(I, ISD::SRA); }
566 void visitICmp(const ICmpInst &I);
567 void visitFCmp(const FCmpInst &I);
568 // Visit the conversion instructions
569 void visitTrunc(const User &I);
570 void visitZExt(const User &I);
571 void visitSExt(const User &I);
572 void visitFPTrunc(const User &I);
573 void visitFPExt(const User &I);
574 void visitFPToUI(const User &I);
575 void visitFPToSI(const User &I);
576 void visitUIToFP(const User &I);
577 void visitSIToFP(const User &I);
578 void visitPtrToInt(const User &I);
579 void visitIntToPtr(const User &I);
580 void visitBitCast(const User &I);
581 void visitAddrSpaceCast(const User &I);
582
583 void visitExtractElement(const User &I);
584 void visitInsertElement(const User &I);
585 void visitShuffleVector(const User &I);
586
587 void visitExtractValue(const ExtractValueInst &I);
588 void visitInsertValue(const InsertValueInst &I);
589 void visitLandingPad(const LandingPadInst &LP);
590
591 void visitGetElementPtr(const User &I);
592 void visitSelect(const User &I);
593
594 void visitAlloca(const AllocaInst &I);
595 void visitLoad(const LoadInst &I);
596 void visitStore(const StoreInst &I);
597 void visitMaskedLoad(const CallInst &I, bool IsExpanding = false);
598 void visitMaskedStore(const CallInst &I, bool IsCompressing = false);
599 void visitMaskedGather(const CallInst &I);
600 void visitMaskedScatter(const CallInst &I);
601 void visitAtomicCmpXchg(const AtomicCmpXchgInst &I);
602 void visitAtomicRMW(const AtomicRMWInst &I);
603 void visitFence(const FenceInst &I);
604 void visitPHI(const PHINode &I);
605 void visitCall(const CallInst &I);
606 bool visitMemCmpBCmpCall(const CallInst &I);
607 bool visitMemPCpyCall(const CallInst &I);
608 bool visitMemChrCall(const CallInst &I);
609 bool visitStrCpyCall(const CallInst &I, bool isStpcpy);
610 bool visitStrCmpCall(const CallInst &I);
611 bool visitStrLenCall(const CallInst &I);
612 bool visitStrNLenCall(const CallInst &I);
613 bool visitUnaryFloatCall(const CallInst &I, unsigned Opcode);
614 bool visitBinaryFloatCall(const CallInst &I, unsigned Opcode);
615 void visitAtomicLoad(const LoadInst &I);
616 void visitAtomicStore(const StoreInst &I);
617 void visitLoadFromSwiftError(const LoadInst &I);
618 void visitStoreToSwiftError(const StoreInst &I);
619 void visitFreeze(const FreezeInst &I);
620
621 void visitInlineAsm(const CallBase &Call,
622 const BasicBlock *EHPadBB = nullptr);
623
624 bool visitEntryValueDbgValue(ArrayRef<const Value *> Values,
625 DILocalVariable *Variable, DIExpression *Expr,
626 DebugLoc DbgLoc);
627 void visitIntrinsicCall(const CallInst &I, unsigned Intrinsic);
628 void visitTargetIntrinsic(const CallInst &I, unsigned Intrinsic);
629 void visitConstrainedFPIntrinsic(const ConstrainedFPIntrinsic &FPI);
630 void visitConvergenceControl(const CallInst &I, unsigned Intrinsic);
631 void visitVectorHistogram(const CallInst &I, unsigned IntrinsicID);
632 void visitVPLoad(const VPIntrinsic &VPIntrin, EVT VT,
633 const SmallVectorImpl<SDValue> &OpValues);
634 void visitVPStore(const VPIntrinsic &VPIntrin,
635 const SmallVectorImpl<SDValue> &OpValues);
636 void visitVPGather(const VPIntrinsic &VPIntrin, EVT VT,
637 const SmallVectorImpl<SDValue> &OpValues);
638 void visitVPScatter(const VPIntrinsic &VPIntrin,
639 const SmallVectorImpl<SDValue> &OpValues);
640 void visitVPStridedLoad(const VPIntrinsic &VPIntrin, EVT VT,
641 const SmallVectorImpl<SDValue> &OpValues);
642 void visitVPStridedStore(const VPIntrinsic &VPIntrin,
643 const SmallVectorImpl<SDValue> &OpValues);
644 void visitVPCmp(const VPCmpIntrinsic &VPIntrin);
645 void visitVectorPredicationIntrinsic(const VPIntrinsic &VPIntrin);
646
647 void visitVAStart(const CallInst &I);
648 void visitVAArg(const VAArgInst &I);
649 void visitVAEnd(const CallInst &I);
650 void visitVACopy(const CallInst &I);
651 void visitStackmap(const CallInst &I);
652 void visitPatchpoint(const CallBase &CB, const BasicBlock *EHPadBB = nullptr);
653
654 // These two are implemented in StatepointLowering.cpp
655 void visitGCRelocate(const GCRelocateInst &Relocate);
656 void visitGCResult(const GCResultInst &I);
657
658 void visitVectorReduce(const CallInst &I, unsigned Intrinsic);
659 void visitVectorReverse(const CallInst &I);
660 void visitVectorSplice(const CallInst &I);
661 void visitVectorInterleave(const CallInst &I);
662 void visitVectorDeinterleave(const CallInst &I);
663 void visitStepVector(const CallInst &I);
664
665 void visitUserOp1(const Instruction &I) {
666 llvm_unreachable("UserOp1 should not exist at instruction selection time!");
667 }
668 void visitUserOp2(const Instruction &I) {
669 llvm_unreachable("UserOp2 should not exist at instruction selection time!");
670 }
671
672 void processIntegerCallValue(const Instruction &I,
673 SDValue Value, bool IsSigned);
674
675 void HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB);
676
677 void emitInlineAsmError(const CallBase &Call, const Twine &Message);
678
679 /// An enum that states to emit func argument dbg value the kind of intrinsic
680 /// it originally had. This controls the internal behavior of
681 /// EmitFuncArgumentDbgValue.
682 enum class FuncArgumentDbgValueKind {
683 Value, // This was originally a llvm.dbg.value.
684 Declare, // This was originally a llvm.dbg.declare.
685 };
686
687 /// If V is an function argument then create corresponding DBG_VALUE machine
688 /// instruction for it now. At the end of instruction selection, they will be
689 /// inserted to the entry BB.
690 bool EmitFuncArgumentDbgValue(const Value *V, DILocalVariable *Variable,
691 DIExpression *Expr, DILocation *DL,
692 FuncArgumentDbgValueKind Kind,
693 const SDValue &N);
694
695 /// Return the next block after MBB, or nullptr if there is none.
696 MachineBasicBlock *NextBlock(MachineBasicBlock *MBB);
697
698 /// Update the DAG and DAG builder with the relevant information after
699 /// a new root node has been created which could be a tail call.
700 void updateDAGForMaybeTailCall(SDValue MaybeTC);
701
702 /// Return the appropriate SDDbgValue based on N.
703 SDDbgValue *getDbgValue(SDValue N, DILocalVariable *Variable,
704 DIExpression *Expr, const DebugLoc &dl,
705 unsigned DbgSDNodeOrder);
706
707 /// Lowers CallInst to an external symbol.
708 void lowerCallToExternalSymbol(const CallInst &I, const char *FunctionName);
709
710 SDValue lowerStartEH(SDValue Chain, const BasicBlock *EHPadBB,
711 MCSymbol *&BeginLabel);
712 SDValue lowerEndEH(SDValue Chain, const InvokeInst *II,
713 const BasicBlock *EHPadBB, MCSymbol *BeginLabel);
714};
715
716/// This struct represents the registers (physical or virtual)
717/// that a particular set of values is assigned, and the type information about
718/// the value. The most common situation is to represent one value at a time,
719/// but struct or array values are handled element-wise as multiple values. The
720/// splitting of aggregates is performed recursively, so that we never have
721/// aggregate-typed registers. The values at this point do not necessarily have
722/// legal types, so each value may require one or more registers of some legal
723/// type.
724///
726 /// The value types of the values, which may not be legal, and
727 /// may need be promoted or synthesized from one or more registers.
729
730 /// The value types of the registers. This is the same size as ValueVTs and it
731 /// records, for each value, what the type of the assigned register or
732 /// registers are. (Individual values are never synthesized from more than one
733 /// type of register.)
734 ///
735 /// With virtual registers, the contents of RegVTs is redundant with TLI's
736 /// getRegisterType member function, however when with physical registers
737 /// it is necessary to have a separate record of the types.
739
740 /// This list holds the registers assigned to the values.
741 /// Each legal or promoted value requires one register, and each
742 /// expanded value requires multiple registers.
744
745 /// This list holds the number of registers for each value.
747
748 /// Records if this value needs to be treated in an ABI dependant manner,
749 /// different to normal type legalization.
750 std::optional<CallingConv::ID> CallConv;
751
752 RegsForValue() = default;
753 RegsForValue(const SmallVector<unsigned, 4> &regs, MVT regvt, EVT valuevt,
754 std::optional<CallingConv::ID> CC = std::nullopt);
755 RegsForValue(LLVMContext &Context, const TargetLowering &TLI,
756 const DataLayout &DL, unsigned Reg, Type *Ty,
757 std::optional<CallingConv::ID> CC);
758
759 bool isABIMangled() const { return CallConv.has_value(); }
760
761 /// Add the specified values to this one.
762 void append(const RegsForValue &RHS) {
763 ValueVTs.append(RHS.ValueVTs.begin(), RHS.ValueVTs.end());
764 RegVTs.append(RHS.RegVTs.begin(), RHS.RegVTs.end());
765 Regs.append(RHS.Regs.begin(), RHS.Regs.end());
766 RegCount.push_back(RHS.Regs.size());
767 }
768
769 /// Emit a series of CopyFromReg nodes that copies from this value and returns
770 /// the result as a ValueVTs value. This uses Chain/Flag as the input and
771 /// updates them for the output Chain/Flag. If the Flag pointer is NULL, no
772 /// flag is used.
774 const SDLoc &dl, SDValue &Chain, SDValue *Glue,
775 const Value *V = nullptr) const;
776
777 /// Emit a series of CopyToReg nodes that copies the specified value into the
778 /// registers specified by this object. This uses Chain/Flag as the input and
779 /// updates them for the output Chain/Flag. If the Flag pointer is nullptr, no
780 /// flag is used. If V is not nullptr, then it is used in printing better
781 /// diagnostic messages on error.
782 void getCopyToRegs(SDValue Val, SelectionDAG &DAG, const SDLoc &dl,
783 SDValue &Chain, SDValue *Glue, const Value *V = nullptr,
784 ISD::NodeType PreferredExtendType = ISD::ANY_EXTEND) const;
785
786 /// Add this value to the specified inlineasm node operand list. This adds the
787 /// code marker, matching input operand index (if applicable), and includes
788 /// the number of values added into it.
789 void AddInlineAsmOperands(InlineAsm::Kind Code, bool HasMatching,
790 unsigned MatchingIdx, const SDLoc &dl,
791 SelectionDAG &DAG, std::vector<SDValue> &Ops) const;
792
793 /// Check if the total RegCount is greater than one.
794 bool occupiesMultipleRegs() const {
795 return std::accumulate(RegCount.begin(), RegCount.end(), 0) > 1;
796 }
797
798 /// Return a list of registers and their sizes.
800};
801
802} // end namespace llvm
803
804#endif // LLVM_LIB_CODEGEN_SELECTIONDAG_SELECTIONDAGBUILDER_H
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
RelocType Type
Definition: COFFYAML.cpp:391
This file defines the DenseMap class.
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned Reg
This file implements a map that provides insertion order iteration.
uint64_t IntrinsicInst * II
#define P(N)
const char LLVMTargetMachineRef TM
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file defines the SmallVector class.
This file describes how to lower LLVM code to machine code.
Value * RHS
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
Conditional or Unconditional Branch instruction.
static BranchProbability getUnknown()
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1494
CallBr instruction, tracking function calls that may not return control but instead transfer it to a ...
This class represents a function call, abstracting a target machine's calling convention.
DWARF expression.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
A debug info location.
Definition: DebugLoc.h:33
Class representing an expression and its matching format.
FunctionLoweringInfo - This contains information that is global to a function that is used when lower...
Garbage collection metadata for a single function.
Definition: GCMetadata.h:78
Represents a gc.statepoint intrinsic call.
Definition: Statepoint.h:61
Indirect Branch Instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:454
Invoke instruction.
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:67
Machine Value Type.
Resume the propagation of an exception.
Return a value (possibly void), from a function.
Wrapper class for IR location info (IR ordering and DebugLoc) to be passed into SDNode creation funct...
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
SDAGSwitchLowering(SelectionDAGBuilder *sdb, FunctionLoweringInfo &funcinfo)
void addSuccessorWithProb(MachineBasicBlock *Src, MachineBasicBlock *Dst, BranchProbability Prob=BranchProbability::getUnknown()) override
SelectionDAGBuilder - This is the common target-independent lowering implementation that is parameter...
SDValue getValue(const Value *V)
getValue - Return an SDValue for the given Value.
void addDanglingDebugInfo(SmallVectorImpl< Value * > &Values, DILocalVariable *Var, DIExpression *Expr, bool IsVariadic, DebugLoc DL, unsigned Order)
Register a dbg_value which relies on a Value which we have not yet seen.
void visitDbgInfo(const Instruction &I)
void clearDanglingDebugInfo()
Clear the dangling debug information map.
StackProtectorDescriptor SPDescriptor
A StackProtectorDescriptor structure used to communicate stack protector information in between Selec...
void LowerCallTo(const CallBase &CB, SDValue Callee, bool IsTailCall, bool IsMustTailCall, const BasicBlock *EHPadBB=nullptr, const TargetLowering::PtrAuthInfo *PAI=nullptr)
void clear()
Clear out the current SelectionDAG and the associated state and prepare this SelectionDAGBuilder obje...
MVT getFrameIndexTy()
Returns the type of FrameIndex and TargetFrameIndex nodes.
void visitBitTestHeader(SwitchCG::BitTestBlock &B, MachineBasicBlock *SwitchBB)
visitBitTestHeader - This function emits necessary code to produce value suitable for "bit tests"
void LowerStatepoint(const GCStatepointInst &I, const BasicBlock *EHPadBB=nullptr)
std::unique_ptr< SDAGSwitchLowering > SL
SDValue lowerRangeToAssertZExt(SelectionDAG &DAG, const Instruction &I, SDValue Op)
bool HasTailCall
This is set to true if a call in the current block has been translated as a tail call.
bool ShouldEmitAsBranches(const std::vector< SwitchCG::CaseBlock > &Cases)
If the set of cases should be emitted as a series of branches, return true.
void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB, MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, BranchProbability TProb, BranchProbability FProb, bool InvertCond)
EmitBranchForMergedCondition - Helper method for FindMergedConditions.
void LowerDeoptimizeCall(const CallInst *CI)
void LowerCallSiteWithDeoptBundle(const CallBase *Call, SDValue Callee, const BasicBlock *EHPadBB)
SwiftErrorValueTracking & SwiftError
Information about the swifterror values used throughout the function.
SDValue getNonRegisterValue(const Value *V)
getNonRegisterValue - Return an SDValue for the given Value, but don't look in FuncInfo....
void CopyValueToVirtualRegister(const Value *V, unsigned Reg, ISD::NodeType ExtendType=ISD::ANY_EXTEND)
DenseMap< MachineBasicBlock *, SmallVector< unsigned, 4 > > LPadToCallSiteMap
Map a landing pad to the call site indexes.
void LowerCallSiteWithDeoptBundleImpl(const CallBase *Call, SDValue Callee, const BasicBlock *EHPadBB, bool VarArgDisallowed, bool ForceVoidReturnTy)
void handleDebugDeclare(Value *Address, DILocalVariable *Variable, DIExpression *Expression, DebugLoc DL)
void visitBitTestCase(SwitchCG::BitTestBlock &BB, MachineBasicBlock *NextMBB, BranchProbability BranchProbToNext, unsigned Reg, SwitchCG::BitTestCase &B, MachineBasicBlock *SwitchBB)
visitBitTestCase - this function produces one "bit test"
void setUnusedArgValue(const Value *V, SDValue NewN)
bool shouldKeepJumpConditionsTogether(const FunctionLoweringInfo &FuncInfo, const BranchInst &I, Instruction::BinaryOps Opc, const Value *Lhs, const Value *Rhs, TargetLoweringBase::CondMergingParams Params) const
StatepointLoweringState StatepointLowering
State used while lowering a statepoint sequence (gc_statepoint, gc_relocate, and gc_result).
void init(GCFunctionInfo *gfi, AAResults *AA, AssumptionCache *AC, const TargetLibraryInfo *li)
DenseMap< const Constant *, unsigned > ConstantsOut
SelectionDAGBuilder(SelectionDAG &dag, FunctionLoweringInfo &funcinfo, SwiftErrorValueTracking &swifterror, CodeGenOptLevel ol)
void populateCallLoweringInfo(TargetLowering::CallLoweringInfo &CLI, const CallBase *Call, unsigned ArgIdx, unsigned NumArgs, SDValue Callee, Type *ReturnTy, AttributeSet RetAttrs, bool IsPatchPoint)
Populate a CallLowerinInfo (into CLI) based on the properties of the call being lowered.
void salvageUnresolvedDbgValue(const Value *V, DanglingDebugInfo &DDI)
For the given dangling debuginfo record, perform last-ditch efforts to resolve the debuginfo to somet...
SmallVector< SDValue, 8 > PendingLoads
Loads are not emitted to the program immediately.
GCFunctionInfo * GFI
Garbage collection metadata for the function.
SDValue getRoot()
Similar to getMemoryRoot, but also flushes PendingConstrainedFP(Strict) items.
void ExportFromCurrentBlock(const Value *V)
ExportFromCurrentBlock - If this condition isn't known to be exported from the current basic block,...
void resolveOrClearDbgInfo()
Evict any dangling debug information, attempting to salvage it first.
std::pair< SDValue, SDValue > lowerInvokable(TargetLowering::CallLoweringInfo &CLI, const BasicBlock *EHPadBB=nullptr)
SDValue getMemoryRoot()
Return the current virtual root of the Selection DAG, flushing any PendingLoad items.
void resolveDanglingDebugInfo(const Value *V, SDValue Val)
If we saw an earlier dbg_value referring to V, generate the debug data structures now that we've seen...
void visit(const Instruction &I)
void dropDanglingDebugInfo(const DILocalVariable *Variable, const DIExpression *Expr)
If we have dangling debug info that describes Variable, or an overlapping part of variable considerin...
SDValue getCopyFromRegs(const Value *V, Type *Ty)
If there was virtual register allocated for the value V emit CopyFromReg of the specified type Ty.
void CopyToExportRegsIfNeeded(const Value *V)
CopyToExportRegsIfNeeded - If the given value has virtual registers created for it,...
void handleKillDebugValue(DILocalVariable *Var, DIExpression *Expr, DebugLoc DbgLoc, unsigned Order)
Create a record for a kill location debug intrinsic.
void visitJumpTable(SwitchCG::JumpTable &JT)
visitJumpTable - Emit JumpTable node in the current MBB
void visitJumpTableHeader(SwitchCG::JumpTable &JT, SwitchCG::JumpTableHeader &JTH, MachineBasicBlock *SwitchBB)
visitJumpTableHeader - This function emits necessary code to produce index in the JumpTable from swit...
void LowerCallSiteWithPtrAuthBundle(const CallBase &CB, const BasicBlock *EHPadBB)
static const unsigned LowestSDNodeOrder
Lowest valid SDNodeOrder.
FunctionLoweringInfo & FuncInfo
Information about the function as a whole.
void setValue(const Value *V, SDValue NewN)
void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB, MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, Instruction::BinaryOps Opc, BranchProbability TProb, BranchProbability FProb, bool InvertCond)
const TargetLibraryInfo * LibInfo
bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB)
void visitSPDescriptorParent(StackProtectorDescriptor &SPD, MachineBasicBlock *ParentBB)
Codegen a new tail for a stack protector check ParentMBB which has had its tail spliced into a stack ...
bool handleDebugValue(ArrayRef< const Value * > Values, DILocalVariable *Var, DIExpression *Expr, DebugLoc DbgLoc, unsigned Order, bool IsVariadic)
For a given list of Values, attempt to create and record a SDDbgValue in the SelectionDAG.
SDValue getControlRoot()
Similar to getRoot, but instead of flushing all the PendingLoad items, flush all the PendingExports (...
void UpdateSplitBlock(MachineBasicBlock *First, MachineBasicBlock *Last)
When an MBB was split during scheduling, update the references that need to refer to the last resulti...
SDValue getValueImpl(const Value *V)
getValueImpl - Helper function for getValue and getNonRegisterValue.
void visitSwitchCase(SwitchCG::CaseBlock &CB, MachineBasicBlock *SwitchBB)
visitSwitchCase - Emits the necessary code to represent a single node in the binary search tree resul...
SDValue LowerAsSTATEPOINT(StatepointLoweringInfo &SI)
Lower SLI into a STATEPOINT instruction.
void visitSPDescriptorFailure(StackProtectorDescriptor &SPD)
Codegen the failure basic block for a stack protector check.
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:227
const TargetLowering & getTargetLoweringInfo() const
Definition: SelectionDAG.h:492
const DataLayout & getDataLayout() const
Definition: SelectionDAG.h:486
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:696
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Encapsulates all of the information needed to generate a stack protector check, and signals to isel w...
This class tracks both per-statepoint and per-selectiondag information.
SwitchLowering(FunctionLoweringInfo &funcinfo)
Multiway switch.
Provides information about what library functions are available for the current target.
MVT getFrameIndexTy(const DataLayout &DL) const
Return the type for frame index, which is determined by the alloca address space specified through th...
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:76
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
This function has undefined behavior.
LLVM Value Representation.
Definition: Value.h:74
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
NodeType
ISD::NodeType enum - This enum defines the target-independent operators for a SelectionDAG.
Definition: ISDOpcodes.h:40
@ ADD
Simple integer binary arithmetic operators.
Definition: ISDOpcodes.h:240
@ ANY_EXTEND
ANY_EXTEND - Used for integer types. The high bits are undefined.
Definition: ISDOpcodes.h:785
@ FADD
Simple binary floating point operators.
Definition: ISDOpcodes.h:391
@ FNEG
Perform various unary floating-point operations inspired by libm.
Definition: ISDOpcodes.h:932
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
@ SHL
Shift and rotation operations.
Definition: ISDOpcodes.h:707
@ AND
Bitwise operators - logical and, logical or, logical xor.
Definition: ISDOpcodes.h:682
std::vector< CaseCluster > CaseClusterVector
@ User
could "use" a pointer
NodeAddr< UseNode * > Use
Definition: RDFGraph.h:385
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
CodeGenOptLevel
Code generation optimization level.
Definition: CodeGen.h:54
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
StatepointFlags
The statepoint intrinsic accepts a set of flags as its third argument.
Definition: Statepoint.h:39
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
#define N
Extended Value Type.
Definition: ValueTypes.h:34
This struct represents the registers (physical or virtual) that a particular set of values is assigne...
SmallVector< unsigned, 4 > Regs
This list holds the registers assigned to the values.
RegsForValue()=default
SmallVector< unsigned, 4 > RegCount
This list holds the number of registers for each value.
SmallVector< EVT, 4 > ValueVTs
The value types of the values, which may not be legal, and may need be promoted or synthesized from o...
SmallVector< std::pair< unsigned, TypeSize >, 4 > getRegsAndSizes() const
Return a list of registers and their sizes.
void append(const RegsForValue &RHS)
Add the specified values to this one.
void AddInlineAsmOperands(InlineAsm::Kind Code, bool HasMatching, unsigned MatchingIdx, const SDLoc &dl, SelectionDAG &DAG, std::vector< SDValue > &Ops) const
Add this value to the specified inlineasm node operand list.
SDValue getCopyFromRegs(SelectionDAG &DAG, FunctionLoweringInfo &FuncInfo, const SDLoc &dl, SDValue &Chain, SDValue *Glue, const Value *V=nullptr) const
Emit a series of CopyFromReg nodes that copies from this value and returns the result as a ValueVTs v...
SmallVector< MVT, 4 > RegVTs
The value types of the registers.
void getCopyToRegs(SDValue Val, SelectionDAG &DAG, const SDLoc &dl, SDValue &Chain, SDValue *Glue, const Value *V=nullptr, ISD::NodeType PreferredExtendType=ISD::ANY_EXTEND) const
Emit a series of CopyToReg nodes that copies the specified value into the registers specified by this...
std::optional< CallingConv::ID > CallConv
Records if this value needs to be treated in an ABI dependant manner, different to normal type legali...
bool occupiesMultipleRegs() const
Check if the total RegCount is greater than one.
Print(const Value *V, const DanglingDebugInfo &DDI)
friend raw_ostream & operator<<(raw_ostream &OS, const DanglingDebugInfo::Print &P)
Describes a gc.statepoint or a gc.statepoint like thing for the purposes of lowering into a STATEPOIN...
unsigned NumPatchBytes
The number of patchable bytes the call needs to get lowered into.
ArrayRef< const Use > GCTransitionArgs
The list of gc transition arguments present in the gc.statepoint being lowered.
const BasicBlock * EHPadBB
The exception handling unwind destination, in case this represents an invoke of gc....
ArrayRef< const Use > DeoptState
The deoptimization state associated with this gc.statepoint call, if any.
TargetLowering::CallLoweringInfo CLI
Information regarding the underlying call instruction.
SmallVector< const GCRelocateInst *, 16 > GCRelocates
The set of gc.relocate calls associated with this gc.statepoint.
const Instruction * StatepointInstr
The gc.statepoint instruction.
ArrayRef< const Use > GCArgs
The full list of gc arguments to the gc.statepoint being lowered.
SmallVector< const Value *, 16 > Bases
Bases[i] is the base pointer for Ptrs[i].
This structure is used to communicate between SelectionDAGBuilder and SDISel for the code generation ...
This structure contains all information that is necessary for lowering calls.
This structure contains the information necessary for lowering pointer-authenticating indirect calls.