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 MachineBasicBlock *SwitchBB,
392 BranchProbability FProb, bool InvertCond);
395 MachineBasicBlock *CurBB,
396 MachineBasicBlock *SwitchBB,
398 bool InvertCond);
399 bool ShouldEmitAsBranches(const std::vector<SwitchCG::CaseBlock> &Cases);
400 bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB);
401 void CopyToExportRegsIfNeeded(const Value *V);
402 void ExportFromCurrentBlock(const Value *V);
403 void LowerCallTo(const CallBase &CB, SDValue Callee, bool IsTailCall,
404 bool IsMustTailCall, const BasicBlock *EHPadBB = nullptr);
405
406 // Lower range metadata from 0 to N to assert zext to an integer of nearest
407 // floor power of two.
409 SDValue Op);
410
412 const CallBase *Call, unsigned ArgIdx,
413 unsigned NumArgs, SDValue Callee,
414 Type *ReturnTy, AttributeSet RetAttrs,
415 bool IsPatchPoint);
416
417 std::pair<SDValue, SDValue>
419 const BasicBlock *EHPadBB = nullptr);
420
421 /// When an MBB was split during scheduling, update the
422 /// references that need to refer to the last resulting block.
424
425 /// Describes a gc.statepoint or a gc.statepoint like thing for the purposes
426 /// of lowering into a STATEPOINT node.
428 /// Bases[i] is the base pointer for Ptrs[i]. Together they denote the set
429 /// of gc pointers this STATEPOINT has to relocate.
432
433 /// The set of gc.relocate calls associated with this gc.statepoint.
435
436 /// The full list of gc arguments to the gc.statepoint being lowered.
438
439 /// The gc.statepoint instruction.
440 const Instruction *StatepointInstr = nullptr;
441
442 /// The list of gc transition arguments present in the gc.statepoint being
443 /// lowered.
445
446 /// The ID that the resulting STATEPOINT instruction has to report.
447 unsigned ID = -1;
448
449 /// Information regarding the underlying call instruction.
451
452 /// The deoptimization state associated with this gc.statepoint call, if
453 /// any.
455
456 /// Flags associated with the meta arguments being lowered.
458
459 /// The number of patchable bytes the call needs to get lowered into.
460 unsigned NumPatchBytes = -1;
461
462 /// The exception handling unwind destination, in case this represents an
463 /// invoke of gc.statepoint.
464 const BasicBlock *EHPadBB = nullptr;
465
467 };
468
469 /// Lower \p SLI into a STATEPOINT instruction.
470 SDValue LowerAsSTATEPOINT(StatepointLoweringInfo &SI);
471
472 // This function is responsible for the whole statepoint lowering process.
473 // It uniformly handles invoke and call statepoints.
475 const BasicBlock *EHPadBB = nullptr);
476
477 void LowerCallSiteWithDeoptBundle(const CallBase *Call, SDValue Callee,
478 const BasicBlock *EHPadBB);
479
480 void LowerDeoptimizeCall(const CallInst *CI);
482
483 void LowerCallSiteWithDeoptBundleImpl(const CallBase *Call, SDValue Callee,
484 const BasicBlock *EHPadBB,
485 bool VarArgDisallowed,
486 bool ForceVoidReturnTy);
487
488 /// Returns the type of FrameIndex and TargetFrameIndex nodes.
491 }
492
493private:
494 // Terminator instructions.
495 void visitRet(const ReturnInst &I);
496 void visitBr(const BranchInst &I);
497 void visitSwitch(const SwitchInst &I);
498 void visitIndirectBr(const IndirectBrInst &I);
499 void visitUnreachable(const UnreachableInst &I);
500 void visitCleanupRet(const CleanupReturnInst &I);
501 void visitCatchSwitch(const CatchSwitchInst &I);
502 void visitCatchRet(const CatchReturnInst &I);
503 void visitCatchPad(const CatchPadInst &I);
504 void visitCleanupPad(const CleanupPadInst &CPI);
505
506 BranchProbability getEdgeProbability(const MachineBasicBlock *Src,
507 const MachineBasicBlock *Dst) const;
508 void addSuccessorWithProb(
511
512public:
515 MachineBasicBlock *ParentBB);
518 MachineBasicBlock *SwitchBB);
520 BranchProbability BranchProbToNext, unsigned Reg,
525 MachineBasicBlock *SwitchBB);
526
527private:
528 // These all get lowered before this pass.
529 void visitInvoke(const InvokeInst &I);
530 void visitCallBr(const CallBrInst &I);
531 void visitCallBrLandingPad(const CallInst &I);
532 void visitResume(const ResumeInst &I);
533
534 void visitUnary(const User &I, unsigned Opcode);
535 void visitFNeg(const User &I) { visitUnary(I, ISD::FNEG); }
536
537 void visitBinary(const User &I, unsigned Opcode);
538 void visitShift(const User &I, unsigned Opcode);
539 void visitAdd(const User &I) { visitBinary(I, ISD::ADD); }
540 void visitFAdd(const User &I) { visitBinary(I, ISD::FADD); }
541 void visitSub(const User &I) { visitBinary(I, ISD::SUB); }
542 void visitFSub(const User &I) { visitBinary(I, ISD::FSUB); }
543 void visitMul(const User &I) { visitBinary(I, ISD::MUL); }
544 void visitFMul(const User &I) { visitBinary(I, ISD::FMUL); }
545 void visitURem(const User &I) { visitBinary(I, ISD::UREM); }
546 void visitSRem(const User &I) { visitBinary(I, ISD::SREM); }
547 void visitFRem(const User &I) { visitBinary(I, ISD::FREM); }
548 void visitUDiv(const User &I) { visitBinary(I, ISD::UDIV); }
549 void visitSDiv(const User &I);
550 void visitFDiv(const User &I) { visitBinary(I, ISD::FDIV); }
551 void visitAnd (const User &I) { visitBinary(I, ISD::AND); }
552 void visitOr (const User &I) { visitBinary(I, ISD::OR); }
553 void visitXor (const User &I) { visitBinary(I, ISD::XOR); }
554 void visitShl (const User &I) { visitShift(I, ISD::SHL); }
555 void visitLShr(const User &I) { visitShift(I, ISD::SRL); }
556 void visitAShr(const User &I) { visitShift(I, ISD::SRA); }
557 void visitICmp(const User &I);
558 void visitFCmp(const User &I);
559 // Visit the conversion instructions
560 void visitTrunc(const User &I);
561 void visitZExt(const User &I);
562 void visitSExt(const User &I);
563 void visitFPTrunc(const User &I);
564 void visitFPExt(const User &I);
565 void visitFPToUI(const User &I);
566 void visitFPToSI(const User &I);
567 void visitUIToFP(const User &I);
568 void visitSIToFP(const User &I);
569 void visitPtrToInt(const User &I);
570 void visitIntToPtr(const User &I);
571 void visitBitCast(const User &I);
572 void visitAddrSpaceCast(const User &I);
573
574 void visitExtractElement(const User &I);
575 void visitInsertElement(const User &I);
576 void visitShuffleVector(const User &I);
577
578 void visitExtractValue(const ExtractValueInst &I);
579 void visitInsertValue(const InsertValueInst &I);
580 void visitLandingPad(const LandingPadInst &LP);
581
582 void visitGetElementPtr(const User &I);
583 void visitSelect(const User &I);
584
585 void visitAlloca(const AllocaInst &I);
586 void visitLoad(const LoadInst &I);
587 void visitStore(const StoreInst &I);
588 void visitMaskedLoad(const CallInst &I, bool IsExpanding = false);
589 void visitMaskedStore(const CallInst &I, bool IsCompressing = false);
590 void visitMaskedGather(const CallInst &I);
591 void visitMaskedScatter(const CallInst &I);
592 void visitAtomicCmpXchg(const AtomicCmpXchgInst &I);
593 void visitAtomicRMW(const AtomicRMWInst &I);
594 void visitFence(const FenceInst &I);
595 void visitPHI(const PHINode &I);
596 void visitCall(const CallInst &I);
597 bool visitMemCmpBCmpCall(const CallInst &I);
598 bool visitMemPCpyCall(const CallInst &I);
599 bool visitMemChrCall(const CallInst &I);
600 bool visitStrCpyCall(const CallInst &I, bool isStpcpy);
601 bool visitStrCmpCall(const CallInst &I);
602 bool visitStrLenCall(const CallInst &I);
603 bool visitStrNLenCall(const CallInst &I);
604 bool visitUnaryFloatCall(const CallInst &I, unsigned Opcode);
605 bool visitBinaryFloatCall(const CallInst &I, unsigned Opcode);
606 void visitAtomicLoad(const LoadInst &I);
607 void visitAtomicStore(const StoreInst &I);
608 void visitLoadFromSwiftError(const LoadInst &I);
609 void visitStoreToSwiftError(const StoreInst &I);
610 void visitFreeze(const FreezeInst &I);
611
612 void visitInlineAsm(const CallBase &Call,
613 const BasicBlock *EHPadBB = nullptr);
614
615 bool visitEntryValueDbgValue(ArrayRef<const Value *> Values,
616 DILocalVariable *Variable, DIExpression *Expr,
617 DebugLoc DbgLoc);
618 void visitIntrinsicCall(const CallInst &I, unsigned Intrinsic);
619 void visitTargetIntrinsic(const CallInst &I, unsigned Intrinsic);
620 void visitConstrainedFPIntrinsic(const ConstrainedFPIntrinsic &FPI);
621 void visitVPLoad(const VPIntrinsic &VPIntrin, EVT VT,
622 const SmallVectorImpl<SDValue> &OpValues);
623 void visitVPStore(const VPIntrinsic &VPIntrin,
624 const SmallVectorImpl<SDValue> &OpValues);
625 void visitVPGather(const VPIntrinsic &VPIntrin, EVT VT,
626 const SmallVectorImpl<SDValue> &OpValues);
627 void visitVPScatter(const VPIntrinsic &VPIntrin,
628 const SmallVectorImpl<SDValue> &OpValues);
629 void visitVPStridedLoad(const VPIntrinsic &VPIntrin, EVT VT,
630 const SmallVectorImpl<SDValue> &OpValues);
631 void visitVPStridedStore(const VPIntrinsic &VPIntrin,
632 const SmallVectorImpl<SDValue> &OpValues);
633 void visitVPCmp(const VPCmpIntrinsic &VPIntrin);
634 void visitVectorPredicationIntrinsic(const VPIntrinsic &VPIntrin);
635
636 void visitVAStart(const CallInst &I);
637 void visitVAArg(const VAArgInst &I);
638 void visitVAEnd(const CallInst &I);
639 void visitVACopy(const CallInst &I);
640 void visitStackmap(const CallInst &I);
641 void visitPatchpoint(const CallBase &CB, const BasicBlock *EHPadBB = nullptr);
642
643 // These two are implemented in StatepointLowering.cpp
644 void visitGCRelocate(const GCRelocateInst &Relocate);
645 void visitGCResult(const GCResultInst &I);
646
647 void visitVectorReduce(const CallInst &I, unsigned Intrinsic);
648 void visitVectorReverse(const CallInst &I);
649 void visitVectorSplice(const CallInst &I);
650 void visitVectorInterleave(const CallInst &I);
651 void visitVectorDeinterleave(const CallInst &I);
652 void visitStepVector(const CallInst &I);
653
654 void visitUserOp1(const Instruction &I) {
655 llvm_unreachable("UserOp1 should not exist at instruction selection time!");
656 }
657 void visitUserOp2(const Instruction &I) {
658 llvm_unreachable("UserOp2 should not exist at instruction selection time!");
659 }
660
661 void processIntegerCallValue(const Instruction &I,
662 SDValue Value, bool IsSigned);
663
664 void HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB);
665
666 void emitInlineAsmError(const CallBase &Call, const Twine &Message);
667
668 /// An enum that states to emit func argument dbg value the kind of intrinsic
669 /// it originally had. This controls the internal behavior of
670 /// EmitFuncArgumentDbgValue.
671 enum class FuncArgumentDbgValueKind {
672 Value, // This was originally a llvm.dbg.value.
673 Declare, // This was originally a llvm.dbg.declare.
674 };
675
676 /// If V is an function argument then create corresponding DBG_VALUE machine
677 /// instruction for it now. At the end of instruction selection, they will be
678 /// inserted to the entry BB.
679 bool EmitFuncArgumentDbgValue(const Value *V, DILocalVariable *Variable,
680 DIExpression *Expr, DILocation *DL,
681 FuncArgumentDbgValueKind Kind,
682 const SDValue &N);
683
684 /// Return the next block after MBB, or nullptr if there is none.
685 MachineBasicBlock *NextBlock(MachineBasicBlock *MBB);
686
687 /// Update the DAG and DAG builder with the relevant information after
688 /// a new root node has been created which could be a tail call.
689 void updateDAGForMaybeTailCall(SDValue MaybeTC);
690
691 /// Return the appropriate SDDbgValue based on N.
692 SDDbgValue *getDbgValue(SDValue N, DILocalVariable *Variable,
693 DIExpression *Expr, const DebugLoc &dl,
694 unsigned DbgSDNodeOrder);
695
696 /// Lowers CallInst to an external symbol.
697 void lowerCallToExternalSymbol(const CallInst &I, const char *FunctionName);
698
699 SDValue lowerStartEH(SDValue Chain, const BasicBlock *EHPadBB,
700 MCSymbol *&BeginLabel);
701 SDValue lowerEndEH(SDValue Chain, const InvokeInst *II,
702 const BasicBlock *EHPadBB, MCSymbol *BeginLabel);
703};
704
705/// This struct represents the registers (physical or virtual)
706/// that a particular set of values is assigned, and the type information about
707/// the value. The most common situation is to represent one value at a time,
708/// but struct or array values are handled element-wise as multiple values. The
709/// splitting of aggregates is performed recursively, so that we never have
710/// aggregate-typed registers. The values at this point do not necessarily have
711/// legal types, so each value may require one or more registers of some legal
712/// type.
713///
715 /// The value types of the values, which may not be legal, and
716 /// may need be promoted or synthesized from one or more registers.
718
719 /// The value types of the registers. This is the same size as ValueVTs and it
720 /// records, for each value, what the type of the assigned register or
721 /// registers are. (Individual values are never synthesized from more than one
722 /// type of register.)
723 ///
724 /// With virtual registers, the contents of RegVTs is redundant with TLI's
725 /// getRegisterType member function, however when with physical registers
726 /// it is necessary to have a separate record of the types.
728
729 /// This list holds the registers assigned to the values.
730 /// Each legal or promoted value requires one register, and each
731 /// expanded value requires multiple registers.
733
734 /// This list holds the number of registers for each value.
736
737 /// Records if this value needs to be treated in an ABI dependant manner,
738 /// different to normal type legalization.
739 std::optional<CallingConv::ID> CallConv;
740
741 RegsForValue() = default;
742 RegsForValue(const SmallVector<unsigned, 4> &regs, MVT regvt, EVT valuevt,
743 std::optional<CallingConv::ID> CC = std::nullopt);
744 RegsForValue(LLVMContext &Context, const TargetLowering &TLI,
745 const DataLayout &DL, unsigned Reg, Type *Ty,
746 std::optional<CallingConv::ID> CC);
747
748 bool isABIMangled() const { return CallConv.has_value(); }
749
750 /// Add the specified values to this one.
751 void append(const RegsForValue &RHS) {
752 ValueVTs.append(RHS.ValueVTs.begin(), RHS.ValueVTs.end());
753 RegVTs.append(RHS.RegVTs.begin(), RHS.RegVTs.end());
754 Regs.append(RHS.Regs.begin(), RHS.Regs.end());
755 RegCount.push_back(RHS.Regs.size());
756 }
757
758 /// Emit a series of CopyFromReg nodes that copies from this value and returns
759 /// the result as a ValueVTs value. This uses Chain/Flag as the input and
760 /// updates them for the output Chain/Flag. If the Flag pointer is NULL, no
761 /// flag is used.
763 const SDLoc &dl, SDValue &Chain, SDValue *Glue,
764 const Value *V = nullptr) const;
765
766 /// Emit a series of CopyToReg nodes that copies the specified value into the
767 /// registers specified by this object. This uses Chain/Flag as the input and
768 /// updates them for the output Chain/Flag. If the Flag pointer is nullptr, no
769 /// flag is used. If V is not nullptr, then it is used in printing better
770 /// diagnostic messages on error.
771 void getCopyToRegs(SDValue Val, SelectionDAG &DAG, const SDLoc &dl,
772 SDValue &Chain, SDValue *Glue, const Value *V = nullptr,
773 ISD::NodeType PreferredExtendType = ISD::ANY_EXTEND) const;
774
775 /// Add this value to the specified inlineasm node operand list. This adds the
776 /// code marker, matching input operand index (if applicable), and includes
777 /// the number of values added into it.
778 void AddInlineAsmOperands(InlineAsm::Kind Code, bool HasMatching,
779 unsigned MatchingIdx, const SDLoc &dl,
780 SelectionDAG &DAG, std::vector<SDValue> &Ops) const;
781
782 /// Check if the total RegCount is greater than one.
783 bool occupiesMultipleRegs() const {
784 return std::accumulate(RegCount.begin(), RegCount.end(), 0) > 1;
785 }
786
787 /// Return a list of registers and their sizes.
789};
790
791} // end namespace llvm
792
793#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.
#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:1457
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:452
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 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)
void LowerCallTo(const CallBase &CB, SDValue Callee, bool IsTailCall, bool IsMustTailCall, const BasicBlock *EHPadBB=nullptr)
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...
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:225
const TargetLowering & getTargetLoweringInfo() const
Definition: SelectionDAG.h:478
const DataLayout & getDataLayout() const
Definition: SelectionDAG.h:472
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:239
@ ANY_EXTEND
ANY_EXTEND - Used for integer types. The high bits are undefined.
Definition: ISDOpcodes.h:783
@ FADD
Simple binary floating point operators.
Definition: ISDOpcodes.h:390
@ FNEG
Perform various unary floating-point operations inspired by libm.
Definition: ISDOpcodes.h:928
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
@ SHL
Shift and rotation operations.
Definition: ISDOpcodes.h:705
@ AND
Bitwise operators - logical and, logical or, logical xor.
Definition: ISDOpcodes.h:680
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.