#include "llvm/Instructions.h"
#include "llvm/Intrinsics.h"
#include "llvm/IntrinsicInst.h"
+#include "llvm/ParameterAttributes.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
createDefaultScheduler);
} // namespace
+namespace { struct AsmOperandInfo; }
+
namespace {
/// RegsForValue - This struct represents the physical registers that a
/// particular value is assigned and the type information about the value.
/// anywhere in the function.
std::map<const AllocaInst*, int> StaticAllocaMap;
+#ifndef NDEBUG
+ SmallSet<Instruction*, 8> CatchInfoLost;
+ SmallSet<Instruction*, 8> CatchInfoFound;
+#endif
+
unsigned MakeReg(MVT::ValueType VT) {
return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
}
};
}
+/// isFilterOrSelector - Return true if this instruction is a call to the
+/// eh.filter or the eh.selector intrinsic.
+static bool isFilterOrSelector(Instruction *I) {
+ if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
+ return II->getIntrinsicID() == Intrinsic::eh_selector
+ || II->getIntrinsicID() == Intrinsic::eh_filter;
+ return false;
+}
+
/// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by
/// PHI nodes or outside of the basic block that defines it, or used by a
/// switch instruction, which may expand to multiple basic blocks.
TySize *= CUI->getZExtValue(); // Get total allocated size.
if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects.
StaticAllocaMap[AI] =
- MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
+ MF.getFrameInfo()->CreateStackObject(TySize, Align);
}
for (; BB != EB; ++BB)
if (PN->use_empty()) continue;
MVT::ValueType VT = TLI.getValueType(PN->getType());
- unsigned NumElements;
+ unsigned NumRegisters;
if (VT != MVT::Vector)
- NumElements = TLI.getNumElements(VT);
+ NumRegisters = TLI.getNumRegisters(VT);
else {
MVT::ValueType VT1,VT2;
- NumElements =
+ NumRegisters =
TLI.getVectorTypeBreakdown(cast<VectorType>(PN->getType()),
VT1, VT2);
}
unsigned PHIReg = ValueMap[PN];
assert(PHIReg && "PHI node does not have an assigned virtual register!");
const TargetInstrInfo *TII = TLI.getTargetMachine().getInstrInfo();
- for (unsigned i = 0; i != NumElements; ++i)
+ for (unsigned i = 0; i != NumRegisters; ++i)
BuildMI(MBB, TII->get(TargetInstrInfo::PHI), PHIReg+i);
}
}
const VectorType *PTy = cast<VectorType>(V->getType());
unsigned NumElts = PTy->getNumElements();
MVT::ValueType EltTy = TLI.getValueType(PTy->getElementType());
+ MVT::ValueType VecTy = MVT::getVectorType(EltTy, NumElts);
// Divide the input until we get to a supported size. This will always
// end with a scalar if the target doesn't support vectors.
- while (NumElts > 1 && !TLI.isTypeLegal(getVectorType(EltTy, NumElts))) {
+ while (NumElts > 1 && !TLI.isTypeLegal(VecTy)) {
NumElts >>= 1;
NumVectorRegs <<= 1;
+ VecTy = MVT::getVectorType(EltTy, NumElts);
}
- if (NumElts == 1)
+
+ // Check that VecTy isn't a 1-element vector.
+ if (NumElts == 1 && VecTy == MVT::Other)
VT = EltTy;
else
- VT = getVectorType(EltTy, NumElts);
+ VT = VecTy;
}
-
+
// The common case is that we will only create one register for this
// value. If we have that case, create and return the virtual register.
- unsigned NV = TLI.getNumElements(VT);
+ unsigned NV = TLI.getNumRegisters(VT);
if (NV == 1) {
// If we are promoting this value, pick the next largest supported type.
MVT::ValueType PromotedType = TLI.getTypeToTransformTo(VT);
}
};
+ struct CaseBits {
+ uint64_t Mask;
+ MachineBasicBlock* BB;
+ unsigned Bits;
+
+ CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits):
+ Mask(mask), BB(bb), Bits(bits) { }
+ };
+
typedef std::vector<Case> CaseVector;
+ typedef std::vector<CaseBits> CaseBitsVector;
typedef CaseVector::iterator CaseItr;
typedef std::pair<CaseItr, CaseItr> CaseRange;
/// The comparison function for sorting the switch case values in the vector.
/// WARNING: Case ranges should be disjoint!
struct CaseCmp {
- bool operator () (const Case& C1,
- const Case& C2) {
-
+ bool operator () (const Case& C1, const Case& C2) {
assert(isa<ConstantInt>(C1.Low) && isa<ConstantInt>(C2.High));
const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low);
const ConstantInt* CI2 = cast<const ConstantInt>(C2.High);
}
};
+ struct CaseBitsCmp {
+ bool operator () (const CaseBits& C1, const CaseBits& C2) {
+ return C1.Bits > C2.Bits;
+ }
+ };
+
unsigned Clusterify(CaseVector& Cases, const SwitchInst &SI);
public:
/// JTCases - Vector of JumpTable structures used to communicate
/// SwitchInst code generation information.
std::vector<SelectionDAGISel::JumpTableBlock> JTCases;
+ std::vector<SelectionDAGISel::BitTestBlock> BitTestCases;
/// FuncInfo - Information about the function as a whole.
///
SDOperand getLoadFrom(const Type *Ty, SDOperand Ptr,
const Value *SV, SDOperand Root,
- bool isVolatile);
+ bool isVolatile, unsigned Alignment);
SDOperand getIntPtrConstant(uint64_t Val) {
return DAG.getConstant(Val, TLI.getPointerTy());
N = NewN;
}
- RegsForValue GetRegistersForValue(const std::string &ConstrCode,
- MVT::ValueType VT,
- bool OutReg, bool InReg,
- std::set<unsigned> &OutputRegs,
- std::set<unsigned> &InputRegs);
+ void GetRegistersForValue(AsmOperandInfo &OpInfo, bool HasEarlyClobber,
+ std::set<unsigned> &OutputRegs,
+ std::set<unsigned> &InputRegs);
void FindMergedConditions(Value *Cond, MachineBasicBlock *TBB,
MachineBasicBlock *FBB, MachineBasicBlock *CurBB,
void ExportFromCurrentBlock(Value *V);
void LowerCallTo(Instruction &I,
const Type *CalledValueTy, unsigned CallingConv,
- bool IsTailCall, SDOperand Callee, unsigned OpIdx);
-
+ bool IsTailCall, SDOperand Callee, unsigned OpIdx,
+ MachineBasicBlock *LandingPad = NULL);
+
// Terminator instructions.
void visitRet(ReturnInst &I);
void visitBr(BranchInst &I);
CaseRecVector& WorkList,
Value* SV,
MachineBasicBlock* Default);
+ bool handleBitTestsSwitchCase(CaseRec& CR,
+ CaseRecVector& WorkList,
+ Value* SV,
+ MachineBasicBlock* Default);
void visitSwitchCase(SelectionDAGISel::CaseBlock &CB);
+ void visitBitTestHeader(SelectionDAGISel::BitTestBlock &B);
+ void visitBitTestCase(MachineBasicBlock* NextMBB,
+ unsigned Reg,
+ SelectionDAGISel::BitTestCase &B);
void visitJumpTable(SelectionDAGISel::JumpTable &JT);
void visitJumpTableHeader(SelectionDAGISel::JumpTable &JT,
SelectionDAGISel::JumpTableHeader &JTH);
// These all get lowered before this pass.
void visitInvoke(InvokeInst &I);
- void visitInvoke(InvokeInst &I, bool AsTerminator);
void visitUnwind(UnwindInst &I);
void visitScalarBinary(User &I, unsigned OpCode);
// Source must be expanded. This input value is actually coming from the
// register pair InReg and InReg+1.
MVT::ValueType DestVT = TLI.getTypeToExpandTo(VT);
- unsigned NumVals = TLI.getNumElements(VT);
+ unsigned NumVals = TLI.getNumRegisters(VT);
N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT);
if (NumVals == 1)
N = DAG.getNode(ISD::BIT_CONVERT, VT, N);
unsigned NE = TLI.getVectorTypeBreakdown(PTy, PTyElementVT,
PTyLegalElementVT);
- // Build a VBUILD_VECTOR with the input registers.
+ // Build a VBUILD_VECTOR or VCONCAT_VECTORS with the input registers.
SmallVector<SDOperand, 8> Ops;
if (PTyElementVT == PTyLegalElementVT) {
// If the value types are legal, just VBUILD the CopyFromReg nodes.
Ops.push_back(DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
PTyElementVT));
} else if (PTyElementVT < PTyLegalElementVT) {
- // If the register was promoted, use TRUNCATE of FP_ROUND as appropriate.
+ // If the register was promoted, use TRUNCATE or FP_ROUND as appropriate.
for (unsigned i = 0; i != NE; ++i) {
SDOperand Op = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
- PTyElementVT);
+ PTyLegalElementVT);
if (MVT::isFloatingPoint(PTyElementVT))
Op = DAG.getNode(ISD::FP_ROUND, PTyElementVT, Op);
else
} else {
// If the register was expanded, use BUILD_PAIR.
assert((NE & 1) == 0 && "Must expand into a multiple of 2 elements!");
- for (unsigned i = 0; i != NE/2; ++i) {
+ for (unsigned i = 0; i != NE; ++i) {
SDOperand Op0 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
- PTyElementVT);
+ PTyLegalElementVT);
SDOperand Op1 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
- PTyElementVT);
- Ops.push_back(DAG.getNode(ISD::BUILD_PAIR, VT, Op0, Op1));
+ PTyLegalElementVT);
+ Ops.push_back(DAG.getNode(ISD::BUILD_PAIR, PTyElementVT, Op0, Op1));
}
}
- Ops.push_back(DAG.getConstant(NE, MVT::i32));
- Ops.push_back(DAG.getValueType(PTyLegalElementVT));
- N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size());
-
- // Finally, use a VBIT_CONVERT to make this available as the appropriate
- // vector type.
- N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N,
- DAG.getConstant(PTy->getNumElements(),
- MVT::i32),
- DAG.getValueType(TLI.getValueType(PTy->getElementType())));
+ if (MVT::isVector(PTyElementVT)) {
+ Ops.push_back(DAG.getConstant(NE * MVT::getVectorNumElements(PTyElementVT), MVT::i32));
+ Ops.push_back(DAG.getValueType(MVT::getVectorElementType(PTyElementVT)));
+ N = DAG.getNode(ISD::VCONCAT_VECTORS, MVT::Vector, &Ops[0], Ops.size());
+ } else {
+ Ops.push_back(DAG.getConstant(NE, MVT::i32));
+ Ops.push_back(DAG.getValueType(PTyElementVT));
+ N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size());
+ }
}
return N;
else
TmpVT = MVT::i32;
const FunctionType *FTy = I.getParent()->getParent()->getFunctionType();
+ const ParamAttrsList *Attrs = FTy->getParamAttrs();
ISD::NodeType ExtendKind = ISD::ANY_EXTEND;
- if (FTy->paramHasAttr(0, FunctionType::SExtAttribute))
+ if (Attrs && Attrs->paramHasAttr(0, ParamAttr::SExt))
ExtendKind = ISD::SIGN_EXTEND;
- if (FTy->paramHasAttr(0, FunctionType::ZExtAttribute))
+ if (Attrs && Attrs->paramHasAttr(0, ParamAttr::ZExt))
ExtendKind = ISD::ZERO_EXTEND;
RetOp = DAG.getNode(ExtendKind, TmpVT, RetOp);
}
/// visitJumpTable - Emit JumpTable node in the current MBB
void SelectionDAGLowering::visitJumpTable(SelectionDAGISel::JumpTable &JT) {
// Emit the code for the jump table
- assert(JT.Reg != -1UL && "Should lower JT Header first!");
+ assert(JT.Reg != -1U && "Should lower JT Header first!");
MVT::ValueType PTy = TLI.getPointerTy();
SDOperand Index = DAG.getCopyFromReg(getRoot(), JT.Reg, PTy);
SDOperand Table = DAG.getJumpTable(JT.JTI, PTy);
DAG.setRoot(BrCond);
else
DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond,
- DAG.getBasicBlock(JT.MBB)));
+ DAG.getBasicBlock(JT.MBB)));
+
+ return;
}
+/// visitBitTestHeader - This function emits necessary code to produce value
+/// suitable for "bit tests"
+void SelectionDAGLowering::visitBitTestHeader(SelectionDAGISel::BitTestBlock &B) {
+ // Subtract the minimum value
+ SDOperand SwitchOp = getValue(B.SValue);
+ MVT::ValueType VT = SwitchOp.getValueType();
+ SDOperand SUB = DAG.getNode(ISD::SUB, VT, SwitchOp,
+ DAG.getConstant(B.First, VT));
+
+ // Check range
+ SDOperand RangeCmp = DAG.getSetCC(TLI.getSetCCResultTy(), SUB,
+ DAG.getConstant(B.Range, VT),
+ ISD::SETUGT);
-void SelectionDAGLowering::visitInvoke(InvokeInst &I) {
- assert(0 && "Should never be visited directly");
+ SDOperand ShiftOp;
+ if (VT > TLI.getShiftAmountTy())
+ ShiftOp = DAG.getNode(ISD::TRUNCATE, TLI.getShiftAmountTy(), SUB);
+ else
+ ShiftOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getShiftAmountTy(), SUB);
+
+ // Make desired shift
+ SDOperand SwitchVal = DAG.getNode(ISD::SHL, TLI.getPointerTy(),
+ DAG.getConstant(1, TLI.getPointerTy()),
+ ShiftOp);
+
+ unsigned SwitchReg = FuncInfo.MakeReg(TLI.getPointerTy());
+ SDOperand CopyTo = DAG.getCopyToReg(getRoot(), SwitchReg, SwitchVal);
+ B.Reg = SwitchReg;
+
+ SDOperand BrRange = DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, RangeCmp,
+ DAG.getBasicBlock(B.Default));
+
+ // Set NextBlock to be the MBB immediately after the current one, if any.
+ // This is used to avoid emitting unnecessary branches to the next block.
+ MachineBasicBlock *NextBlock = 0;
+ MachineFunction::iterator BBI = CurMBB;
+ if (++BBI != CurMBB->getParent()->end())
+ NextBlock = BBI;
+
+ MachineBasicBlock* MBB = B.Cases[0].ThisBB;
+ if (MBB == NextBlock)
+ DAG.setRoot(BrRange);
+ else
+ DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, CopyTo,
+ DAG.getBasicBlock(MBB)));
+
+ CurMBB->addSuccessor(B.Default);
+ CurMBB->addSuccessor(MBB);
+
+ return;
}
-void SelectionDAGLowering::visitInvoke(InvokeInst &I, bool AsTerminator) {
+
+/// visitBitTestCase - this function produces one "bit test"
+void SelectionDAGLowering::visitBitTestCase(MachineBasicBlock* NextMBB,
+ unsigned Reg,
+ SelectionDAGISel::BitTestCase &B) {
+ // Emit bit tests and jumps
+ SDOperand SwitchVal = DAG.getCopyFromReg(getRoot(), Reg, TLI.getPointerTy());
+
+ SDOperand AndOp = DAG.getNode(ISD::AND, TLI.getPointerTy(),
+ SwitchVal,
+ DAG.getConstant(B.Mask,
+ TLI.getPointerTy()));
+ SDOperand AndCmp = DAG.getSetCC(TLI.getSetCCResultTy(), AndOp,
+ DAG.getConstant(0, TLI.getPointerTy()),
+ ISD::SETNE);
+ SDOperand BrAnd = DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(),
+ AndCmp, DAG.getBasicBlock(B.TargetBB));
+
+ // Set NextBlock to be the MBB immediately after the current one, if any.
+ // This is used to avoid emitting unnecessary branches to the next block.
+ MachineBasicBlock *NextBlock = 0;
+ MachineFunction::iterator BBI = CurMBB;
+ if (++BBI != CurMBB->getParent()->end())
+ NextBlock = BBI;
+
+ if (NextMBB == NextBlock)
+ DAG.setRoot(BrAnd);
+ else
+ DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrAnd,
+ DAG.getBasicBlock(NextMBB)));
+
+ CurMBB->addSuccessor(B.TargetBB);
+ CurMBB->addSuccessor(NextMBB);
+
+ return;
+}
+
+void SelectionDAGLowering::visitInvoke(InvokeInst &I) {
// Retrieve successors.
MachineBasicBlock *Return = FuncInfo.MBBMap[I.getSuccessor(0)];
MachineBasicBlock *LandingPad = FuncInfo.MBBMap[I.getSuccessor(1)];
-
- if (!AsTerminator) {
- // Mark landing pad so that it doesn't get deleted in branch folding.
- LandingPad->setIsLandingPad();
-
- // Insert a label before the invoke call to mark the try range.
- // This can be used to detect deletion of the invoke via the
- // MachineModuleInfo.
- MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
- unsigned BeginLabel = MMI->NextLabelID();
- DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
- DAG.getConstant(BeginLabel, MVT::i32)));
-
- LowerCallTo(I, I.getCalledValue()->getType(),
- I.getCallingConv(),
- false,
- getValue(I.getOperand(0)),
- 3);
- // Insert a label before the invoke call to mark the try range.
- // This can be used to detect deletion of the invoke via the
- // MachineModuleInfo.
- unsigned EndLabel = MMI->NextLabelID();
- DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
- DAG.getConstant(EndLabel, MVT::i32)));
-
- // Inform MachineModuleInfo of range.
- MMI->addInvoke(LandingPad, BeginLabel, EndLabel);
-
- // Update successor info
- CurMBB->addSuccessor(Return);
- CurMBB->addSuccessor(LandingPad);
- } else {
- // Drop into normal successor.
- DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
- DAG.getBasicBlock(Return)));
+ LowerCallTo(I, I.getCalledValue()->getType(),
+ I.getCallingConv(),
+ false,
+ getValue(I.getOperand(0)),
+ 3, LandingPad);
+
+ // If the value of the invoke is used outside of its defining block, make it
+ // available as a virtual register.
+ if (!I.use_empty()) {
+ DenseMap<const Value*, unsigned>::iterator VMI = FuncInfo.ValueMap.find(&I);
+ if (VMI != FuncInfo.ValueMap.end())
+ DAG.setRoot(CopyValueToVirtualRegister(&I, VMI->second));
}
+
+ // Drop into normal successor.
+ DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
+ DAG.getBasicBlock(Return)));
+
+ // Update successor info
+ CurMBB->addSuccessor(Return);
+ CurMBB->addSuccessor(LandingPad);
}
void SelectionDAGLowering::visitUnwind(UnwindInst &I) {
// Size is the number of Cases represented by this range.
unsigned Size = CR.Range.second - CR.Range.first;
- if (Size >=3)
+ if (Size > 3)
return false;
// Get the MachineFunction which holds the current MBB. This is used when
return true;
}
+static inline bool areJTsAllowed(const TargetLowering &TLI) {
+ return (TLI.isOperationLegal(ISD::BR_JT, MVT::Other) ||
+ TLI.isOperationLegal(ISD::BRIND, MVT::Other));
+}
+
/// handleJTSwitchCase - Emit jumptable for current switch case range
bool SelectionDAGLowering::handleJTSwitchCase(CaseRec& CR,
CaseRecVector& WorkList,
Case& FrontCase = *CR.Range.first;
Case& BackCase = *(CR.Range.second-1);
- // Size is the number of Cases represented by this range.
- unsigned Size = CR.Range.second - CR.Range.first;
-
int64_t First = cast<ConstantInt>(FrontCase.Low)->getSExtValue();
int64_t Last = cast<ConstantInt>(BackCase.High)->getSExtValue();
I!=E; ++I)
TSize += I->size();
- if ((!TLI.isOperationLegal(ISD::BR_JT, MVT::Other) &&
- !TLI.isOperationLegal(ISD::BRIND, MVT::Other)) ||
- Size <= 5)
+ if (!areJTsAllowed(TLI) || TSize <= 3)
return false;
double Density = (double)TSize / (double)((Last - First) + 1ULL);
DOUT << "Lowering jump table\n"
<< "First entry: " << First << ". Last entry: " << Last << "\n"
- << "Size: " << TSize << ". Density: " << Density << "\n";
+ << "Size: " << TSize << ". Density: " << Density << "\n\n";
// Get the MachineFunction which holds the current MBB. This is used when
// inserting any additional MBBs necessary to represent the switch.
CR.CaseBB->addSuccessor(JumpTableBB);
// Build a vector of destination BBs, corresponding to each target
- // of the jump table. If the value of the jump table slot corresponds to
+ // of the jump table. If the value of the jump table slot corresponds to
// a case statement, push the case's BB onto the vector, otherwise, push
// the default BB.
std::vector<MachineBasicBlock*> DestBBs;
// Set the jump table information so that we can codegen it as a second
// MachineBasicBlock
- SelectionDAGISel::JumpTable JT(-1UL, JTI, JumpTableBB, Default);
+ SelectionDAGISel::JumpTable JT(-1U, JTI, JumpTableBB, Default);
SelectionDAGISel::JumpTableHeader JTH(First, Last, SV, CR.CaseBB,
(CR.CaseBB == CurMBB));
if (CR.CaseBB == CurMBB)
int64_t First = cast<ConstantInt>(FrontCase.Low)->getSExtValue();
int64_t Last = cast<ConstantInt>(BackCase.High)->getSExtValue();
- double Density = 0;
+ double FMetric = 0;
CaseItr Pivot = CR.Range.first + Size/2;
// Select optimal pivot, maximizing sum density of LHS and RHS. This will
uint64_t LSize = FrontCase.size();
uint64_t RSize = TSize-LSize;
+ DOUT << "Selecting best pivot: \n"
+ << "First: " << First << ", Last: " << Last <<"\n"
+ << "LSize: " << LSize << ", RSize: " << RSize << "\n";
for (CaseItr I = CR.Range.first, J=I+1, E = CR.Range.second;
J!=E; ++I, ++J) {
int64_t LEnd = cast<ConstantInt>(I->High)->getSExtValue();
int64_t RBegin = cast<ConstantInt>(J->Low)->getSExtValue();
+ assert((RBegin-LEnd>=1) && "Invalid case distance");
double LDensity = (double)LSize / (double)((LEnd - First) + 1ULL);
double RDensity = (double)RSize / (double)((Last - RBegin) + 1ULL);
- if (Density < (LDensity + RDensity)) {
+ double Metric = Log2_64(RBegin-LEnd)*(LDensity+RDensity);
+ // Should always split in some non-trivial place
+ DOUT <<"=>Step\n"
+ << "LEnd: " << LEnd << ", RBegin: " << RBegin << "\n"
+ << "LDensity: " << LDensity << ", RDensity: " << RDensity << "\n"
+ << "Metric: " << Metric << "\n";
+ if (FMetric < Metric) {
Pivot = J;
- Density = LDensity + RDensity;
+ FMetric = Metric;
+ DOUT << "Current metric set to: " << FMetric << "\n";
}
LSize += J->size();
RSize -= J->size();
}
+ if (areJTsAllowed(TLI)) {
+ // If our case is dense we *really* should handle it earlier!
+ assert((FMetric > 0) && "Should handle dense range earlier!");
+ } else {
+ Pivot = CR.Range.first + Size/2;
+ }
CaseRange LHSR(CR.Range.first, Pivot);
CaseRange RHSR(Pivot, CR.Range.second);
return true;
}
+/// handleBitTestsSwitchCase - if current case range has few destination and
+/// range span less, than machine word bitwidth, encode case range into series
+/// of masks and emit bit tests with these masks.
+bool SelectionDAGLowering::handleBitTestsSwitchCase(CaseRec& CR,
+ CaseRecVector& WorkList,
+ Value* SV,
+ MachineBasicBlock* Default){
+ unsigned IntPtrBits = MVT::getSizeInBits(TLI.getPointerTy());
+
+ Case& FrontCase = *CR.Range.first;
+ Case& BackCase = *(CR.Range.second-1);
+
+ // Get the MachineFunction which holds the current MBB. This is used when
+ // inserting any additional MBBs necessary to represent the switch.
+ MachineFunction *CurMF = CurMBB->getParent();
+
+ unsigned numCmps = 0;
+ for (CaseItr I = CR.Range.first, E = CR.Range.second;
+ I!=E; ++I) {
+ // Single case counts one, case range - two.
+ if (I->Low == I->High)
+ numCmps +=1;
+ else
+ numCmps +=2;
+ }
+
+ // Count unique destinations
+ SmallSet<MachineBasicBlock*, 4> Dests;
+ for (CaseItr I = CR.Range.first, E = CR.Range.second; I!=E; ++I) {
+ Dests.insert(I->BB);
+ if (Dests.size() > 3)
+ // Don't bother the code below, if there are too much unique destinations
+ return false;
+ }
+ DOUT << "Total number of unique destinations: " << Dests.size() << "\n"
+ << "Total number of comparisons: " << numCmps << "\n";
+
+ // Compute span of values.
+ Constant* minValue = FrontCase.Low;
+ Constant* maxValue = BackCase.High;
+ uint64_t range = cast<ConstantInt>(maxValue)->getSExtValue() -
+ cast<ConstantInt>(minValue)->getSExtValue();
+ DOUT << "Compare range: " << range << "\n"
+ << "Low bound: " << cast<ConstantInt>(minValue)->getSExtValue() << "\n"
+ << "High bound: " << cast<ConstantInt>(maxValue)->getSExtValue() << "\n";
+
+ if (range>=IntPtrBits ||
+ (!(Dests.size() == 1 && numCmps >= 3) &&
+ !(Dests.size() == 2 && numCmps >= 5) &&
+ !(Dests.size() >= 3 && numCmps >= 6)))
+ return false;
+
+ DOUT << "Emitting bit tests\n";
+ int64_t lowBound = 0;
+
+ // Optimize the case where all the case values fit in a
+ // word without having to subtract minValue. In this case,
+ // we can optimize away the subtraction.
+ if (cast<ConstantInt>(minValue)->getSExtValue() >= 0 &&
+ cast<ConstantInt>(maxValue)->getSExtValue() < IntPtrBits) {
+ range = cast<ConstantInt>(maxValue)->getSExtValue();
+ } else {
+ lowBound = cast<ConstantInt>(minValue)->getSExtValue();
+ }
+
+ CaseBitsVector CasesBits;
+ unsigned i, count = 0;
+
+ for (CaseItr I = CR.Range.first, E = CR.Range.second; I!=E; ++I) {
+ MachineBasicBlock* Dest = I->BB;
+ for (i = 0; i < count; ++i)
+ if (Dest == CasesBits[i].BB)
+ break;
+
+ if (i == count) {
+ assert((count < 3) && "Too much destinations to test!");
+ CasesBits.push_back(CaseBits(0, Dest, 0));
+ count++;
+ }
+
+ uint64_t lo = cast<ConstantInt>(I->Low)->getSExtValue() - lowBound;
+ uint64_t hi = cast<ConstantInt>(I->High)->getSExtValue() - lowBound;
+
+ for (uint64_t j = lo; j <= hi; j++) {
+ CasesBits[i].Mask |= 1ULL << j;
+ CasesBits[i].Bits++;
+ }
+
+ }
+ std::sort(CasesBits.begin(), CasesBits.end(), CaseBitsCmp());
+
+ SelectionDAGISel::BitTestInfo BTC;
+
+ // Figure out which block is immediately after the current one.
+ MachineFunction::iterator BBI = CR.CaseBB;
+ ++BBI;
+
+ const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock();
+
+ DOUT << "Cases:\n";
+ for (unsigned i = 0, e = CasesBits.size(); i!=e; ++i) {
+ DOUT << "Mask: " << CasesBits[i].Mask << ", Bits: " << CasesBits[i].Bits
+ << ", BB: " << CasesBits[i].BB << "\n";
+
+ MachineBasicBlock *CaseBB = new MachineBasicBlock(LLVMBB);
+ CurMF->getBasicBlockList().insert(BBI, CaseBB);
+ BTC.push_back(SelectionDAGISel::BitTestCase(CasesBits[i].Mask,
+ CaseBB,
+ CasesBits[i].BB));
+ }
+
+ SelectionDAGISel::BitTestBlock BTB(lowBound, range, SV,
+ -1U, (CR.CaseBB == CurMBB),
+ CR.CaseBB, Default, BTC);
+
+ if (CR.CaseBB == CurMBB)
+ visitBitTestHeader(BTB);
+
+ BitTestCases.push_back(BTB);
+
+ return true;
+}
+
+
// Clusterify - Transform simple list of Cases into list of CaseRange's
unsigned SelectionDAGLowering::Clusterify(CaseVector& Cases,
const SwitchInst& SI) {
CaseRec CR = WorkList.back();
WorkList.pop_back();
+ if (handleBitTestsSwitchCase(CR, WorkList, SV, Default))
+ continue;
+
// If the range has few cases (two or less) emit a series of specific
// tests.
if (handleSmallSwitchRange(CR, WorkList, SV, Default))
continue;
- // If the switch has more than 5 blocks, and at least 31.25% dense, and the
+ // If the switch has more than 5 blocks, and at least 40% dense, and the
// target supports indirect branches, then emit a jump table rather than
// lowering the switch to a binary tree of conditional branches.
if (handleJTSwitchCase(CR, WorkList, SV, Default))
}
setValue(&I, getLoadFrom(I.getType(), Ptr, I.getOperand(0),
- Root, I.isVolatile()));
+ Root, I.isVolatile(), I.getAlignment()));
}
SDOperand SelectionDAGLowering::getLoadFrom(const Type *Ty, SDOperand Ptr,
const Value *SV, SDOperand Root,
- bool isVolatile) {
+ bool isVolatile,
+ unsigned Alignment) {
SDOperand L;
if (const VectorType *PTy = dyn_cast<VectorType>(Ty)) {
MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
L = DAG.getVecLoad(PTy->getNumElements(), PVT, Root, Ptr,
DAG.getSrcValue(SV));
} else {
- L = DAG.getLoad(TLI.getValueType(Ty), Root, Ptr, SV, 0, isVolatile);
+ L = DAG.getLoad(TLI.getValueType(Ty), Root, Ptr, SV, 0,
+ isVolatile, Alignment);
}
if (isVolatile)
SDOperand Src = getValue(SrcV);
SDOperand Ptr = getValue(I.getOperand(1));
DAG.setRoot(DAG.getStore(getRoot(), Src, Ptr, I.getOperand(1), 0,
- I.isVolatile()));
+ I.isVolatile(), I.getAlignment()));
}
/// IntrinsicCannotAccessMemory - Return true if the specified intrinsic cannot
}
}
+/// ExtractGlobalVariable - If C is a global variable, or a bitcast of one
+/// (possibly constant folded), return it. Otherwise return NULL.
+static GlobalVariable *ExtractGlobalVariable (Constant *C) {
+ if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C))
+ return GV;
+ else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
+ if (CE->getOpcode() == Instruction::BitCast)
+ return dyn_cast<GlobalVariable>(CE->getOperand(0));
+ else if (CE->getOpcode() == Instruction::GetElementPtr) {
+ for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
+ if (!CE->getOperand(i)->isNullValue())
+ return NULL;
+ return dyn_cast<GlobalVariable>(CE->getOperand(0));
+ }
+ }
+ return NULL;
+}
+
+/// addCatchInfo - Extract the personality and type infos from an eh.selector
+/// or eh.filter call, and add them to the specified machine basic block.
+static void addCatchInfo(CallInst &I, MachineModuleInfo *MMI,
+ MachineBasicBlock *MBB) {
+ // Inform the MachineModuleInfo of the personality for this landing pad.
+ ConstantExpr *CE = cast<ConstantExpr>(I.getOperand(2));
+ assert(CE->getOpcode() == Instruction::BitCast &&
+ isa<Function>(CE->getOperand(0)) &&
+ "Personality should be a function");
+ MMI->addPersonality(MBB, cast<Function>(CE->getOperand(0)));
+
+ // Gather all the type infos for this landing pad and pass them along to
+ // MachineModuleInfo.
+ std::vector<GlobalVariable *> TyInfo;
+ for (unsigned i = 3, N = I.getNumOperands(); i < N; ++i) {
+ Constant *C = cast<Constant>(I.getOperand(i));
+ GlobalVariable *GV = ExtractGlobalVariable(C);
+ assert (GV || isa<ConstantPointerNull>(C) &&
+ "TypeInfo must be a global variable or NULL");
+ TyInfo.push_back(GV);
+ }
+ if (I.getCalledFunction()->getIntrinsicID() == Intrinsic::eh_filter)
+ MMI->addFilterTypeInfo(MBB, TyInfo);
+ else
+ MMI->addCatchTypeInfo(MBB, TyInfo);
+}
+
/// visitIntrinsicCall - Lower the call to the specified intrinsic function. If
/// we want to emit this as a call to a named external function, return the name
/// otherwise lower it and return null.
case Intrinsic::eh_exception: {
MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
- if (MMI) {
- // Add a label to mark the beginning of the landing pad. Deletion of the
- // landing pad can thus be detected via the MachineModuleInfo.
- unsigned LabelID = MMI->addLandingPad(CurMBB);
- DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, DAG.getEntryNode(),
- DAG.getConstant(LabelID, MVT::i32)));
-
+ if (ExceptionHandling && MMI) {
// Mark exception register as live in.
unsigned Reg = TLI.getExceptionAddressRegister();
if (Reg) CurMBB->addLiveIn(Reg);
-
+
// Insert the EXCEPTIONADDR instruction.
SDVTList VTs = DAG.getVTList(TLI.getPointerTy(), MVT::Other);
SDOperand Ops[1];
case Intrinsic::eh_selector:
case Intrinsic::eh_filter:{
MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
-
- if (MMI) {
- // Inform the MachineModuleInfo of the personality for this landing pad.
- ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(2));
- assert(CE && CE->getOpcode() == Instruction::BitCast &&
- isa<Function>(CE->getOperand(0)) &&
- "Personality should be a function");
- MMI->addPersonality(CurMBB, cast<Function>(CE->getOperand(0)));
- if (Intrinsic == Intrinsic::eh_filter)
- MMI->setIsFilterLandingPad(CurMBB);
-
- // Gather all the type infos for this landing pad and pass them along to
- // MachineModuleInfo.
- std::vector<GlobalVariable *> TyInfo;
- for (unsigned i = 3, N = I.getNumOperands(); i < N; ++i) {
- ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(i));
- if (CE && CE->getOpcode() == Instruction::BitCast &&
- isa<GlobalVariable>(CE->getOperand(0))) {
- TyInfo.push_back(cast<GlobalVariable>(CE->getOperand(0)));
- } else {
- ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(i));
- assert(CI && CI->getZExtValue() == 0 &&
- "TypeInfo must be a global variable typeinfo or NULL");
- TyInfo.push_back(NULL);
- }
- }
- MMI->addCatchTypeInfo(CurMBB, TyInfo);
-
+
+ if (ExceptionHandling && MMI) {
+ if (CurMBB->isLandingPad())
+ addCatchInfo(I, MMI, CurMBB);
+#ifndef NDEBUG
+ else
+ FuncInfo.CatchInfoLost.insert(&I);
+#endif
+
// Mark exception selector register as live in.
unsigned Reg = TLI.getExceptionSelectorRegister();
if (Reg) CurMBB->addLiveIn(Reg);
// Insert the EHSELECTION instruction.
- SDVTList VTs = DAG.getVTList(MVT::i32, MVT::Other);
+ SDVTList VTs = DAG.getVTList(TLI.getPointerTy(), MVT::Other);
SDOperand Ops[2];
Ops[0] = getValue(I.getOperand(1));
Ops[1] = getRoot();
setValue(&I, Op);
DAG.setRoot(Op.getValue(1));
} else {
- setValue(&I, DAG.getConstant(0, MVT::i32));
+ setValue(&I, DAG.getConstant(0, TLI.getPointerTy()));
}
return 0;
if (MMI) {
// Find the type id for the given typeinfo.
- GlobalVariable *GV = NULL;
- ConstantExpr *CE = dyn_cast<ConstantExpr>(I.getOperand(1));
- if (CE && CE->getOpcode() == Instruction::BitCast &&
- isa<GlobalVariable>(CE->getOperand(0))) {
- GV = cast<GlobalVariable>(CE->getOperand(0));
- } else {
- ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(1));
- assert(CI && CI->getZExtValue() == 0 &&
- "TypeInfo must be a global variable typeinfo or NULL");
- GV = NULL;
- }
-
+ Constant *C = cast<Constant>(I.getOperand(1));
+ GlobalVariable *GV = ExtractGlobalVariable(C);
+ assert (GV || isa<ConstantPointerNull>(C) &&
+ "TypeInfo must be a global variable or NULL");
+
unsigned TypeID = MMI->getTypeIDFor(GV);
setValue(&I, DAG.getConstant(TypeID, MVT::i32));
} else {
DAG.setRoot(Tmp.getValue(1));
return 0;
}
+ case Intrinsic::part_select: {
+ // Currently not implemented: just abort
+ assert(0 && "part_select intrinsic not implemented");
+ abort();
+ }
+ case Intrinsic::part_set: {
+ // Currently not implemented: just abort
+ assert(0 && "part_set intrinsic not implemented");
+ abort();
+ }
case Intrinsic::bswap:
setValue(&I, DAG.getNode(ISD::BSWAP,
getValue(I.getOperand(1)).getValueType(),
case Intrinsic::prefetch:
// FIXME: Currently discarding prefetches.
return 0;
+
+ case Intrinsic::var_annotation:
+ // Discard annotate attributes
+ return 0;
}
}
const Type *CalledValueTy,
unsigned CallingConv,
bool IsTailCall,
- SDOperand Callee, unsigned OpIdx) {
+ SDOperand Callee, unsigned OpIdx,
+ MachineBasicBlock *LandingPad) {
const PointerType *PT = cast<PointerType>(CalledValueTy);
const FunctionType *FTy = cast<FunctionType>(PT->getElementType());
-
+ const ParamAttrsList *Attrs = FTy->getParamAttrs();
+ MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
+ unsigned BeginLabel = 0, EndLabel = 0;
+
TargetLowering::ArgListTy Args;
TargetLowering::ArgListEntry Entry;
Args.reserve(I.getNumOperands());
Value *Arg = I.getOperand(i);
SDOperand ArgNode = getValue(Arg);
Entry.Node = ArgNode; Entry.Ty = Arg->getType();
- Entry.isSExt = FTy->paramHasAttr(i, FunctionType::SExtAttribute);
- Entry.isZExt = FTy->paramHasAttr(i, FunctionType::ZExtAttribute);
- Entry.isInReg = FTy->paramHasAttr(i, FunctionType::InRegAttribute);
- Entry.isSRet = FTy->paramHasAttr(i, FunctionType::StructRetAttribute);
+
+ unsigned attrInd = i - OpIdx + 1;
+ Entry.isSExt = Attrs && Attrs->paramHasAttr(attrInd, ParamAttr::SExt);
+ Entry.isZExt = Attrs && Attrs->paramHasAttr(attrInd, ParamAttr::ZExt);
+ Entry.isInReg = Attrs && Attrs->paramHasAttr(attrInd, ParamAttr::InReg);
+ Entry.isSRet = Attrs && Attrs->paramHasAttr(attrInd, ParamAttr::StructRet);
Args.push_back(Entry);
}
+ if (ExceptionHandling && MMI) {
+ // Insert a label before the invoke call to mark the try range. This can be
+ // used to detect deletion of the invoke via the MachineModuleInfo.
+ BeginLabel = MMI->NextLabelID();
+ DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
+ DAG.getConstant(BeginLabel, MVT::i32)));
+ }
+
std::pair<SDOperand,SDOperand> Result =
TLI.LowerCallTo(getRoot(), I.getType(),
- FTy->paramHasAttr(0,FunctionType::SExtAttribute),
+ Attrs && Attrs->paramHasAttr(0, ParamAttr::SExt),
FTy->isVarArg(), CallingConv, IsTailCall,
Callee, Args, DAG);
if (I.getType() != Type::VoidTy)
setValue(&I, Result.first);
DAG.setRoot(Result.second);
+
+ if (ExceptionHandling && MMI) {
+ // Insert a label at the end of the invoke call to mark the try range. This
+ // can be used to detect deletion of the invoke via the MachineModuleInfo.
+ EndLabel = MMI->NextLabelID();
+ DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(),
+ DAG.getConstant(EndLabel, MVT::i32)));
+
+ // Inform MachineModuleInfo of range.
+ MMI->addInvoke(LandingPad, BeginLabel, EndLabel);
+ }
}
Callee = getValue(I.getOperand(0));
else
Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy());
-
+
LowerCallTo(I, I.getCalledValue()->getType(),
- I.getCallingConv(),
- I.isTailCall(),
- Callee,
- 1);
+ I.getCallingConv(),
+ I.isTailCall(),
+ Callee,
+ 1);
}
return DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Val,
DAG.getConstant(MVT::getVectorNumElements(RegVT),
MVT::i32),
- DAG.getValueType(MVT::getVectorBaseType(RegVT)));
+ DAG.getValueType(MVT::getVectorElementType(RegVT)));
}
if (MVT::isInteger(RegVT)) {
if (MVT::isVector(RegVT)) {
assert(Val.getValueType() == MVT::Vector &&"Not a vector-vector cast?");
Val = DAG.getNode(ISD::VBIT_CONVERT, RegVT, Val);
- } else if (MVT::isInteger(RegVT)) {
+ } else if (MVT::isInteger(RegVT) && MVT::isInteger(Val.getValueType())) {
if (RegVT < ValueVT)
Val = DAG.getNode(ISD::TRUNCATE, RegVT, Val);
else
Val = DAG.getNode(ISD::ANY_EXTEND, RegVT, Val);
- } else
+ } else if (MVT::isFloatingPoint(RegVT) &&
+ MVT::isFloatingPoint(Val.getValueType())) {
Val = DAG.getNode(ISD::FP_EXTEND, RegVT, Val);
+ } else if (MVT::getSizeInBits(RegVT) ==
+ MVT::getSizeInBits(Val.getValueType())) {
+ Val = DAG.getNode(ISD::BIT_CONVERT, RegVT, Val);
+ } else {
+ assert(0 && "Unknown mismatch!");
+ }
}
Chain = DAG.getCopyToReg(Chain, Regs[0], Val, Flag);
Flag = Chain.getValue(1);
/// values added into it.
void RegsForValue::AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
std::vector<SDOperand> &Ops) const {
- Ops.push_back(DAG.getConstant(Code | (Regs.size() << 3), MVT::i32));
+ MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy();
+ Ops.push_back(DAG.getTargetConstant(Code | (Regs.size() << 3), IntPtrTy));
for (unsigned i = 0, e = Regs.size(); i != e; ++i)
Ops.push_back(DAG.getRegister(Regs[i], RegVT));
}
return FoundRC;
}
-RegsForValue SelectionDAGLowering::
-GetRegistersForValue(const std::string &ConstrCode,
- MVT::ValueType VT, bool isOutReg, bool isInReg,
+
+namespace {
+/// AsmOperandInfo - This contains information for each constraint that we are
+/// lowering.
+struct AsmOperandInfo : public InlineAsm::ConstraintInfo {
+ /// ConstraintCode - This contains the actual string for the code, like "m".
+ std::string ConstraintCode;
+
+ /// ConstraintType - Information about the constraint code, e.g. Register,
+ /// RegisterClass, Memory, Other, Unknown.
+ TargetLowering::ConstraintType ConstraintType;
+
+ /// CallOperand/CallOperandval - If this is the result output operand or a
+ /// clobber, this is null, otherwise it is the incoming operand to the
+ /// CallInst. This gets modified as the asm is processed.
+ SDOperand CallOperand;
+ Value *CallOperandVal;
+
+ /// ConstraintVT - The ValueType for the operand value.
+ MVT::ValueType ConstraintVT;
+
+ /// AssignedRegs - If this is a register or register class operand, this
+ /// contains the set of register corresponding to the operand.
+ RegsForValue AssignedRegs;
+
+ AsmOperandInfo(const InlineAsm::ConstraintInfo &info)
+ : InlineAsm::ConstraintInfo(info),
+ ConstraintType(TargetLowering::C_Unknown),
+ CallOperand(0,0), CallOperandVal(0), ConstraintVT(MVT::Other) {
+ }
+
+ void ComputeConstraintToUse(const TargetLowering &TLI);
+
+ /// MarkAllocatedRegs - Once AssignedRegs is set, mark the assigned registers
+ /// busy in OutputRegs/InputRegs.
+ void MarkAllocatedRegs(bool isOutReg, bool isInReg,
+ std::set<unsigned> &OutputRegs,
+ std::set<unsigned> &InputRegs) const {
+ if (isOutReg)
+ OutputRegs.insert(AssignedRegs.Regs.begin(), AssignedRegs.Regs.end());
+ if (isInReg)
+ InputRegs.insert(AssignedRegs.Regs.begin(), AssignedRegs.Regs.end());
+ }
+};
+} // end anon namespace.
+
+/// getConstraintGenerality - Return an integer indicating how general CT is.
+static unsigned getConstraintGenerality(TargetLowering::ConstraintType CT) {
+ switch (CT) {
+ default: assert(0 && "Unknown constraint type!");
+ case TargetLowering::C_Other:
+ case TargetLowering::C_Unknown:
+ return 0;
+ case TargetLowering::C_Register:
+ return 1;
+ case TargetLowering::C_RegisterClass:
+ return 2;
+ case TargetLowering::C_Memory:
+ return 3;
+ }
+}
+
+void AsmOperandInfo::ComputeConstraintToUse(const TargetLowering &TLI) {
+ assert(!Codes.empty() && "Must have at least one constraint");
+
+ std::string *Current = &Codes[0];
+ TargetLowering::ConstraintType CurType = TLI.getConstraintType(*Current);
+ if (Codes.size() == 1) { // Single-letter constraints ('r') are very common.
+ ConstraintCode = *Current;
+ ConstraintType = CurType;
+ return;
+ }
+
+ unsigned CurGenerality = getConstraintGenerality(CurType);
+
+ // If we have multiple constraints, try to pick the most general one ahead
+ // of time. This isn't a wonderful solution, but handles common cases.
+ for (unsigned j = 1, e = Codes.size(); j != e; ++j) {
+ TargetLowering::ConstraintType ThisType = TLI.getConstraintType(Codes[j]);
+ unsigned ThisGenerality = getConstraintGenerality(ThisType);
+ if (ThisGenerality > CurGenerality) {
+ // This constraint letter is more general than the previous one,
+ // use it.
+ CurType = ThisType;
+ Current = &Codes[j];
+ CurGenerality = ThisGenerality;
+ }
+ }
+
+ ConstraintCode = *Current;
+ ConstraintType = CurType;
+}
+
+
+void SelectionDAGLowering::
+GetRegistersForValue(AsmOperandInfo &OpInfo, bool HasEarlyClobber,
std::set<unsigned> &OutputRegs,
std::set<unsigned> &InputRegs) {
- std::pair<unsigned, const TargetRegisterClass*> PhysReg =
- TLI.getRegForInlineAsmConstraint(ConstrCode, VT);
+ // Compute whether this value requires an input register, an output register,
+ // or both.
+ bool isOutReg = false;
+ bool isInReg = false;
+ switch (OpInfo.Type) {
+ case InlineAsm::isOutput:
+ isOutReg = true;
+
+ // If this is an early-clobber output, or if there is an input
+ // constraint that matches this, we need to reserve the input register
+ // so no other inputs allocate to it.
+ isInReg = OpInfo.isEarlyClobber || OpInfo.hasMatchingInput;
+ break;
+ case InlineAsm::isInput:
+ isInReg = true;
+ isOutReg = false;
+ break;
+ case InlineAsm::isClobber:
+ isOutReg = true;
+ isInReg = true;
+ break;
+ }
+
+
+ MachineFunction &MF = DAG.getMachineFunction();
std::vector<unsigned> Regs;
+
+ // If this is a constraint for a single physreg, or a constraint for a
+ // register class, find it.
+ std::pair<unsigned, const TargetRegisterClass*> PhysReg =
+ TLI.getRegForInlineAsmConstraint(OpInfo.ConstraintCode,
+ OpInfo.ConstraintVT);
- unsigned NumRegs = VT != MVT::Other ? TLI.getNumElements(VT) : 1;
+ unsigned NumRegs = 1;
+ if (OpInfo.ConstraintVT != MVT::Other)
+ NumRegs = TLI.getNumRegisters(OpInfo.ConstraintVT);
MVT::ValueType RegVT;
- MVT::ValueType ValueVT = VT;
+ MVT::ValueType ValueVT = OpInfo.ConstraintVT;
+
// If this is a constraint for a specific physical register, like {r17},
// assign it now.
if (PhysReg.first) {
- if (VT == MVT::Other)
+ if (OpInfo.ConstraintVT == MVT::Other)
ValueVT = *PhysReg.second->vt_begin();
// Get the actual register value type. This is important, because the user
Regs.push_back(*I);
}
}
- return RegsForValue(Regs, RegVT, ValueVT);
+ OpInfo.AssignedRegs = RegsForValue(Regs, RegVT, ValueVT);
+ OpInfo.MarkAllocatedRegs(isOutReg, isInReg, OutputRegs, InputRegs);
+ return;
}
// Otherwise, if this was a reference to an LLVM register class, create vregs
// for this reference.
std::vector<unsigned> RegClassRegs;
- if (PhysReg.second) {
+ const TargetRegisterClass *RC = PhysReg.second;
+ if (RC) {
// If this is an early clobber or tied register, our regalloc doesn't know
// how to maintain the constraint. If it isn't, go ahead and create vreg
// and let the regalloc do the right thing.
- if (!isOutReg || !isInReg) {
- if (VT == MVT::Other)
- ValueVT = *PhysReg.second->vt_begin();
+ if (!OpInfo.hasMatchingInput && !OpInfo.isEarlyClobber &&
+ // If there is some other early clobber and this is an input register,
+ // then we are forced to pre-allocate the input reg so it doesn't
+ // conflict with the earlyclobber.
+ !(OpInfo.Type == InlineAsm::isInput && HasEarlyClobber)) {
RegVT = *PhysReg.second->vt_begin();
+
+ if (OpInfo.ConstraintVT == MVT::Other)
+ ValueVT = RegVT;
// Create the appropriate number of virtual registers.
- SSARegMap *RegMap = DAG.getMachineFunction().getSSARegMap();
+ SSARegMap *RegMap = MF.getSSARegMap();
for (; NumRegs; --NumRegs)
Regs.push_back(RegMap->createVirtualRegister(PhysReg.second));
- return RegsForValue(Regs, RegVT, ValueVT);
+ OpInfo.AssignedRegs = RegsForValue(Regs, RegVT, ValueVT);
+ OpInfo.MarkAllocatedRegs(isOutReg, isInReg, OutputRegs, InputRegs);
+ return;
}
// Otherwise, we can't allocate it. Let the code below figure out how to
// This is a reference to a register class that doesn't directly correspond
// to an LLVM register class. Allocate NumRegs consecutive, available,
// registers from the class.
- RegClassRegs = TLI.getRegClassForInlineAsmConstraint(ConstrCode, VT);
+ RegClassRegs = TLI.getRegClassForInlineAsmConstraint(OpInfo.ConstraintCode,
+ OpInfo.ConstraintVT);
}
-
+
const MRegisterInfo *MRI = DAG.getTarget().getRegisterInfo();
- MachineFunction &MF = *CurMBB->getParent();
unsigned NumAllocated = 0;
for (unsigned i = 0, e = RegClassRegs.size(); i != e; ++i) {
unsigned Reg = RegClassRegs[i];
// Check to see if this register is allocatable (i.e. don't give out the
// stack pointer).
- const TargetRegisterClass *RC = isAllocatableRegister(Reg, MF, TLI, MRI);
- if (!RC) {
- // Make sure we find consecutive registers.
- NumAllocated = 0;
- continue;
+ if (RC == 0) {
+ RC = isAllocatableRegister(Reg, MF, TLI, MRI);
+ if (!RC) { // Couldn't allocate this register.
+ // Reset NumAllocated to make sure we return consecutive registers.
+ NumAllocated = 0;
+ continue;
+ }
}
// Okay, this register is good, we can use it.
++NumAllocated;
- // If we allocated enough consecutive
+ // If we allocated enough consecutive registers, succeed.
if (NumAllocated == NumRegs) {
unsigned RegStart = (i-NumAllocated)+1;
unsigned RegEnd = i+1;
// Mark all of the allocated registers used.
- for (unsigned i = RegStart; i != RegEnd; ++i) {
- unsigned Reg = RegClassRegs[i];
- Regs.push_back(Reg);
- if (isOutReg) OutputRegs.insert(Reg); // Mark reg used.
- if (isInReg) InputRegs.insert(Reg); // Mark reg used.
- }
+ for (unsigned i = RegStart; i != RegEnd; ++i)
+ Regs.push_back(RegClassRegs[i]);
- return RegsForValue(Regs, *RC->vt_begin(), VT);
+ OpInfo.AssignedRegs = RegsForValue(Regs, *RC->vt_begin(),
+ OpInfo.ConstraintVT);
+ OpInfo.MarkAllocatedRegs(isOutReg, isInReg, OutputRegs, InputRegs);
+ return;
}
}
// Otherwise, we couldn't allocate enough registers for this.
- return RegsForValue();
-}
-
-/// getConstraintGenerality - Return an integer indicating how general CT is.
-static unsigned getConstraintGenerality(TargetLowering::ConstraintType CT) {
- switch (CT) {
- default: assert(0 && "Unknown constraint type!");
- case TargetLowering::C_Other:
- case TargetLowering::C_Unknown:
- return 0;
- case TargetLowering::C_Register:
- return 1;
- case TargetLowering::C_RegisterClass:
- return 2;
- case TargetLowering::C_Memory:
- return 3;
- }
-}
-
-static std::string GetMostGeneralConstraint(std::vector<std::string> &C,
- const TargetLowering &TLI) {
- assert(!C.empty() && "Must have at least one constraint");
- if (C.size() == 1) return C[0];
-
- std::string *Current = &C[0];
- // If we have multiple constraints, try to pick the most general one ahead
- // of time. This isn't a wonderful solution, but handles common cases.
- TargetLowering::ConstraintType Flavor = TLI.getConstraintType(Current[0]);
- for (unsigned j = 1, e = C.size(); j != e; ++j) {
- TargetLowering::ConstraintType ThisFlavor = TLI.getConstraintType(C[j]);
- if (getConstraintGenerality(ThisFlavor) >
- getConstraintGenerality(Flavor)) {
- // This constraint letter is more general than the previous one,
- // use it.
- Flavor = ThisFlavor;
- Current = &C[j];
- }
- }
- return *Current;
+ return;
}
///
void SelectionDAGLowering::visitInlineAsm(CallInst &I) {
InlineAsm *IA = cast<InlineAsm>(I.getOperand(0));
-
- SDOperand AsmStr = DAG.getTargetExternalSymbol(IA->getAsmString().c_str(),
- MVT::Other);
- std::vector<InlineAsm::ConstraintInfo> Constraints = IA->ParseConstraints();
- std::vector<MVT::ValueType> ConstraintVTs;
-
- /// AsmNodeOperands - A list of pairs. The first element is a register, the
- /// second is a bitfield where bit #0 is set if it is a use and bit #1 is set
- /// if it is a def of that register.
- std::vector<SDOperand> AsmNodeOperands;
- AsmNodeOperands.push_back(SDOperand()); // reserve space for input chain
- AsmNodeOperands.push_back(AsmStr);
+ /// ConstraintOperands - Information about all of the constraints.
+ std::vector<AsmOperandInfo> ConstraintOperands;
SDOperand Chain = getRoot();
SDOperand Flag;
- // We fully assign registers here at isel time. This is not optimal, but
- // should work. For register classes that correspond to LLVM classes, we
- // could let the LLVM RA do its thing, but we currently don't. Do a prepass
- // over the constraints, collecting fixed registers that we know we can't use.
std::set<unsigned> OutputRegs, InputRegs;
- unsigned OpNum = 1;
- for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
- std::string ConstraintCode =
- GetMostGeneralConstraint(Constraints[i].Codes, TLI);
+
+ // Do a prepass over the constraints, canonicalizing them, and building up the
+ // ConstraintOperands list.
+ std::vector<InlineAsm::ConstraintInfo>
+ ConstraintInfos = IA->ParseConstraints();
+
+ // SawEarlyClobber - Keep track of whether we saw an earlyclobber output
+ // constraint. If so, we can't let the register allocator allocate any input
+ // registers, because it will not know to avoid the earlyclobbered output reg.
+ bool SawEarlyClobber = false;
+
+ unsigned OpNo = 1; // OpNo - The operand of the CallInst.
+ for (unsigned i = 0, e = ConstraintInfos.size(); i != e; ++i) {
+ ConstraintOperands.push_back(AsmOperandInfo(ConstraintInfos[i]));
+ AsmOperandInfo &OpInfo = ConstraintOperands.back();
- MVT::ValueType OpVT;
+ MVT::ValueType OpVT = MVT::Other;
- // Compute the value type for each operand and add it to ConstraintVTs.
- switch (Constraints[i].Type) {
+ // Compute the value type for each operand.
+ switch (OpInfo.Type) {
case InlineAsm::isOutput:
- if (!Constraints[i].isIndirectOutput) {
+ if (!OpInfo.isIndirect) {
+ // The return value of the call is this value. As such, there is no
+ // corresponding argument.
assert(I.getType() != Type::VoidTy && "Bad inline asm!");
OpVT = TLI.getValueType(I.getType());
} else {
- const Type *OpTy = I.getOperand(OpNum)->getType();
- OpVT = TLI.getValueType(cast<PointerType>(OpTy)->getElementType());
- OpNum++; // Consumes a call operand.
+ OpInfo.CallOperandVal = I.getOperand(OpNo++);
}
break;
case InlineAsm::isInput:
- OpVT = TLI.getValueType(I.getOperand(OpNum)->getType());
- OpNum++; // Consumes a call operand.
+ OpInfo.CallOperandVal = I.getOperand(OpNo++);
break;
case InlineAsm::isClobber:
- OpVT = MVT::Other;
+ // Nothing to do.
break;
}
-
- ConstraintVTs.push_back(OpVT);
- if (TLI.getRegForInlineAsmConstraint(ConstraintCode, OpVT).first == 0)
- continue; // Not assigned a fixed reg.
+ // If this is an input or an indirect output, process the call argument.
+ if (OpInfo.CallOperandVal) {
+ OpInfo.CallOperand = getValue(OpInfo.CallOperandVal);
+ const Type *OpTy = OpInfo.CallOperandVal->getType();
+ // If this is an indirect operand, the operand is a pointer to the
+ // accessed type.
+ if (OpInfo.isIndirect)
+ OpTy = cast<PointerType>(OpTy)->getElementType();
+
+ // If OpTy is not a first-class value, it may be a struct/union that we
+ // can tile with integers.
+ if (!OpTy->isFirstClassType() && OpTy->isSized()) {
+ unsigned BitSize = TD->getTypeSizeInBits(OpTy);
+ switch (BitSize) {
+ default: break;
+ case 1:
+ case 8:
+ case 16:
+ case 32:
+ case 64:
+ OpTy = IntegerType::get(BitSize);
+ break;
+ }
+ }
+
+ OpVT = TLI.getValueType(OpTy, true);
+ }
- // Build a list of regs that this operand uses. This always has a single
- // element for promoted/expanded operands.
- RegsForValue Regs = GetRegistersForValue(ConstraintCode, OpVT,
- false, false,
- OutputRegs, InputRegs);
+ OpInfo.ConstraintVT = OpVT;
- switch (Constraints[i].Type) {
- case InlineAsm::isOutput:
- // We can't assign any other output to this register.
- OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
- // If this is an early-clobber output, it cannot be assigned to the same
- // value as the input reg.
- if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput)
- InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
- break;
- case InlineAsm::isInput:
- // We can't assign any other input to this register.
- InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
- break;
- case InlineAsm::isClobber:
- // Clobbered regs cannot be used as inputs or outputs.
- InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
- OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end());
- break;
+ // Compute the constraint code and ConstraintType to use.
+ OpInfo.ComputeConstraintToUse(TLI);
+
+ // Keep track of whether we see an earlyclobber.
+ SawEarlyClobber |= OpInfo.isEarlyClobber;
+
+ // If this is a memory input, and if the operand is not indirect, do what we
+ // need to to provide an address for the memory input.
+ if (OpInfo.ConstraintType == TargetLowering::C_Memory &&
+ !OpInfo.isIndirect) {
+ assert(OpInfo.Type == InlineAsm::isInput &&
+ "Can only indirectify direct input operands!");
+
+ // Memory operands really want the address of the value. If we don't have
+ // an indirect input, put it in the constpool if we can, otherwise spill
+ // it to a stack slot.
+
+ // If the operand is a float, integer, or vector constant, spill to a
+ // constant pool entry to get its address.
+ Value *OpVal = OpInfo.CallOperandVal;
+ if (isa<ConstantFP>(OpVal) || isa<ConstantInt>(OpVal) ||
+ isa<ConstantVector>(OpVal)) {
+ OpInfo.CallOperand = DAG.getConstantPool(cast<Constant>(OpVal),
+ TLI.getPointerTy());
+ } else {
+ // Otherwise, create a stack slot and emit a store to it before the
+ // asm.
+ const Type *Ty = OpVal->getType();
+ uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty);
+ unsigned Align = TLI.getTargetData()->getPrefTypeAlignment(Ty);
+ MachineFunction &MF = DAG.getMachineFunction();
+ int SSFI = MF.getFrameInfo()->CreateStackObject(TySize, Align);
+ SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy());
+ Chain = DAG.getStore(Chain, OpInfo.CallOperand, StackSlot, NULL, 0);
+ OpInfo.CallOperand = StackSlot;
+ }
+
+ // There is no longer a Value* corresponding to this operand.
+ OpInfo.CallOperandVal = 0;
+ // It is now an indirect operand.
+ OpInfo.isIndirect = true;
}
- }
+
+ // If this constraint is for a specific register, allocate it before
+ // anything else.
+ if (OpInfo.ConstraintType == TargetLowering::C_Register)
+ GetRegistersForValue(OpInfo, SawEarlyClobber, OutputRegs, InputRegs);
+ }
+ ConstraintInfos.clear();
+
+
+ // Second pass - Loop over all of the operands, assigning virtual or physregs
+ // to registerclass operands.
+ for (unsigned i = 0, e = ConstraintOperands.size(); i != e; ++i) {
+ AsmOperandInfo &OpInfo = ConstraintOperands[i];
+
+ // C_Register operands have already been allocated, Other/Memory don't need
+ // to be.
+ if (OpInfo.ConstraintType == TargetLowering::C_RegisterClass)
+ GetRegistersForValue(OpInfo, SawEarlyClobber, OutputRegs, InputRegs);
+ }
+
+ // AsmNodeOperands - The operands for the ISD::INLINEASM node.
+ std::vector<SDOperand> AsmNodeOperands;
+ AsmNodeOperands.push_back(SDOperand()); // reserve space for input chain
+ AsmNodeOperands.push_back(
+ DAG.getTargetExternalSymbol(IA->getAsmString().c_str(), MVT::Other));
+
// Loop over all of the inputs, copying the operand values into the
// appropriate registers and processing the output regs.
RegsForValue RetValRegs;
+
+ // IndirectStoresToEmit - The set of stores to emit after the inline asm node.
std::vector<std::pair<RegsForValue, Value*> > IndirectStoresToEmit;
- OpNum = 1;
- for (unsigned i = 0, e = Constraints.size(); i != e; ++i) {
- std::string ConstraintCode =
- GetMostGeneralConstraint(Constraints[i].Codes, TLI);
+ for (unsigned i = 0, e = ConstraintOperands.size(); i != e; ++i) {
+ AsmOperandInfo &OpInfo = ConstraintOperands[i];
- switch (Constraints[i].Type) {
+ switch (OpInfo.Type) {
case InlineAsm::isOutput: {
- TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
- if (ConstraintCode.size() == 1) // not a physreg name.
- CTy = TLI.getConstraintType(ConstraintCode);
-
- if (CTy == TargetLowering::C_Memory) {
- // Memory output.
- SDOperand InOperandVal = getValue(I.getOperand(OpNum));
-
- // Check that the operand (the address to store to) isn't a float.
- if (!MVT::isInteger(InOperandVal.getValueType()))
- assert(0 && "MATCH FAIL!");
-
- if (!Constraints[i].isIndirectOutput)
- assert(0 && "MATCH FAIL!");
+ if (OpInfo.ConstraintType != TargetLowering::C_RegisterClass &&
+ OpInfo.ConstraintType != TargetLowering::C_Register) {
+ // Memory output, or 'other' output (e.g. 'X' constraint).
+ assert(OpInfo.isIndirect && "Memory output must be indirect operand");
- OpNum++; // Consumes a call operand.
-
- // Extend/truncate to the right pointer type if needed.
- MVT::ValueType PtrType = TLI.getPointerTy();
- if (InOperandVal.getValueType() < PtrType)
- InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal);
- else if (InOperandVal.getValueType() > PtrType)
- InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal);
-
// Add information to the INLINEASM node to know about this output.
unsigned ResOpType = 4/*MEM*/ | (1 << 3);
- AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
- AsmNodeOperands.push_back(InOperandVal);
+ AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType,
+ TLI.getPointerTy()));
+ AsmNodeOperands.push_back(OpInfo.CallOperand);
break;
}
- // Otherwise, this is a register output.
- assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!");
+ // Otherwise, this is a register or register class output.
- // If this is an early-clobber output, or if there is an input
- // constraint that matches this, we need to reserve the input register
- // so no other inputs allocate to it.
- bool UsesInputRegister = false;
- if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput)
- UsesInputRegister = true;
-
// Copy the output from the appropriate register. Find a register that
// we can use.
- RegsForValue Regs =
- GetRegistersForValue(ConstraintCode, ConstraintVTs[i],
- true, UsesInputRegister,
- OutputRegs, InputRegs);
- if (Regs.Regs.empty()) {
+ if (OpInfo.AssignedRegs.Regs.empty()) {
cerr << "Couldn't allocate output reg for contraint '"
- << ConstraintCode << "'!\n";
+ << OpInfo.ConstraintCode << "'!\n";
exit(1);
}
- if (!Constraints[i].isIndirectOutput) {
+ if (!OpInfo.isIndirect) {
+ // This is the result value of the call.
assert(RetValRegs.Regs.empty() &&
"Cannot have multiple output constraints yet!");
assert(I.getType() != Type::VoidTy && "Bad inline asm!");
- RetValRegs = Regs;
+ RetValRegs = OpInfo.AssignedRegs;
} else {
- IndirectStoresToEmit.push_back(std::make_pair(Regs,
- I.getOperand(OpNum)));
- OpNum++; // Consumes a call operand.
+ IndirectStoresToEmit.push_back(std::make_pair(OpInfo.AssignedRegs,
+ OpInfo.CallOperandVal));
}
// Add information to the INLINEASM node to know that this register is
// set.
- Regs.AddInlineAsmOperands(2 /*REGDEF*/, DAG, AsmNodeOperands);
+ OpInfo.AssignedRegs.AddInlineAsmOperands(2 /*REGDEF*/, DAG,
+ AsmNodeOperands);
break;
}
case InlineAsm::isInput: {
- SDOperand InOperandVal = getValue(I.getOperand(OpNum));
- OpNum++; // Consumes a call operand.
+ SDOperand InOperandVal = OpInfo.CallOperand;
- if (isdigit(ConstraintCode[0])) { // Matching constraint?
+ if (isdigit(OpInfo.ConstraintCode[0])) { // Matching constraint?
// If this is required to match an output register we have already set,
// just use its register.
- unsigned OperandNo = atoi(ConstraintCode.c_str());
+ unsigned OperandNo = atoi(OpInfo.ConstraintCode.c_str());
// Scan until we find the definition we already emitted of this operand.
// When we find it, create a RegsForValue operand.
}
}
- TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
- if (ConstraintCode.size() == 1) // not a physreg name.
- CTy = TLI.getConstraintType(ConstraintCode);
+ if (OpInfo.ConstraintType == TargetLowering::C_Other) {
+ assert(!OpInfo.isIndirect &&
+ "Don't know how to handle indirect other inputs yet!");
- if (CTy == TargetLowering::C_Other) {
InOperandVal = TLI.isOperandValidForConstraint(InOperandVal,
- ConstraintCode[0], DAG);
+ OpInfo.ConstraintCode[0],
+ DAG);
if (!InOperandVal.Val) {
cerr << "Invalid operand for inline asm constraint '"
- << ConstraintCode << "'!\n";
+ << OpInfo.ConstraintCode << "'!\n";
exit(1);
}
// Add information to the INLINEASM node to know about this input.
unsigned ResOpType = 3 /*IMM*/ | (1 << 3);
- AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
+ AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType,
+ TLI.getPointerTy()));
AsmNodeOperands.push_back(InOperandVal);
break;
- } else if (CTy == TargetLowering::C_Memory) {
- // Memory input.
-
- // If the operand is a float, spill to a constant pool entry to get its
- // address.
- if (ConstantFP *Val = dyn_cast<ConstantFP>(I.getOperand(OpNum-1)))
- InOperandVal = DAG.getConstantPool(Val, TLI.getPointerTy());
-
- if (!MVT::isInteger(InOperandVal.getValueType())) {
- cerr << "Match failed, cannot handle this yet!\n";
- InOperandVal.Val->dump();
- exit(1);
- }
-
- // Extend/truncate to the right pointer type if needed.
- MVT::ValueType PtrType = TLI.getPointerTy();
- if (InOperandVal.getValueType() < PtrType)
- InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal);
- else if (InOperandVal.getValueType() > PtrType)
- InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal);
-
+ } else if (OpInfo.ConstraintType == TargetLowering::C_Memory) {
+ assert(OpInfo.isIndirect && "Operand must be indirect to be a mem!");
+ assert(InOperandVal.getValueType() == TLI.getPointerTy() &&
+ "Memory operands expect pointer values");
+
// Add information to the INLINEASM node to know about this input.
unsigned ResOpType = 4/*MEM*/ | (1 << 3);
- AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32));
+ AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType,
+ TLI.getPointerTy()));
AsmNodeOperands.push_back(InOperandVal);
break;
}
- assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!");
+ assert((OpInfo.ConstraintType == TargetLowering::C_RegisterClass ||
+ OpInfo.ConstraintType == TargetLowering::C_Register) &&
+ "Unknown constraint type!");
+ assert(!OpInfo.isIndirect &&
+ "Don't know how to handle indirect register inputs yet!");
// Copy the input into the appropriate registers.
- RegsForValue InRegs =
- GetRegistersForValue(ConstraintCode, ConstraintVTs[i],
- false, true, OutputRegs, InputRegs);
- // FIXME: should be match fail.
- assert(!InRegs.Regs.empty() && "Couldn't allocate input reg!");
+ assert(!OpInfo.AssignedRegs.Regs.empty() &&
+ "Couldn't allocate input reg!");
- InRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag, TLI.getPointerTy());
+ OpInfo.AssignedRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag,
+ TLI.getPointerTy());
- InRegs.AddInlineAsmOperands(1/*REGUSE*/, DAG, AsmNodeOperands);
+ OpInfo.AssignedRegs.AddInlineAsmOperands(1/*REGUSE*/, DAG,
+ AsmNodeOperands);
break;
}
case InlineAsm::isClobber: {
- RegsForValue ClobberedRegs =
- GetRegistersForValue(ConstraintCode, MVT::Other, false, false,
- OutputRegs, InputRegs);
// Add the clobbered value to the operand list, so that the register
// allocator is aware that the physreg got clobbered.
- if (!ClobberedRegs.Regs.empty())
- ClobberedRegs.AddInlineAsmOperands(2/*REGDEF*/, DAG, AsmNodeOperands);
+ if (!OpInfo.AssignedRegs.Regs.empty())
+ OpInfo.AssignedRegs.AddInlineAsmOperands(2/*REGDEF*/, DAG,
+ AsmNodeOperands);
break;
}
}
// If this asm returns a register value, copy the result from that register
// and set it as the value of the call.
- if (!RetValRegs.Regs.empty())
- setValue(&I, RetValRegs.getCopyFromRegs(DAG, Chain, Flag));
+ if (!RetValRegs.Regs.empty()) {
+ SDOperand Val = RetValRegs.getCopyFromRegs(DAG, Chain, Flag);
+
+ // If the result of the inline asm is a vector, it may have the wrong
+ // width/num elts. Make sure to convert it to the right type with
+ // vbit_convert.
+ if (Val.getValueType() == MVT::Vector) {
+ const VectorType *VTy = cast<VectorType>(I.getType());
+ unsigned DesiredNumElts = VTy->getNumElements();
+ MVT::ValueType DesiredEltVT = TLI.getValueType(VTy->getElementType());
+
+ Val = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Val,
+ DAG.getConstant(DesiredNumElts, MVT::i32),
+ DAG.getValueType(DesiredEltVT));
+ }
+
+ setValue(&I, Val);
+ }
std::vector<std::pair<SDOperand, Value*> > StoresToEmit;
// Emit the non-flagged stores from the physregs.
SmallVector<SDOperand, 8> OutChains;
for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i)
- OutChains.push_back(DAG.getStore(Chain, StoresToEmit[i].first,
+ OutChains.push_back(DAG.getStore(Chain, StoresToEmit[i].first,
getValue(StoresToEmit[i].second),
StoresToEmit[i].second, 0));
if (!OutChains.empty())
std::vector<SDOperand>
TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
const FunctionType *FTy = F.getFunctionType();
+ const ParamAttrsList *Attrs = FTy->getParamAttrs();
// Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node.
std::vector<SDOperand> Ops;
Ops.push_back(DAG.getRoot());
// FIXME: Distinguish between a formal with no [sz]ext attribute from one
// that is zero extended!
- if (FTy->paramHasAttr(j, FunctionType::ZExtAttribute))
+ if (Attrs && Attrs->paramHasAttr(j, ParamAttr::ZExt))
Flags &= ~(ISD::ParamFlags::SExt);
- if (FTy->paramHasAttr(j, FunctionType::SExtAttribute))
+ if (Attrs && Attrs->paramHasAttr(j, ParamAttr::SExt))
Flags |= ISD::ParamFlags::SExt;
- if (FTy->paramHasAttr(j, FunctionType::InRegAttribute))
+ if (Attrs && Attrs->paramHasAttr(j, ParamAttr::InReg))
Flags |= ISD::ParamFlags::InReg;
- if (FTy->paramHasAttr(j, FunctionType::StructRetAttribute))
+ if (Attrs && Attrs->paramHasAttr(j, ParamAttr::StructRet))
Flags |= ISD::ParamFlags::StructReturn;
Flags |= (OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs);
// integers. Figure out what the destination type is and how many small
// integers it turns into.
MVT::ValueType NVT = getTypeToExpandTo(VT);
- unsigned NumVals = getNumElements(VT);
+ unsigned NumVals = getNumRegisters(VT);
for (unsigned i = 0; i != NumVals; ++i) {
RetVals.push_back(NVT);
// if it isn't first piece, alignment must be 1
case Promote: {
SDOperand Op(Result, i++);
if (MVT::isInteger(VT)) {
- if (FTy->paramHasAttr(Idx, FunctionType::SExtAttribute))
+ if (Attrs && Attrs->paramHasAttr(Idx, ParamAttr::SExt))
Op = DAG.getNode(ISD::AssertSext, Op.getValueType(), Op,
DAG.getValueType(VT));
- else if (FTy->paramHasAttr(Idx, FunctionType::ZExtAttribute))
+ else if (Attrs && Attrs->paramHasAttr(Idx, ParamAttr::ZExt))
Op = DAG.getNode(ISD::AssertZext, Op.getValueType(), Op,
DAG.getValueType(VT));
Op = DAG.getNode(ISD::TRUNCATE, VT, Op);
Op = DAG.getNode(ExtOp, getTypeToTransformTo(VT), Op);
} else {
assert(MVT::isFloatingPoint(VT) && "Not int or FP?");
- Op = DAG.getNode(ISD::FP_EXTEND, getTypeToTransformTo(VT), Op);
+ // A true promotion would change the size of the argument.
+ // Instead, pretend this is an int. If FP objects are not
+ // passed the same as ints, the original type should be Legal
+ // and we should not get here.
+ Op = DAG.getNode(ISD::BIT_CONVERT,
+ VT==MVT::f32 ? MVT::i32 :
+ (VT==MVT::f64 ? MVT::i64 :
+ MVT::Other),
+ Op);
}
Ops.push_back(Op);
Ops.push_back(DAG.getConstant(Flags, MVT::i32));
// integers. Figure out what the source elt type is and how many small
// integers it is.
MVT::ValueType NVT = getTypeToExpandTo(VT);
- unsigned NumVals = getNumElements(VT);
+ unsigned NumVals = getNumRegisters(VT);
for (unsigned i = 0; i != NumVals; ++i)
RetTys.push_back(NVT);
} else {
SelectionDAG &DAG, TargetLowering &TLI,
std::string &Str, unsigned Offset) {
uint64_t Val = 0;
- unsigned MSB = getSizeInBits(VT) / 8;
+ unsigned MSB = MVT::getSizeInBits(VT) / 8;
if (TLI.isLittleEndian())
Offset = Offset + MSB - 1;
for (unsigned i = 0; i != MSB; ++i) {
unsigned NumMemOps = 0;
while (Size != 0) {
- unsigned VTSize = getSizeInBits(VT) / 8;
+ unsigned VTSize = MVT::getSizeInBits(VT) / 8;
while (VTSize > Size) {
VT = (MVT::ValueType)((unsigned)VT - 1);
VTSize >>= 1;
unsigned Offset = 0;
for (unsigned i = 0; i < NumMemOps; i++) {
MVT::ValueType VT = MemOps[i];
- unsigned VTSize = getSizeInBits(VT) / 8;
+ unsigned VTSize = MVT::getSizeInBits(VT) / 8;
SDOperand Value = getMemsetValue(Op2, VT, DAG);
SDOperand Store = DAG.getStore(getRoot(), Value,
getMemBasePlusOffset(Op1, Offset, DAG, TLI),
for (unsigned i = 0; i < NumMemOps; i++) {
MVT::ValueType VT = MemOps[i];
- unsigned VTSize = getSizeInBits(VT) / 8;
+ unsigned VTSize = MVT::getSizeInBits(VT) / 8;
SDOperand Value, Chain, Store;
if (CopyFromStr) {
FunctionLoweringInfo FuncInfo(TLI, Fn, MF);
+ if (ExceptionHandling)
+ for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
+ if (InvokeInst *Invoke = dyn_cast<InvokeInst>(I->getTerminator()))
+ // Mark landing pad.
+ FuncInfo.MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad();
+
for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
SelectBasicBlock(I, MF, FuncInfo);
E = MF.livein_end(); I != E; ++I)
BB->addLiveIn(I->first);
+#ifndef NDEBUG
+ assert(FuncInfo.CatchInfoFound.size() == FuncInfo.CatchInfoLost.size() &&
+ "Not all catch info was assigned to a landing pad!");
+#endif
+
return true;
}
MVT::ValueType PTyElementVT, PTyLegalElementVT;
unsigned NE = TLI.getVectorTypeBreakdown(cast<VectorType>(V->getType()),
PTyElementVT, PTyLegalElementVT);
+ uint64_t SrcVL = cast<ConstantSDNode>(*(Op.Val->op_end()-2))->getValue();
- // Insert a VBIT_CONVERT of the input vector to a "N x PTyElementVT"
- // MVT::Vector type.
- Op = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Op,
- DAG.getConstant(NE, MVT::i32),
- DAG.getValueType(PTyElementVT));
-
// Loop over all of the elements of the resultant vector,
- // VEXTRACT_VECTOR_ELT'ing them, converting them to PTyLegalElementVT, then
- // copying them into output registers.
+ // VEXTRACT_VECTOR_ELT'ing or VEXTRACT_SUBVECTOR'ing them, converting them
+ // to PTyLegalElementVT, then copying them into output registers.
SmallVector<SDOperand, 8> OutChains;
SDOperand Root = getRoot();
for (unsigned i = 0; i != NE; ++i) {
- SDOperand Elt = DAG.getNode(ISD::VEXTRACT_VECTOR_ELT, PTyElementVT,
- Op, DAG.getConstant(i, TLI.getPointerTy()));
+ SDOperand Elt = MVT::isVector(PTyElementVT) ?
+ DAG.getNode(ISD::VEXTRACT_SUBVECTOR, PTyElementVT,
+ Op, DAG.getConstant(i * (SrcVL / NE), TLI.getPointerTy())) :
+ DAG.getNode(ISD::VEXTRACT_VECTOR_ELT, PTyElementVT,
+ Op, DAG.getConstant(i, TLI.getPointerTy()));
if (PTyElementVT == PTyLegalElementVT) {
// Elements are legal.
OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt));
return DAG.getCopyToReg(getRoot(), Reg, Op);
} else {
DestVT = TLI.getTypeToExpandTo(SrcVT);
- unsigned NumVals = TLI.getNumElements(SrcVT);
+ unsigned NumVals = TLI.getNumRegisters(SrcVT);
if (NumVals == 1)
return DAG.getCopyToReg(getRoot(), Reg,
DAG.getNode(ISD::BIT_CONVERT, DestVT, Op));
EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction());
}
+static void copyCatchInfo(BasicBlock *SrcBB, BasicBlock *DestBB,
+ MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) {
+ assert(!FLI.MBBMap[SrcBB]->isLandingPad() &&
+ "Copying catch info out of a landing pad!");
+ for (BasicBlock::iterator I = SrcBB->begin(), E = --SrcBB->end(); I != E; ++I)
+ if (isFilterOrSelector(I)) {
+ // Apply the catch info to DestBB.
+ addCatchInfo(cast<CallInst>(*I), MMI, FLI.MBBMap[DestBB]);
+#ifndef NDEBUG
+ FLI.CatchInfoFound.insert(I);
+#endif
+ }
+}
+
void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
FunctionLoweringInfo &FuncInfo) {
BB = FuncInfo.MBBMap[LLVMBB];
SDL.setCurrentBasicBlock(BB);
+ MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
+
+ if (ExceptionHandling && MMI && BB->isLandingPad()) {
+ // Add a label to mark the beginning of the landing pad. Deletion of the
+ // landing pad can thus be detected via the MachineModuleInfo.
+ unsigned LabelID = MMI->addLandingPad(BB);
+ DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, DAG.getEntryNode(),
+ DAG.getConstant(LabelID, MVT::i32)));
+
+ // FIXME: Hack around an exception handling flaw (PR1508): the personality
+ // function and list of typeids logically belong to the invoke (or, if you
+ // like, the basic block containing the invoke), and need to be associated
+ // with it in the dwarf exception handling tables. Currently however the
+ // information is provided by intrinsics (eh.filter and eh.selector) that
+ // can be moved to unexpected places by the optimizers: if the unwind edge
+ // is critical, then breaking it can result in the intrinsics being in the
+ // successor of the landing pad, not the landing pad itself. This results
+ // in exceptions not being caught because no typeids are associated with
+ // the invoke. This may not be the only way things can go wrong, but it
+ // is the only way we try to work around for the moment.
+ BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator());
+
+ if (Br && Br->isUnconditional()) { // Critical edge?
+ BasicBlock::iterator I, E;
+ for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I)
+ if (isFilterOrSelector(I))
+ break;
+
+ if (I == E)
+ // No catch info found - try to extract some from the successor.
+ copyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, FuncInfo);
+ }
+ }
+
// Lower all of the non-terminator instructions.
for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end();
I != E; ++I)
SDL.visit(*I);
-
- // Lower call part of invoke.
- InvokeInst *Invoke = dyn_cast<InvokeInst>(LLVMBB->getTerminator());
- if (Invoke) SDL.visitInvoke(*Invoke, false);
-
+
// Ensure that all instructions which are used outside of their defining
- // blocks are available as virtual registers.
+ // blocks are available as virtual registers. Invoke is handled elsewhere.
for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I)
- if (!I->use_empty() && !isa<PHINode>(I)) {
+ if (!I->use_empty() && !isa<PHINode>(I) && !isa<InvokeInst>(I)) {
DenseMap<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I);
if (VMI != FuncInfo.ValueMap.end())
UnorderedChains.push_back(
// Remember that this register needs to added to the machine PHI node as
// the input for this MBB.
MVT::ValueType VT = TLI.getValueType(PN->getType());
- unsigned NumElements;
+ unsigned NumRegisters;
if (VT != MVT::Vector)
- NumElements = TLI.getNumElements(VT);
+ NumRegisters = TLI.getNumRegisters(VT);
else {
MVT::ValueType VT1,VT2;
- NumElements =
+ NumRegisters =
TLI.getVectorTypeBreakdown(cast<VectorType>(PN->getType()),
VT1, VT2);
}
- for (unsigned i = 0, e = NumElements; i != e; ++i)
+ for (unsigned i = 0, e = NumRegisters; i != e; ++i)
PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i));
}
}
}
// Lower the terminator after the copies are emitted.
- if (Invoke) {
- // Just the branch part of invoke.
- SDL.visitInvoke(*Invoke, true);
- } else {
- SDL.visit(*LLVMBB->getTerminator());
- }
+ SDL.visit(*LLVMBB->getTerminator());
// Copy over any CaseBlock records that may now exist due to SwitchInst
// lowering, as well as any jump table information.
SwitchCases = SDL.SwitchCases;
JTCases.clear();
JTCases = SDL.JTCases;
-
+ BitTestCases.clear();
+ BitTestCases = SDL.BitTestCases;
+
// Make sure the root of the DAG is up-to-date.
DAG.setRoot(SDL.getRoot());
}
// Second step, emit the lowered DAG as machine code.
CodeGenAndEmitDAG(DAG);
}
+
+ DOUT << "Total amount of phi nodes to update: "
+ << PHINodesToUpdate.size() << "\n";
+ DEBUG(for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i)
+ DOUT << "Node " << i << " : (" << PHINodesToUpdate[i].first
+ << ", " << PHINodesToUpdate[i].second << ")\n";);
// Next, now that we know what the last MBB the LLVM BB expanded is, update
// PHI nodes in successors.
- if (SwitchCases.empty() && JTCases.empty()) {
+ if (SwitchCases.empty() && JTCases.empty() && BitTestCases.empty()) {
for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) {
MachineInstr *PHI = PHINodesToUpdate[i].first;
assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
}
return;
}
-
+
+ for (unsigned i = 0, e = BitTestCases.size(); i != e; ++i) {
+ // Lower header first, if it wasn't already lowered
+ if (!BitTestCases[i].Emitted) {
+ SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
+ CurDAG = &HSDAG;
+ SelectionDAGLowering HSDL(HSDAG, TLI, FuncInfo);
+ // Set the current basic block to the mbb we wish to insert the code into
+ BB = BitTestCases[i].Parent;
+ HSDL.setCurrentBasicBlock(BB);
+ // Emit the code
+ HSDL.visitBitTestHeader(BitTestCases[i]);
+ HSDAG.setRoot(HSDL.getRoot());
+ CodeGenAndEmitDAG(HSDAG);
+ }
+
+ for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) {
+ SelectionDAG BSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
+ CurDAG = &BSDAG;
+ SelectionDAGLowering BSDL(BSDAG, TLI, FuncInfo);
+ // Set the current basic block to the mbb we wish to insert the code into
+ BB = BitTestCases[i].Cases[j].ThisBB;
+ BSDL.setCurrentBasicBlock(BB);
+ // Emit the code
+ if (j+1 != ej)
+ BSDL.visitBitTestCase(BitTestCases[i].Cases[j+1].ThisBB,
+ BitTestCases[i].Reg,
+ BitTestCases[i].Cases[j]);
+ else
+ BSDL.visitBitTestCase(BitTestCases[i].Default,
+ BitTestCases[i].Reg,
+ BitTestCases[i].Cases[j]);
+
+
+ BSDAG.setRoot(BSDL.getRoot());
+ CodeGenAndEmitDAG(BSDAG);
+ }
+
+ // Update PHI Nodes
+ for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) {
+ MachineInstr *PHI = PHINodesToUpdate[pi].first;
+ MachineBasicBlock *PHIBB = PHI->getParent();
+ assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
+ "This is not a machine PHI node that we are updating!");
+ // This is "default" BB. We have two jumps to it. From "header" BB and
+ // from last "case" BB.
+ if (PHIBB == BitTestCases[i].Default) {
+ PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
+ PHI->addMachineBasicBlockOperand(BitTestCases[i].Parent);
+ PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
+ PHI->addMachineBasicBlockOperand(BitTestCases[i].Cases.back().ThisBB);
+ }
+ // One of "cases" BB.
+ for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) {
+ MachineBasicBlock* cBB = BitTestCases[i].Cases[j].ThisBB;
+ if (cBB->succ_end() !=
+ std::find(cBB->succ_begin(),cBB->succ_end(), PHIBB)) {
+ PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
+ PHI->addMachineBasicBlockOperand(cBB);
+ }
+ }
+ }
+ }
+
// If the JumpTable record is filled in, then we need to emit a jump table.
// Updating the PHI nodes is tricky in this case, since we need to determine
// whether the PHI is a successor of the range check MBB or the jump table MBB
HSDL.visitJumpTableHeader(JTCases[i].second, JTCases[i].first);
HSDAG.setRoot(HSDL.getRoot());
CodeGenAndEmitDAG(HSDAG);
- }
+ }
SelectionDAG JSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
CurDAG = &JSDAG;
MachineBasicBlock *PHIBB = PHI->getParent();
assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
"This is not a machine PHI node that we are updating!");
+ // "default" BB. We can go there only from header BB.
if (PHIBB == JTCases[i].second.Default) {
PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
PHI->addMachineBasicBlockOperand(JTCases[i].first.HeaderBB);
}
+ // JT BB. Just iterate over successors here
if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) {
PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
PHI->addMachineBasicBlockOperand(BB);
}
// Add this to the output node.
+ MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy();
Ops.push_back(DAG.getTargetConstant(4/*MEM*/ | (SelOps.size() << 3),
- MVT::i32));
+ IntPtrTy));
Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
i += 2;
}
if (e != InOps.size())
Ops.push_back(InOps.back());
}
+
+char SelectionDAGISel::ID = 0;
projects / oota-llvm.git / blobdiff