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