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/IR/DebugLoc.h" 29 #include "llvm/IR/Instruction.h" 30 #include "llvm/Support/BranchProbability.h" 31 #include "llvm/Support/CodeGen.h" 32 #include "llvm/Support/ErrorHandling.h" 33 #include "llvm/Support/MachineValueType.h" 34 #include <algorithm> 35 #include <cassert> 36 #include <cstdint> 37 #include <optional> 38 #include <utility> 39 #include <vector> 40 41 namespace llvm { 42 43 class AAResults; 44 class AllocaInst; 45 class AtomicCmpXchgInst; 46 class AtomicRMWInst; 47 class AssumptionCache; 48 class BasicBlock; 49 class BranchInst; 50 class CallInst; 51 class CallBrInst; 52 class CatchPadInst; 53 class CatchReturnInst; 54 class CatchSwitchInst; 55 class CleanupPadInst; 56 class CleanupReturnInst; 57 class Constant; 58 class ConstrainedFPIntrinsic; 59 class DbgValueInst; 60 class DataLayout; 61 class DIExpression; 62 class DILocalVariable; 63 class DILocation; 64 class FenceInst; 65 class FunctionLoweringInfo; 66 class GCFunctionInfo; 67 class GCRelocateInst; 68 class GCResultInst; 69 class GCStatepointInst; 70 class IndirectBrInst; 71 class InvokeInst; 72 class LandingPadInst; 73 class LLVMContext; 74 class LoadInst; 75 class MachineBasicBlock; 76 class PHINode; 77 class ResumeInst; 78 class ReturnInst; 79 class SDDbgValue; 80 class SelectionDAG; 81 class StoreInst; 82 class SwiftErrorValueTracking; 83 class SwitchInst; 84 class TargetLibraryInfo; 85 class TargetMachine; 86 class Type; 87 class VAArgInst; 88 class UnreachableInst; 89 class Use; 90 class User; 91 class Value; 92 93 //===----------------------------------------------------------------------===// 94 /// SelectionDAGBuilder - This is the common target-independent lowering 95 /// implementation that is parameterized by a TargetLowering object. 96 /// 97 class 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 using DbgValTy = const DbgValueInst *; 110 using VarLocTy = const VarLocInfo *; 111 PointerUnion<DbgValTy, VarLocTy> Info; 112 unsigned SDNodeOrder = 0; 113 114 public: 115 DanglingDebugInfo() = default; 116 DanglingDebugInfo(const DbgValueInst *DI, unsigned SDNO) 117 : Info(DI), SDNodeOrder(SDNO) {} 118 DanglingDebugInfo(const VarLocInfo *VarLoc, unsigned SDNO) 119 : Info(VarLoc), SDNodeOrder(SDNO) {} 120 121 DILocalVariable *getVariable(const FunctionVarLocs *Locs) const { 122 if (Info.is<VarLocTy>()) 123 return Locs->getDILocalVariable(Info.get<VarLocTy>()->VariableID); 124 return Info.get<DbgValTy>()->getVariable(); 125 } 126 DIExpression *getExpression() const { 127 if (Info.is<VarLocTy>()) 128 return Info.get<VarLocTy>()->Expr; 129 return Info.get<DbgValTy>()->getExpression(); 130 } 131 Value *getVariableLocationOp(unsigned Idx) const { 132 assert(Idx == 0 && "Dangling variadic debug values not supported yet"); 133 if (Info.is<VarLocTy>()) 134 return Info.get<VarLocTy>()->V; 135 return Info.get<DbgValTy>()->getVariableLocationOp(Idx); 136 } 137 DebugLoc getDebugLoc() const { 138 if (Info.is<VarLocTy>()) 139 return Info.get<VarLocTy>()->DL; 140 return Info.get<DbgValTy>()->getDebugLoc(); 141 } 142 unsigned getSDNodeOrder() const { return SDNodeOrder; } 143 144 /// Helper for printing DanglingDebugInfo. This hoop-jumping is to 145 /// accommodate the fact that an argument is required for getVariable. 146 /// Call SelectionDAGBuilder::printDDI instead of using directly. 147 struct Print { 148 Print(const DanglingDebugInfo &DDI, const FunctionVarLocs *VarLocs) 149 : DDI(DDI), VarLocs(VarLocs) {} 150 const DanglingDebugInfo &DDI; 151 const FunctionVarLocs *VarLocs; 152 friend raw_ostream &operator<<(raw_ostream &OS, 153 const DanglingDebugInfo::Print &P) { 154 OS << "DDI(var=" << *P.DDI.getVariable(P.VarLocs) 155 << ", val= " << *P.DDI.getVariableLocationOp(0) 156 << ", expr=" << *P.DDI.getExpression() 157 << ", order=" << P.DDI.getSDNodeOrder() 158 << ", loc=" << P.DDI.getDebugLoc() << ")"; 159 return OS; 160 } 161 }; 162 }; 163 164 /// Returns an object that defines `raw_ostream &operator<<` for printing. 165 /// Usage example: 166 //// errs() << printDDI(MyDanglingInfo) << " is dangling\n"; 167 DanglingDebugInfo::Print printDDI(const DanglingDebugInfo &DDI) { 168 return DanglingDebugInfo::Print(DDI, DAG.getFunctionVarLocs()); 169 } 170 171 /// Helper type for DanglingDebugInfoMap. 172 typedef std::vector<DanglingDebugInfo> DanglingDebugInfoVector; 173 174 /// Keeps track of dbg_values for which we have not yet seen the referent. 175 /// We defer handling these until we do see it. 176 MapVector<const Value*, DanglingDebugInfoVector> DanglingDebugInfoMap; 177 178 public: 179 /// Loads are not emitted to the program immediately. We bunch them up and 180 /// then emit token factor nodes when possible. This allows us to get simple 181 /// disambiguation between loads without worrying about alias analysis. 182 SmallVector<SDValue, 8> PendingLoads; 183 184 /// State used while lowering a statepoint sequence (gc_statepoint, 185 /// gc_relocate, and gc_result). See StatepointLowering.hpp/cpp for details. 186 StatepointLoweringState StatepointLowering; 187 188 private: 189 /// CopyToReg nodes that copy values to virtual registers for export to other 190 /// blocks need to be emitted before any terminator instruction, but they have 191 /// no other ordering requirements. We bunch them up and the emit a single 192 /// tokenfactor for them just before terminator instructions. 193 SmallVector<SDValue, 8> PendingExports; 194 195 /// Similar to loads, nodes corresponding to constrained FP intrinsics are 196 /// bunched up and emitted when necessary. These can be moved across each 197 /// other and any (normal) memory operation (load or store), but not across 198 /// calls or instructions having unspecified side effects. As a special 199 /// case, constrained FP intrinsics using fpexcept.strict may not be deleted 200 /// even if otherwise unused, so they need to be chained before any 201 /// terminator instruction (like PendingExports). We track the latter 202 /// set of nodes in a separate list. 203 SmallVector<SDValue, 8> PendingConstrainedFP; 204 SmallVector<SDValue, 8> PendingConstrainedFPStrict; 205 206 /// Update root to include all chains from the Pending list. 207 SDValue updateRoot(SmallVectorImpl<SDValue> &Pending); 208 209 /// A unique monotonically increasing number used to order the SDNodes we 210 /// create. 211 unsigned SDNodeOrder; 212 213 /// Determine the rank by weight of CC in [First,Last]. If CC has more weight 214 /// than each cluster in the range, its rank is 0. 215 unsigned caseClusterRank(const SwitchCG::CaseCluster &CC, 216 SwitchCG::CaseClusterIt First, 217 SwitchCG::CaseClusterIt Last); 218 219 /// Emit comparison and split W into two subtrees. 220 void splitWorkItem(SwitchCG::SwitchWorkList &WorkList, 221 const SwitchCG::SwitchWorkListItem &W, Value *Cond, 222 MachineBasicBlock *SwitchMBB); 223 224 /// Lower W. 225 void lowerWorkItem(SwitchCG::SwitchWorkListItem W, Value *Cond, 226 MachineBasicBlock *SwitchMBB, 227 MachineBasicBlock *DefaultMBB); 228 229 /// Peel the top probability case if it exceeds the threshold 230 MachineBasicBlock * 231 peelDominantCaseCluster(const SwitchInst &SI, 232 SwitchCG::CaseClusterVector &Clusters, 233 BranchProbability &PeeledCaseProb); 234 235 private: 236 const TargetMachine &TM; 237 238 public: 239 /// Lowest valid SDNodeOrder. The special case 0 is reserved for scheduling 240 /// nodes without a corresponding SDNode. 241 static const unsigned LowestSDNodeOrder = 1; 242 243 SelectionDAG &DAG; 244 AAResults *AA = nullptr; 245 AssumptionCache *AC = nullptr; 246 const TargetLibraryInfo *LibInfo; 247 248 class SDAGSwitchLowering : public SwitchCG::SwitchLowering { 249 public: 250 SDAGSwitchLowering(SelectionDAGBuilder *sdb, FunctionLoweringInfo &funcinfo) 251 : SwitchCG::SwitchLowering(funcinfo), SDB(sdb) {} 252 253 void addSuccessorWithProb( 254 MachineBasicBlock *Src, MachineBasicBlock *Dst, 255 BranchProbability Prob = BranchProbability::getUnknown()) override { 256 SDB->addSuccessorWithProb(Src, Dst, Prob); 257 } 258 259 private: 260 SelectionDAGBuilder *SDB; 261 }; 262 263 // Data related to deferred switch lowerings. Used to construct additional 264 // Basic Blocks in SelectionDAGISel::FinishBasicBlock. 265 std::unique_ptr<SDAGSwitchLowering> SL; 266 267 /// A StackProtectorDescriptor structure used to communicate stack protector 268 /// information in between SelectBasicBlock and FinishBasicBlock. 269 StackProtectorDescriptor SPDescriptor; 270 271 // Emit PHI-node-operand constants only once even if used by multiple 272 // PHI nodes. 273 DenseMap<const Constant *, unsigned> ConstantsOut; 274 275 /// Information about the function as a whole. 276 FunctionLoweringInfo &FuncInfo; 277 278 /// Information about the swifterror values used throughout the function. 279 SwiftErrorValueTracking &SwiftError; 280 281 /// Garbage collection metadata for the function. 282 GCFunctionInfo *GFI; 283 284 /// Map a landing pad to the call site indexes. 285 DenseMap<MachineBasicBlock *, SmallVector<unsigned, 4>> LPadToCallSiteMap; 286 287 /// This is set to true if a call in the current block has been translated as 288 /// a tail call. In this case, no subsequent DAG nodes should be created. 289 bool HasTailCall = false; 290 291 LLVMContext *Context; 292 293 SelectionDAGBuilder(SelectionDAG &dag, FunctionLoweringInfo &funcinfo, 294 SwiftErrorValueTracking &swifterror, CodeGenOpt::Level ol) 295 : SDNodeOrder(LowestSDNodeOrder), TM(dag.getTarget()), DAG(dag), 296 SL(std::make_unique<SDAGSwitchLowering>(this, funcinfo)), FuncInfo(funcinfo), 297 SwiftError(swifterror) {} 298 299 void init(GCFunctionInfo *gfi, AAResults *AA, AssumptionCache *AC, 300 const TargetLibraryInfo *li); 301 302 /// Clear out the current SelectionDAG and the associated state and prepare 303 /// this SelectionDAGBuilder object to be used for a new block. This doesn't 304 /// clear out information about additional blocks that are needed to complete 305 /// switch lowering or PHI node updating; that information is cleared out as 306 /// it is consumed. 307 void clear(); 308 309 /// Clear the dangling debug information map. This function is separated from 310 /// the clear so that debug information that is dangling in a basic block can 311 /// be properly resolved in a different basic block. This allows the 312 /// SelectionDAG to resolve dangling debug information attached to PHI nodes. 313 void clearDanglingDebugInfo(); 314 315 /// Return the current virtual root of the Selection DAG, flushing any 316 /// PendingLoad items. This must be done before emitting a store or any other 317 /// memory node that may need to be ordered after any prior load instructions. 318 SDValue getMemoryRoot(); 319 320 /// Similar to getMemoryRoot, but also flushes PendingConstrainedFP(Strict) 321 /// items. This must be done before emitting any call other any other node 322 /// that may need to be ordered after FP instructions due to other side 323 /// effects. 324 SDValue getRoot(); 325 326 /// Similar to getRoot, but instead of flushing all the PendingLoad items, 327 /// flush all the PendingExports (and PendingConstrainedFPStrict) items. 328 /// It is necessary to do this before emitting a terminator instruction. 329 SDValue getControlRoot(); 330 331 SDLoc getCurSDLoc() const { 332 return SDLoc(CurInst, SDNodeOrder); 333 } 334 335 DebugLoc getCurDebugLoc() const { 336 return CurInst ? CurInst->getDebugLoc() : DebugLoc(); 337 } 338 339 void CopyValueToVirtualRegister(const Value *V, unsigned Reg, 340 ISD::NodeType ExtendType = ISD::ANY_EXTEND); 341 342 void visit(const Instruction &I); 343 344 void visit(unsigned Opcode, const User &I); 345 346 /// If there was virtual register allocated for the value V emit CopyFromReg 347 /// of the specified type Ty. Return empty SDValue() otherwise. 348 SDValue getCopyFromRegs(const Value *V, Type *Ty); 349 350 /// Register a dbg_value which relies on a Value which we have not yet seen. 351 void addDanglingDebugInfo(const DbgValueInst *DI, unsigned Order); 352 void addDanglingDebugInfo(const VarLocInfo *VarLoc, unsigned Order); 353 354 /// If we have dangling debug info that describes \p Variable, or an 355 /// overlapping part of variable considering the \p Expr, then this method 356 /// will drop that debug info as it isn't valid any longer. 357 void dropDanglingDebugInfo(const DILocalVariable *Variable, 358 const DIExpression *Expr); 359 360 /// If we saw an earlier dbg_value referring to V, generate the debug data 361 /// structures now that we've seen its definition. 362 void resolveDanglingDebugInfo(const Value *V, SDValue Val); 363 364 /// For the given dangling debuginfo record, perform last-ditch efforts to 365 /// resolve the debuginfo to something that is represented in this DAG. If 366 /// this cannot be done, produce an Undef debug value record. 367 void salvageUnresolvedDbgValue(DanglingDebugInfo &DDI); 368 369 /// For a given list of Values, attempt to create and record a SDDbgValue in 370 /// the SelectionDAG. 371 bool handleDebugValue(ArrayRef<const Value *> Values, DILocalVariable *Var, 372 DIExpression *Expr, DebugLoc DbgLoc, unsigned Order, 373 bool IsVariadic); 374 375 /// Evict any dangling debug information, attempting to salvage it first. 376 void resolveOrClearDbgInfo(); 377 378 SDValue getValue(const Value *V); 379 380 SDValue getNonRegisterValue(const Value *V); 381 SDValue getValueImpl(const Value *V); 382 383 void setValue(const Value *V, SDValue NewN) { 384 SDValue &N = NodeMap[V]; 385 assert(!N.getNode() && "Already set a value for this node!"); 386 N = NewN; 387 } 388 389 void setUnusedArgValue(const Value *V, SDValue NewN) { 390 SDValue &N = UnusedArgNodeMap[V]; 391 assert(!N.getNode() && "Already set a value for this node!"); 392 N = NewN; 393 } 394 395 void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB, 396 MachineBasicBlock *FBB, MachineBasicBlock *CurBB, 397 MachineBasicBlock *SwitchBB, 398 Instruction::BinaryOps Opc, BranchProbability TProb, 399 BranchProbability FProb, bool InvertCond); 400 void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB, 401 MachineBasicBlock *FBB, 402 MachineBasicBlock *CurBB, 403 MachineBasicBlock *SwitchBB, 404 BranchProbability TProb, BranchProbability FProb, 405 bool InvertCond); 406 bool ShouldEmitAsBranches(const std::vector<SwitchCG::CaseBlock> &Cases); 407 bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB); 408 void CopyToExportRegsIfNeeded(const Value *V); 409 void ExportFromCurrentBlock(const Value *V); 410 void LowerCallTo(const CallBase &CB, SDValue Callee, bool IsTailCall, 411 bool IsMustTailCall, const BasicBlock *EHPadBB = nullptr); 412 413 // Lower range metadata from 0 to N to assert zext to an integer of nearest 414 // floor power of two. 415 SDValue lowerRangeToAssertZExt(SelectionDAG &DAG, const Instruction &I, 416 SDValue Op); 417 418 void populateCallLoweringInfo(TargetLowering::CallLoweringInfo &CLI, 419 const CallBase *Call, unsigned ArgIdx, 420 unsigned NumArgs, SDValue Callee, 421 Type *ReturnTy, bool IsPatchPoint); 422 423 std::pair<SDValue, SDValue> 424 lowerInvokable(TargetLowering::CallLoweringInfo &CLI, 425 const BasicBlock *EHPadBB = nullptr); 426 427 /// When an MBB was split during scheduling, update the 428 /// references that need to refer to the last resulting block. 429 void UpdateSplitBlock(MachineBasicBlock *First, MachineBasicBlock *Last); 430 431 /// Describes a gc.statepoint or a gc.statepoint like thing for the purposes 432 /// of lowering into a STATEPOINT node. 433 struct StatepointLoweringInfo { 434 /// Bases[i] is the base pointer for Ptrs[i]. Together they denote the set 435 /// of gc pointers this STATEPOINT has to relocate. 436 SmallVector<const Value *, 16> Bases; 437 SmallVector<const Value *, 16> Ptrs; 438 439 /// The set of gc.relocate calls associated with this gc.statepoint. 440 SmallVector<const GCRelocateInst *, 16> GCRelocates; 441 442 /// The full list of gc arguments to the gc.statepoint being lowered. 443 ArrayRef<const Use> GCArgs; 444 445 /// The gc.statepoint instruction. 446 const Instruction *StatepointInstr = nullptr; 447 448 /// The list of gc transition arguments present in the gc.statepoint being 449 /// lowered. 450 ArrayRef<const Use> GCTransitionArgs; 451 452 /// The ID that the resulting STATEPOINT instruction has to report. 453 unsigned ID = -1; 454 455 /// Information regarding the underlying call instruction. 456 TargetLowering::CallLoweringInfo CLI; 457 458 /// The deoptimization state associated with this gc.statepoint call, if 459 /// any. 460 ArrayRef<const Use> DeoptState; 461 462 /// Flags associated with the meta arguments being lowered. 463 uint64_t StatepointFlags = -1; 464 465 /// The number of patchable bytes the call needs to get lowered into. 466 unsigned NumPatchBytes = -1; 467 468 /// The exception handling unwind destination, in case this represents an 469 /// invoke of gc.statepoint. 470 const BasicBlock *EHPadBB = nullptr; 471 472 explicit StatepointLoweringInfo(SelectionDAG &DAG) : CLI(DAG) {} 473 }; 474 475 /// Lower \p SLI into a STATEPOINT instruction. 476 SDValue LowerAsSTATEPOINT(StatepointLoweringInfo &SI); 477 478 // This function is responsible for the whole statepoint lowering process. 479 // It uniformly handles invoke and call statepoints. 480 void LowerStatepoint(const GCStatepointInst &I, 481 const BasicBlock *EHPadBB = nullptr); 482 483 void LowerCallSiteWithDeoptBundle(const CallBase *Call, SDValue Callee, 484 const BasicBlock *EHPadBB); 485 486 void LowerDeoptimizeCall(const CallInst *CI); 487 void LowerDeoptimizingReturn(); 488 489 void LowerCallSiteWithDeoptBundleImpl(const CallBase *Call, SDValue Callee, 490 const BasicBlock *EHPadBB, 491 bool VarArgDisallowed, 492 bool ForceVoidReturnTy); 493 494 /// Returns the type of FrameIndex and TargetFrameIndex nodes. 495 MVT getFrameIndexTy() { 496 return DAG.getTargetLoweringInfo().getFrameIndexTy(DAG.getDataLayout()); 497 } 498 499 private: 500 // Terminator instructions. 501 void visitRet(const ReturnInst &I); 502 void visitBr(const BranchInst &I); 503 void visitSwitch(const SwitchInst &I); 504 void visitIndirectBr(const IndirectBrInst &I); 505 void visitUnreachable(const UnreachableInst &I); 506 void visitCleanupRet(const CleanupReturnInst &I); 507 void visitCatchSwitch(const CatchSwitchInst &I); 508 void visitCatchRet(const CatchReturnInst &I); 509 void visitCatchPad(const CatchPadInst &I); 510 void visitCleanupPad(const CleanupPadInst &CPI); 511 512 BranchProbability getEdgeProbability(const MachineBasicBlock *Src, 513 const MachineBasicBlock *Dst) const; 514 void addSuccessorWithProb( 515 MachineBasicBlock *Src, MachineBasicBlock *Dst, 516 BranchProbability Prob = BranchProbability::getUnknown()); 517 518 public: 519 void visitSwitchCase(SwitchCG::CaseBlock &CB, MachineBasicBlock *SwitchBB); 520 void visitSPDescriptorParent(StackProtectorDescriptor &SPD, 521 MachineBasicBlock *ParentBB); 522 void visitSPDescriptorFailure(StackProtectorDescriptor &SPD); 523 void visitBitTestHeader(SwitchCG::BitTestBlock &B, 524 MachineBasicBlock *SwitchBB); 525 void visitBitTestCase(SwitchCG::BitTestBlock &BB, MachineBasicBlock *NextMBB, 526 BranchProbability BranchProbToNext, unsigned Reg, 527 SwitchCG::BitTestCase &B, MachineBasicBlock *SwitchBB); 528 void visitJumpTable(SwitchCG::JumpTable &JT); 529 void visitJumpTableHeader(SwitchCG::JumpTable &JT, 530 SwitchCG::JumpTableHeader &JTH, 531 MachineBasicBlock *SwitchBB); 532 533 private: 534 // These all get lowered before this pass. 535 void visitInvoke(const InvokeInst &I); 536 void visitCallBr(const CallBrInst &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 void visitIntrinsicCall(const CallInst &I, unsigned Intrinsic); 620 void visitTargetIntrinsic(const CallInst &I, unsigned Intrinsic); 621 void visitConstrainedFPIntrinsic(const ConstrainedFPIntrinsic &FPI); 622 void visitVPLoad(const VPIntrinsic &VPIntrin, EVT VT, 623 SmallVector<SDValue, 7> &OpValues); 624 void visitVPStore(const VPIntrinsic &VPIntrin, 625 SmallVector<SDValue, 7> &OpValues); 626 void visitVPGather(const VPIntrinsic &VPIntrin, EVT VT, 627 SmallVector<SDValue, 7> &OpValues); 628 void visitVPScatter(const VPIntrinsic &VPIntrin, 629 SmallVector<SDValue, 7> &OpValues); 630 void visitVPStridedLoad(const VPIntrinsic &VPIntrin, EVT VT, 631 SmallVectorImpl<SDValue> &OpValues); 632 void visitVPStridedStore(const VPIntrinsic &VPIntrin, 633 SmallVectorImpl<SDValue> &OpValues); 634 void visitVPCmp(const VPCmpIntrinsic &VPIntrin); 635 void visitVectorPredicationIntrinsic(const VPIntrinsic &VPIntrin); 636 637 void visitVAStart(const CallInst &I); 638 void visitVAArg(const VAArgInst &I); 639 void visitVAEnd(const CallInst &I); 640 void visitVACopy(const CallInst &I); 641 void visitStackmap(const CallInst &I); 642 void visitPatchpoint(const CallBase &CB, const BasicBlock *EHPadBB = nullptr); 643 644 // These two are implemented in StatepointLowering.cpp 645 void visitGCRelocate(const GCRelocateInst &Relocate); 646 void visitGCResult(const GCResultInst &I); 647 648 void visitVectorReduce(const CallInst &I, unsigned Intrinsic); 649 void visitVectorReverse(const CallInst &I); 650 void visitVectorSplice(const CallInst &I); 651 void visitStepVector(const CallInst &I); 652 653 void visitUserOp1(const Instruction &I) { 654 llvm_unreachable("UserOp1 should not exist at instruction selection time!"); 655 } 656 void visitUserOp2(const Instruction &I) { 657 llvm_unreachable("UserOp2 should not exist at instruction selection time!"); 658 } 659 660 void processIntegerCallValue(const Instruction &I, 661 SDValue Value, bool IsSigned); 662 663 void HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB); 664 665 void emitInlineAsmError(const CallBase &Call, const Twine &Message); 666 667 /// An enum that states to emit func argument dbg value the kind of intrinsic 668 /// it originally had. This controls the internal behavior of 669 /// EmitFuncArgumentDbgValue. 670 enum class FuncArgumentDbgValueKind { 671 Value, // This was originally a llvm.dbg.value. 672 Addr, // This was originally a llvm.dbg.addr. 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 /// 714 struct 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> ®s, 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. 762 SDValue getCopyFromRegs(SelectionDAG &DAG, FunctionLoweringInfo &FuncInfo, 763 const SDLoc &dl, SDValue &Chain, SDValue *Flag, 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 *Flag, 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(unsigned 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. 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