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"
20#include "llvm/ADT/SmallVector.h"
21#include "llvm/CodeGen/AssignmentTrackingAnalysis.h"
22#include "llvm/CodeGen/CodeGenCommonISel.h"
23#include "llvm/CodeGen/ISDOpcodes.h"
24#include "llvm/CodeGen/SelectionDAGNodes.h"
25#include "llvm/CodeGen/SwitchLoweringUtils.h"
26#include "llvm/CodeGen/TargetLowering.h"
27#include "llvm/CodeGen/ValueTypes.h"
28#include "llvm/CodeGenTypes/MachineValueType.h"
29#include "llvm/IR/DebugLoc.h"
30#include "llvm/IR/Instruction.h"
31#include "llvm/Support/BranchProbability.h"
32#include "llvm/Support/CodeGen.h"
33#include "llvm/Support/ErrorHandling.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///
97class SelectionDAGBuilder {
98 /// The current instruction being visited.
99 const Instruction *CurInst = nullptr;
100
101 DenseMap<const Value*, SDValue> NodeMap;
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;
113 DIExpression *Expression;
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;
133 friend raw_ostream &operator<<(raw_ostream &OS,
134 const DanglingDebugInfo::Print &P) {
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.
172 SmallVector<SDValue, 8> PendingLoads;
173
174 /// State used while lowering a statepoint sequence (gc_statepoint,
175 /// gc_relocate, and gc_result). See StatepointLowering.hpp/cpp for details.
176 StatepointLoweringState StatepointLowering;
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,
205 const SwitchCG::SwitchWorkListItem &W, Value *Cond,
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
214 MachineBasicBlock *
215 peelDominantCaseCluster(const SwitchInst &SI,
216 SwitchCG::CaseClusterVector &Clusters,
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
227 SelectionDAG &DAG;
228 AAResults *AA = nullptr;
229 AssumptionCache *AC = nullptr;
230 const TargetLibraryInfo *LibInfo = nullptr;
231
232 class SDAGSwitchLowering : public SwitchCG::SwitchLowering {
233 public:
234 SDAGSwitchLowering(SelectionDAGBuilder *sdb, FunctionLoweringInfo &funcinfo)
235 : SwitchCG::SwitchLowering(funcinfo), SDB(sdb) {}
236
237 void addSuccessorWithProb(
238 MachineBasicBlock *Src, MachineBasicBlock *Dst,
239 BranchProbability Prob = BranchProbability::getUnknown()) override {
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.
253 StackProtectorDescriptor SPDescriptor;
254
255 // Emit PHI-node-operand constants only once even if used by multiple
256 // PHI nodes.
257 DenseMap<const Constant *, unsigned> ConstantsOut;
258
259 /// Information about the function as a whole.
260 FunctionLoweringInfo &FuncInfo;
261
262 /// Information about the swifterror values used throughout the function.
263 SwiftErrorValueTracking &SwiftError;
264
265 /// Garbage collection metadata for the function.
266 GCFunctionInfo *GFI = nullptr;
267
268 /// Map a landing pad to the call site indexes.
269 DenseMap<MachineBasicBlock *, SmallVector<unsigned, 4>> LPadToCallSiteMap;
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
275 LLVMContext *Context = nullptr;
276
277 SelectionDAGBuilder(SelectionDAG &dag, FunctionLoweringInfo &funcinfo,
278 SwiftErrorValueTracking &swifterror, CodeGenOptLevel ol)
279 : SDNodeOrder(LowestSDNodeOrder), TM(dag.getTarget()), DAG(dag),
280 SL(std::make_unique<SDAGSwitchLowering>(args: this, args&: funcinfo)),
281 FuncInfo(funcinfo), SwiftError(swifterror) {}
282
283 void init(GCFunctionInfo *gfi, AAResults *AA, AssumptionCache *AC,
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.
297 void clearDanglingDebugInfo();
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.
302 SDValue getMemoryRoot();
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.
308 SDValue getRoot();
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.
313 SDValue getControlRoot();
314
315 SDLoc getCurSDLoc() const {
316 return SDLoc(CurInst, SDNodeOrder);
317 }
318
319 DebugLoc getCurDebugLoc() const {
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.
336 void addDanglingDebugInfo(SmallVectorImpl<Value *> &Values,
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.
357 bool handleDebugValue(ArrayRef<const Value *> Values, DILocalVariable *Var,
358 DIExpression *Expr, DebugLoc DbgLoc, unsigned Order,
359 bool IsVariadic);
360
361 /// Create a record for a kill location debug intrinsic.
362 void handleKillDebugValue(DILocalVariable *Var, DIExpression *Expr,
363 DebugLoc DbgLoc, unsigned Order);
364
365 void handleDebugDeclare(Value *Address, DILocalVariable *Variable,
366 DIExpression *Expression, DebugLoc DL);
367
368 /// Evict any dangling debug information, attempting to salvage it first.
369 void resolveOrClearDbgInfo();
370
371 SDValue getValue(const Value *V);
372
373 SDValue getNonRegisterValue(const Value *V);
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
388 void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB,
389 MachineBasicBlock *FBB, MachineBasicBlock *CurBB,
390 MachineBasicBlock *SwitchBB,
391 Instruction::BinaryOps Opc, BranchProbability TProb,
392 BranchProbability FProb, bool InvertCond);
393 void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB,
394 MachineBasicBlock *FBB,
395 MachineBasicBlock *CurBB,
396 MachineBasicBlock *SwitchBB,
397 BranchProbability TProb, BranchProbability FProb,
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.
408 SDValue lowerRangeToAssertZExt(SelectionDAG &DAG, const Instruction &I,
409 SDValue Op);
410
411 void populateCallLoweringInfo(TargetLowering::CallLoweringInfo &CLI,
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>
418 lowerInvokable(TargetLowering::CallLoweringInfo &CLI,
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.
423 void UpdateSplitBlock(MachineBasicBlock *First, MachineBasicBlock *Last);
424
425 /// Describes a gc.statepoint or a gc.statepoint like thing for the purposes
426 /// of lowering into a STATEPOINT node.
427 struct StatepointLoweringInfo {
428 /// Bases[i] is the base pointer for Ptrs[i]. Together they denote the set
429 /// of gc pointers this STATEPOINT has to relocate.
430 SmallVector<const Value *, 16> Bases;
431 SmallVector<const Value *, 16> Ptrs;
432
433 /// The set of gc.relocate calls associated with this gc.statepoint.
434 SmallVector<const GCRelocateInst *, 16> GCRelocates;
435
436 /// The full list of gc arguments to the gc.statepoint being lowered.
437 ArrayRef<const Use> GCArgs;
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.
444 ArrayRef<const Use> GCTransitionArgs;
445
446 /// The ID that the resulting STATEPOINT instruction has to report.
447 unsigned ID = -1;
448
449 /// Information regarding the underlying call instruction.
450 TargetLowering::CallLoweringInfo CLI;
451
452 /// The deoptimization state associated with this gc.statepoint call, if
453 /// any.
454 ArrayRef<const Use> DeoptState;
455
456 /// Flags associated with the meta arguments being lowered.
457 uint64_t StatepointFlags = -1;
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
466 explicit StatepointLoweringInfo(SelectionDAG &DAG) : CLI(DAG) {}
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.
474 void LowerStatepoint(const GCStatepointInst &I,
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);
481 void LowerDeoptimizingReturn();
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.
489 MVT getFrameIndexTy() {
490 return DAG.getTargetLoweringInfo().getFrameIndexTy(DL: DAG.getDataLayout());
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(
509 MachineBasicBlock *Src, MachineBasicBlock *Dst,
510 BranchProbability Prob = BranchProbability::getUnknown());
511
512public:
513 void visitSwitchCase(SwitchCG::CaseBlock &CB, MachineBasicBlock *SwitchBB);
514 void visitSPDescriptorParent(StackProtectorDescriptor &SPD,
515 MachineBasicBlock *ParentBB);
516 void visitSPDescriptorFailure(StackProtectorDescriptor &SPD);
517 void visitBitTestHeader(SwitchCG::BitTestBlock &B,
518 MachineBasicBlock *SwitchBB);
519 void visitBitTestCase(SwitchCG::BitTestBlock &BB, MachineBasicBlock *NextMBB,
520 BranchProbability BranchProbToNext, unsigned Reg,
521 SwitchCG::BitTestCase &B, MachineBasicBlock *SwitchBB);
522 void visitJumpTable(SwitchCG::JumpTable &JT);
523 void visitJumpTableHeader(SwitchCG::JumpTable &JT,
524 SwitchCG::JumpTableHeader &JTH,
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, Opcode: 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, Opcode: ISD::ADD); }
540 void visitFAdd(const User &I) { visitBinary(I, Opcode: ISD::FADD); }
541 void visitSub(const User &I) { visitBinary(I, Opcode: ISD::SUB); }
542 void visitFSub(const User &I) { visitBinary(I, Opcode: ISD::FSUB); }
543 void visitMul(const User &I) { visitBinary(I, Opcode: ISD::MUL); }
544 void visitFMul(const User &I) { visitBinary(I, Opcode: ISD::FMUL); }
545 void visitURem(const User &I) { visitBinary(I, Opcode: ISD::UREM); }
546 void visitSRem(const User &I) { visitBinary(I, Opcode: ISD::SREM); }
547 void visitFRem(const User &I) { visitBinary(I, Opcode: ISD::FREM); }
548 void visitUDiv(const User &I) { visitBinary(I, Opcode: ISD::UDIV); }
549 void visitSDiv(const User &I);
550 void visitFDiv(const User &I) { visitBinary(I, Opcode: ISD::FDIV); }
551 void visitAnd (const User &I) { visitBinary(I, Opcode: ISD::AND); }
552 void visitOr (const User &I) { visitBinary(I, Opcode: ISD::OR); }
553 void visitXor (const User &I) { visitBinary(I, Opcode: ISD::XOR); }
554 void visitShl (const User &I) { visitShift(I, Opcode: ISD::SHL); }
555 void visitLShr(const User &I) { visitShift(I, Opcode: ISD::SRL); }
556 void visitAShr(const User &I) { visitShift(I, Opcode: 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///
714struct RegsForValue {
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.
717 SmallVector<EVT, 4> ValueVTs;
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.
727 SmallVector<MVT, 4> RegVTs;
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.
732 SmallVector<unsigned, 4> Regs;
733
734 /// This list holds the number of registers for each value.
735 SmallVector<unsigned, 4> RegCount;
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(in_start: RHS.ValueVTs.begin(), in_end: RHS.ValueVTs.end());
753 RegVTs.append(in_start: RHS.RegVTs.begin(), in_end: RHS.RegVTs.end());
754 Regs.append(in_start: RHS.Regs.begin(), in_end: RHS.Regs.end());
755 RegCount.push_back(Elt: 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.
762 SDValue getCopyFromRegs(SelectionDAG &DAG, FunctionLoweringInfo &FuncInfo,
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(first: RegCount.begin(), last: RegCount.end(), init: 0) > 1;
785 }
786
787 /// Return a list of registers and their sizes.
788 SmallVector<std::pair<unsigned, TypeSize>, 4> getRegsAndSizes() const;
789};
790
791} // end namespace llvm
792
793#endif // LLVM_LIB_CODEGEN_SELECTIONDAG_SELECTIONDAGBUILDER_H
794

source code of llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h