SelectionDAGBuilder.h [plain text]
#ifndef LLVM_LIB_CODEGEN_SELECTIONDAG_SELECTIONDAGBUILDER_H
#define LLVM_LIB_CODEGEN_SELECTIONDAG_SELECTIONDAGBUILDER_H
#include "StatepointLowering.h"
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/Analysis.h"
#include "llvm/CodeGen/SelectionDAG.h"
#include "llvm/CodeGen/SelectionDAGNodes.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Statepoint.h"
#include "llvm/IR/Constants.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Target/TargetLowering.h"
#include <vector>
namespace llvm {
class AddrSpaceCastInst;
class AllocaInst;
class BasicBlock;
class BitCastInst;
class BranchInst;
class CallInst;
class DbgValueInst;
class ExtractElementInst;
class ExtractValueInst;
class FCmpInst;
class FPExtInst;
class FPToSIInst;
class FPToUIInst;
class FPTruncInst;
class Function;
class FunctionLoweringInfo;
class GetElementPtrInst;
class GCFunctionInfo;
class ICmpInst;
class IntToPtrInst;
class IndirectBrInst;
class InvokeInst;
class InsertElementInst;
class InsertValueInst;
class Instruction;
class LoadInst;
class MachineBasicBlock;
class MachineInstr;
class MachineRegisterInfo;
class MDNode;
class MVT;
class PHINode;
class PtrToIntInst;
class ReturnInst;
class SDDbgValue;
class SExtInst;
class SelectInst;
class ShuffleVectorInst;
class SIToFPInst;
class StoreInst;
class SwitchInst;
class DataLayout;
class TargetLibraryInfo;
class TargetLowering;
class TruncInst;
class UIToFPInst;
class UnreachableInst;
class VAArgInst;
class ZExtInst;
class SelectionDAGBuilder {
const Instruction *CurInst;
DenseMap<const Value*, SDValue> NodeMap;
DenseMap<const Value*, SDValue> UnusedArgNodeMap;
class DanglingDebugInfo {
const DbgValueInst* DI;
DebugLoc dl;
unsigned SDNodeOrder;
public:
DanglingDebugInfo() : DI(nullptr), dl(DebugLoc()), SDNodeOrder(0) { }
DanglingDebugInfo(const DbgValueInst *di, DebugLoc DL, unsigned SDNO) :
DI(di), dl(DL), SDNodeOrder(SDNO) { }
const DbgValueInst* getDI() { return DI; }
DebugLoc getdl() { return dl; }
unsigned getSDNodeOrder() { return SDNodeOrder; }
};
DenseMap<const Value*, DanglingDebugInfo> DanglingDebugInfoMap;
public:
SmallVector<SDValue, 8> PendingLoads;
StatepointLoweringState StatepointLowering;
private:
SmallVector<SDValue, 8> PendingExports;
unsigned SDNodeOrder;
enum CaseClusterKind {
CC_Range,
CC_JumpTable,
CC_BitTests
};
struct CaseCluster {
CaseClusterKind Kind;
const ConstantInt *Low, *High;
union {
MachineBasicBlock *MBB;
unsigned JTCasesIndex;
unsigned BTCasesIndex;
};
uint32_t Weight;
static CaseCluster range(const ConstantInt *Low, const ConstantInt *High,
MachineBasicBlock *MBB, uint32_t Weight) {
CaseCluster C;
C.Kind = CC_Range;
C.Low = Low;
C.High = High;
C.MBB = MBB;
C.Weight = Weight;
return C;
}
static CaseCluster jumpTable(const ConstantInt *Low,
const ConstantInt *High, unsigned JTCasesIndex,
uint32_t Weight) {
CaseCluster C;
C.Kind = CC_JumpTable;
C.Low = Low;
C.High = High;
C.JTCasesIndex = JTCasesIndex;
C.Weight = Weight;
return C;
}
static CaseCluster bitTests(const ConstantInt *Low, const ConstantInt *High,
unsigned BTCasesIndex, uint32_t Weight) {
CaseCluster C;
C.Kind = CC_BitTests;
C.Low = Low;
C.High = High;
C.BTCasesIndex = BTCasesIndex;
C.Weight = Weight;
return C;
}
};
typedef std::vector<CaseCluster> CaseClusterVector;
typedef CaseClusterVector::iterator CaseClusterIt;
struct CaseBits {
uint64_t Mask;
MachineBasicBlock* BB;
unsigned Bits;
uint32_t ExtraWeight;
CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits,
uint32_t Weight):
Mask(mask), BB(bb), Bits(bits), ExtraWeight(Weight) { }
CaseBits() : Mask(0), BB(nullptr), Bits(0), ExtraWeight(0) {}
};
typedef std::vector<CaseBits> CaseBitsVector;
void sortAndRangeify(CaseClusterVector &Clusters);
struct CaseBlock {
CaseBlock(ISD::CondCode cc, const Value *cmplhs, const Value *cmprhs,
const Value *cmpmiddle,
MachineBasicBlock *truebb, MachineBasicBlock *falsebb,
MachineBasicBlock *me,
uint32_t trueweight = 0, uint32_t falseweight = 0)
: CC(cc), CmpLHS(cmplhs), CmpMHS(cmpmiddle), CmpRHS(cmprhs),
TrueBB(truebb), FalseBB(falsebb), ThisBB(me),
TrueWeight(trueweight), FalseWeight(falseweight) { }
ISD::CondCode CC;
const Value *CmpLHS, *CmpMHS, *CmpRHS;
MachineBasicBlock *TrueBB, *FalseBB;
MachineBasicBlock *ThisBB;
uint32_t TrueWeight, FalseWeight;
};
struct JumpTable {
JumpTable(unsigned R, unsigned J, MachineBasicBlock *M,
MachineBasicBlock *D): Reg(R), JTI(J), MBB(M), Default(D) {}
unsigned Reg;
unsigned JTI;
MachineBasicBlock *MBB;
MachineBasicBlock *Default;
};
struct JumpTableHeader {
JumpTableHeader(APInt F, APInt L, const Value *SV, MachineBasicBlock *H,
bool E = false):
First(F), Last(L), SValue(SV), HeaderBB(H), Emitted(E) {}
APInt First;
APInt Last;
const Value *SValue;
MachineBasicBlock *HeaderBB;
bool Emitted;
};
typedef std::pair<JumpTableHeader, JumpTable> JumpTableBlock;
struct BitTestCase {
BitTestCase(uint64_t M, MachineBasicBlock* T, MachineBasicBlock* Tr,
uint32_t Weight):
Mask(M), ThisBB(T), TargetBB(Tr), ExtraWeight(Weight) { }
uint64_t Mask;
MachineBasicBlock *ThisBB;
MachineBasicBlock *TargetBB;
uint32_t ExtraWeight;
};
typedef SmallVector<BitTestCase, 3> BitTestInfo;
struct BitTestBlock {
BitTestBlock(APInt F, APInt R, const Value *SV, unsigned Rg, MVT RgVT,
bool E, bool CR, MachineBasicBlock *P, MachineBasicBlock *D,
BitTestInfo C, uint32_t W)
: First(F), Range(R), SValue(SV), Reg(Rg), RegVT(RgVT), Emitted(E),
ContiguousRange(CR), Parent(P), Default(D), Cases(std::move(C)),
Weight(W), DefaultWeight(0) {}
APInt First;
APInt Range;
const Value *SValue;
unsigned Reg;
MVT RegVT;
bool Emitted;
bool ContiguousRange;
MachineBasicBlock *Parent;
MachineBasicBlock *Default;
BitTestInfo Cases;
uint32_t Weight;
uint32_t DefaultWeight;
};
enum { MinJumpTableDensity = 40 };
bool isDense(const CaseClusterVector &Clusters, unsigned *TotalCases,
unsigned First, unsigned Last);
bool buildJumpTable(CaseClusterVector &Clusters, unsigned First,
unsigned Last, const SwitchInst *SI,
MachineBasicBlock *DefaultMBB, CaseCluster &JTCluster);
void findJumpTables(CaseClusterVector &Clusters, const SwitchInst *SI,
MachineBasicBlock *DefaultMBB);
bool rangeFitsInWord(const APInt &Low, const APInt &High);
bool isSuitableForBitTests(unsigned NumDests, unsigned NumCmps,
const APInt &Low, const APInt &High);
bool buildBitTests(CaseClusterVector &Clusters, unsigned First, unsigned Last,
const SwitchInst *SI, CaseCluster &BTCluster);
void findBitTestClusters(CaseClusterVector &Clusters, const SwitchInst *SI);
struct SwitchWorkListItem {
MachineBasicBlock *MBB;
CaseClusterIt FirstCluster;
CaseClusterIt LastCluster;
const ConstantInt *GE;
const ConstantInt *LT;
uint32_t DefaultWeight;
};
typedef SmallVector<SwitchWorkListItem, 4> SwitchWorkList;
static unsigned caseClusterRank(const CaseCluster &CC, CaseClusterIt First,
CaseClusterIt Last);
void splitWorkItem(SwitchWorkList &WorkList, const SwitchWorkListItem &W,
Value *Cond, MachineBasicBlock *SwitchMBB);
void lowerWorkItem(SwitchWorkListItem W, Value *Cond,
MachineBasicBlock *SwitchMBB,
MachineBasicBlock *DefaultMBB);
class StackProtectorDescriptor {
public:
StackProtectorDescriptor() : ParentMBB(nullptr), SuccessMBB(nullptr),
FailureMBB(nullptr), Guard(nullptr),
GuardReg(0) { }
bool shouldEmitStackProtector() const {
return ParentMBB && SuccessMBB && FailureMBB && Guard;
}
void initialize(const BasicBlock *BB,
MachineBasicBlock *MBB,
const CallInst &StackProtCheckCall) {
assert(!shouldEmitStackProtector() && "Stack Protector Descriptor is "
"already initialized!");
ParentMBB = MBB;
SuccessMBB = AddSuccessorMBB(BB, MBB, true);
FailureMBB = AddSuccessorMBB(BB, MBB, false, FailureMBB);
if (!Guard)
Guard = StackProtCheckCall.getArgOperand(0);
}
void resetPerBBState() {
ParentMBB = nullptr;
SuccessMBB = nullptr;
}
void resetPerFunctionState() {
FailureMBB = nullptr;
Guard = nullptr;
GuardReg = 0;
}
MachineBasicBlock *getParentMBB() { return ParentMBB; }
MachineBasicBlock *getSuccessMBB() { return SuccessMBB; }
MachineBasicBlock *getFailureMBB() { return FailureMBB; }
const Value *getGuard() { return Guard; }
unsigned getGuardReg() const { return GuardReg; }
void setGuardReg(unsigned R) { GuardReg = R; }
private:
MachineBasicBlock *ParentMBB;
MachineBasicBlock *SuccessMBB;
MachineBasicBlock *FailureMBB;
const Value *Guard;
unsigned GuardReg;
MachineBasicBlock *AddSuccessorMBB(const BasicBlock *BB,
MachineBasicBlock *ParentMBB,
bool IsLikely,
MachineBasicBlock *SuccMBB = nullptr);
};
private:
const TargetMachine &TM;
public:
static const unsigned LowestSDNodeOrder = 1;
SelectionDAG &DAG;
const DataLayout *DL;
AliasAnalysis *AA;
const TargetLibraryInfo *LibInfo;
std::vector<CaseBlock> SwitchCases;
std::vector<JumpTableBlock> JTCases;
std::vector<BitTestBlock> BitTestCases;
StackProtectorDescriptor SPDescriptor;
DenseMap<const Constant *, unsigned> ConstantsOut;
FunctionLoweringInfo &FuncInfo;
GCFunctionInfo *GFI;
DenseMap<MachineBasicBlock*, SmallVector<unsigned, 4> > LPadToCallSiteMap;
bool HasTailCall;
LLVMContext *Context;
SelectionDAGBuilder(SelectionDAG &dag, FunctionLoweringInfo &funcinfo,
CodeGenOpt::Level ol)
: CurInst(nullptr), SDNodeOrder(LowestSDNodeOrder), TM(dag.getTarget()),
DAG(dag), FuncInfo(funcinfo),
HasTailCall(false) {
}
void init(GCFunctionInfo *gfi, AliasAnalysis &aa,
const TargetLibraryInfo *li);
void clear();
void clearDanglingDebugInfo();
SDValue getRoot();
SDValue getControlRoot();
SDLoc getCurSDLoc() const {
return SDLoc(CurInst, SDNodeOrder);
}
DebugLoc getCurDebugLoc() const {
return CurInst ? CurInst->getDebugLoc() : DebugLoc();
}
unsigned getSDNodeOrder() const { return SDNodeOrder; }
void CopyValueToVirtualRegister(const Value *V, unsigned Reg);
void visit(const Instruction &I);
void visit(unsigned Opcode, const User &I);
SDValue getCopyFromRegs(const Value *V, Type *Ty);
void resolveDanglingDebugInfo(const Value *V, SDValue Val);
SDValue getValue(const Value *V);
bool findValue(const Value *V) const;
SDValue getNonRegisterValue(const Value *V);
SDValue getValueImpl(const Value *V);
void setValue(const Value *V, SDValue NewN) {
SDValue &N = NodeMap[V];
assert(!N.getNode() && "Already set a value for this node!");
N = NewN;
}
void setUnusedArgValue(const Value *V, SDValue NewN) {
SDValue &N = UnusedArgNodeMap[V];
assert(!N.getNode() && "Already set a value for this node!");
N = NewN;
}
void FindMergedConditions(const Value *Cond, MachineBasicBlock *TBB,
MachineBasicBlock *FBB, MachineBasicBlock *CurBB,
MachineBasicBlock *SwitchBB,
Instruction::BinaryOps Opc,
uint32_t TW, uint32_t FW);
void EmitBranchForMergedCondition(const Value *Cond, MachineBasicBlock *TBB,
MachineBasicBlock *FBB,
MachineBasicBlock *CurBB,
MachineBasicBlock *SwitchBB,
uint32_t TW, uint32_t FW);
bool ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases);
bool isExportableFromCurrentBlock(const Value *V, const BasicBlock *FromBB);
void CopyToExportRegsIfNeeded(const Value *V);
void ExportFromCurrentBlock(const Value *V);
void LowerCallTo(ImmutableCallSite CS, SDValue Callee, bool IsTailCall,
const BasicBlock *EHPadBB = nullptr);
std::pair<SDValue, SDValue> lowerCallOperands(
ImmutableCallSite CS,
unsigned ArgIdx,
unsigned NumArgs,
SDValue Callee,
Type *ReturnTy,
const BasicBlock *EHPadBB = nullptr,
bool IsPatchPoint = false);
void UpdateSplitBlock(MachineBasicBlock *First, MachineBasicBlock *Last);
void LowerStatepoint(ImmutableStatepoint Statepoint,
const BasicBlock *EHPadBB = nullptr);
private:
std::pair<SDValue, SDValue>
lowerInvokable(TargetLowering::CallLoweringInfo &CLI,
const BasicBlock *EHPadBB = nullptr);
void visitRet(const ReturnInst &I);
void visitBr(const BranchInst &I);
void visitSwitch(const SwitchInst &I);
void visitIndirectBr(const IndirectBrInst &I);
void visitUnreachable(const UnreachableInst &I);
void visitCleanupEndPad(const CleanupEndPadInst &I);
void visitCleanupRet(const CleanupReturnInst &I);
void visitCatchEndPad(const CatchEndPadInst &I);
void visitCatchRet(const CatchReturnInst &I);
void visitCatchPad(const CatchPadInst &I);
void visitTerminatePad(const TerminatePadInst &TPI);
void visitCleanupPad(const CleanupPadInst &CPI);
uint32_t getEdgeWeight(const MachineBasicBlock *Src,
const MachineBasicBlock *Dst) const;
void addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst,
uint32_t Weight = 0);
public:
void visitSwitchCase(CaseBlock &CB,
MachineBasicBlock *SwitchBB);
void visitSPDescriptorParent(StackProtectorDescriptor &SPD,
MachineBasicBlock *ParentBB);
void visitSPDescriptorFailure(StackProtectorDescriptor &SPD);
void visitBitTestHeader(BitTestBlock &B, MachineBasicBlock *SwitchBB);
void visitBitTestCase(BitTestBlock &BB,
MachineBasicBlock* NextMBB,
uint32_t BranchWeightToNext,
unsigned Reg,
BitTestCase &B,
MachineBasicBlock *SwitchBB);
void visitJumpTable(JumpTable &JT);
void visitJumpTableHeader(JumpTable &JT, JumpTableHeader &JTH,
MachineBasicBlock *SwitchBB);
private:
void visitInvoke(const InvokeInst &I);
void visitResume(const ResumeInst &I);
void visitBinary(const User &I, unsigned OpCode);
void visitShift(const User &I, unsigned Opcode);
void visitAdd(const User &I) { visitBinary(I, ISD::ADD); }
void visitFAdd(const User &I) { visitBinary(I, ISD::FADD); }
void visitSub(const User &I) { visitBinary(I, ISD::SUB); }
void visitFSub(const User &I);
void visitMul(const User &I) { visitBinary(I, ISD::MUL); }
void visitFMul(const User &I) { visitBinary(I, ISD::FMUL); }
void visitURem(const User &I) { visitBinary(I, ISD::UREM); }
void visitSRem(const User &I) { visitBinary(I, ISD::SREM); }
void visitFRem(const User &I) { visitBinary(I, ISD::FREM); }
void visitUDiv(const User &I) { visitBinary(I, ISD::UDIV); }
void visitSDiv(const User &I);
void visitFDiv(const User &I) { visitBinary(I, ISD::FDIV); }
void visitAnd (const User &I) { visitBinary(I, ISD::AND); }
void visitOr (const User &I) { visitBinary(I, ISD::OR); }
void visitXor (const User &I) { visitBinary(I, ISD::XOR); }
void visitShl (const User &I) { visitShift(I, ISD::SHL); }
void visitLShr(const User &I) { visitShift(I, ISD::SRL); }
void visitAShr(const User &I) { visitShift(I, ISD::SRA); }
void visitICmp(const User &I);
void visitFCmp(const User &I);
void visitTrunc(const User &I);
void visitZExt(const User &I);
void visitSExt(const User &I);
void visitFPTrunc(const User &I);
void visitFPExt(const User &I);
void visitFPToUI(const User &I);
void visitFPToSI(const User &I);
void visitUIToFP(const User &I);
void visitSIToFP(const User &I);
void visitPtrToInt(const User &I);
void visitIntToPtr(const User &I);
void visitBitCast(const User &I);
void visitAddrSpaceCast(const User &I);
void visitExtractElement(const User &I);
void visitInsertElement(const User &I);
void visitShuffleVector(const User &I);
void visitExtractValue(const ExtractValueInst &I);
void visitInsertValue(const InsertValueInst &I);
void visitLandingPad(const LandingPadInst &I);
void visitGetElementPtr(const User &I);
void visitSelect(const User &I);
void visitAlloca(const AllocaInst &I);
void visitLoad(const LoadInst &I);
void visitStore(const StoreInst &I);
void visitMaskedLoad(const CallInst &I);
void visitMaskedStore(const CallInst &I);
void visitMaskedGather(const CallInst &I);
void visitMaskedScatter(const CallInst &I);
void visitAtomicCmpXchg(const AtomicCmpXchgInst &I);
void visitAtomicRMW(const AtomicRMWInst &I);
void visitFence(const FenceInst &I);
void visitPHI(const PHINode &I);
void visitCall(const CallInst &I);
bool visitMemCmpCall(const CallInst &I);
bool visitMemChrCall(const CallInst &I);
bool visitStrCpyCall(const CallInst &I, bool isStpcpy);
bool visitStrCmpCall(const CallInst &I);
bool visitStrLenCall(const CallInst &I);
bool visitStrNLenCall(const CallInst &I);
bool visitUnaryFloatCall(const CallInst &I, unsigned Opcode);
bool visitBinaryFloatCall(const CallInst &I, unsigned Opcode);
void visitAtomicLoad(const LoadInst &I);
void visitAtomicStore(const StoreInst &I);
void visitLoadFromSwiftError(const LoadInst &I);
void visitStoreToSwiftError(const StoreInst &I);
void visitInlineAsm(ImmutableCallSite CS);
const char *visitIntrinsicCall(const CallInst &I, unsigned Intrinsic);
void visitTargetIntrinsic(const CallInst &I, unsigned Intrinsic);
void visitVAStart(const CallInst &I);
void visitVAArg(const VAArgInst &I);
void visitVAEnd(const CallInst &I);
void visitVACopy(const CallInst &I);
void visitStackmap(const CallInst &I);
void visitPatchpoint(ImmutableCallSite CS,
const BasicBlock *EHPadBB = nullptr);
void visitStatepoint(const CallInst &I);
void visitGCRelocate(const CallInst &I);
void visitGCResult(const CallInst &I);
void visitUserOp1(const Instruction &I) {
llvm_unreachable("UserOp1 should not exist at instruction selection time!");
}
void visitUserOp2(const Instruction &I) {
llvm_unreachable("UserOp2 should not exist at instruction selection time!");
}
void processIntegerCallValue(const Instruction &I,
SDValue Value, bool IsSigned);
void HandlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB);
bool EmitFuncArgumentDbgValue(const Value *V, DILocalVariable *Variable,
DIExpression *Expr, DILocation *DL,
int64_t Offset, bool IsIndirect,
const SDValue &N);
MachineBasicBlock *NextBlock(MachineBasicBlock *MBB);
void updateDAGForMaybeTailCall(SDValue MaybeTC);
};
struct RegsForValue {
SmallVector<EVT, 4> ValueVTs;
SmallVector<MVT, 4> RegVTs;
SmallVector<unsigned, 4> Regs;
RegsForValue();
RegsForValue(const SmallVector<unsigned, 4> ®s, MVT regvt, EVT valuevt);
RegsForValue(LLVMContext &Context, const TargetLowering &TLI,
const DataLayout &DL, unsigned Reg, Type *Ty);
void append(const RegsForValue &RHS) {
ValueVTs.append(RHS.ValueVTs.begin(), RHS.ValueVTs.end());
RegVTs.append(RHS.RegVTs.begin(), RHS.RegVTs.end());
Regs.append(RHS.Regs.begin(), RHS.Regs.end());
}
SDValue getCopyFromRegs(SelectionDAG &DAG, FunctionLoweringInfo &FuncInfo,
SDLoc dl,
SDValue &Chain, SDValue *Flag,
const Value *V = nullptr) const;
void
getCopyToRegs(SDValue Val, SelectionDAG &DAG, SDLoc dl, SDValue &Chain,
SDValue *Flag, const Value *V = nullptr,
ISD::NodeType PreferredExtendType = ISD::ANY_EXTEND) const;
void AddInlineAsmOperands(unsigned Kind,
bool HasMatching, unsigned MatchingIdx, SDLoc dl,
SelectionDAG &DAG,
std::vector<SDValue> &Ops) const;
};
}
#endif