//===- SelectionDAGBuilder.cpp - Selection-DAG building -------------------===// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This implements routines for translating from LLVM IR into SelectionDAG IR. // //===----------------------------------------------------------------------===// #include "SelectionDAGBuilder.h" #include "SDNodeDbgValue.h" #include "llvm/ADT/APFloat.h" #include "llvm/ADT/APInt.h" #include "llvm/ADT/BitVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/StringRef.h" #include "llvm/ADT/Twine.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/Loads.h" #include "llvm/Analysis/MemoryLocation.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/Analysis/VectorUtils.h" #include "llvm/CodeGen/Analysis.h" #include "llvm/CodeGen/AssignmentTrackingAnalysis.h" #include "llvm/CodeGen/CodeGenCommonISel.h" #include "llvm/CodeGen/FunctionLoweringInfo.h" #include "llvm/CodeGen/GCMetadata.h" #include "llvm/CodeGen/ISDOpcodes.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstrBuilder.h" #include "llvm/CodeGen/MachineInstrBundleIterator.h" #include "llvm/CodeGen/MachineMemOperand.h" #include "llvm/CodeGen/MachineModuleInfo.h" #include "llvm/CodeGen/MachineOperand.h" #include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/RuntimeLibcallUtil.h" #include "llvm/CodeGen/SelectionDAG.h" #include "llvm/CodeGen/SelectionDAGTargetInfo.h" #include "llvm/CodeGen/StackMaps.h" #include "llvm/CodeGen/SwiftErrorValueTracking.h" #include "llvm/CodeGen/TargetFrameLowering.h" #include "llvm/CodeGen/TargetInstrInfo.h" #include "llvm/CodeGen/TargetOpcodes.h" #include "llvm/CodeGen/TargetRegisterInfo.h" #include "llvm/CodeGen/TargetSubtargetInfo.h" #include "llvm/CodeGen/WinEHFuncInfo.h" #include "llvm/IR/Argument.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/CallingConv.h" #include "llvm/IR/Constant.h" #include "llvm/IR/ConstantRange.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DebugInfo.h" #include "llvm/IR/DebugInfoMetadata.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/DiagnosticInfo.h" #include "llvm/IR/EHPersonalities.h" #include "llvm/IR/Function.h" #include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/InlineAsm.h" #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Intrinsics.h" #include "llvm/IR/IntrinsicsAArch64.h" #include "llvm/IR/IntrinsicsAMDGPU.h" #include "llvm/IR/IntrinsicsWebAssembly.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/MemoryModelRelaxationAnnotations.h" #include "llvm/IR/Metadata.h" #include "llvm/IR/Module.h" #include "llvm/IR/Operator.h" #include "llvm/IR/PatternMatch.h" #include "llvm/IR/Statepoint.h" #include "llvm/IR/Type.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" #include "llvm/MC/MCContext.h" #include "llvm/Support/AtomicOrdering.h" #include "llvm/Support/Casting.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/Debug.h" #include "llvm/Support/InstructionCost.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetIntrinsicInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetOptions.h" #include "llvm/TargetParser/Triple.h" #include "llvm/Transforms/Utils/Local.h" #include <cstddef> #include <deque> #include <iterator> #include <limits> #include <optional> #include <tuple> usingnamespacellvm; usingnamespacePatternMatch; usingnamespaceSwitchCG; #define DEBUG_TYPE … /// LimitFloatPrecision - Generate low-precision inline sequences for /// some float libcalls (6, 8 or 12 bits). static unsigned LimitFloatPrecision; static cl::opt<bool> InsertAssertAlign("insert-assert-align", cl::init(true), cl::desc("Insert the experimental `assertalign` node."), cl::ReallyHidden); static cl::opt<unsigned, true> LimitFPPrecision("limit-float-precision", cl::desc("Generate low-precision inline sequences " "for some float libcalls"), cl::location(LimitFloatPrecision), cl::Hidden, cl::init(0)); static cl::opt<unsigned> SwitchPeelThreshold( "switch-peel-threshold", cl::Hidden, cl::init(66), cl::desc("Set the case probability threshold for peeling the case from a " "switch statement. A value greater than 100 will void this " "optimization")); // Limit the width of DAG chains. This is important in general to prevent // DAG-based analysis from blowing up. For example, alias analysis and // load clustering may not complete in reasonable time. It is difficult to // recognize and avoid this situation within each individual analysis, and // future analyses are likely to have the same behavior. Limiting DAG width is // the safe approach and will be especially important with global DAGs. // // MaxParallelChains default is arbitrarily high to avoid affecting // optimization, but could be lowered to improve compile time. Any ld-ld-st-st // sequence over this should have been converted to llvm.memcpy by the // frontend. It is easy to induce this behavior with .ll code such as: // %buffer = alloca [4096 x i8] // %data = load [4096 x i8]* %argPtr // store [4096 x i8] %data, [4096 x i8]* %buffer static const unsigned MaxParallelChains = …; static SDValue getCopyFromPartsVector(SelectionDAG &DAG, const SDLoc &DL, const SDValue *Parts, unsigned NumParts, MVT PartVT, EVT ValueVT, const Value *V, SDValue InChain, std::optional<CallingConv::ID> CC); /// getCopyFromParts - Create a value that contains the specified legal parts /// combined into the value they represent. If the parts combine to a type /// larger than ValueVT then AssertOp can be used to specify whether the extra /// bits are known to be zero (ISD::AssertZext) or sign extended from ValueVT /// (ISD::AssertSext). static SDValue getCopyFromParts(SelectionDAG &DAG, const SDLoc &DL, const SDValue *Parts, unsigned NumParts, MVT PartVT, EVT ValueVT, const Value *V, SDValue InChain, std::optional<CallingConv::ID> CC = std::nullopt, std::optional<ISD::NodeType> AssertOp = std::nullopt) { … } static void diagnosePossiblyInvalidConstraint(LLVMContext &Ctx, const Value *V, const Twine &ErrMsg) { … } /// getCopyFromPartsVector - Create a value that contains the specified legal /// parts combined into the value they represent. If the parts combine to a /// type larger than ValueVT then AssertOp can be used to specify whether the /// extra bits are known to be zero (ISD::AssertZext) or sign extended from /// ValueVT (ISD::AssertSext). static SDValue getCopyFromPartsVector(SelectionDAG &DAG, const SDLoc &DL, const SDValue *Parts, unsigned NumParts, MVT PartVT, EVT ValueVT, const Value *V, SDValue InChain, std::optional<CallingConv::ID> CallConv) { … } static void getCopyToPartsVector(SelectionDAG &DAG, const SDLoc &dl, SDValue Val, SDValue *Parts, unsigned NumParts, MVT PartVT, const Value *V, std::optional<CallingConv::ID> CallConv); /// getCopyToParts - Create a series of nodes that contain the specified value /// split into legal parts. If the parts contain more bits than Val, then, for /// integers, ExtendKind can be used to specify how to generate the extra bits. static void getCopyToParts(SelectionDAG &DAG, const SDLoc &DL, SDValue Val, SDValue *Parts, unsigned NumParts, MVT PartVT, const Value *V, std::optional<CallingConv::ID> CallConv = std::nullopt, ISD::NodeType ExtendKind = ISD::ANY_EXTEND) { … } static SDValue widenVectorToPartType(SelectionDAG &DAG, SDValue Val, const SDLoc &DL, EVT PartVT) { … } /// getCopyToPartsVector - Create a series of nodes that contain the specified /// value split into legal parts. static void getCopyToPartsVector(SelectionDAG &DAG, const SDLoc &DL, SDValue Val, SDValue *Parts, unsigned NumParts, MVT PartVT, const Value *V, std::optional<CallingConv::ID> CallConv) { … } RegsForValue::RegsForValue(const SmallVector<Register, 4> ®s, MVT regvt, EVT valuevt, std::optional<CallingConv::ID> CC) : … { … } RegsForValue::RegsForValue(LLVMContext &Context, const TargetLowering &TLI, const DataLayout &DL, Register Reg, Type *Ty, std::optional<CallingConv::ID> CC) { … } SDValue RegsForValue::getCopyFromRegs(SelectionDAG &DAG, FunctionLoweringInfo &FuncInfo, const SDLoc &dl, SDValue &Chain, SDValue *Glue, const Value *V) const { … } void RegsForValue::getCopyToRegs(SDValue Val, SelectionDAG &DAG, const SDLoc &dl, SDValue &Chain, SDValue *Glue, const Value *V, ISD::NodeType PreferredExtendType) const { … } void RegsForValue::AddInlineAsmOperands(InlineAsm::Kind Code, bool HasMatching, unsigned MatchingIdx, const SDLoc &dl, SelectionDAG &DAG, std::vector<SDValue> &Ops) const { … } SmallVector<std::pair<Register, TypeSize>, 4> RegsForValue::getRegsAndSizes() const { … } void SelectionDAGBuilder::init(GCFunctionInfo *gfi, AliasAnalysis *aa, AssumptionCache *ac, const TargetLibraryInfo *li) { … } void SelectionDAGBuilder::clear() { … } void SelectionDAGBuilder::clearDanglingDebugInfo() { … } // Update DAG root to include dependencies on Pending chains. SDValue SelectionDAGBuilder::updateRoot(SmallVectorImpl<SDValue> &Pending) { … } SDValue SelectionDAGBuilder::getMemoryRoot() { … } SDValue SelectionDAGBuilder::getRoot() { … } SDValue SelectionDAGBuilder::getControlRoot() { … } void SelectionDAGBuilder::handleDebugDeclare(Value *Address, DILocalVariable *Variable, DIExpression *Expression, DebugLoc DL) { … } void SelectionDAGBuilder::visitDbgInfo(const Instruction &I) { … } void SelectionDAGBuilder::visit(const Instruction &I) { … } void SelectionDAGBuilder::visitPHI(const PHINode &) { … } void SelectionDAGBuilder::visit(unsigned Opcode, const User &I) { … } static bool handleDanglingVariadicDebugInfo(SelectionDAG &DAG, DILocalVariable *Variable, DebugLoc DL, unsigned Order, SmallVectorImpl<Value *> &Values, DIExpression *Expression) { … } void SelectionDAGBuilder::addDanglingDebugInfo(SmallVectorImpl<Value *> &Values, DILocalVariable *Var, DIExpression *Expr, bool IsVariadic, DebugLoc DL, unsigned Order) { … } void SelectionDAGBuilder::dropDanglingDebugInfo(const DILocalVariable *Variable, const DIExpression *Expr) { … } // resolveDanglingDebugInfo - if we saw an earlier dbg_value referring to V, // generate the debug data structures now that we've seen its definition. void SelectionDAGBuilder::resolveDanglingDebugInfo(const Value *V, SDValue Val) { … } void SelectionDAGBuilder::salvageUnresolvedDbgValue(const Value *V, DanglingDebugInfo &DDI) { … } void SelectionDAGBuilder::handleKillDebugValue(DILocalVariable *Var, DIExpression *Expr, DebugLoc DbgLoc, unsigned Order) { … } bool SelectionDAGBuilder::handleDebugValue(ArrayRef<const Value *> Values, DILocalVariable *Var, DIExpression *Expr, DebugLoc DbgLoc, unsigned Order, bool IsVariadic) { … } void SelectionDAGBuilder::resolveOrClearDbgInfo() { … } /// getCopyFromRegs - If there was virtual register allocated for the value V /// emit CopyFromReg of the specified type Ty. Return empty SDValue() otherwise. SDValue SelectionDAGBuilder::getCopyFromRegs(const Value *V, Type *Ty) { … } /// getValue - Return an SDValue for the given Value. SDValue SelectionDAGBuilder::getValue(const Value *V) { … } /// getNonRegisterValue - Return an SDValue for the given Value, but /// don't look in FuncInfo.ValueMap for a virtual register. SDValue SelectionDAGBuilder::getNonRegisterValue(const Value *V) { … } /// getValueImpl - Helper function for getValue and getNonRegisterValue. /// Create an SDValue for the given value. SDValue SelectionDAGBuilder::getValueImpl(const Value *V) { … } void SelectionDAGBuilder::visitCatchPad(const CatchPadInst &I) { … } void SelectionDAGBuilder::visitCatchRet(const CatchReturnInst &I) { … } void SelectionDAGBuilder::visitCleanupPad(const CleanupPadInst &CPI) { … } // In wasm EH, even though a catchpad may not catch an exception if a tag does // not match, it is OK to add only the first unwind destination catchpad to the // successors, because there will be at least one invoke instruction within the // catch scope that points to the next unwind destination, if one exists, so // CFGSort cannot mess up with BB sorting order. // (All catchpads with 'catch (type)' clauses have a 'llvm.rethrow' intrinsic // call within them, and catchpads only consisting of 'catch (...)' have a // '__cxa_end_catch' call within them, both of which generate invokes in case // the next unwind destination exists, i.e., the next unwind destination is not // the caller.) // // Having at most one EH pad successor is also simpler and helps later // transformations. // // For example, // current: // invoke void @foo to ... unwind label %catch.dispatch // catch.dispatch: // %0 = catchswitch within ... [label %catch.start] unwind label %next // catch.start: // ... // ... in this BB or some other child BB dominated by this BB there will be an // invoke that points to 'next' BB as an unwind destination // // next: ; We don't need to add this to 'current' BB's successor // ... static void findWasmUnwindDestinations( FunctionLoweringInfo &FuncInfo, const BasicBlock *EHPadBB, BranchProbability Prob, SmallVectorImpl<std::pair<MachineBasicBlock *, BranchProbability>> &UnwindDests) { … } /// When an invoke or a cleanupret unwinds to the next EH pad, there are /// many places it could ultimately go. In the IR, we have a single unwind /// destination, but in the machine CFG, we enumerate all the possible blocks. /// This function skips over imaginary basic blocks that hold catchswitch /// instructions, and finds all the "real" machine /// basic block destinations. As those destinations may not be successors of /// EHPadBB, here we also calculate the edge probability to those destinations. /// The passed-in Prob is the edge probability to EHPadBB. static void findUnwindDestinations( FunctionLoweringInfo &FuncInfo, const BasicBlock *EHPadBB, BranchProbability Prob, SmallVectorImpl<std::pair<MachineBasicBlock *, BranchProbability>> &UnwindDests) { … } void SelectionDAGBuilder::visitCleanupRet(const CleanupReturnInst &I) { … } void SelectionDAGBuilder::visitCatchSwitch(const CatchSwitchInst &CSI) { … } void SelectionDAGBuilder::visitRet(const ReturnInst &I) { … } /// CopyToExportRegsIfNeeded - If the given value has virtual registers /// created for it, emit nodes to copy the value into the virtual /// registers. void SelectionDAGBuilder::CopyToExportRegsIfNeeded(const Value *V) { … } /// ExportFromCurrentBlock - If this condition isn't known to be exported from /// the current basic block, add it to ValueMap now so that we'll get a /// CopyTo/FromReg. void SelectionDAGBuilder::ExportFromCurrentBlock(const Value *V) { … } bool SelectionDAGBuilder::isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB) { … } /// Return branch probability calculated by BranchProbabilityInfo for IR blocks. BranchProbability SelectionDAGBuilder::getEdgeProbability(const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const { … } void SelectionDAGBuilder::addSuccessorWithProb(MachineBasicBlock *Src, MachineBasicBlock *Dst, BranchProbability Prob) { … } static bool InBlock(const Value *V, const BasicBlock *BB) { … } /// EmitBranchForMergedCondition - Helper method for FindMergedConditions. /// This function emits a branch and is used at the leaves of an OR or an /// AND operator tree. void SelectionDAGBuilder::EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB, MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, BranchProbability TProb, BranchProbability FProb, bool InvertCond) { … } // Collect dependencies on V recursively. This is used for the cost analysis in // `shouldKeepJumpConditionsTogether`. static bool collectInstructionDeps( SmallMapVector<const Instruction *, bool, 8> *Deps, const Value *V, SmallMapVector<const Instruction *, bool, 8> *Necessary = nullptr, unsigned Depth = 0) { … } bool SelectionDAGBuilder::shouldKeepJumpConditionsTogether( const FunctionLoweringInfo &FuncInfo, const BranchInst &I, Instruction::BinaryOps Opc, const Value *Lhs, const Value *Rhs, TargetLoweringBase::CondMergingParams Params) const { … } void SelectionDAGBuilder::FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB, MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB, Instruction::BinaryOps Opc, BranchProbability TProb, BranchProbability FProb, bool InvertCond) { … } /// If the set of cases should be emitted as a series of branches, return true. /// If we should emit this as a bunch of and/or'd together conditions, return /// false. bool SelectionDAGBuilder::ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases) { … } void SelectionDAGBuilder::visitBr(const BranchInst &I) { … } /// visitSwitchCase - Emits the necessary code to represent a single node in /// the binary search tree resulting from lowering a switch instruction. void SelectionDAGBuilder::visitSwitchCase(CaseBlock &CB, MachineBasicBlock *SwitchBB) { … } /// visitJumpTable - Emit JumpTable node in the current MBB void SelectionDAGBuilder::visitJumpTable(SwitchCG::JumpTable &JT) { … } /// visitJumpTableHeader - This function emits necessary code to produce index /// in the JumpTable from switch case. void SelectionDAGBuilder::visitJumpTableHeader(SwitchCG::JumpTable &JT, JumpTableHeader &JTH, MachineBasicBlock *SwitchBB) { … } /// Create a LOAD_STACK_GUARD node, and let it carry the target specific global /// variable if there exists one. static SDValue getLoadStackGuard(SelectionDAG &DAG, const SDLoc &DL, SDValue &Chain) { … } /// Codegen a new tail for a stack protector check ParentMBB which has had its /// tail spliced into a stack protector check success bb. /// /// For a high level explanation of how this fits into the stack protector /// generation see the comment on the declaration of class /// StackProtectorDescriptor. void SelectionDAGBuilder::visitSPDescriptorParent(StackProtectorDescriptor &SPD, MachineBasicBlock *ParentBB) { … } /// Codegen the failure basic block for a stack protector check. /// /// A failure stack protector machine basic block consists simply of a call to /// __stack_chk_fail(). /// /// For a high level explanation of how this fits into the stack protector /// generation see the comment on the declaration of class /// StackProtectorDescriptor. void SelectionDAGBuilder::visitSPDescriptorFailure(StackProtectorDescriptor &SPD) { … } /// visitBitTestHeader - This function emits necessary code to produce value /// suitable for "bit tests" void SelectionDAGBuilder::visitBitTestHeader(BitTestBlock &B, MachineBasicBlock *SwitchBB) { … } /// visitBitTestCase - this function produces one "bit test" void SelectionDAGBuilder::visitBitTestCase(BitTestBlock &BB, MachineBasicBlock *NextMBB, BranchProbability BranchProbToNext, Register Reg, BitTestCase &B, MachineBasicBlock *SwitchBB) { … } void SelectionDAGBuilder::visitInvoke(const InvokeInst &I) { … } void SelectionDAGBuilder::visitCallBr(const CallBrInst &I) { … } void SelectionDAGBuilder::visitResume(const ResumeInst &RI) { … } void SelectionDAGBuilder::visitLandingPad(const LandingPadInst &LP) { … } void SelectionDAGBuilder::UpdateSplitBlock(MachineBasicBlock *First, MachineBasicBlock *Last) { … } void SelectionDAGBuilder::visitIndirectBr(const IndirectBrInst &I) { … } void SelectionDAGBuilder::visitUnreachable(const UnreachableInst &I) { … } void SelectionDAGBuilder::visitUnary(const User &I, unsigned Opcode) { … } void SelectionDAGBuilder::visitBinary(const User &I, unsigned Opcode) { … } void SelectionDAGBuilder::visitShift(const User &I, unsigned Opcode) { … } void SelectionDAGBuilder::visitSDiv(const User &I) { … } void SelectionDAGBuilder::visitICmp(const ICmpInst &I) { … } void SelectionDAGBuilder::visitFCmp(const FCmpInst &I) { … } // Check if the condition of the select has one use or two users that are both // selects with the same condition. static bool hasOnlySelectUsers(const Value *Cond) { … } void SelectionDAGBuilder::visitSelect(const User &I) { … } void SelectionDAGBuilder::visitTrunc(const User &I) { … } void SelectionDAGBuilder::visitZExt(const User &I) { … } void SelectionDAGBuilder::visitSExt(const User &I) { … } void SelectionDAGBuilder::visitFPTrunc(const User &I) { … } void SelectionDAGBuilder::visitFPExt(const User &I) { … } void SelectionDAGBuilder::visitFPToUI(const User &I) { … } void SelectionDAGBuilder::visitFPToSI(const User &I) { … } void SelectionDAGBuilder::visitUIToFP(const User &I) { … } void SelectionDAGBuilder::visitSIToFP(const User &I) { … } void SelectionDAGBuilder::visitPtrToInt(const User &I) { … } void SelectionDAGBuilder::visitIntToPtr(const User &I) { … } void SelectionDAGBuilder::visitBitCast(const User &I) { … } void SelectionDAGBuilder::visitAddrSpaceCast(const User &I) { … } void SelectionDAGBuilder::visitInsertElement(const User &I) { … } void SelectionDAGBuilder::visitExtractElement(const User &I) { … } void SelectionDAGBuilder::visitShuffleVector(const User &I) { … } void SelectionDAGBuilder::visitInsertValue(const InsertValueInst &I) { … } void SelectionDAGBuilder::visitExtractValue(const ExtractValueInst &I) { … } void SelectionDAGBuilder::visitGetElementPtr(const User &I) { … } void SelectionDAGBuilder::visitAlloca(const AllocaInst &I) { … } static const MDNode *getRangeMetadata(const Instruction &I) { … } static std::optional<ConstantRange> getRange(const Instruction &I) { … } void SelectionDAGBuilder::visitLoad(const LoadInst &I) { … } void SelectionDAGBuilder::visitStoreToSwiftError(const StoreInst &I) { … } void SelectionDAGBuilder::visitLoadFromSwiftError(const LoadInst &I) { … } void SelectionDAGBuilder::visitStore(const StoreInst &I) { … } void SelectionDAGBuilder::visitMaskedStore(const CallInst &I, bool IsCompressing) { … } // Get a uniform base for the Gather/Scatter intrinsic. // The first argument of the Gather/Scatter intrinsic is a vector of pointers. // We try to represent it as a base pointer + vector of indices. // Usually, the vector of pointers comes from a 'getelementptr' instruction. // The first operand of the GEP may be a single pointer or a vector of pointers // Example: // %gep.ptr = getelementptr i32, <8 x i32*> %vptr, <8 x i32> %ind // or // %gep.ptr = getelementptr i32, i32* %ptr, <8 x i32> %ind // %res = call <8 x i32> @llvm.masked.gather.v8i32(<8 x i32*> %gep.ptr, .. // // When the first GEP operand is a single pointer - it is the uniform base we // are looking for. If first operand of the GEP is a splat vector - we // extract the splat value and use it as a uniform base. // In all other cases the function returns 'false'. static bool getUniformBase(const Value *Ptr, SDValue &Base, SDValue &Index, ISD::MemIndexType &IndexType, SDValue &Scale, SelectionDAGBuilder *SDB, const BasicBlock *CurBB, uint64_t ElemSize) { … } void SelectionDAGBuilder::visitMaskedScatter(const CallInst &I) { … } void SelectionDAGBuilder::visitMaskedLoad(const CallInst &I, bool IsExpanding) { … } void SelectionDAGBuilder::visitMaskedGather(const CallInst &I) { … } void SelectionDAGBuilder::visitAtomicCmpXchg(const AtomicCmpXchgInst &I) { … } void SelectionDAGBuilder::visitAtomicRMW(const AtomicRMWInst &I) { … } void SelectionDAGBuilder::visitFence(const FenceInst &I) { … } void SelectionDAGBuilder::visitAtomicLoad(const LoadInst &I) { … } void SelectionDAGBuilder::visitAtomicStore(const StoreInst &I) { … } /// visitTargetIntrinsic - Lower a call of a target intrinsic to an INTRINSIC /// node. void SelectionDAGBuilder::visitTargetIntrinsic(const CallInst &I, unsigned Intrinsic) { … } /// GetSignificand - Get the significand and build it into a floating-point /// number with exponent of 1: /// /// Op = (Op & 0x007fffff) | 0x3f800000; /// /// where Op is the hexadecimal representation of floating point value. static SDValue GetSignificand(SelectionDAG &DAG, SDValue Op, const SDLoc &dl) { … } /// GetExponent - Get the exponent: /// /// (float)(int)(((Op & 0x7f800000) >> 23) - 127); /// /// where Op is the hexadecimal representation of floating point value. static SDValue GetExponent(SelectionDAG &DAG, SDValue Op, const TargetLowering &TLI, const SDLoc &dl) { … } /// getF32Constant - Get 32-bit floating point constant. static SDValue getF32Constant(SelectionDAG &DAG, unsigned Flt, const SDLoc &dl) { … } static SDValue getLimitedPrecisionExp2(SDValue t0, const SDLoc &dl, SelectionDAG &DAG) { … } /// expandExp - Lower an exp intrinsic. Handles the special sequences for /// limited-precision mode. static SDValue expandExp(const SDLoc &dl, SDValue Op, SelectionDAG &DAG, const TargetLowering &TLI, SDNodeFlags Flags) { … } /// expandLog - Lower a log intrinsic. Handles the special sequences for /// limited-precision mode. static SDValue expandLog(const SDLoc &dl, SDValue Op, SelectionDAG &DAG, const TargetLowering &TLI, SDNodeFlags Flags) { … } /// expandLog2 - Lower a log2 intrinsic. Handles the special sequences for /// limited-precision mode. static SDValue expandLog2(const SDLoc &dl, SDValue Op, SelectionDAG &DAG, const TargetLowering &TLI, SDNodeFlags Flags) { … } /// expandLog10 - Lower a log10 intrinsic. Handles the special sequences for /// limited-precision mode. static SDValue expandLog10(const SDLoc &dl, SDValue Op, SelectionDAG &DAG, const TargetLowering &TLI, SDNodeFlags Flags) { … } /// expandExp2 - Lower an exp2 intrinsic. Handles the special sequences for /// limited-precision mode. static SDValue expandExp2(const SDLoc &dl, SDValue Op, SelectionDAG &DAG, const TargetLowering &TLI, SDNodeFlags Flags) { … } /// visitPow - Lower a pow intrinsic. Handles the special sequences for /// limited-precision mode with x == 10.0f. static SDValue expandPow(const SDLoc &dl, SDValue LHS, SDValue RHS, SelectionDAG &DAG, const TargetLowering &TLI, SDNodeFlags Flags) { … } /// ExpandPowI - Expand a llvm.powi intrinsic. static SDValue ExpandPowI(const SDLoc &DL, SDValue LHS, SDValue RHS, SelectionDAG &DAG) { … } static SDValue expandDivFix(unsigned Opcode, const SDLoc &DL, SDValue LHS, SDValue RHS, SDValue Scale, SelectionDAG &DAG, const TargetLowering &TLI) { … } // getUnderlyingArgRegs - Find underlying registers used for a truncated, // bitcasted, or split argument. Returns a list of <Register, size in bits> static void getUnderlyingArgRegs(SmallVectorImpl<std::pair<Register, TypeSize>> &Regs, const SDValue &N) { … } /// If the DbgValueInst is a dbg_value of a function argument, create the /// corresponding DBG_VALUE machine instruction for it now. At the end of /// instruction selection, they will be inserted to the entry BB. /// We don't currently support this for variadic dbg_values, as they shouldn't /// appear for function arguments or in the prologue. bool SelectionDAGBuilder::EmitFuncArgumentDbgValue( const Value *V, DILocalVariable *Variable, DIExpression *Expr, DILocation *DL, FuncArgumentDbgValueKind Kind, const SDValue &N) { … } /// Return the appropriate SDDbgValue based on N. SDDbgValue *SelectionDAGBuilder::getDbgValue(SDValue N, DILocalVariable *Variable, DIExpression *Expr, const DebugLoc &dl, unsigned DbgSDNodeOrder) { … } static unsigned FixedPointIntrinsicToOpcode(unsigned Intrinsic) { … } void SelectionDAGBuilder::lowerCallToExternalSymbol(const CallInst &I, const char *FunctionName) { … } /// Given a @llvm.call.preallocated.setup, return the corresponding /// preallocated call. static const CallBase *FindPreallocatedCall(const Value *PreallocatedSetup) { … } /// If DI is a debug value with an EntryValue expression, lower it using the /// corresponding physical register of the associated Argument value /// (guaranteed to exist by the verifier). bool SelectionDAGBuilder::visitEntryValueDbgValue( ArrayRef<const Value *> Values, DILocalVariable *Variable, DIExpression *Expr, DebugLoc DbgLoc) { … } /// Lower the call to the specified intrinsic function. void SelectionDAGBuilder::visitConvergenceControl(const CallInst &I, unsigned Intrinsic) { … } void SelectionDAGBuilder::visitVectorHistogram(const CallInst &I, unsigned IntrinsicID) { … } /// Lower the call to the specified intrinsic function. void SelectionDAGBuilder::visitIntrinsicCall(const CallInst &I, unsigned Intrinsic) { … } void SelectionDAGBuilder::visitConstrainedFPIntrinsic( const ConstrainedFPIntrinsic &FPI) { … } static unsigned getISDForVPIntrinsic(const VPIntrinsic &VPIntrin) { … } void SelectionDAGBuilder::visitVPLoad( const VPIntrinsic &VPIntrin, EVT VT, const SmallVectorImpl<SDValue> &OpValues) { … } void SelectionDAGBuilder::visitVPGather( const VPIntrinsic &VPIntrin, EVT VT, const SmallVectorImpl<SDValue> &OpValues) { … } void SelectionDAGBuilder::visitVPStore( const VPIntrinsic &VPIntrin, const SmallVectorImpl<SDValue> &OpValues) { … } void SelectionDAGBuilder::visitVPScatter( const VPIntrinsic &VPIntrin, const SmallVectorImpl<SDValue> &OpValues) { … } void SelectionDAGBuilder::visitVPStridedLoad( const VPIntrinsic &VPIntrin, EVT VT, const SmallVectorImpl<SDValue> &OpValues) { … } void SelectionDAGBuilder::visitVPStridedStore( const VPIntrinsic &VPIntrin, const SmallVectorImpl<SDValue> &OpValues) { … } void SelectionDAGBuilder::visitVPCmp(const VPCmpIntrinsic &VPIntrin) { … } void SelectionDAGBuilder::visitVectorPredicationIntrinsic( const VPIntrinsic &VPIntrin) { … } SDValue SelectionDAGBuilder::lowerStartEH(SDValue Chain, const BasicBlock *EHPadBB, MCSymbol *&BeginLabel) { … } SDValue SelectionDAGBuilder::lowerEndEH(SDValue Chain, const InvokeInst *II, const BasicBlock *EHPadBB, MCSymbol *BeginLabel) { … } std::pair<SDValue, SDValue> SelectionDAGBuilder::lowerInvokable(TargetLowering::CallLoweringInfo &CLI, const BasicBlock *EHPadBB) { … } void SelectionDAGBuilder::LowerCallTo(const CallBase &CB, SDValue Callee, bool isTailCall, bool isMustTailCall, const BasicBlock *EHPadBB, const TargetLowering::PtrAuthInfo *PAI) { … } static SDValue getMemCmpLoad(const Value *PtrVal, MVT LoadVT, SelectionDAGBuilder &Builder) { … } /// Record the value for an instruction that produces an integer result, /// converting the type where necessary. void SelectionDAGBuilder::processIntegerCallValue(const Instruction &I, SDValue Value, bool IsSigned) { … } /// See if we can lower a memcmp/bcmp call into an optimized form. If so, return /// true and lower it. Otherwise return false, and it will be lowered like a /// normal call. /// The caller already checked that \p I calls the appropriate LibFunc with a /// correct prototype. bool SelectionDAGBuilder::visitMemCmpBCmpCall(const CallInst &I) { … } /// See if we can lower a memchr call into an optimized form. If so, return /// true and lower it. Otherwise return false, and it will be lowered like a /// normal call. /// The caller already checked that \p I calls the appropriate LibFunc with a /// correct prototype. bool SelectionDAGBuilder::visitMemChrCall(const CallInst &I) { … } /// See if we can lower a mempcpy call into an optimized form. If so, return /// true and lower it. Otherwise return false, and it will be lowered like a /// normal call. /// The caller already checked that \p I calls the appropriate LibFunc with a /// correct prototype. bool SelectionDAGBuilder::visitMemPCpyCall(const CallInst &I) { … } /// See if we can lower a strcpy call into an optimized form. If so, return /// true and lower it, otherwise return false and it will be lowered like a /// normal call. /// The caller already checked that \p I calls the appropriate LibFunc with a /// correct prototype. bool SelectionDAGBuilder::visitStrCpyCall(const CallInst &I, bool isStpcpy) { … } /// See if we can lower a strcmp call into an optimized form. If so, return /// true and lower it, otherwise return false and it will be lowered like a /// normal call. /// The caller already checked that \p I calls the appropriate LibFunc with a /// correct prototype. bool SelectionDAGBuilder::visitStrCmpCall(const CallInst &I) { … } /// See if we can lower a strlen call into an optimized form. If so, return /// true and lower it, otherwise return false and it will be lowered like a /// normal call. /// The caller already checked that \p I calls the appropriate LibFunc with a /// correct prototype. bool SelectionDAGBuilder::visitStrLenCall(const CallInst &I) { … } /// See if we can lower a strnlen call into an optimized form. If so, return /// true and lower it, otherwise return false and it will be lowered like a /// normal call. /// The caller already checked that \p I calls the appropriate LibFunc with a /// correct prototype. bool SelectionDAGBuilder::visitStrNLenCall(const CallInst &I) { … } /// See if we can lower a unary floating-point operation into an SDNode with /// the specified Opcode. If so, return true and lower it, otherwise return /// false and it will be lowered like a normal call. /// The caller already checked that \p I calls the appropriate LibFunc with a /// correct prototype. bool SelectionDAGBuilder::visitUnaryFloatCall(const CallInst &I, unsigned Opcode) { … } /// See if we can lower a binary floating-point operation into an SDNode with /// the specified Opcode. If so, return true and lower it. Otherwise return /// false, and it will be lowered like a normal call. /// The caller already checked that \p I calls the appropriate LibFunc with a /// correct prototype. bool SelectionDAGBuilder::visitBinaryFloatCall(const CallInst &I, unsigned Opcode) { … } void SelectionDAGBuilder::visitCall(const CallInst &I) { … } void SelectionDAGBuilder::LowerCallSiteWithPtrAuthBundle( const CallBase &CB, const BasicBlock *EHPadBB) { … } namespace { /// AsmOperandInfo - This contains information for each constraint that we are /// lowering. class SDISelAsmOperandInfo : public TargetLowering::AsmOperandInfo { … }; } // end anonymous namespace /// Make sure that the output operand \p OpInfo and its corresponding input /// operand \p MatchingOpInfo have compatible constraint types (otherwise error /// out). static void patchMatchingInput(const SDISelAsmOperandInfo &OpInfo, SDISelAsmOperandInfo &MatchingOpInfo, SelectionDAG &DAG) { … } /// Get a direct memory input to behave well as an indirect operand. /// This may introduce stores, hence the need for a \p Chain. /// \return The (possibly updated) chain. static SDValue getAddressForMemoryInput(SDValue Chain, const SDLoc &Location, SDISelAsmOperandInfo &OpInfo, SelectionDAG &DAG) { … } /// GetRegistersForValue - Assign registers (virtual or physical) for the /// specified operand. We prefer to assign virtual registers, to allow the /// register allocator to handle the assignment process. However, if the asm /// uses features that we can't model on machineinstrs, we have SDISel do the /// allocation. This produces generally horrible, but correct, code. /// /// OpInfo describes the operand /// RefOpInfo describes the matching operand if any, the operand otherwise static std::optional<unsigned> getRegistersForValue(SelectionDAG &DAG, const SDLoc &DL, SDISelAsmOperandInfo &OpInfo, SDISelAsmOperandInfo &RefOpInfo) { … } static unsigned findMatchingInlineAsmOperand(unsigned OperandNo, const std::vector<SDValue> &AsmNodeOperands) { … } namespace { class ExtraFlags { … }; } // end anonymous namespace static bool isFunction(SDValue Op) { … } /// visitInlineAsm - Handle a call to an InlineAsm object. void SelectionDAGBuilder::visitInlineAsm(const CallBase &Call, const BasicBlock *EHPadBB) { … } void SelectionDAGBuilder::emitInlineAsmError(const CallBase &Call, const Twine &Message) { … } void SelectionDAGBuilder::visitVAStart(const CallInst &I) { … } void SelectionDAGBuilder::visitVAArg(const VAArgInst &I) { … } void SelectionDAGBuilder::visitVAEnd(const CallInst &I) { … } void SelectionDAGBuilder::visitVACopy(const CallInst &I) { … } SDValue SelectionDAGBuilder::lowerRangeToAssertZExt(SelectionDAG &DAG, const Instruction &I, SDValue Op) { … } /// Populate a CallLowerinInfo (into \p CLI) based on the properties of /// the call being lowered. /// /// This is a helper for lowering intrinsics that follow a target calling /// convention or require stack pointer adjustment. Only a subset of the /// intrinsic's operands need to participate in the calling convention. void SelectionDAGBuilder::populateCallLoweringInfo( TargetLowering::CallLoweringInfo &CLI, const CallBase *Call, unsigned ArgIdx, unsigned NumArgs, SDValue Callee, Type *ReturnTy, AttributeSet RetAttrs, bool IsPatchPoint) { … } /// Add a stack map intrinsic call's live variable operands to a stackmap /// or patchpoint target node's operand list. /// /// Constants are converted to TargetConstants purely as an optimization to /// avoid constant materialization and register allocation. /// /// FrameIndex operands are converted to TargetFrameIndex so that ISEL does not /// generate addess computation nodes, and so FinalizeISel can convert the /// TargetFrameIndex into a DirectMemRefOp StackMap location. This avoids /// address materialization and register allocation, but may also be required /// for correctness. If a StackMap (or PatchPoint) intrinsic directly uses an /// alloca in the entry block, then the runtime may assume that the alloca's /// StackMap location can be read immediately after compilation and that the /// location is valid at any point during execution (this is similar to the /// assumption made by the llvm.gcroot intrinsic). If the alloca's location were /// only available in a register, then the runtime would need to trap when /// execution reaches the StackMap in order to read the alloca's location. static void addStackMapLiveVars(const CallBase &Call, unsigned StartIdx, const SDLoc &DL, SmallVectorImpl<SDValue> &Ops, SelectionDAGBuilder &Builder) { … } /// Lower llvm.experimental.stackmap. void SelectionDAGBuilder::visitStackmap(const CallInst &CI) { … } /// Lower llvm.experimental.patchpoint directly to its target opcode. void SelectionDAGBuilder::visitPatchpoint(const CallBase &CB, const BasicBlock *EHPadBB) { … } void SelectionDAGBuilder::visitVectorReduce(const CallInst &I, unsigned Intrinsic) { … } /// Returns an AttributeList representing the attributes applied to the return /// value of the given call. static AttributeList getReturnAttrs(TargetLowering::CallLoweringInfo &CLI) { … } /// TargetLowering::LowerCallTo - This is the default LowerCallTo /// implementation, which just calls LowerCall. /// FIXME: When all targets are /// migrated to using LowerCall, this hook should be integrated into SDISel. std::pair<SDValue, SDValue> TargetLowering::LowerCallTo(TargetLowering::CallLoweringInfo &CLI) const { … } /// Places new result values for the node in Results (their number /// and types must exactly match those of the original return values of /// the node), or leaves Results empty, which indicates that the node is not /// to be custom lowered after all. void TargetLowering::LowerOperationWrapper(SDNode *N, SmallVectorImpl<SDValue> &Results, SelectionDAG &DAG) const { … } SDValue TargetLowering::LowerOperation(SDValue Op, SelectionDAG &DAG) const { … } void SelectionDAGBuilder::CopyValueToVirtualRegister(const Value *V, unsigned Reg, ISD::NodeType ExtendType) { … } #include "llvm/CodeGen/SelectionDAGISel.h" /// isOnlyUsedInEntryBlock - If the specified argument is only used in the /// entry block, return true. This includes arguments used by switches, since /// the switch may expand into multiple basic blocks. static bool isOnlyUsedInEntryBlock(const Argument *A, bool FastISel) { … } ArgCopyElisionMapTy; /// Scan the entry block of the function in FuncInfo for arguments that look /// like copies into a local alloca. Record any copied arguments in /// ArgCopyElisionCandidates. static void findArgumentCopyElisionCandidates(const DataLayout &DL, FunctionLoweringInfo *FuncInfo, ArgCopyElisionMapTy &ArgCopyElisionCandidates) { … } /// Try to elide argument copies from memory into a local alloca. Succeeds if /// ArgVal is a load from a suitable fixed stack object. static void tryToElideArgumentCopy( FunctionLoweringInfo &FuncInfo, SmallVectorImpl<SDValue> &Chains, DenseMap<int, int> &ArgCopyElisionFrameIndexMap, SmallPtrSetImpl<const Instruction *> &ElidedArgCopyInstrs, ArgCopyElisionMapTy &ArgCopyElisionCandidates, const Argument &Arg, ArrayRef<SDValue> ArgVals, bool &ArgHasUses) { … } void SelectionDAGISel::LowerArguments(const Function &F) { … } /// Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to /// ensure constants are generated when needed. Remember the virtual registers /// that need to be added to the Machine PHI nodes as input. We cannot just /// directly add them, because expansion might result in multiple MBB's for one /// BB. As such, the start of the BB might correspond to a different MBB than /// the end. void SelectionDAGBuilder::HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) { … } MachineBasicBlock *SelectionDAGBuilder::NextBlock(MachineBasicBlock *MBB) { … } /// During lowering new call nodes can be created (such as memset, etc.). /// Those will become new roots of the current DAG, but complications arise /// when they are tail calls. In such cases, the call lowering will update /// the root, but the builder still needs to know that a tail call has been /// lowered in order to avoid generating an additional return. void SelectionDAGBuilder::updateDAGForMaybeTailCall(SDValue MaybeTC) { … } void SelectionDAGBuilder::lowerWorkItem(SwitchWorkListItem W, Value *Cond, MachineBasicBlock *SwitchMBB, MachineBasicBlock *DefaultMBB) { … } void SelectionDAGBuilder::splitWorkItem(SwitchWorkList &WorkList, const SwitchWorkListItem &W, Value *Cond, MachineBasicBlock *SwitchMBB) { … } // Scale CaseProb after peeling a case with the probablity of PeeledCaseProb // from the swith statement. static BranchProbability scaleCaseProbality(BranchProbability CaseProb, BranchProbability PeeledCaseProb) { … } // Try to peel the top probability case if it exceeds the threshold. // Return current MachineBasicBlock for the switch statement if the peeling // does not occur. // If the peeling is performed, return the newly created MachineBasicBlock // for the peeled switch statement. Also update Clusters to remove the peeled // case. PeeledCaseProb is the BranchProbability for the peeled case. MachineBasicBlock *SelectionDAGBuilder::peelDominantCaseCluster( const SwitchInst &SI, CaseClusterVector &Clusters, BranchProbability &PeeledCaseProb) { … } void SelectionDAGBuilder::visitSwitch(const SwitchInst &SI) { … } void SelectionDAGBuilder::visitStepVector(const CallInst &I) { … } void SelectionDAGBuilder::visitVectorReverse(const CallInst &I) { … } void SelectionDAGBuilder::visitVectorDeinterleave(const CallInst &I) { … } void SelectionDAGBuilder::visitVectorInterleave(const CallInst &I) { … } void SelectionDAGBuilder::visitFreeze(const FreezeInst &I) { … } void SelectionDAGBuilder::visitVectorSplice(const CallInst &I) { … } // Consider the following MIR after SelectionDAG, which produces output in // phyregs in the first case or virtregs in the second case. // // INLINEASM_BR ..., implicit-def $ebx, ..., implicit-def $edx // %5:gr32 = COPY $ebx // %6:gr32 = COPY $edx // %1:gr32 = COPY %6:gr32 // %0:gr32 = COPY %5:gr32 // // INLINEASM_BR ..., def %5:gr32, ..., def %6:gr32 // %1:gr32 = COPY %6:gr32 // %0:gr32 = COPY %5:gr32 // // Given %0, we'd like to return $ebx in the first case and %5 in the second. // Given %1, we'd like to return $edx in the first case and %6 in the second. // // If a callbr has outputs, it will have a single mapping in FuncInfo.ValueMap // to a single virtreg (such as %0). The remaining outputs monotonically // increase in virtreg number from there. If a callbr has no outputs, then it // should not have a corresponding callbr landingpad; in fact, the callbr // landingpad would not even be able to refer to such a callbr. static Register FollowCopyChain(MachineRegisterInfo &MRI, Register Reg) { … } // We must do this walk rather than the simpler // setValue(&I, getCopyFromRegs(CBR, CBR->getType())); // otherwise we will end up with copies of virtregs only valid along direct // edges. void SelectionDAGBuilder::visitCallBrLandingPad(const CallInst &I) { … }
Codebase Browser
llvm