//
// The LLVM Compiler Infrastructure
//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "isel"
+#include "llvm/ADT/BitVector.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/CodeGen/SelectionDAGISel.h"
#include "llvm/CodeGen/ScheduleDAG.h"
-#include "llvm/CallingConv.h"
#include "llvm/Constants.h"
+#include "llvm/CallingConv.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Instructions.h"
#include "llvm/Intrinsics.h"
#include "llvm/IntrinsicInst.h"
-#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/ParameterAttributes.h"
+#include "llvm/CodeGen/Collector.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
-#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineJumpTableInfo.h"
+#include "llvm/CodeGen/MachineModuleInfo.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/SchedulerRegistry.h"
#include "llvm/CodeGen/SelectionDAG.h"
-#include "llvm/CodeGen/SSARegMap.h"
#include "llvm/Target/MRegisterInfo.h"
-#include "llvm/Target/TargetAsmInfo.h"
#include "llvm/Target/TargetData.h"
#include "llvm/Target/TargetFrameInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetOptions.h"
-#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/Compiler.h"
static cl::opt<bool>
ViewSchedDAGs("view-sched-dags", cl::Hidden,
cl::desc("Pop up a window to show sched dags as they are processed"));
+static cl::opt<bool>
+ViewSUnitDAGs("view-sunit-dags", cl::Hidden,
+ cl::desc("Pop up a window to show SUnit dags after they are processed"));
#else
-static const bool ViewISelDAGs = 0, ViewSchedDAGs = 0;
+static const bool ViewISelDAGs = 0, ViewSchedDAGs = 0, ViewSUnitDAGs = 0;
#endif
-
//===---------------------------------------------------------------------===//
///
/// RegisterScheduler class - Track the registration of instruction schedulers.
namespace {
cl::opt<RegisterScheduler::FunctionPassCtor, false,
RegisterPassParser<RegisterScheduler> >
- ISHeuristic("sched",
+ ISHeuristic("pre-RA-sched",
cl::init(&createDefaultScheduler),
- cl::desc("Instruction schedulers available:"));
+ cl::desc("Instruction schedulers available (before register allocation):"));
static RegisterScheduler
defaultListDAGScheduler("default", " Best scheduler for the target",
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.
/// This is needed because values can be promoted into larger registers and
/// expanded into multiple smaller registers than the value.
struct VISIBILITY_HIDDEN RegsForValue {
- /// Regs - This list hold the register (for legal and promoted values)
+ /// Regs - This list holds the register (for legal and promoted values)
/// or register set (for expanded values) that the value should be assigned
/// to.
std::vector<unsigned> Regs;
/// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from
/// this value and returns the result as a ValueVT value. This uses
/// Chain/Flag as the input and updates them for the output Chain/Flag.
+ /// If the Flag pointer is NULL, no flag is used.
SDOperand getCopyFromRegs(SelectionDAG &DAG,
- SDOperand &Chain, SDOperand &Flag) const;
+ SDOperand &Chain, SDOperand *Flag) const;
/// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
/// specified value into the registers specified by this object. This uses
/// Chain/Flag as the input and updates them for the output Chain/Flag.
+ /// If the Flag pointer is NULL, no flag is used.
void getCopyToRegs(SDOperand Val, SelectionDAG &DAG,
- SDOperand &Chain, SDOperand &Flag,
- MVT::ValueType PtrVT) const;
+ SDOperand &Chain, SDOperand *Flag) const;
/// AddInlineAsmOperands - Add this value to the specified inlineasm node
/// operand list. This adds the code marker and includes the number of
TargetLowering &TLI;
Function &Fn;
MachineFunction &MF;
- SSARegMap *RegMap;
+ MachineRegisterInfo &RegInfo;
FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF);
/// 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));
+ return RegInfo.createVirtualRegister(TLI.getRegClassFor(VT));
}
/// isExportedInst - Return true if the specified value is an instruction
};
}
+/// isSelector - Return true if this instruction is a call to the
+/// eh.selector intrinsic.
+static bool isSelector(Instruction *I) {
+ if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))
+ return (II->getIntrinsicID() == Intrinsic::eh_selector_i32 ||
+ II->getIntrinsicID() == Intrinsic::eh_selector_i64);
+ 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.
FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli,
Function &fn, MachineFunction &mf)
- : TLI(tli), Fn(fn), MF(mf), RegMap(MF.getSSARegMap()) {
+ : TLI(tli), Fn(fn), MF(mf), RegInfo(MF.getRegInfo()) {
// Create a vreg for each argument register that is not dead and is used
// outside of the entry block for the function.
if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
if (ConstantInt *CUI = dyn_cast<ConstantInt>(AI->getArraySize())) {
const Type *Ty = AI->getAllocatedType();
- uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty);
+ uint64_t TySize = TLI.getTargetData()->getABITypeSize(Ty);
unsigned Align =
- std::max((unsigned)TLI.getTargetData()->getTypeAlignmentPref(Ty),
+ std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
AI->getAlignment());
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;
- if (VT != MVT::Vector)
- NumElements = TLI.getNumElements(VT);
- else {
- MVT::ValueType VT1,VT2;
- NumElements =
- TLI.getPackedTypeBreakdown(cast<PackedType>(PN->getType()),
- VT1, VT2);
- }
+ unsigned NumRegisters = TLI.getNumRegisters(VT);
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);
}
}
unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) {
MVT::ValueType VT = TLI.getValueType(V->getType());
- // The number of multiples of registers that we need, to, e.g., split up
- // a <2 x int64> -> 4 x i32 registers.
- unsigned NumVectorRegs = 1;
-
- // If this is a packed type, figure out what type it will decompose into
- // and how many of the elements it will use.
- if (VT == MVT::Vector) {
- const PackedType *PTy = cast<PackedType>(V->getType());
- unsigned NumElts = PTy->getNumElements();
- MVT::ValueType EltTy = TLI.getValueType(PTy->getElementType());
-
- // 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))) {
- NumElts >>= 1;
- NumVectorRegs <<= 1;
- }
- if (NumElts == 1)
- VT = EltTy;
- else
- VT = getVectorType(EltTy, NumElts);
- }
-
- // 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);
- if (NV == 1) {
- // If we are promoting this value, pick the next largest supported type.
- MVT::ValueType PromotedType = TLI.getTypeToTransformTo(VT);
- unsigned Reg = MakeReg(PromotedType);
- // If this is a vector of supported or promoted types (e.g. 4 x i16),
- // create all of the registers.
- for (unsigned i = 1; i != NumVectorRegs; ++i)
- MakeReg(PromotedType);
- return Reg;
- }
-
- // If this value is represented with multiple target registers, make sure
- // to create enough consecutive registers of the right (smaller) type.
- VT = TLI.getTypeToExpandTo(VT);
- unsigned R = MakeReg(VT);
- for (unsigned i = 1; i != NV*NumVectorRegs; ++i)
- MakeReg(VT);
+ unsigned NumRegisters = TLI.getNumRegisters(VT);
+ MVT::ValueType RegisterVT = TLI.getRegisterType(VT);
+
+ unsigned R = MakeReg(RegisterVT);
+ for (unsigned i = 1; i != NumRegisters; ++i)
+ MakeReg(RegisterVT);
+
return R;
}
/// analysis.
std::vector<SDOperand> PendingLoads;
- /// Case - A pair of values to record the Value for a switch case, and the
- /// case's target basic block.
- typedef std::pair<Constant*, MachineBasicBlock*> Case;
- typedef std::vector<Case>::iterator CaseItr;
- typedef std::pair<CaseItr, CaseItr> CaseRange;
+ /// Case - A struct to record the Value for a switch case, and the
+ /// case's target basic block.
+ struct Case {
+ Constant* Low;
+ Constant* High;
+ MachineBasicBlock* BB;
+
+ Case() : Low(0), High(0), BB(0) { }
+ Case(Constant* low, Constant* high, MachineBasicBlock* bb) :
+ Low(low), High(high), BB(bb) { }
+ uint64_t size() const {
+ uint64_t rHigh = cast<ConstantInt>(High)->getSExtValue();
+ uint64_t rLow = cast<ConstantInt>(Low)->getSExtValue();
+ return (rHigh - rLow + 1ULL);
+ }
+ };
+
+ 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;
/// CaseRec - A struct with ctor used in lowering switches to a binary tree
/// of conditional branches.
/// processed at this point in the binary search tree.
CaseRange Range;
};
-
- /// The comparison function for sorting Case values.
+
+ typedef std::vector<CaseRec> CaseRecVector;
+
+ /// 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) {
- assert(isa<ConstantInt>(C1.first) && isa<ConstantInt>(C2.first));
- return cast<const ConstantInt>(C1.first)->getZExtValue() <
- cast<const ConstantInt>(C2.first)->getZExtValue();
+ 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);
+ return CI1->getValue().slt(CI2->getValue());
}
};
+
+ struct CaseBitsCmp {
+ bool operator () (const CaseBits& C1, const CaseBits& C2) {
+ return C1.Bits > C2.Bits;
+ }
+ };
+
+ unsigned Clusterify(CaseVector& Cases, const SwitchInst &SI);
public:
// TLI - This is information that describes the available target features we
TargetLowering &TLI;
SelectionDAG &DAG;
const TargetData *TD;
+ AliasAnalysis &AA;
/// SwitchCases - Vector of CaseBlock structures used to communicate
/// SwitchInst code generation information.
std::vector<SelectionDAGISel::CaseBlock> SwitchCases;
- SelectionDAGISel::JumpTable JT;
+ /// 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.
///
FunctionLoweringInfo &FuncInfo;
+
+ /// GCI - Garbage collection metadata for the function.
+ CollectorMetadata *GCI;
SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli,
- FunctionLoweringInfo &funcinfo)
- : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()),
- JT(0,0,0,0), FuncInfo(funcinfo) {
+ AliasAnalysis &aa,
+ FunctionLoweringInfo &funcinfo,
+ CollectorMetadata *gci)
+ : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()), AA(aa),
+ FuncInfo(funcinfo), GCI(gci) {
}
/// getRoot - Return the current virtual root of the Selection DAG.
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,
unsigned Opc);
bool isExportableFromCurrentBlock(Value *V, const BasicBlock *FromBB);
void ExportFromCurrentBlock(Value *V);
-
+ void LowerCallTo(CallSite CS, SDOperand Callee, bool IsTailCall,
+ MachineBasicBlock *LandingPad = NULL);
+
// Terminator instructions.
void visitRet(ReturnInst &I);
void visitBr(BranchInst &I);
void visitSwitch(SwitchInst &I);
void visitUnreachable(UnreachableInst &I) { /* noop */ }
- // Helper for visitSwitch
+ // Helpers for visitSwitch
+ bool handleSmallSwitchRange(CaseRec& CR,
+ CaseRecVector& WorkList,
+ Value* SV,
+ MachineBasicBlock* Default);
+ bool handleJTSwitchCase(CaseRec& CR,
+ CaseRecVector& WorkList,
+ Value* SV,
+ MachineBasicBlock* Default);
+ bool handleBTSplitSwitchCase(CaseRec& CR,
+ 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) { assert(0 && "TODO"); }
- void visitUnwind(UnwindInst &I) { assert(0 && "TODO"); }
+ void visitInvoke(InvokeInst &I);
+ void visitUnwind(UnwindInst &I);
- void visitScalarBinary(User &I, unsigned OpCode);
- void visitVectorBinary(User &I, unsigned OpCode);
- void visitEitherBinary(User &I, unsigned ScalarOp, unsigned VectorOp);
+ void visitBinary(User &I, unsigned OpCode);
void visitShift(User &I, unsigned Opcode);
void visitAdd(User &I) {
- if (isa<PackedType>(I.getType()))
- visitVectorBinary(I, ISD::VADD);
- else if (I.getType()->isFloatingPoint())
- visitScalarBinary(I, ISD::FADD);
+ if (I.getType()->isFPOrFPVector())
+ visitBinary(I, ISD::FADD);
else
- visitScalarBinary(I, ISD::ADD);
+ visitBinary(I, ISD::ADD);
}
void visitSub(User &I);
void visitMul(User &I) {
- if (isa<PackedType>(I.getType()))
- visitVectorBinary(I, ISD::VMUL);
- else if (I.getType()->isFloatingPoint())
- visitScalarBinary(I, ISD::FMUL);
+ if (I.getType()->isFPOrFPVector())
+ visitBinary(I, ISD::FMUL);
else
- visitScalarBinary(I, ISD::MUL);
+ visitBinary(I, ISD::MUL);
}
- void visitURem(User &I) { visitScalarBinary(I, ISD::UREM); }
- void visitSRem(User &I) { visitScalarBinary(I, ISD::SREM); }
- void visitFRem(User &I) { visitScalarBinary(I, ISD::FREM); }
- void visitUDiv(User &I) { visitEitherBinary(I, ISD::UDIV, ISD::VUDIV); }
- void visitSDiv(User &I) { visitEitherBinary(I, ISD::SDIV, ISD::VSDIV); }
- void visitFDiv(User &I) { visitEitherBinary(I, ISD::FDIV, ISD::VSDIV); }
- void visitAnd (User &I) { visitEitherBinary(I, ISD::AND, ISD::VAND ); }
- void visitOr (User &I) { visitEitherBinary(I, ISD::OR, ISD::VOR ); }
- void visitXor (User &I) { visitEitherBinary(I, ISD::XOR, ISD::VXOR ); }
+ void visitURem(User &I) { visitBinary(I, ISD::UREM); }
+ void visitSRem(User &I) { visitBinary(I, ISD::SREM); }
+ void visitFRem(User &I) { visitBinary(I, ISD::FREM); }
+ void visitUDiv(User &I) { visitBinary(I, ISD::UDIV); }
+ void visitSDiv(User &I) { visitBinary(I, ISD::SDIV); }
+ void visitFDiv(User &I) { visitBinary(I, ISD::FDIV); }
+ void visitAnd (User &I) { visitBinary(I, ISD::AND); }
+ void visitOr (User &I) { visitBinary(I, ISD::OR); }
+ void visitXor (User &I) { visitBinary(I, ISD::XOR); }
void visitShl (User &I) { visitShift(I, ISD::SHL); }
void visitLShr(User &I) { visitShift(I, ISD::SRL); }
void visitAShr(User &I) { visitShift(I, ISD::SRA); }
void visitStore(StoreInst &I);
void visitPHI(PHINode &I) { } // PHI nodes are handled specially.
void visitCall(CallInst &I);
- void visitInlineAsm(CallInst &I);
+ void visitInlineAsm(CallSite CS);
const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic);
void visitTargetIntrinsic(CallInst &I, unsigned Intrinsic);
};
} // end namespace llvm
+
+/// getCopyFromParts - Create a value that contains the
+/// specified legal parts combined into the value they represent.
+static SDOperand getCopyFromParts(SelectionDAG &DAG,
+ const SDOperand *Parts,
+ unsigned NumParts,
+ MVT::ValueType PartVT,
+ MVT::ValueType ValueVT,
+ ISD::NodeType AssertOp = ISD::DELETED_NODE) {
+ if (!MVT::isVector(ValueVT) || NumParts == 1) {
+ SDOperand Val = Parts[0];
+
+ // If the value was expanded, copy from the top part.
+ if (NumParts > 1) {
+ assert(NumParts == 2 &&
+ "Cannot expand to more than 2 elts yet!");
+ SDOperand Hi = Parts[1];
+ if (!DAG.getTargetLoweringInfo().isLittleEndian())
+ std::swap(Val, Hi);
+ return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Val, Hi);
+ }
+
+ // Otherwise, if the value was promoted or extended, truncate it to the
+ // appropriate type.
+ if (PartVT == ValueVT)
+ return Val;
+
+ if (MVT::isVector(PartVT)) {
+ assert(MVT::isVector(ValueVT) && "Unknown vector conversion!");
+ return DAG.getNode(ISD::BIT_CONVERT, ValueVT, Val);
+ }
+
+ if (MVT::isVector(ValueVT)) {
+ assert(NumParts == 1 &&
+ MVT::getVectorElementType(ValueVT) == PartVT &&
+ MVT::getVectorNumElements(ValueVT) == 1 &&
+ "Only trivial scalar-to-vector conversions should get here!");
+ return DAG.getNode(ISD::BUILD_VECTOR, ValueVT, Val);
+ }
+
+ if (MVT::isInteger(PartVT) &&
+ MVT::isInteger(ValueVT)) {
+ if (ValueVT < PartVT) {
+ // For a truncate, see if we have any information to
+ // indicate whether the truncated bits will always be
+ // zero or sign-extension.
+ if (AssertOp != ISD::DELETED_NODE)
+ Val = DAG.getNode(AssertOp, PartVT, Val,
+ DAG.getValueType(ValueVT));
+ return DAG.getNode(ISD::TRUNCATE, ValueVT, Val);
+ } else {
+ return DAG.getNode(ISD::ANY_EXTEND, ValueVT, Val);
+ }
+ }
+
+ if (MVT::isFloatingPoint(PartVT) &&
+ MVT::isFloatingPoint(ValueVT))
+ return DAG.getNode(ISD::FP_ROUND, ValueVT, Val);
+
+ if (MVT::getSizeInBits(PartVT) ==
+ MVT::getSizeInBits(ValueVT))
+ return DAG.getNode(ISD::BIT_CONVERT, ValueVT, Val);
+
+ assert(0 && "Unknown mismatch!");
+ }
+
+ // Handle a multi-element vector.
+ MVT::ValueType IntermediateVT, RegisterVT;
+ unsigned NumIntermediates;
+ unsigned NumRegs =
+ DAG.getTargetLoweringInfo()
+ .getVectorTypeBreakdown(ValueVT, IntermediateVT, NumIntermediates,
+ RegisterVT);
+
+ assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!");
+ assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!");
+ assert(RegisterVT == Parts[0].getValueType() &&
+ "Part type doesn't match part!");
+
+ // Assemble the parts into intermediate operands.
+ SmallVector<SDOperand, 8> Ops(NumIntermediates);
+ if (NumIntermediates == NumParts) {
+ // If the register was not expanded, truncate or copy the value,
+ // as appropriate.
+ for (unsigned i = 0; i != NumParts; ++i)
+ Ops[i] = getCopyFromParts(DAG, &Parts[i], 1,
+ PartVT, IntermediateVT);
+ } else if (NumParts > 0) {
+ // If the intermediate type was expanded, build the intermediate operands
+ // from the parts.
+ assert(NumParts % NumIntermediates == 0 &&
+ "Must expand into a divisible number of parts!");
+ unsigned Factor = NumParts / NumIntermediates;
+ for (unsigned i = 0; i != NumIntermediates; ++i)
+ Ops[i] = getCopyFromParts(DAG, &Parts[i * Factor], Factor,
+ PartVT, IntermediateVT);
+ }
+
+ // Build a vector with BUILD_VECTOR or CONCAT_VECTORS from the intermediate
+ // operands.
+ return DAG.getNode(MVT::isVector(IntermediateVT) ?
+ ISD::CONCAT_VECTORS :
+ ISD::BUILD_VECTOR,
+ ValueVT, &Ops[0], NumIntermediates);
+}
+
+/// getCopyToParts - Create a series of nodes that contain the
+/// specified value split into legal parts.
+static void getCopyToParts(SelectionDAG &DAG,
+ SDOperand Val,
+ SDOperand *Parts,
+ unsigned NumParts,
+ MVT::ValueType PartVT) {
+ TargetLowering &TLI = DAG.getTargetLoweringInfo();
+ MVT::ValueType PtrVT = TLI.getPointerTy();
+ MVT::ValueType ValueVT = Val.getValueType();
+
+ if (!MVT::isVector(ValueVT) || NumParts == 1) {
+ // If the value was expanded, copy from the parts.
+ if (NumParts > 1) {
+ for (unsigned i = 0; i != NumParts; ++i)
+ Parts[i] = DAG.getNode(ISD::EXTRACT_ELEMENT, PartVT, Val,
+ DAG.getConstant(i, PtrVT));
+ if (!DAG.getTargetLoweringInfo().isLittleEndian())
+ std::reverse(Parts, Parts + NumParts);
+ return;
+ }
+
+ // If there is a single part and the types differ, this must be
+ // a promotion.
+ if (PartVT != ValueVT) {
+ if (MVT::isVector(PartVT)) {
+ assert(MVT::isVector(ValueVT) &&
+ "Not a vector-vector cast?");
+ Val = DAG.getNode(ISD::BIT_CONVERT, PartVT, Val);
+ } else if (MVT::isVector(ValueVT)) {
+ assert(NumParts == 1 &&
+ MVT::getVectorElementType(ValueVT) == PartVT &&
+ MVT::getVectorNumElements(ValueVT) == 1 &&
+ "Only trivial vector-to-scalar conversions should get here!");
+ Val = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, PartVT, Val,
+ DAG.getConstant(0, PtrVT));
+ } else if (MVT::isInteger(PartVT) && MVT::isInteger(ValueVT)) {
+ if (PartVT < ValueVT)
+ Val = DAG.getNode(ISD::TRUNCATE, PartVT, Val);
+ else
+ Val = DAG.getNode(ISD::ANY_EXTEND, PartVT, Val);
+ } else if (MVT::isFloatingPoint(PartVT) &&
+ MVT::isFloatingPoint(ValueVT)) {
+ Val = DAG.getNode(ISD::FP_EXTEND, PartVT, Val);
+ } else if (MVT::getSizeInBits(PartVT) ==
+ MVT::getSizeInBits(ValueVT)) {
+ Val = DAG.getNode(ISD::BIT_CONVERT, PartVT, Val);
+ } else {
+ assert(0 && "Unknown mismatch!");
+ }
+ }
+ Parts[0] = Val;
+ return;
+ }
+
+ // Handle a multi-element vector.
+ MVT::ValueType IntermediateVT, RegisterVT;
+ unsigned NumIntermediates;
+ unsigned NumRegs =
+ DAG.getTargetLoweringInfo()
+ .getVectorTypeBreakdown(ValueVT, IntermediateVT, NumIntermediates,
+ RegisterVT);
+ unsigned NumElements = MVT::getVectorNumElements(ValueVT);
+
+ assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!");
+ assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!");
+
+ // Split the vector into intermediate operands.
+ SmallVector<SDOperand, 8> Ops(NumIntermediates);
+ for (unsigned i = 0; i != NumIntermediates; ++i)
+ if (MVT::isVector(IntermediateVT))
+ Ops[i] = DAG.getNode(ISD::EXTRACT_SUBVECTOR,
+ IntermediateVT, Val,
+ DAG.getConstant(i * (NumElements / NumIntermediates),
+ PtrVT));
+ else
+ Ops[i] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT,
+ IntermediateVT, Val,
+ DAG.getConstant(i, PtrVT));
+
+ // Split the intermediate operands into legal parts.
+ if (NumParts == NumIntermediates) {
+ // If the register was not expanded, promote or copy the value,
+ // as appropriate.
+ for (unsigned i = 0; i != NumParts; ++i)
+ getCopyToParts(DAG, Ops[i], &Parts[i], 1, PartVT);
+ } else if (NumParts > 0) {
+ // If the intermediate type was expanded, split each the value into
+ // legal parts.
+ assert(NumParts % NumIntermediates == 0 &&
+ "Must expand into a divisible number of parts!");
+ unsigned Factor = NumParts / NumIntermediates;
+ for (unsigned i = 0; i != NumIntermediates; ++i)
+ getCopyToParts(DAG, Ops[i], &Parts[i * Factor], Factor, PartVT);
+ }
+}
+
+
SDOperand SelectionDAGLowering::getValue(const Value *V) {
SDOperand &N = NodeMap[V];
if (N.Val) return N;
} else if (isa<ConstantPointerNull>(C)) {
return N = DAG.getConstant(0, TLI.getPointerTy());
} else if (isa<UndefValue>(C)) {
- if (!isa<PackedType>(VTy))
+ if (!isa<VectorType>(VTy))
return N = DAG.getNode(ISD::UNDEF, VT);
- // Create a VBUILD_VECTOR of undef nodes.
- const PackedType *PTy = cast<PackedType>(VTy);
+ // Create a BUILD_VECTOR of undef nodes.
+ const VectorType *PTy = cast<VectorType>(VTy);
unsigned NumElements = PTy->getNumElements();
MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
Ops.assign(NumElements, DAG.getNode(ISD::UNDEF, PVT));
// Create a VConstant node with generic Vector type.
- Ops.push_back(DAG.getConstant(NumElements, MVT::i32));
- Ops.push_back(DAG.getValueType(PVT));
- return N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector,
+ MVT::ValueType VT = MVT::getVectorType(PVT, NumElements);
+ return N = DAG.getNode(ISD::BUILD_VECTOR, VT,
&Ops[0], Ops.size());
} else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
- return N = DAG.getConstantFP(CFP->getValue(), VT);
- } else if (const PackedType *PTy = dyn_cast<PackedType>(VTy)) {
+ return N = DAG.getConstantFP(CFP->getValueAPF(), VT);
+ } else if (const VectorType *PTy = dyn_cast<VectorType>(VTy)) {
unsigned NumElements = PTy->getNumElements();
MVT::ValueType PVT = TLI.getValueType(PTy->getElementType());
// Now that we know the number and type of the elements, push a
// Constant or ConstantFP node onto the ops list for each element of
- // the packed constant.
+ // the vector constant.
SmallVector<SDOperand, 8> Ops;
- if (ConstantPacked *CP = dyn_cast<ConstantPacked>(C)) {
+ if (ConstantVector *CP = dyn_cast<ConstantVector>(C)) {
for (unsigned i = 0; i != NumElements; ++i)
Ops.push_back(getValue(CP->getOperand(i)));
} else {
- assert(isa<ConstantAggregateZero>(C) && "Unknown packed constant!");
+ assert(isa<ConstantAggregateZero>(C) && "Unknown vector constant!");
SDOperand Op;
if (MVT::isFloatingPoint(PVT))
Op = DAG.getConstantFP(0, PVT);
Ops.assign(NumElements, Op);
}
- // Create a VBUILD_VECTOR node with generic Vector type.
- Ops.push_back(DAG.getConstant(NumElements, MVT::i32));
- Ops.push_back(DAG.getValueType(PVT));
- return NodeMap[V] = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0],
+ // Create a BUILD_VECTOR node.
+ MVT::ValueType VT = MVT::getVectorType(PVT, NumElements);
+ return NodeMap[V] = DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0],
Ops.size());
} else {
// Canonicalize all constant ints to be unsigned.
return DAG.getFrameIndex(SI->second, TLI.getPointerTy());
}
- DenseMap<const Value*, unsigned>::iterator VMI =
- FuncInfo.ValueMap.find(V);
- assert(VMI != FuncInfo.ValueMap.end() && "Value not in map!");
-
- unsigned InReg = VMI->second;
-
- // If this type is not legal, make it so now.
- if (VT != MVT::Vector) {
- if (TLI.getTypeAction(VT) == TargetLowering::Expand) {
- // Source must be expanded. This input value is actually coming from the
- // register pair VMI->second and VMI->second+1.
- MVT::ValueType DestVT = TLI.getTypeToExpandTo(VT);
- unsigned NumVals = TLI.getNumElements(VT);
- N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT);
- if (NumVals == 1)
- N = DAG.getNode(ISD::BIT_CONVERT, VT, N);
- else {
- assert(NumVals == 2 && "1 to 4 (and more) expansion not implemented!");
- N = DAG.getNode(ISD::BUILD_PAIR, VT, N,
- DAG.getCopyFromReg(DAG.getEntryNode(), InReg+1, DestVT));
- }
- } else {
- MVT::ValueType DestVT = TLI.getTypeToTransformTo(VT);
- N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT);
- if (TLI.getTypeAction(VT) == TargetLowering::Promote) // Promotion case
- N = MVT::isFloatingPoint(VT)
- ? DAG.getNode(ISD::FP_ROUND, VT, N)
- : DAG.getNode(ISD::TRUNCATE, VT, N);
- }
- } else {
- // Otherwise, if this is a vector, make it available as a generic vector
- // here.
- MVT::ValueType PTyElementVT, PTyLegalElementVT;
- const PackedType *PTy = cast<PackedType>(VTy);
- unsigned NE = TLI.getPackedTypeBreakdown(PTy, PTyElementVT,
- PTyLegalElementVT);
-
- // Build a VBUILD_VECTOR with the input registers.
- SmallVector<SDOperand, 8> Ops;
- if (PTyElementVT == PTyLegalElementVT) {
- // If the value types are legal, just VBUILD the CopyFromReg nodes.
- for (unsigned i = 0; i != NE; ++i)
- 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.
- for (unsigned i = 0; i != NE; ++i) {
- SDOperand Op = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
- PTyElementVT);
- if (MVT::isFloatingPoint(PTyElementVT))
- Op = DAG.getNode(ISD::FP_ROUND, PTyElementVT, Op);
- else
- Op = DAG.getNode(ISD::TRUNCATE, PTyElementVT, Op);
- Ops.push_back(Op);
- }
- } 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) {
- SDOperand Op0 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
- PTyElementVT);
- SDOperand Op1 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++,
- PTyElementVT);
- Ops.push_back(DAG.getNode(ISD::BUILD_PAIR, VT, 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())));
- }
+ unsigned InReg = FuncInfo.ValueMap[V];
+ assert(InReg && "Value not in map!");
- return N;
+ MVT::ValueType RegisterVT = TLI.getRegisterType(VT);
+ unsigned NumRegs = TLI.getNumRegisters(VT);
+
+ std::vector<unsigned> Regs(NumRegs);
+ for (unsigned i = 0; i != NumRegs; ++i)
+ Regs[i] = InReg + i;
+
+ RegsForValue RFV(Regs, RegisterVT, VT);
+ SDOperand Chain = DAG.getEntryNode();
+
+ return RFV.getCopyFromRegs(DAG, Chain, NULL);
}
SDOperand RetOp = getValue(I.getOperand(i));
// If this is an integer return value, we need to promote it ourselves to
- // the full width of a register, since LegalizeOp will use ANY_EXTEND rather
- // than sign/zero.
+ // the full width of a register, since getCopyToParts and Legalize will use
+ // ANY_EXTEND rather than sign/zero.
// FIXME: C calling convention requires the return type to be promoted to
// at least 32-bit. But this is not necessary for non-C calling conventions.
if (MVT::isInteger(RetOp.getValueType()) &&
TmpVT = TLI.getTypeToTransformTo(MVT::i32);
else
TmpVT = MVT::i32;
- const FunctionType *FTy = I.getParent()->getParent()->getFunctionType();
+ const Function *F = I.getParent()->getParent();
ISD::NodeType ExtendKind = ISD::ANY_EXTEND;
- if (FTy->paramHasAttr(0, FunctionType::SExtAttribute))
+ if (F->paramHasAttr(0, ParamAttr::SExt))
ExtendKind = ISD::SIGN_EXTEND;
- if (FTy->paramHasAttr(0, FunctionType::ZExtAttribute))
+ if (F->paramHasAttr(0, ParamAttr::ZExt))
ExtendKind = ISD::ZERO_EXTEND;
RetOp = DAG.getNode(ExtendKind, TmpVT, RetOp);
+ NewValues.push_back(RetOp);
+ NewValues.push_back(DAG.getConstant(false, MVT::i32));
+ } else {
+ MVT::ValueType VT = RetOp.getValueType();
+ unsigned NumParts = TLI.getNumRegisters(VT);
+ MVT::ValueType PartVT = TLI.getRegisterType(VT);
+ SmallVector<SDOperand, 4> Parts(NumParts);
+ getCopyToParts(DAG, RetOp, &Parts[0], NumParts, PartVT);
+ for (unsigned i = 0; i < NumParts; ++i) {
+ NewValues.push_back(Parts[i]);
+ NewValues.push_back(DAG.getConstant(false, MVT::i32));
+ }
}
- NewValues.push_back(RetOp);
- NewValues.push_back(DAG.getConstant(false, MVT::i32));
}
DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other,
&NewValues[0], NewValues.size()));
}
SelectionDAGISel::CaseBlock CB(Condition, BOp->getOperand(0),
- BOp->getOperand(1), TBB, FBB, CurBB);
+ BOp->getOperand(1), NULL, TBB, FBB, CurBB);
SwitchCases.push_back(CB);
return;
}
// Create a CaseBlock record representing this branch.
SelectionDAGISel::CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(),
- TBB, FBB, CurBB);
+ NULL, TBB, FBB, CurBB);
SwitchCases.push_back(CB);
return;
}
// Update machine-CFG edges.
CurMBB->addSuccessor(Succ0MBB);
-
return;
}
// Create a CaseBlock record representing this branch.
SelectionDAGISel::CaseBlock CB(ISD::SETEQ, CondVal, ConstantInt::getTrue(),
- Succ0MBB, Succ1MBB, CurMBB);
+ NULL, Succ0MBB, Succ1MBB, CurMBB);
// Use visitSwitchCase to actually insert the fast branch sequence for this
// cond branch.
visitSwitchCase(CB);
SDOperand Cond;
SDOperand CondLHS = getValue(CB.CmpLHS);
- // Build the setcc now, fold "(X == true)" to X and "(X == false)" to !X to
- // handle common cases produced by branch lowering.
- if (CB.CmpRHS == ConstantInt::getTrue() && CB.CC == ISD::SETEQ)
- Cond = CondLHS;
- else if (CB.CmpRHS == ConstantInt::getFalse() && CB.CC == ISD::SETEQ) {
- SDOperand True = DAG.getConstant(1, CondLHS.getValueType());
- Cond = DAG.getNode(ISD::XOR, CondLHS.getValueType(), CondLHS, True);
- } else
- Cond = DAG.getSetCC(MVT::i1, CondLHS, getValue(CB.CmpRHS), CB.CC);
+ // Build the setcc now.
+ if (CB.CmpMHS == NULL) {
+ // Fold "(X == true)" to X and "(X == false)" to !X to
+ // handle common cases produced by branch lowering.
+ if (CB.CmpRHS == ConstantInt::getTrue() && CB.CC == ISD::SETEQ)
+ Cond = CondLHS;
+ else if (CB.CmpRHS == ConstantInt::getFalse() && CB.CC == ISD::SETEQ) {
+ SDOperand True = DAG.getConstant(1, CondLHS.getValueType());
+ Cond = DAG.getNode(ISD::XOR, CondLHS.getValueType(), CondLHS, True);
+ } else
+ Cond = DAG.getSetCC(MVT::i1, CondLHS, getValue(CB.CmpRHS), CB.CC);
+ } else {
+ assert(CB.CC == ISD::SETLE && "Can handle only LE ranges now");
+
+ uint64_t Low = cast<ConstantInt>(CB.CmpLHS)->getSExtValue();
+ uint64_t High = cast<ConstantInt>(CB.CmpRHS)->getSExtValue();
+
+ SDOperand CmpOp = getValue(CB.CmpMHS);
+ MVT::ValueType VT = CmpOp.getValueType();
+
+ if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) {
+ Cond = DAG.getSetCC(MVT::i1, CmpOp, DAG.getConstant(High, VT), ISD::SETLE);
+ } else {
+ SDOperand SUB = DAG.getNode(ISD::SUB, VT, CmpOp, DAG.getConstant(Low, VT));
+ Cond = DAG.getSetCC(MVT::i1, SUB,
+ DAG.getConstant(High-Low, VT), ISD::SETULE);
+ }
+
+ }
// 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.
CurMBB->addSuccessor(CB.FalseBB);
}
+/// visitJumpTable - Emit JumpTable node in the current MBB
void SelectionDAGLowering::visitJumpTable(SelectionDAGISel::JumpTable &JT) {
// Emit the code for the jump table
+ 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);
return;
}
-void SelectionDAGLowering::visitSwitch(SwitchInst &I) {
- // Figure out which block is immediately after the current one.
+/// visitJumpTableHeader - This function emits necessary code to produce index
+/// in the JumpTable from switch case.
+void SelectionDAGLowering::visitJumpTableHeader(SelectionDAGISel::JumpTable &JT,
+ SelectionDAGISel::JumpTableHeader &JTH) {
+ // Subtract the lowest switch case value from the value being switched on
+ // and conditional branch to default mbb if the result is greater than the
+ // difference between smallest and largest cases.
+ SDOperand SwitchOp = getValue(JTH.SValue);
+ MVT::ValueType VT = SwitchOp.getValueType();
+ SDOperand SUB = DAG.getNode(ISD::SUB, VT, SwitchOp,
+ DAG.getConstant(JTH.First, VT));
+
+ // The SDNode we just created, which holds the value being switched on
+ // minus the the smallest case value, needs to be copied to a virtual
+ // register so it can be used as an index into the jump table in a
+ // subsequent basic block. This value may be smaller or larger than the
+ // target's pointer type, and therefore require extension or truncating.
+ if (MVT::getSizeInBits(VT) > MVT::getSizeInBits(TLI.getPointerTy()))
+ SwitchOp = DAG.getNode(ISD::TRUNCATE, TLI.getPointerTy(), SUB);
+ else
+ SwitchOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), SUB);
+
+ unsigned JumpTableReg = FuncInfo.MakeReg(TLI.getPointerTy());
+ SDOperand CopyTo = DAG.getCopyToReg(getRoot(), JumpTableReg, SwitchOp);
+ JT.Reg = JumpTableReg;
+
+ // Emit the range check for the jump table, and branch to the default
+ // block for the switch statement if the value being switched on exceeds
+ // the largest case in the switch.
+ SDOperand CMP = DAG.getSetCC(TLI.getSetCCResultTy(), SUB,
+ DAG.getConstant(JTH.Last-JTH.First,VT),
+ ISD::SETUGT);
+
+ // 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;
+
+ SDOperand BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, CMP,
+ DAG.getBasicBlock(JT.Default));
+
+ if (JT.MBB == NextBlock)
+ DAG.setRoot(BrCond);
+ else
+ DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond,
+ 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);
+
+ SDOperand ShiftOp;
+ if (MVT::getSizeInBits(VT) > MVT::getSizeInBits(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 *Default = FuncInfo.MBBMap[I.getDefaultDest()];
- // If there is only the default destination, branch to it if it is not the
- // next basic block. Otherwise, just fall through.
- if (I.getNumOperands() == 2) {
- // Update machine-CFG edges.
+ 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)));
- // If this is not a fall-through branch, emit the branch.
- if (Default != NextBlock)
- DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
- DAG.getBasicBlock(Default)));
+ CurMBB->addSuccessor(B.Default);
+ CurMBB->addSuccessor(MBB);
- CurMBB->addSuccessor(Default);
- return;
- }
+ return;
+}
+
+/// 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());
- // If there are any non-default case statements, create a vector of Cases
- // representing each one, and sort the vector so that we can efficiently
- // create a binary search tree from them.
- std::vector<Case> Cases;
+ 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;
+}
- for (unsigned i = 1; i < I.getNumSuccessors(); ++i) {
- MachineBasicBlock *SMBB = FuncInfo.MBBMap[I.getSuccessor(i)];
- Cases.push_back(Case(I.getSuccessorValue(i), SMBB));
+void SelectionDAGLowering::visitInvoke(InvokeInst &I) {
+ // Retrieve successors.
+ MachineBasicBlock *Return = FuncInfo.MBBMap[I.getSuccessor(0)];
+ MachineBasicBlock *LandingPad = FuncInfo.MBBMap[I.getSuccessor(1)];
+
+ if (isa<InlineAsm>(I.getCalledValue()))
+ visitInlineAsm(&I);
+ else
+ LowerCallTo(&I, getValue(I.getOperand(0)), false, 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));
}
- std::sort(Cases.begin(), Cases.end(), CaseCmp());
-
- // Get the Value to be switched on and default basic blocks, which will be
- // inserted into CaseBlock records, representing basic blocks in the binary
- // search tree.
- Value *SV = I.getOperand(0);
+ // Drop into normal successor.
+ DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
+ DAG.getBasicBlock(Return)));
- // Get the MachineFunction which holds the current MBB. This is used during
- // emission of jump tables, and when inserting any additional MBBs necessary
- // to represent the switch.
- MachineFunction *CurMF = CurMBB->getParent();
- const BasicBlock *LLVMBB = CurMBB->getBasicBlock();
+ // Update successor info
+ CurMBB->addSuccessor(Return);
+ CurMBB->addSuccessor(LandingPad);
+}
+
+void SelectionDAGLowering::visitUnwind(UnwindInst &I) {
+}
+
+/// handleSmallSwitchCaseRange - Emit a series of specific tests (suitable for
+/// small case ranges).
+bool SelectionDAGLowering::handleSmallSwitchRange(CaseRec& CR,
+ CaseRecVector& WorkList,
+ Value* SV,
+ MachineBasicBlock* Default) {
+ Case& BackCase = *(CR.Range.second-1);
- // If the switch has few cases (two or less) emit a series of specific
- // tests.
- if (Cases.size() < 3) {
- // TODO: If any two of the cases has the same destination, and if one value
- // is the same as the other, but has one bit unset that the other has set,
- // use bit manipulation to do two compares at once. For example:
- // "if (X == 6 || X == 4)" -> "if ((X|2) == 6)"
-
- // Rearrange the case blocks so that the last one falls through if possible.
- if (NextBlock && Default != NextBlock && Cases.back().second != NextBlock) {
- // The last case block won't fall through into 'NextBlock' if we emit the
- // branches in this order. See if rearranging a case value would help.
- for (unsigned i = 0, e = Cases.size()-1; i != e; ++i) {
- if (Cases[i].second == NextBlock) {
- std::swap(Cases[i], Cases.back());
- break;
- }
- }
- }
-
- // Create a CaseBlock record representing a conditional branch to
- // the Case's target mbb if the value being switched on SV is equal
- // to C.
- MachineBasicBlock *CurBlock = CurMBB;
- for (unsigned i = 0, e = Cases.size(); i != e; ++i) {
- MachineBasicBlock *FallThrough;
- if (i != e-1) {
- FallThrough = new MachineBasicBlock(CurMBB->getBasicBlock());
- CurMF->getBasicBlockList().insert(BBI, FallThrough);
- } else {
- // If the last case doesn't match, go to the default block.
- FallThrough = Default;
- }
-
- SelectionDAGISel::CaseBlock CB(ISD::SETEQ, SV, Cases[i].first,
- Cases[i].second, FallThrough, CurBlock);
-
- // If emitting the first comparison, just call visitSwitchCase to emit the
- // code into the current block. Otherwise, push the CaseBlock onto the
- // vector to be later processed by SDISel, and insert the node's MBB
- // before the next MBB.
- if (CurBlock == CurMBB)
- visitSwitchCase(CB);
- else
- SwitchCases.push_back(CB);
-
- CurBlock = FallThrough;
- }
- return;
- }
+ // Size is the number of Cases represented by this range.
+ unsigned Size = CR.Range.second - CR.Range.first;
+ if (Size > 3)
+ return false;
+
+ // 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();
- // If the switch has more than 5 blocks, and at least 31.25% 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 ((TLI.isOperationLegal(ISD::BR_JT, MVT::Other) ||
- TLI.isOperationLegal(ISD::BRIND, MVT::Other)) &&
- Cases.size() > 5) {
- uint64_t First =cast<ConstantInt>(Cases.front().first)->getZExtValue();
- uint64_t Last = cast<ConstantInt>(Cases.back().first)->getZExtValue();
- double Density = (double)Cases.size() / (double)((Last - First) + 1ULL);
-
- if (Density >= 0.3125) {
- // Create a new basic block to hold the code for loading the address
- // of the jump table, and jumping to it. Update successor information;
- // we will either branch to the default case for the switch, or the jump
- // table.
- MachineBasicBlock *JumpTableBB = new MachineBasicBlock(LLVMBB);
- CurMF->getBasicBlockList().insert(BBI, JumpTableBB);
- CurMBB->addSuccessor(Default);
- CurMBB->addSuccessor(JumpTableBB);
-
- // Subtract the lowest switch case value from the value being switched on
- // and conditional branch to default mbb if the result is greater than the
- // difference between smallest and largest cases.
- SDOperand SwitchOp = getValue(SV);
- MVT::ValueType VT = SwitchOp.getValueType();
- SDOperand SUB = DAG.getNode(ISD::SUB, VT, SwitchOp,
- DAG.getConstant(First, VT));
-
- // The SDNode we just created, which holds the value being switched on
- // minus the the smallest case value, needs to be copied to a virtual
- // register so it can be used as an index into the jump table in a
- // subsequent basic block. This value may be smaller or larger than the
- // target's pointer type, and therefore require extension or truncating.
- if (VT > TLI.getPointerTy())
- SwitchOp = DAG.getNode(ISD::TRUNCATE, TLI.getPointerTy(), SUB);
- else
- SwitchOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), SUB);
+ // Figure out which block is immediately after the current one.
+ MachineBasicBlock *NextBlock = 0;
+ MachineFunction::iterator BBI = CR.CaseBB;
- unsigned JumpTableReg = FuncInfo.MakeReg(TLI.getPointerTy());
- SDOperand CopyTo = DAG.getCopyToReg(getRoot(), JumpTableReg, SwitchOp);
-
- // Emit the range check for the jump table, and branch to the default
- // block for the switch statement if the value being switched on exceeds
- // the largest case in the switch.
- SDOperand CMP = DAG.getSetCC(TLI.getSetCCResultTy(), SUB,
- DAG.getConstant(Last-First,VT), ISD::SETUGT);
- DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, CMP,
- DAG.getBasicBlock(Default)));
+ if (++BBI != CurMBB->getParent()->end())
+ NextBlock = BBI;
- // Build a vector of destination BBs, corresponding to each target
- // 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;
- uint64_t TEI = First;
- for (CaseItr ii = Cases.begin(), ee = Cases.end(); ii != ee; ++TEI)
- if (cast<ConstantInt>(ii->first)->getZExtValue() == TEI) {
- DestBBs.push_back(ii->second);
- ++ii;
- } else {
- DestBBs.push_back(Default);
- }
-
- // Update successor info. Add one edge to each unique successor.
- // Vector bool would be better, but vector<bool> is really slow.
- std::vector<unsigned char> SuccsHandled;
- SuccsHandled.resize(CurMBB->getParent()->getNumBlockIDs());
-
- for (std::vector<MachineBasicBlock*>::iterator I = DestBBs.begin(),
- E = DestBBs.end(); I != E; ++I) {
- if (!SuccsHandled[(*I)->getNumber()]) {
- SuccsHandled[(*I)->getNumber()] = true;
- JumpTableBB->addSuccessor(*I);
- }
+ // TODO: If any two of the cases has the same destination, and if one value
+ // is the same as the other, but has one bit unset that the other has set,
+ // use bit manipulation to do two compares at once. For example:
+ // "if (X == 6 || X == 4)" -> "if ((X|2) == 6)"
+
+ // Rearrange the case blocks so that the last one falls through if possible.
+ if (NextBlock && Default != NextBlock && BackCase.BB != NextBlock) {
+ // The last case block won't fall through into 'NextBlock' if we emit the
+ // branches in this order. See if rearranging a case value would help.
+ for (CaseItr I = CR.Range.first, E = CR.Range.second-1; I != E; ++I) {
+ if (I->BB == NextBlock) {
+ std::swap(*I, BackCase);
+ break;
}
-
- // Create a jump table index for this jump table, or return an existing
- // one.
- unsigned JTI = CurMF->getJumpTableInfo()->getJumpTableIndex(DestBBs);
-
- // Set the jump table information so that we can codegen it as a second
- // MachineBasicBlock
- JT.Reg = JumpTableReg;
- JT.JTI = JTI;
- JT.MBB = JumpTableBB;
- JT.Default = Default;
- return;
}
}
- // Push the initial CaseRec onto the worklist
- std::vector<CaseRec> CaseVec;
- CaseVec.push_back(CaseRec(CurMBB,0,0,CaseRange(Cases.begin(),Cases.end())));
-
- while (!CaseVec.empty()) {
- // Grab a record representing a case range to process off the worklist
- CaseRec CR = CaseVec.back();
- CaseVec.pop_back();
-
- // Size is the number of Cases represented by this range. If Size is 1,
- // then we are processing a leaf of the binary search tree. Otherwise,
- // we need to pick a pivot, and push left and right ranges onto the
- // worklist.
- unsigned Size = CR.Range.second - CR.Range.first;
-
- if (Size == 1) {
- // Create a CaseBlock record representing a conditional branch to
- // the Case's target mbb if the value being switched on SV is equal
- // to C. Otherwise, branch to default.
- Constant *C = CR.Range.first->first;
- MachineBasicBlock *Target = CR.Range.first->second;
- SelectionDAGISel::CaseBlock CB(ISD::SETEQ, SV, C, Target, Default,
- CR.CaseBB);
-
- // If the MBB representing the leaf node is the current MBB, then just
- // call visitSwitchCase to emit the code into the current block.
- // Otherwise, push the CaseBlock onto the vector to be later processed
- // by SDISel, and insert the node's MBB before the next MBB.
- if (CR.CaseBB == CurMBB)
- visitSwitchCase(CB);
- else
- SwitchCases.push_back(CB);
+ // Create a CaseBlock record representing a conditional branch to
+ // the Case's target mbb if the value being switched on SV is equal
+ // to C.
+ MachineBasicBlock *CurBlock = CR.CaseBB;
+ for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++I) {
+ MachineBasicBlock *FallThrough;
+ if (I != E-1) {
+ FallThrough = new MachineBasicBlock(CurBlock->getBasicBlock());
+ CurMF->getBasicBlockList().insert(BBI, FallThrough);
} else {
- // split case range at pivot
- CaseItr Pivot = CR.Range.first + (Size / 2);
- CaseRange LHSR(CR.Range.first, Pivot);
- CaseRange RHSR(Pivot, CR.Range.second);
- Constant *C = Pivot->first;
- MachineBasicBlock *FalseBB = 0, *TrueBB = 0;
-
- // We know that we branch to the LHS if the Value being switched on is
- // less than the Pivot value, C. We use this to optimize our binary
- // tree a bit, by recognizing that if SV is greater than or equal to the
- // LHS's Case Value, and that Case Value is exactly one less than the
- // Pivot's Value, then we can branch directly to the LHS's Target,
- // rather than creating a leaf node for it.
- if ((LHSR.second - LHSR.first) == 1 &&
- LHSR.first->first == CR.GE &&
- cast<ConstantInt>(C)->getZExtValue() ==
- (cast<ConstantInt>(CR.GE)->getZExtValue() + 1ULL)) {
- TrueBB = LHSR.first->second;
- } else {
- TrueBB = new MachineBasicBlock(LLVMBB);
- CurMF->getBasicBlockList().insert(BBI, TrueBB);
- CaseVec.push_back(CaseRec(TrueBB, C, CR.GE, LHSR));
- }
-
- // Similar to the optimization above, if the Value being switched on is
- // known to be less than the Constant CR.LT, and the current Case Value
- // is CR.LT - 1, then we can branch directly to the target block for
- // the current Case Value, rather than emitting a RHS leaf node for it.
- if ((RHSR.second - RHSR.first) == 1 && CR.LT &&
- cast<ConstantInt>(RHSR.first->first)->getZExtValue() ==
- (cast<ConstantInt>(CR.LT)->getZExtValue() - 1ULL)) {
- FalseBB = RHSR.first->second;
- } else {
- FalseBB = new MachineBasicBlock(LLVMBB);
- CurMF->getBasicBlockList().insert(BBI, FalseBB);
- CaseVec.push_back(CaseRec(FalseBB,CR.LT,C,RHSR));
- }
-
- // Create a CaseBlock record representing a conditional branch to
- // the LHS node if the value being switched on SV is less than C.
- // Otherwise, branch to LHS.
- ISD::CondCode CC = ISD::SETLT;
- SelectionDAGISel::CaseBlock CB(CC, SV, C, TrueBB, FalseBB, CR.CaseBB);
+ // If the last case doesn't match, go to the default block.
+ FallThrough = Default;
+ }
- if (CR.CaseBB == CurMBB)
- visitSwitchCase(CB);
- else
- SwitchCases.push_back(CB);
+ Value *RHS, *LHS, *MHS;
+ ISD::CondCode CC;
+ if (I->High == I->Low) {
+ // This is just small small case range :) containing exactly 1 case
+ CC = ISD::SETEQ;
+ LHS = SV; RHS = I->High; MHS = NULL;
+ } else {
+ CC = ISD::SETLE;
+ LHS = I->Low; MHS = SV; RHS = I->High;
}
+ SelectionDAGISel::CaseBlock CB(CC, LHS, RHS, MHS,
+ I->BB, FallThrough, CurBlock);
+
+ // If emitting the first comparison, just call visitSwitchCase to emit the
+ // code into the current block. Otherwise, push the CaseBlock onto the
+ // vector to be later processed by SDISel, and insert the node's MBB
+ // before the next MBB.
+ if (CurBlock == CurMBB)
+ visitSwitchCase(CB);
+ else
+ SwitchCases.push_back(CB);
+
+ CurBlock = FallThrough;
}
-}
-void SelectionDAGLowering::visitSub(User &I) {
- // -0.0 - X --> fneg
- const Type *Ty = I.getType();
- if (isa<PackedType>(Ty)) {
- visitVectorBinary(I, ISD::VSUB);
- } else if (Ty->isFloatingPoint()) {
- if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0)))
- if (CFP->isExactlyValue(-0.0)) {
- SDOperand Op2 = getValue(I.getOperand(1));
- setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2));
- return;
- }
- visitScalarBinary(I, ISD::FSUB);
- } else
- visitScalarBinary(I, ISD::SUB);
+ return true;
}
-void SelectionDAGLowering::visitScalarBinary(User &I, unsigned OpCode) {
- SDOperand Op1 = getValue(I.getOperand(0));
- SDOperand Op2 = getValue(I.getOperand(1));
-
- setValue(&I, DAG.getNode(OpCode, Op1.getValueType(), Op1, Op2));
+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,
+ Value* SV,
+ MachineBasicBlock* Default) {
+ Case& FrontCase = *CR.Range.first;
+ Case& BackCase = *(CR.Range.second-1);
+
+ int64_t First = cast<ConstantInt>(FrontCase.Low)->getSExtValue();
+ int64_t Last = cast<ConstantInt>(BackCase.High)->getSExtValue();
+
+ uint64_t TSize = 0;
+ for (CaseItr I = CR.Range.first, E = CR.Range.second;
+ I!=E; ++I)
+ TSize += I->size();
+
+ if (!areJTsAllowed(TLI) || TSize <= 3)
+ return false;
+
+ double Density = (double)TSize / (double)((Last - First) + 1ULL);
+ if (Density < 0.4)
+ return false;
-void
-SelectionDAGLowering::visitVectorBinary(User &I, unsigned OpCode) {
- assert(isa<PackedType>(I.getType()));
- const PackedType *Ty = cast<PackedType>(I.getType());
- SDOperand Typ = DAG.getValueType(TLI.getValueType(Ty->getElementType()));
-
- setValue(&I, DAG.getNode(OpCode, MVT::Vector,
- getValue(I.getOperand(0)),
- getValue(I.getOperand(1)),
- DAG.getConstant(Ty->getNumElements(), MVT::i32),
- Typ));
-}
+ DOUT << "Lowering jump table\n"
+ << "First entry: " << First << ". Last entry: " << Last << "\n"
+ << "Size: " << TSize << ". Density: " << Density << "\n\n";
-void SelectionDAGLowering::visitEitherBinary(User &I, unsigned ScalarOp,
- unsigned VectorOp) {
- if (isa<PackedType>(I.getType()))
- visitVectorBinary(I, VectorOp);
- else
- visitScalarBinary(I, ScalarOp);
-}
+ // 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();
+
+ // Figure out which block is immediately after the current one.
+ MachineBasicBlock *NextBlock = 0;
+ MachineFunction::iterator BBI = CR.CaseBB;
+
+ if (++BBI != CurMBB->getParent()->end())
+ NextBlock = BBI;
+
+ const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock();
+
+ // Create a new basic block to hold the code for loading the address
+ // of the jump table, and jumping to it. Update successor information;
+ // we will either branch to the default case for the switch, or the jump
+ // table.
+ MachineBasicBlock *JumpTableBB = new MachineBasicBlock(LLVMBB);
+ CurMF->getBasicBlockList().insert(BBI, JumpTableBB);
+ CR.CaseBB->addSuccessor(Default);
+ 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
+ // a case statement, push the case's BB onto the vector, otherwise, push
+ // the default BB.
+ std::vector<MachineBasicBlock*> DestBBs;
+ int64_t TEI = First;
+ for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++TEI) {
+ int64_t Low = cast<ConstantInt>(I->Low)->getSExtValue();
+ int64_t High = cast<ConstantInt>(I->High)->getSExtValue();
+
+ if ((Low <= TEI) && (TEI <= High)) {
+ DestBBs.push_back(I->BB);
+ if (TEI==High)
+ ++I;
+ } else {
+ DestBBs.push_back(Default);
+ }
+ }
+
+ // Update successor info. Add one edge to each unique successor.
+ BitVector SuccsHandled(CR.CaseBB->getParent()->getNumBlockIDs());
+ for (std::vector<MachineBasicBlock*>::iterator I = DestBBs.begin(),
+ E = DestBBs.end(); I != E; ++I) {
+ if (!SuccsHandled[(*I)->getNumber()]) {
+ SuccsHandled[(*I)->getNumber()] = true;
+ JumpTableBB->addSuccessor(*I);
+ }
+ }
+
+ // Create a jump table index for this jump table, or return an existing
+ // one.
+ unsigned JTI = CurMF->getJumpTableInfo()->getJumpTableIndex(DestBBs);
+
+ // Set the jump table information so that we can codegen it as a second
+ // MachineBasicBlock
+ SelectionDAGISel::JumpTable JT(-1U, JTI, JumpTableBB, Default);
+ SelectionDAGISel::JumpTableHeader JTH(First, Last, SV, CR.CaseBB,
+ (CR.CaseBB == CurMBB));
+ if (CR.CaseBB == CurMBB)
+ visitJumpTableHeader(JT, JTH);
+
+ JTCases.push_back(SelectionDAGISel::JumpTableBlock(JTH, JT));
+
+ return true;
+}
+
+/// handleBTSplitSwitchCase - emit comparison and split binary search tree into
+/// 2 subtrees.
+bool SelectionDAGLowering::handleBTSplitSwitchCase(CaseRec& CR,
+ CaseRecVector& WorkList,
+ Value* SV,
+ MachineBasicBlock* Default) {
+ // 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();
+
+ // Figure out which block is immediately after the current one.
+ MachineBasicBlock *NextBlock = 0;
+ MachineFunction::iterator BBI = CR.CaseBB;
+
+ if (++BBI != CurMBB->getParent()->end())
+ NextBlock = BBI;
+
+ Case& FrontCase = *CR.Range.first;
+ Case& BackCase = *(CR.Range.second-1);
+ const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock();
+
+ // 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();
+ double FMetric = 0;
+ CaseItr Pivot = CR.Range.first + Size/2;
+
+ // Select optimal pivot, maximizing sum density of LHS and RHS. This will
+ // (heuristically) allow us to emit JumpTable's later.
+ uint64_t TSize = 0;
+ for (CaseItr I = CR.Range.first, E = CR.Range.second;
+ I!=E; ++I)
+ TSize += I->size();
+
+ 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);
+ 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;
+ 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);
+ Constant *C = Pivot->Low;
+ MachineBasicBlock *FalseBB = 0, *TrueBB = 0;
+
+ // We know that we branch to the LHS if the Value being switched on is
+ // less than the Pivot value, C. We use this to optimize our binary
+ // tree a bit, by recognizing that if SV is greater than or equal to the
+ // LHS's Case Value, and that Case Value is exactly one less than the
+ // Pivot's Value, then we can branch directly to the LHS's Target,
+ // rather than creating a leaf node for it.
+ if ((LHSR.second - LHSR.first) == 1 &&
+ LHSR.first->High == CR.GE &&
+ cast<ConstantInt>(C)->getSExtValue() ==
+ (cast<ConstantInt>(CR.GE)->getSExtValue() + 1LL)) {
+ TrueBB = LHSR.first->BB;
+ } else {
+ TrueBB = new MachineBasicBlock(LLVMBB);
+ CurMF->getBasicBlockList().insert(BBI, TrueBB);
+ WorkList.push_back(CaseRec(TrueBB, C, CR.GE, LHSR));
+ }
+
+ // Similar to the optimization above, if the Value being switched on is
+ // known to be less than the Constant CR.LT, and the current Case Value
+ // is CR.LT - 1, then we can branch directly to the target block for
+ // the current Case Value, rather than emitting a RHS leaf node for it.
+ if ((RHSR.second - RHSR.first) == 1 && CR.LT &&
+ cast<ConstantInt>(RHSR.first->Low)->getSExtValue() ==
+ (cast<ConstantInt>(CR.LT)->getSExtValue() - 1LL)) {
+ FalseBB = RHSR.first->BB;
+ } else {
+ FalseBB = new MachineBasicBlock(LLVMBB);
+ CurMF->getBasicBlockList().insert(BBI, FalseBB);
+ WorkList.push_back(CaseRec(FalseBB,CR.LT,C,RHSR));
+ }
+
+ // Create a CaseBlock record representing a conditional branch to
+ // the LHS node if the value being switched on SV is less than C.
+ // Otherwise, branch to LHS.
+ SelectionDAGISel::CaseBlock CB(ISD::SETLT, SV, C, NULL,
+ TrueBB, FalseBB, CR.CaseBB);
+
+ if (CR.CaseBB == CurMBB)
+ visitSwitchCase(CB);
+ else
+ SwitchCases.push_back(CB);
+
+ 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) {
+ unsigned numCmps = 0;
+
+ // Start with "simple" cases
+ for (unsigned i = 1; i < SI.getNumSuccessors(); ++i) {
+ MachineBasicBlock *SMBB = FuncInfo.MBBMap[SI.getSuccessor(i)];
+ Cases.push_back(Case(SI.getSuccessorValue(i),
+ SI.getSuccessorValue(i),
+ SMBB));
+ }
+ std::sort(Cases.begin(), Cases.end(), CaseCmp());
+
+ // Merge case into clusters
+ if (Cases.size()>=2)
+ // Must recompute end() each iteration because it may be
+ // invalidated by erase if we hold on to it
+ for (CaseItr I=Cases.begin(), J=++(Cases.begin()); J!=Cases.end(); ) {
+ int64_t nextValue = cast<ConstantInt>(J->Low)->getSExtValue();
+ int64_t currentValue = cast<ConstantInt>(I->High)->getSExtValue();
+ MachineBasicBlock* nextBB = J->BB;
+ MachineBasicBlock* currentBB = I->BB;
+
+ // If the two neighboring cases go to the same destination, merge them
+ // into a single case.
+ if ((nextValue-currentValue==1) && (currentBB == nextBB)) {
+ I->High = J->High;
+ J = Cases.erase(J);
+ } else {
+ I = J++;
+ }
+ }
+
+ for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) {
+ if (I->Low != I->High)
+ // A range counts double, since it requires two compares.
+ ++numCmps;
+ }
+
+ return numCmps;
+}
+
+void SelectionDAGLowering::visitSwitch(SwitchInst &SI) {
+ // Figure out which block is immediately after the current one.
+ MachineBasicBlock *NextBlock = 0;
+ MachineFunction::iterator BBI = CurMBB;
+
+ MachineBasicBlock *Default = FuncInfo.MBBMap[SI.getDefaultDest()];
+
+ // If there is only the default destination, branch to it if it is not the
+ // next basic block. Otherwise, just fall through.
+ if (SI.getNumOperands() == 2) {
+ // Update machine-CFG edges.
+
+ // If this is not a fall-through branch, emit the branch.
+ if (Default != NextBlock)
+ DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(),
+ DAG.getBasicBlock(Default)));
+
+ CurMBB->addSuccessor(Default);
+ return;
+ }
+
+ // If there are any non-default case statements, create a vector of Cases
+ // representing each one, and sort the vector so that we can efficiently
+ // create a binary search tree from them.
+ CaseVector Cases;
+ unsigned numCmps = Clusterify(Cases, SI);
+ DOUT << "Clusterify finished. Total clusters: " << Cases.size()
+ << ". Total compares: " << numCmps << "\n";
+
+ // Get the Value to be switched on and default basic blocks, which will be
+ // inserted into CaseBlock records, representing basic blocks in the binary
+ // search tree.
+ Value *SV = SI.getOperand(0);
+
+ // Push the initial CaseRec onto the worklist
+ CaseRecVector WorkList;
+ WorkList.push_back(CaseRec(CurMBB,0,0,CaseRange(Cases.begin(),Cases.end())));
+
+ while (!WorkList.empty()) {
+ // Grab a record representing a case range to process off the worklist
+ 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 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))
+ continue;
+
+ // Emit binary tree. We need to pick a pivot, and push left and right ranges
+ // onto the worklist. Leafs are handled via handleSmallSwitchRange() call.
+ handleBTSplitSwitchCase(CR, WorkList, SV, Default);
+ }
+}
+
+
+void SelectionDAGLowering::visitSub(User &I) {
+ // -0.0 - X --> fneg
+ const Type *Ty = I.getType();
+ if (isa<VectorType>(Ty)) {
+ if (ConstantVector *CV = dyn_cast<ConstantVector>(I.getOperand(0))) {
+ const VectorType *DestTy = cast<VectorType>(I.getType());
+ const Type *ElTy = DestTy->getElementType();
+ if (ElTy->isFloatingPoint()) {
+ unsigned VL = DestTy->getNumElements();
+ std::vector<Constant*> NZ(VL, ConstantFP::getNegativeZero(ElTy));
+ Constant *CNZ = ConstantVector::get(&NZ[0], NZ.size());
+ if (CV == CNZ) {
+ SDOperand Op2 = getValue(I.getOperand(1));
+ setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2));
+ return;
+ }
+ }
+ }
+ }
+ if (Ty->isFloatingPoint()) {
+ if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0)))
+ if (CFP->isExactlyValue(ConstantFP::getNegativeZero(Ty)->getValueAPF())) {
+ SDOperand Op2 = getValue(I.getOperand(1));
+ setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2));
+ return;
+ }
+ }
+
+ visitBinary(I, Ty->isFPOrFPVector() ? ISD::FSUB : ISD::SUB);
+}
+
+void SelectionDAGLowering::visitBinary(User &I, unsigned OpCode) {
+ SDOperand Op1 = getValue(I.getOperand(0));
+ SDOperand Op2 = getValue(I.getOperand(1));
+
+ setValue(&I, DAG.getNode(OpCode, Op1.getValueType(), Op1, Op2));
+}
void SelectionDAGLowering::visitShift(User &I, unsigned Opcode) {
SDOperand Op1 = getValue(I.getOperand(0));
SDOperand Op2 = getValue(I.getOperand(1));
- if (TLI.getShiftAmountTy() < Op2.getValueType())
+ if (MVT::getSizeInBits(TLI.getShiftAmountTy()) <
+ MVT::getSizeInBits(Op2.getValueType()))
Op2 = DAG.getNode(ISD::TRUNCATE, TLI.getShiftAmountTy(), Op2);
else if (TLI.getShiftAmountTy() > Op2.getValueType())
Op2 = DAG.getNode(ISD::ANY_EXTEND, TLI.getShiftAmountTy(), Op2);
SDOperand Cond = getValue(I.getOperand(0));
SDOperand TrueVal = getValue(I.getOperand(1));
SDOperand FalseVal = getValue(I.getOperand(2));
- if (!isa<PackedType>(I.getType())) {
- setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond,
- TrueVal, FalseVal));
- } else {
- setValue(&I, DAG.getNode(ISD::VSELECT, MVT::Vector, Cond, TrueVal, FalseVal,
- *(TrueVal.Val->op_end()-2),
- *(TrueVal.Val->op_end()-1)));
- }
+ setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond,
+ TrueVal, FalseVal));
}
void SelectionDAGLowering::visitBitCast(User &I) {
SDOperand N = getValue(I.getOperand(0));
MVT::ValueType DestVT = TLI.getValueType(I.getType());
- if (DestVT == MVT::Vector) {
- // This is a cast to a vector from something else.
- // Get information about the output vector.
- const PackedType *DestTy = cast<PackedType>(I.getType());
- MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType());
- setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N,
- DAG.getConstant(DestTy->getNumElements(),MVT::i32),
- DAG.getValueType(EltVT)));
- return;
- }
- MVT::ValueType SrcVT = N.getValueType();
- if (SrcVT == MVT::Vector) {
- // This is a cast from a vctor to something else.
- // Get information about the input vector.
- setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N));
- return;
- }
// BitCast assures us that source and destination are the same size so this
// is either a BIT_CONVERT or a no-op.
SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(),
getValue(I.getOperand(2)));
- SDOperand Num = *(InVec.Val->op_end()-2);
- SDOperand Typ = *(InVec.Val->op_end()-1);
- setValue(&I, DAG.getNode(ISD::VINSERT_VECTOR_ELT, MVT::Vector,
- InVec, InVal, InIdx, Num, Typ));
+ setValue(&I, DAG.getNode(ISD::INSERT_VECTOR_ELT,
+ TLI.getValueType(I.getType()),
+ InVec, InVal, InIdx));
}
void SelectionDAGLowering::visitExtractElement(User &I) {
SDOperand InVec = getValue(I.getOperand(0));
SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(),
getValue(I.getOperand(1)));
- SDOperand Typ = *(InVec.Val->op_end()-1);
- setValue(&I, DAG.getNode(ISD::VEXTRACT_VECTOR_ELT,
+ setValue(&I, DAG.getNode(ISD::EXTRACT_VECTOR_ELT,
TLI.getValueType(I.getType()), InVec, InIdx));
}
SDOperand V2 = getValue(I.getOperand(1));
SDOperand Mask = getValue(I.getOperand(2));
- SDOperand Num = *(V1.Val->op_end()-2);
- SDOperand Typ = *(V2.Val->op_end()-1);
- setValue(&I, DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector,
- V1, V2, Mask, Num, Typ));
+ setValue(&I, DAG.getNode(ISD::VECTOR_SHUFFLE,
+ TLI.getValueType(I.getType()),
+ V1, V2, Mask));
}
if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
if (CI->getZExtValue() == 0) continue;
uint64_t Offs =
- TD->getTypeSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
+ TD->getABITypeSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
N = DAG.getNode(ISD::ADD, N.getValueType(), N, getIntPtrConstant(Offs));
continue;
}
// N = N + Idx * ElementSize;
- uint64_t ElementSize = TD->getTypeSize(Ty);
+ uint64_t ElementSize = TD->getABITypeSize(Ty);
SDOperand IdxN = getValue(Idx);
// If the index is smaller or larger than intptr_t, truncate or extend
return; // getValue will auto-populate this.
const Type *Ty = I.getAllocatedType();
- uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty);
+ uint64_t TySize = TLI.getTargetData()->getABITypeSize(Ty);
unsigned Align =
- std::max((unsigned)TLI.getTargetData()->getTypeAlignmentPref(Ty),
+ std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty),
I.getAlignment());
SDOperand AllocSize = getValue(I.getArraySize());
AllocSize = DAG.getNode(ISD::MUL, IntPtr, AllocSize,
getIntPtrConstant(TySize));
- // Handle alignment. If the requested alignment is less than or equal to the
- // stack alignment, ignore it and round the size of the allocation up to the
- // stack alignment size. If the size is greater than the stack alignment, we
- // note this in the DYNAMIC_STACKALLOC node.
+ // Handle alignment. If the requested alignment is less than or equal to
+ // the stack alignment, ignore it. If the size is greater than or equal to
+ // the stack alignment, we note this in the DYNAMIC_STACKALLOC node.
unsigned StackAlign =
TLI.getTargetMachine().getFrameInfo()->getStackAlignment();
- if (Align <= StackAlign) {
+ if (Align <= StackAlign)
Align = 0;
- // Add SA-1 to the size.
- AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize,
- getIntPtrConstant(StackAlign-1));
- // Mask out the low bits for alignment purposes.
- AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize,
- getIntPtrConstant(~(uint64_t)(StackAlign-1)));
- }
+
+ // Round the size of the allocation up to the stack alignment size
+ // by add SA-1 to the size.
+ AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize,
+ getIntPtrConstant(StackAlign-1));
+ // Mask out the low bits for alignment purposes.
+ AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize,
+ getIntPtrConstant(~(uint64_t)(StackAlign-1)));
SDOperand Ops[] = { getRoot(), AllocSize, getIntPtrConstant(Align) };
const MVT::ValueType *VTs = DAG.getNodeValueTypes(AllocSize.getValueType(),
}
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) {
- SDOperand L;
- if (const PackedType *PTy = dyn_cast<PackedType>(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);
- }
+ bool isVolatile,
+ unsigned Alignment) {
+ SDOperand L =
+ DAG.getLoad(TLI.getValueType(Ty), Root, Ptr, SV, 0,
+ isVolatile, Alignment);
if (isVolatile)
DAG.setRoot(L.getValue(1));
SDOperand Src = getValue(SrcV);
SDOperand Ptr = getValue(I.getOperand(1));
DAG.setRoot(DAG.getStore(getRoot(), Src, Ptr, I.getOperand(1), 0,
- I.isVolatile()));
-}
-
-/// IntrinsicCannotAccessMemory - Return true if the specified intrinsic cannot
-/// access memory and has no other side effects at all.
-static bool IntrinsicCannotAccessMemory(unsigned IntrinsicID) {
-#define GET_NO_MEMORY_INTRINSICS
-#include "llvm/Intrinsics.gen"
-#undef GET_NO_MEMORY_INTRINSICS
- return false;
-}
-
-// IntrinsicOnlyReadsMemory - Return true if the specified intrinsic doesn't
-// have any side-effects or if it only reads memory.
-static bool IntrinsicOnlyReadsMemory(unsigned IntrinsicID) {
-#define GET_SIDE_EFFECT_INFO
-#include "llvm/Intrinsics.gen"
-#undef GET_SIDE_EFFECT_INFO
- return false;
+ I.isVolatile(), I.getAlignment()));
}
/// visitTargetIntrinsic - Lower a call of a target intrinsic to an INTRINSIC
/// node.
void SelectionDAGLowering::visitTargetIntrinsic(CallInst &I,
unsigned Intrinsic) {
- bool HasChain = !IntrinsicCannotAccessMemory(Intrinsic);
- bool OnlyLoad = HasChain && IntrinsicOnlyReadsMemory(Intrinsic);
-
+ bool HasChain = !I.doesNotAccessMemory();
+ bool OnlyLoad = HasChain && I.onlyReadsMemory();
+
// Build the operand list.
SmallVector<SDOperand, 8> Ops;
if (HasChain) { // If this intrinsic has side-effects, chainify it.
// Add all operands of the call to the operand list.
for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) {
SDOperand Op = getValue(I.getOperand(i));
-
- // If this is a vector type, force it to the right packed type.
- if (Op.getValueType() == MVT::Vector) {
- const PackedType *OpTy = cast<PackedType>(I.getOperand(i)->getType());
- MVT::ValueType EltVT = TLI.getValueType(OpTy->getElementType());
-
- MVT::ValueType VVT = MVT::getVectorType(EltVT, OpTy->getNumElements());
- assert(VVT != MVT::Other && "Intrinsic uses a non-legal type?");
- Op = DAG.getNode(ISD::VBIT_CONVERT, VVT, Op);
- }
-
assert(TLI.isTypeLegal(Op.getValueType()) &&
"Intrinsic uses a non-legal type?");
Ops.push_back(Op);
std::vector<MVT::ValueType> VTs;
if (I.getType() != Type::VoidTy) {
MVT::ValueType VT = TLI.getValueType(I.getType());
- if (VT == MVT::Vector) {
- const PackedType *DestTy = cast<PackedType>(I.getType());
+ if (MVT::isVector(VT)) {
+ const VectorType *DestTy = cast<VectorType>(I.getType());
MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType());
VT = MVT::getVectorType(EltVT, DestTy->getNumElements());
DAG.setRoot(Chain);
}
if (I.getType() != Type::VoidTy) {
- if (const PackedType *PTy = dyn_cast<PackedType>(I.getType())) {
- MVT::ValueType EVT = TLI.getValueType(PTy->getElementType());
- Result = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Result,
- DAG.getConstant(PTy->getNumElements(), MVT::i32),
- DAG.getValueType(EVT));
+ if (const VectorType *PTy = dyn_cast<VectorType>(I.getType())) {
+ MVT::ValueType VT = TLI.getValueType(PTy);
+ Result = DAG.getNode(ISD::BIT_CONVERT, VT, Result);
}
setValue(&I, Result);
}
}
+/// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V.
+static GlobalVariable *ExtractTypeInfo (Value *V) {
+ V = IntrinsicInst::StripPointerCasts(V);
+ GlobalVariable *GV = dyn_cast<GlobalVariable>(V);
+ assert (GV || isa<ConstantPointerNull>(V) &&
+ "TypeInfo must be a global variable or NULL");
+ return GV;
+}
+
+/// addCatchInfo - Extract the personality and type infos from an eh.selector
+/// 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;
+ unsigned N = I.getNumOperands();
+
+ for (unsigned i = N - 1; i > 2; --i) {
+ if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(i))) {
+ unsigned FilterLength = CI->getZExtValue();
+ unsigned FirstCatch = i + FilterLength + !FilterLength;
+ assert (FirstCatch <= N && "Invalid filter length");
+
+ if (FirstCatch < N) {
+ TyInfo.reserve(N - FirstCatch);
+ for (unsigned j = FirstCatch; j < N; ++j)
+ TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
+ MMI->addCatchTypeInfo(MBB, TyInfo);
+ TyInfo.clear();
+ }
+
+ if (!FilterLength) {
+ // Cleanup.
+ MMI->addCleanup(MBB);
+ } else {
+ // Filter.
+ TyInfo.reserve(FilterLength - 1);
+ for (unsigned j = i + 1; j < FirstCatch; ++j)
+ TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
+ MMI->addFilterTypeInfo(MBB, TyInfo);
+ TyInfo.clear();
+ }
+
+ N = i;
+ }
+ }
+
+ if (N > 3) {
+ TyInfo.reserve(N - 3);
+ for (unsigned j = 3; j < N; ++j)
+ TyInfo.push_back(ExtractTypeInfo(I.getOperand(j)));
+ 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.
return 0;
}
- case Intrinsic::sqrt_f32:
- case Intrinsic::sqrt_f64:
+ case Intrinsic::eh_exception: {
+ if (ExceptionHandling) {
+ if (!CurMBB->isLandingPad()) {
+ // FIXME: Mark exception register as live in. Hack for PR1508.
+ unsigned Reg = TLI.getExceptionAddressRegister();
+ if (Reg) CurMBB->addLiveIn(Reg);
+ }
+ // Insert the EXCEPTIONADDR instruction.
+ SDVTList VTs = DAG.getVTList(TLI.getPointerTy(), MVT::Other);
+ SDOperand Ops[1];
+ Ops[0] = DAG.getRoot();
+ SDOperand Op = DAG.getNode(ISD::EXCEPTIONADDR, VTs, Ops, 1);
+ setValue(&I, Op);
+ DAG.setRoot(Op.getValue(1));
+ } else {
+ setValue(&I, DAG.getConstant(0, TLI.getPointerTy()));
+ }
+ return 0;
+ }
+
+ case Intrinsic::eh_selector_i32:
+ case Intrinsic::eh_selector_i64: {
+ MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
+ MVT::ValueType VT = (Intrinsic == Intrinsic::eh_selector_i32 ?
+ MVT::i32 : MVT::i64);
+
+ if (ExceptionHandling && MMI) {
+ if (CurMBB->isLandingPad())
+ addCatchInfo(I, MMI, CurMBB);
+ else {
+#ifndef NDEBUG
+ FuncInfo.CatchInfoLost.insert(&I);
+#endif
+ // FIXME: Mark exception selector register as live in. Hack for PR1508.
+ unsigned Reg = TLI.getExceptionSelectorRegister();
+ if (Reg) CurMBB->addLiveIn(Reg);
+ }
+
+ // Insert the EHSELECTION instruction.
+ SDVTList VTs = DAG.getVTList(VT, MVT::Other);
+ SDOperand Ops[2];
+ Ops[0] = getValue(I.getOperand(1));
+ Ops[1] = getRoot();
+ SDOperand Op = DAG.getNode(ISD::EHSELECTION, VTs, Ops, 2);
+ setValue(&I, Op);
+ DAG.setRoot(Op.getValue(1));
+ } else {
+ setValue(&I, DAG.getConstant(0, VT));
+ }
+
+ return 0;
+ }
+
+ case Intrinsic::eh_typeid_for_i32:
+ case Intrinsic::eh_typeid_for_i64: {
+ MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
+ MVT::ValueType VT = (Intrinsic == Intrinsic::eh_typeid_for_i32 ?
+ MVT::i32 : MVT::i64);
+
+ if (MMI) {
+ // Find the type id for the given typeinfo.
+ GlobalVariable *GV = ExtractTypeInfo(I.getOperand(1));
+
+ unsigned TypeID = MMI->getTypeIDFor(GV);
+ setValue(&I, DAG.getConstant(TypeID, VT));
+ } else {
+ // Return something different to eh_selector.
+ setValue(&I, DAG.getConstant(1, VT));
+ }
+
+ return 0;
+ }
+
+ case Intrinsic::eh_return: {
+ MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
+
+ if (MMI && ExceptionHandling) {
+ MMI->setCallsEHReturn(true);
+ DAG.setRoot(DAG.getNode(ISD::EH_RETURN,
+ MVT::Other,
+ getRoot(),
+ getValue(I.getOperand(1)),
+ getValue(I.getOperand(2))));
+ } else {
+ setValue(&I, DAG.getConstant(0, TLI.getPointerTy()));
+ }
+
+ return 0;
+ }
+
+ case Intrinsic::eh_unwind_init: {
+ if (MachineModuleInfo *MMI = DAG.getMachineModuleInfo()) {
+ MMI->setCallsUnwindInit(true);
+ }
+
+ return 0;
+ }
+
+ case Intrinsic::eh_dwarf_cfa: {
+ if (ExceptionHandling) {
+ MVT::ValueType VT = getValue(I.getOperand(1)).getValueType();
+ SDOperand CfaArg;
+ if (MVT::getSizeInBits(VT) > MVT::getSizeInBits(TLI.getPointerTy()))
+ CfaArg = DAG.getNode(ISD::TRUNCATE,
+ TLI.getPointerTy(), getValue(I.getOperand(1)));
+ else
+ CfaArg = DAG.getNode(ISD::SIGN_EXTEND,
+ TLI.getPointerTy(), getValue(I.getOperand(1)));
+
+ SDOperand Offset = DAG.getNode(ISD::ADD,
+ TLI.getPointerTy(),
+ DAG.getNode(ISD::FRAME_TO_ARGS_OFFSET,
+ TLI.getPointerTy()),
+ CfaArg);
+ setValue(&I, DAG.getNode(ISD::ADD,
+ TLI.getPointerTy(),
+ DAG.getNode(ISD::FRAMEADDR,
+ TLI.getPointerTy(),
+ DAG.getConstant(0,
+ TLI.getPointerTy())),
+ Offset));
+ } else {
+ setValue(&I, DAG.getConstant(0, TLI.getPointerTy()));
+ }
+
+ return 0;
+ }
+
+ case Intrinsic::sqrt:
setValue(&I, DAG.getNode(ISD::FSQRT,
getValue(I.getOperand(1)).getValueType(),
getValue(I.getOperand(1))));
return 0;
- case Intrinsic::powi_f32:
- case Intrinsic::powi_f64:
+ case Intrinsic::powi:
setValue(&I, DAG.getNode(ISD::FPOWI,
getValue(I.getOperand(1)).getValueType(),
getValue(I.getOperand(1)),
getValue(I.getOperand(2))));
return 0;
+ case Intrinsic::sin:
+ setValue(&I, DAG.getNode(ISD::FSIN,
+ getValue(I.getOperand(1)).getValueType(),
+ getValue(I.getOperand(1))));
+ return 0;
+ case Intrinsic::cos:
+ setValue(&I, DAG.getNode(ISD::FCOS,
+ getValue(I.getOperand(1)).getValueType(),
+ getValue(I.getOperand(1))));
+ return 0;
+ case Intrinsic::pow:
+ setValue(&I, DAG.getNode(ISD::FPOW,
+ getValue(I.getOperand(1)).getValueType(),
+ getValue(I.getOperand(1)),
+ getValue(I.getOperand(2))));
+ return 0;
case Intrinsic::pcmarker: {
SDOperand Tmp = getValue(I.getOperand(1));
DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Tmp));
DAG.setRoot(Tmp.getValue(1));
return 0;
}
- case Intrinsic::bswap_i16:
- case Intrinsic::bswap_i32:
- case Intrinsic::bswap_i64:
+ 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(),
getValue(I.getOperand(1))));
return 0;
- case Intrinsic::cttz_i8:
- case Intrinsic::cttz_i16:
- case Intrinsic::cttz_i32:
- case Intrinsic::cttz_i64:
- setValue(&I, DAG.getNode(ISD::CTTZ,
- getValue(I.getOperand(1)).getValueType(),
- getValue(I.getOperand(1))));
+ case Intrinsic::cttz: {
+ SDOperand Arg = getValue(I.getOperand(1));
+ MVT::ValueType Ty = Arg.getValueType();
+ SDOperand result = DAG.getNode(ISD::CTTZ, Ty, Arg);
+ setValue(&I, result);
return 0;
- case Intrinsic::ctlz_i8:
- case Intrinsic::ctlz_i16:
- case Intrinsic::ctlz_i32:
- case Intrinsic::ctlz_i64:
- setValue(&I, DAG.getNode(ISD::CTLZ,
- getValue(I.getOperand(1)).getValueType(),
- getValue(I.getOperand(1))));
+ }
+ case Intrinsic::ctlz: {
+ SDOperand Arg = getValue(I.getOperand(1));
+ MVT::ValueType Ty = Arg.getValueType();
+ SDOperand result = DAG.getNode(ISD::CTLZ, Ty, Arg);
+ setValue(&I, result);
return 0;
- case Intrinsic::ctpop_i8:
- case Intrinsic::ctpop_i16:
- case Intrinsic::ctpop_i32:
- case Intrinsic::ctpop_i64:
- setValue(&I, DAG.getNode(ISD::CTPOP,
- getValue(I.getOperand(1)).getValueType(),
- getValue(I.getOperand(1))));
+ }
+ case Intrinsic::ctpop: {
+ SDOperand Arg = getValue(I.getOperand(1));
+ MVT::ValueType Ty = Arg.getValueType();
+ SDOperand result = DAG.getNode(ISD::CTPOP, Ty, Arg);
+ setValue(&I, result);
return 0;
+ }
case Intrinsic::stacksave: {
SDOperand Op = getRoot();
SDOperand Tmp = DAG.getNode(ISD::STACKSAVE,
case Intrinsic::prefetch:
// FIXME: Currently discarding prefetches.
return 0;
+
+ case Intrinsic::var_annotation:
+ // Discard annotate attributes
+ return 0;
+
+ case Intrinsic::init_trampoline: {
+ const Function *F =
+ cast<Function>(IntrinsicInst::StripPointerCasts(I.getOperand(2)));
+
+ SDOperand Ops[6];
+ Ops[0] = getRoot();
+ Ops[1] = getValue(I.getOperand(1));
+ Ops[2] = getValue(I.getOperand(2));
+ Ops[3] = getValue(I.getOperand(3));
+ Ops[4] = DAG.getSrcValue(I.getOperand(1));
+ Ops[5] = DAG.getSrcValue(F);
+
+ SDOperand Tmp = DAG.getNode(ISD::TRAMPOLINE,
+ DAG.getNodeValueTypes(TLI.getPointerTy(),
+ MVT::Other), 2,
+ Ops, 6);
+
+ setValue(&I, Tmp);
+ DAG.setRoot(Tmp.getValue(1));
+ return 0;
+ }
+
+ case Intrinsic::gcroot:
+ if (GCI) {
+ Value *Alloca = I.getOperand(1);
+ Constant *TypeMap = cast<Constant>(I.getOperand(2));
+
+ FrameIndexSDNode *FI = cast<FrameIndexSDNode>(getValue(Alloca).Val);
+ GCI->addStackRoot(FI->getIndex(), TypeMap);
+ }
+ return 0;
+
+ case Intrinsic::gcread:
+ case Intrinsic::gcwrite:
+ assert(0 && "Collector failed to lower gcread/gcwrite intrinsics!");
+ return 0;
+
+ case Intrinsic::flt_rounds: {
+ setValue(&I, DAG.getNode(ISD::FLT_ROUNDS, MVT::i32));
+ return 0;
+ }
+ }
+}
+
+
+void SelectionDAGLowering::LowerCallTo(CallSite CS, SDOperand Callee,
+ bool IsTailCall,
+ MachineBasicBlock *LandingPad) {
+ const PointerType *PT = cast<PointerType>(CS.getCalledValue()->getType());
+ const FunctionType *FTy = cast<FunctionType>(PT->getElementType());
+ MachineModuleInfo *MMI = DAG.getMachineModuleInfo();
+ unsigned BeginLabel = 0, EndLabel = 0;
+
+ TargetLowering::ArgListTy Args;
+ TargetLowering::ArgListEntry Entry;
+ Args.reserve(CS.arg_size());
+ for (CallSite::arg_iterator i = CS.arg_begin(), e = CS.arg_end();
+ i != e; ++i) {
+ SDOperand ArgNode = getValue(*i);
+ Entry.Node = ArgNode; Entry.Ty = (*i)->getType();
+
+ unsigned attrInd = i - CS.arg_begin() + 1;
+ Entry.isSExt = CS.paramHasAttr(attrInd, ParamAttr::SExt);
+ Entry.isZExt = CS.paramHasAttr(attrInd, ParamAttr::ZExt);
+ Entry.isInReg = CS.paramHasAttr(attrInd, ParamAttr::InReg);
+ Entry.isSRet = CS.paramHasAttr(attrInd, ParamAttr::StructRet);
+ Entry.isNest = CS.paramHasAttr(attrInd, ParamAttr::Nest);
+ Entry.isByVal = CS.paramHasAttr(attrInd, ParamAttr::ByVal);
+ Args.push_back(Entry);
+ }
+
+ bool MarkTryRange = LandingPad ||
+ // C++ requires special handling of 'nounwind' calls.
+ (CS.doesNotThrow());
+
+ if (MarkTryRange && 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(), CS.getType(),
+ CS.paramHasAttr(0, ParamAttr::SExt),
+ FTy->isVarArg(), CS.getCallingConv(), IsTailCall,
+ Callee, Args, DAG);
+ if (CS.getType() != Type::VoidTy)
+ setValue(CS.getInstruction(), Result.first);
+ DAG.setRoot(Result.second);
+
+ if (MarkTryRange && 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);
}
}
void SelectionDAGLowering::visitCall(CallInst &I) {
const char *RenameFn = 0;
if (Function *F = I.getCalledFunction()) {
- if (F->isDeclaration())
+ if (F->isDeclaration()) {
if (unsigned IID = F->getIntrinsicID()) {
RenameFn = visitIntrinsicCall(I, IID);
if (!RenameFn)
return;
- } else { // Not an LLVM intrinsic.
- const std::string &Name = F->getName();
- if (Name[0] == 'c' && (Name == "copysign" || Name == "copysignf")) {
- if (I.getNumOperands() == 3 && // Basic sanity checks.
- I.getOperand(1)->getType()->isFloatingPoint() &&
- I.getType() == I.getOperand(1)->getType() &&
- I.getType() == I.getOperand(2)->getType()) {
- SDOperand LHS = getValue(I.getOperand(1));
- SDOperand RHS = getValue(I.getOperand(2));
- setValue(&I, DAG.getNode(ISD::FCOPYSIGN, LHS.getValueType(),
- LHS, RHS));
- return;
- }
- } else if (Name[0] == 'f' && (Name == "fabs" || Name == "fabsf")) {
- if (I.getNumOperands() == 2 && // Basic sanity checks.
- I.getOperand(1)->getType()->isFloatingPoint() &&
- I.getType() == I.getOperand(1)->getType()) {
- SDOperand Tmp = getValue(I.getOperand(1));
- setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp));
- return;
- }
- } else if (Name[0] == 's' && (Name == "sin" || Name == "sinf")) {
- if (I.getNumOperands() == 2 && // Basic sanity checks.
- I.getOperand(1)->getType()->isFloatingPoint() &&
- I.getType() == I.getOperand(1)->getType()) {
- SDOperand Tmp = getValue(I.getOperand(1));
- setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp));
- return;
- }
- } else if (Name[0] == 'c' && (Name == "cos" || Name == "cosf")) {
- if (I.getNumOperands() == 2 && // Basic sanity checks.
- I.getOperand(1)->getType()->isFloatingPoint() &&
- I.getType() == I.getOperand(1)->getType()) {
- SDOperand Tmp = getValue(I.getOperand(1));
- setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp));
- return;
- }
+ }
+ }
+
+ // Check for well-known libc/libm calls. If the function is internal, it
+ // can't be a library call.
+ unsigned NameLen = F->getNameLen();
+ if (!F->hasInternalLinkage() && NameLen) {
+ const char *NameStr = F->getNameStart();
+ if (NameStr[0] == 'c' &&
+ ((NameLen == 8 && !strcmp(NameStr, "copysign")) ||
+ (NameLen == 9 && !strcmp(NameStr, "copysignf")))) {
+ if (I.getNumOperands() == 3 && // Basic sanity checks.
+ I.getOperand(1)->getType()->isFloatingPoint() &&
+ I.getType() == I.getOperand(1)->getType() &&
+ I.getType() == I.getOperand(2)->getType()) {
+ SDOperand LHS = getValue(I.getOperand(1));
+ SDOperand RHS = getValue(I.getOperand(2));
+ setValue(&I, DAG.getNode(ISD::FCOPYSIGN, LHS.getValueType(),
+ LHS, RHS));
+ return;
+ }
+ } else if (NameStr[0] == 'f' &&
+ ((NameLen == 4 && !strcmp(NameStr, "fabs")) ||
+ (NameLen == 5 && !strcmp(NameStr, "fabsf")) ||
+ (NameLen == 5 && !strcmp(NameStr, "fabsl")))) {
+ if (I.getNumOperands() == 2 && // Basic sanity checks.
+ I.getOperand(1)->getType()->isFloatingPoint() &&
+ I.getType() == I.getOperand(1)->getType()) {
+ SDOperand Tmp = getValue(I.getOperand(1));
+ setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp));
+ return;
+ }
+ } else if (NameStr[0] == 's' &&
+ ((NameLen == 3 && !strcmp(NameStr, "sin")) ||
+ (NameLen == 4 && !strcmp(NameStr, "sinf")) ||
+ (NameLen == 4 && !strcmp(NameStr, "sinl")))) {
+ if (I.getNumOperands() == 2 && // Basic sanity checks.
+ I.getOperand(1)->getType()->isFloatingPoint() &&
+ I.getType() == I.getOperand(1)->getType()) {
+ SDOperand Tmp = getValue(I.getOperand(1));
+ setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp));
+ return;
+ }
+ } else if (NameStr[0] == 'c' &&
+ ((NameLen == 3 && !strcmp(NameStr, "cos")) ||
+ (NameLen == 4 && !strcmp(NameStr, "cosf")) ||
+ (NameLen == 4 && !strcmp(NameStr, "cosl")))) {
+ if (I.getNumOperands() == 2 && // Basic sanity checks.
+ I.getOperand(1)->getType()->isFloatingPoint() &&
+ I.getType() == I.getOperand(1)->getType()) {
+ SDOperand Tmp = getValue(I.getOperand(1));
+ setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp));
+ return;
}
}
+ }
} else if (isa<InlineAsm>(I.getOperand(0))) {
- visitInlineAsm(I);
+ visitInlineAsm(&I);
return;
}
- const PointerType *PT = cast<PointerType>(I.getCalledValue()->getType());
- const FunctionType *FTy = cast<FunctionType>(PT->getElementType());
-
SDOperand Callee;
if (!RenameFn)
Callee = getValue(I.getOperand(0));
else
Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy());
- TargetLowering::ArgListTy Args;
- TargetLowering::ArgListEntry Entry;
- Args.reserve(I.getNumOperands());
- for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) {
- Value *Arg = I.getOperand(i);
- SDOperand ArgNode = getValue(Arg);
- Entry.Node = ArgNode; Entry.Ty = Arg->getType();
- Entry.isSigned = FTy->paramHasAttr(i, FunctionType::SExtAttribute);
- Entry.isInReg = FTy->paramHasAttr(i, FunctionType::InRegAttribute);
- Entry.isSRet = FTy->paramHasAttr(i, FunctionType::StructRetAttribute);
- Args.push_back(Entry);
- }
- std::pair<SDOperand,SDOperand> Result =
- TLI.LowerCallTo(getRoot(), I.getType(),
- FTy->paramHasAttr(0,FunctionType::SExtAttribute),
- FTy->isVarArg(), I.getCallingConv(), I.isTailCall(),
- Callee, Args, DAG);
- if (I.getType() != Type::VoidTy)
- setValue(&I, Result.first);
- DAG.setRoot(Result.second);
+ LowerCallTo(&I, Callee, I.isTailCall());
}
+
+/// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from
+/// this value and returns the result as a ValueVT value. This uses
+/// Chain/Flag as the input and updates them for the output Chain/Flag.
+/// If the Flag pointer is NULL, no flag is used.
SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG,
- SDOperand &Chain, SDOperand &Flag)const{
- SDOperand Val = DAG.getCopyFromReg(Chain, Regs[0], RegVT, Flag);
- Chain = Val.getValue(1);
- Flag = Val.getValue(2);
-
- // If the result was expanded, copy from the top part.
- if (Regs.size() > 1) {
- assert(Regs.size() == 2 &&
- "Cannot expand to more than 2 elts yet!");
- SDOperand Hi = DAG.getCopyFromReg(Chain, Regs[1], RegVT, Flag);
- Chain = Hi.getValue(1);
- Flag = Hi.getValue(2);
- if (DAG.getTargetLoweringInfo().isLittleEndian())
- return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Val, Hi);
- else
- return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Hi, Val);
+ SDOperand &Chain, SDOperand *Flag)const{
+ // Copy the legal parts from the registers.
+ unsigned NumParts = Regs.size();
+ SmallVector<SDOperand, 8> Parts(NumParts);
+ for (unsigned i = 0; i != NumParts; ++i) {
+ SDOperand Part = Flag ?
+ DAG.getCopyFromReg(Chain, Regs[i], RegVT, *Flag) :
+ DAG.getCopyFromReg(Chain, Regs[i], RegVT);
+ Chain = Part.getValue(1);
+ if (Flag)
+ *Flag = Part.getValue(2);
+ Parts[i] = Part;
}
-
- // Otherwise, if the return value was promoted or extended, truncate it to the
- // appropriate type.
- if (RegVT == ValueVT)
- return Val;
- if (MVT::isInteger(RegVT)) {
- if (ValueVT < RegVT)
- return DAG.getNode(ISD::TRUNCATE, ValueVT, Val);
- else
- return DAG.getNode(ISD::ANY_EXTEND, ValueVT, Val);
- } else {
- return DAG.getNode(ISD::FP_ROUND, ValueVT, Val);
- }
+ // Assemble the legal parts into the final value.
+ return getCopyFromParts(DAG, &Parts[0], NumParts, RegVT, ValueVT);
}
/// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
/// specified value into the registers specified by this object. This uses
/// Chain/Flag as the input and updates them for the output Chain/Flag.
+/// If the Flag pointer is NULL, no flag is used.
void RegsForValue::getCopyToRegs(SDOperand Val, SelectionDAG &DAG,
- SDOperand &Chain, SDOperand &Flag,
- MVT::ValueType PtrVT) const {
- if (Regs.size() == 1) {
- // If there is a single register and the types differ, this must be
- // a promotion.
- if (RegVT != ValueVT) {
- if (MVT::isInteger(RegVT)) {
- if (RegVT < ValueVT)
- Val = DAG.getNode(ISD::TRUNCATE, RegVT, Val);
- else
- Val = DAG.getNode(ISD::ANY_EXTEND, RegVT, Val);
- } else
- Val = DAG.getNode(ISD::FP_EXTEND, RegVT, Val);
- }
- Chain = DAG.getCopyToReg(Chain, Regs[0], Val, Flag);
- Flag = Chain.getValue(1);
- } else {
- std::vector<unsigned> R(Regs);
- if (!DAG.getTargetLoweringInfo().isLittleEndian())
- std::reverse(R.begin(), R.end());
-
- for (unsigned i = 0, e = R.size(); i != e; ++i) {
- SDOperand Part = DAG.getNode(ISD::EXTRACT_ELEMENT, RegVT, Val,
- DAG.getConstant(i, PtrVT));
- Chain = DAG.getCopyToReg(Chain, R[i], Part, Flag);
- Flag = Chain.getValue(1);
- }
+ SDOperand &Chain, SDOperand *Flag) const {
+ // Get the list of the values's legal parts.
+ unsigned NumParts = Regs.size();
+ SmallVector<SDOperand, 8> Parts(NumParts);
+ getCopyToParts(DAG, Val, &Parts[0], NumParts, RegVT);
+
+ // Copy the parts into the registers.
+ for (unsigned i = 0; i != NumParts; ++i) {
+ SDOperand Part = Flag ?
+ DAG.getCopyToReg(Chain, Regs[i], Parts[i], *Flag) :
+ DAG.getCopyToReg(Chain, Regs[i], Parts[i]);
+ Chain = Part.getValue(0);
+ if (Flag)
+ *Flag = Part.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();
+ MachineRegisterInfo &RegInfo = MF.getRegInfo();
for (; NumRegs; --NumRegs)
- Regs.push_back(RegMap->createVirtualRegister(PhysReg.second));
+ Regs.push_back(RegInfo.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][0]);
- for (unsigned j = 1, e = C.size(); j != e; ++j) {
- TargetLowering::ConstraintType ThisFlavor = TLI.getConstraintType(C[j][0]);
- 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;
}
/// visitInlineAsm - Handle a call to an InlineAsm object.
///
-void SelectionDAGLowering::visitInlineAsm(CallInst &I) {
- InlineAsm *IA = cast<InlineAsm>(I.getOperand(0));
-
- SDOperand AsmStr = DAG.getTargetExternalSymbol(IA->getAsmString().c_str(),
- MVT::Other);
+void SelectionDAGLowering::visitInlineAsm(CallSite CS) {
+ InlineAsm *IA = cast<InlineAsm>(CS.getCalledValue());
- 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 ArgNo = 0; // ArgNo - The argument 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) {
- assert(I.getType() != Type::VoidTy && "Bad inline asm!");
- OpVT = TLI.getValueType(I.getType());
+ if (!OpInfo.isIndirect) {
+ // The return value of the call is this value. As such, there is no
+ // corresponding argument.
+ assert(CS.getType() != Type::VoidTy && "Bad inline asm!");
+ OpVT = TLI.getValueType(CS.getType());
} else {
- const Type *OpTy = I.getOperand(OpNum)->getType();
- OpVT = TLI.getValueType(cast<PointerType>(OpTy)->getElementType());
- OpNum++; // Consumes a call operand.
+ OpInfo.CallOperandVal = CS.getArgument(ArgNo++);
}
break;
case InlineAsm::isInput:
- OpVT = TLI.getValueType(I.getOperand(OpNum)->getType());
- OpNum++; // Consumes a call operand.
+ OpInfo.CallOperandVal = CS.getArgument(ArgNo++);
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.
+ // BasicBlocks are labels, currently appearing only in asm's.
+ if (OpInfo.CallOperandVal) {
+ if (isa<BasicBlock>(OpInfo.CallOperandVal))
+ OpInfo.CallOperand =
+ DAG.getBasicBlock(FuncInfo.MBBMap[cast<BasicBlock>(OpInfo.CallOperandVal)]);
+ else {
+ 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()->getABITypeSize(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[0]);
-
- 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;
+ assert(CS.getType() != Type::VoidTy && "Bad inline asm!");
+ 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.
}
// Use the produced MatchedRegs object to
- MatchedRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag,
- TLI.getPointerTy());
+ MatchedRegs.getCopyToRegs(InOperandVal, DAG, Chain, &Flag);
MatchedRegs.AddInlineAsmOperands(1 /*REGUSE*/, DAG, AsmNodeOperands);
break;
} else {
}
}
- TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
- if (ConstraintCode.size() == 1) // not a physreg name.
- CTy = TLI.getConstraintType(ConstraintCode[0]);
+ 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);
- if (!InOperandVal.Val) {
+ std::vector<SDOperand> Ops;
+ TLI.LowerAsmOperandForConstraint(InOperandVal, OpInfo.ConstraintCode[0],
+ Ops, DAG);
+ if (Ops.empty()) {
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(InOperandVal);
+ unsigned ResOpType = 3 /*IMM*/ | (Ops.size() << 3);
+ AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType,
+ TLI.getPointerTy()));
+ AsmNodeOperands.insert(AsmNodeOperands.end(), Ops.begin(), Ops.end());
break;
- } else if (CTy == TargetLowering::C_Memory) {
- // Memory input.
-
- // Check that the operand isn't a float.
- if (!MVT::isInteger(InOperandVal.getValueType()))
- assert(0 && "MATCH FAIL!");
-
- // 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);
- 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
+ // bit_convert.
+ if (MVT::isVector(Val.getValueType())) {
+ const VectorType *VTy = cast<VectorType>(CS.getType());
+ MVT::ValueType DesiredVT = TLI.getValueType(VTy);
+
+ Val = DAG.getNode(ISD::BIT_CONVERT, DesiredVT, Val);
+ }
+
+ setValue(CS.getInstruction(), Val);
+ }
std::vector<std::pair<SDOperand, Value*> > StoresToEmit;
for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) {
RegsForValue &OutRegs = IndirectStoresToEmit[i].first;
Value *Ptr = IndirectStoresToEmit[i].second;
- SDOperand OutVal = OutRegs.getCopyFromRegs(DAG, Chain, Flag);
+ SDOperand OutVal = OutRegs.getCopyFromRegs(DAG, Chain, &Flag);
StoresToEmit.push_back(std::make_pair(OutVal, Ptr));
}
// 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())
Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src);
// Scale the source by the type size.
- uint64_t ElementSize = TD->getTypeSize(I.getType()->getElementType());
+ uint64_t ElementSize = TD->getABITypeSize(I.getType()->getElementType());
Src = DAG.getNode(ISD::MUL, Src.getValueType(),
Src, getIntPtrConstant(ElementSize));
TargetLowering::ArgListEntry Entry;
Entry.Node = Src;
Entry.Ty = TLI.getTargetData()->getIntPtrType();
- Entry.isSigned = false;
- Entry.isInReg = false;
- Entry.isSRet = false;
Args.push_back(Entry);
std::pair<SDOperand,SDOperand> Result =
TargetLowering::ArgListEntry Entry;
Entry.Node = getValue(I.getOperand(0));
Entry.Ty = TLI.getTargetData()->getIntPtrType();
- Entry.isSigned = false;
- Entry.isInReg = false;
- Entry.isSRet = false;
Args.push_back(Entry);
MVT::ValueType IntPtr = TLI.getPointerTy();
std::pair<SDOperand,SDOperand> Result =
getValue(I.getOperand(1)),
getValue(I.getOperand(2)),
DAG.getSrcValue(I.getOperand(1)),
- DAG.getSrcValue(I.getOperand(2))));
-}
-
-/// ExpandScalarFormalArgs - Recursively expand the formal_argument node, either
-/// bit_convert it or join a pair of them with a BUILD_PAIR when appropriate.
-static SDOperand ExpandScalarFormalArgs(MVT::ValueType VT, SDNode *Arg,
- unsigned &i, SelectionDAG &DAG,
- TargetLowering &TLI) {
- if (TLI.getTypeAction(VT) != TargetLowering::Expand)
- return SDOperand(Arg, i++);
-
- MVT::ValueType EVT = TLI.getTypeToTransformTo(VT);
- unsigned NumVals = MVT::getSizeInBits(VT) / MVT::getSizeInBits(EVT);
- if (NumVals == 1) {
- return DAG.getNode(ISD::BIT_CONVERT, VT,
- ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI));
- } else if (NumVals == 2) {
- SDOperand Lo = ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI);
- SDOperand Hi = ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI);
- if (!TLI.isLittleEndian())
- std::swap(Lo, Hi);
- return DAG.getNode(ISD::BUILD_PAIR, VT, Lo, Hi);
- } else {
- // Value scalarized into many values. Unimp for now.
- assert(0 && "Cannot expand i64 -> i16 yet!");
- }
- return SDOperand();
+ DAG.getSrcValue(I.getOperand(2))));
}
/// TargetLowering::LowerArguments - This is the default LowerArguments
/// integrated into SDISel.
std::vector<SDOperand>
TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
- const FunctionType *FTy = F.getFunctionType();
// Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node.
std::vector<SDOperand> Ops;
Ops.push_back(DAG.getRoot());
for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end();
I != E; ++I, ++j) {
MVT::ValueType VT = getValueType(I->getType());
- bool isInReg = FTy->paramHasAttr(j, FunctionType::InRegAttribute);
- bool isSRet = FTy->paramHasAttr(j, FunctionType::StructRetAttribute);
- unsigned Flags = (isInReg << 1) | (isSRet << 2);
+ unsigned Flags = ISD::ParamFlags::NoFlagSet;
+ unsigned OriginalAlignment =
+ getTargetData()->getABITypeAlignment(I->getType());
+
+ // FIXME: Distinguish between a formal with no [sz]ext attribute from one
+ // that is zero extended!
+ if (F.paramHasAttr(j, ParamAttr::ZExt))
+ Flags &= ~(ISD::ParamFlags::SExt);
+ if (F.paramHasAttr(j, ParamAttr::SExt))
+ Flags |= ISD::ParamFlags::SExt;
+ if (F.paramHasAttr(j, ParamAttr::InReg))
+ Flags |= ISD::ParamFlags::InReg;
+ if (F.paramHasAttr(j, ParamAttr::StructRet))
+ Flags |= ISD::ParamFlags::StructReturn;
+ if (F.paramHasAttr(j, ParamAttr::ByVal)) {
+ Flags |= ISD::ParamFlags::ByVal;
+ const PointerType *Ty = cast<PointerType>(I->getType());
+ const StructType *STy = cast<StructType>(Ty->getElementType());
+ unsigned StructAlign =
+ Log2_32(getTargetData()->getCallFrameTypeAlignment(STy));
+ unsigned StructSize = getTargetData()->getABITypeSize(STy);
+ Flags |= (StructAlign << ISD::ParamFlags::ByValAlignOffs);
+ Flags |= (StructSize << ISD::ParamFlags::ByValSizeOffs);
+ }
+ if (F.paramHasAttr(j, ParamAttr::Nest))
+ Flags |= ISD::ParamFlags::Nest;
+ Flags |= (OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs);
switch (getTypeAction(VT)) {
default: assert(0 && "Unknown type action!");
RetVals.push_back(getTypeToTransformTo(VT));
Ops.push_back(DAG.getConstant(Flags, MVT::i32));
break;
- case Expand:
- if (VT != MVT::Vector) {
- // If this is a large integer, it needs to be broken up into small
- // 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);
- for (unsigned i = 0; i != NumVals; ++i) {
- RetVals.push_back(NVT);
- Ops.push_back(DAG.getConstant(Flags, MVT::i32));
- }
- } else {
- // Otherwise, this is a vector type. We only support legal vectors
- // right now.
- unsigned NumElems = cast<PackedType>(I->getType())->getNumElements();
- const Type *EltTy = cast<PackedType>(I->getType())->getElementType();
-
- // Figure out if there is a Packed type corresponding to this Vector
- // type. If so, convert to the packed type.
- MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
- if (TVT != MVT::Other && isTypeLegal(TVT)) {
- RetVals.push_back(TVT);
- Ops.push_back(DAG.getConstant(Flags, MVT::i32));
- } else {
- assert(0 && "Don't support illegal by-val vector arguments yet!");
- }
+ case Expand: {
+ // If this is an illegal type, it needs to be broken up to fit into
+ // registers.
+ MVT::ValueType RegisterVT = getRegisterType(VT);
+ unsigned NumRegs = getNumRegisters(VT);
+ for (unsigned i = 0; i != NumRegs; ++i) {
+ RetVals.push_back(RegisterVT);
+ // if it isn't first piece, alignment must be 1
+ if (i > 0)
+ Flags = (Flags & (~ISD::ParamFlags::OrigAlignment)) |
+ (1 << ISD::ParamFlags::OrigAlignmentOffs);
+ Ops.push_back(DAG.getConstant(Flags, MVT::i32));
}
break;
}
+ }
}
RetVals.push_back(MVT::Other);
SDNode *Result = DAG.getNode(ISD::FORMAL_ARGUMENTS,
DAG.getNodeValueTypes(RetVals), RetVals.size(),
&Ops[0], Ops.size()).Val;
-
- DAG.setRoot(SDOperand(Result, Result->getNumValues()-1));
+ unsigned NumArgRegs = Result->getNumValues() - 1;
+ DAG.setRoot(SDOperand(Result, NumArgRegs));
// Set up the return result vector.
Ops.clear();
case Promote: {
SDOperand Op(Result, i++);
if (MVT::isInteger(VT)) {
- if (FTy->paramHasAttr(Idx, FunctionType::SExtAttribute))
+ if (F.paramHasAttr(Idx, ParamAttr::SExt))
Op = DAG.getNode(ISD::AssertSext, Op.getValueType(), Op,
DAG.getValueType(VT));
- else if (FTy->paramHasAttr(Idx, FunctionType::ZExtAttribute))
+ else if (F.paramHasAttr(Idx, ParamAttr::ZExt))
Op = DAG.getNode(ISD::AssertZext, Op.getValueType(), Op,
DAG.getValueType(VT));
Op = DAG.getNode(ISD::TRUNCATE, VT, Op);
Ops.push_back(Op);
break;
}
- case Expand:
- if (VT != MVT::Vector) {
- // If this is a large integer or a floating point node that needs to be
- // expanded, it needs to be reassembled from small integers. Figure out
- // what the source elt type is and how many small integers it is.
- Ops.push_back(ExpandScalarFormalArgs(VT, Result, i, DAG, *this));
- } else {
- // Otherwise, this is a vector type. We only support legal vectors
- // right now.
- const PackedType *PTy = cast<PackedType>(I->getType());
- unsigned NumElems = PTy->getNumElements();
- const Type *EltTy = PTy->getElementType();
-
- // Figure out if there is a Packed type corresponding to this Vector
- // type. If so, convert to the packed type.
- MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
- if (TVT != MVT::Other && isTypeLegal(TVT)) {
- SDOperand N = SDOperand(Result, i++);
- // Handle copies from generic vectors to registers.
- N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N,
- DAG.getConstant(NumElems, MVT::i32),
- DAG.getValueType(getValueType(EltTy)));
- Ops.push_back(N);
- } else {
- assert(0 && "Don't support illegal by-val vector arguments yet!");
- abort();
- }
- }
+ case Expand: {
+ MVT::ValueType PartVT = getRegisterType(VT);
+ unsigned NumParts = getNumRegisters(VT);
+ SmallVector<SDOperand, 4> Parts(NumParts);
+ for (unsigned j = 0; j != NumParts; ++j)
+ Parts[j] = SDOperand(Result, i++);
+ Ops.push_back(getCopyFromParts(DAG, &Parts[0], NumParts, PartVT, VT));
break;
}
+ }
}
+ assert(i == NumArgRegs && "Argument register count mismatch!");
return Ops;
}
-/// ExpandScalarCallArgs - Recursively expand call argument node by
-/// bit_converting it or extract a pair of elements from the larger node.
-static void ExpandScalarCallArgs(MVT::ValueType VT, SDOperand Arg,
- unsigned Flags,
- SmallVector<SDOperand, 32> &Ops,
- SelectionDAG &DAG,
- TargetLowering &TLI) {
- if (TLI.getTypeAction(VT) != TargetLowering::Expand) {
- Ops.push_back(Arg);
- Ops.push_back(DAG.getConstant(Flags, MVT::i32));
- return;
- }
-
- MVT::ValueType EVT = TLI.getTypeToTransformTo(VT);
- unsigned NumVals = MVT::getSizeInBits(VT) / MVT::getSizeInBits(EVT);
- if (NumVals == 1) {
- Arg = DAG.getNode(ISD::BIT_CONVERT, EVT, Arg);
- ExpandScalarCallArgs(EVT, Arg, Flags, Ops, DAG, TLI);
- } else if (NumVals == 2) {
- SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, EVT, Arg,
- DAG.getConstant(0, TLI.getPointerTy()));
- SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, EVT, Arg,
- DAG.getConstant(1, TLI.getPointerTy()));
- if (!TLI.isLittleEndian())
- std::swap(Lo, Hi);
- ExpandScalarCallArgs(EVT, Lo, Flags, Ops, DAG, TLI);
- ExpandScalarCallArgs(EVT, Hi, Flags, Ops, DAG, TLI);
- } else {
- // Value scalarized into many values. Unimp for now.
- assert(0 && "Cannot expand i64 -> i16 yet!");
- }
-}
-
/// TargetLowering::LowerCallTo - This is the default LowerCallTo
/// implementation, which just inserts an ISD::CALL node, which is later custom
/// lowered by the target to something concrete. FIXME: When all targets are
for (unsigned i = 0, e = Args.size(); i != e; ++i) {
MVT::ValueType VT = getValueType(Args[i].Ty);
SDOperand Op = Args[i].Node;
- bool isSigned = Args[i].isSigned;
- bool isInReg = Args[i].isInReg;
- bool isSRet = Args[i].isSRet;
- unsigned Flags = (isSRet << 2) | (isInReg << 1) | isSigned;
+ unsigned Flags = ISD::ParamFlags::NoFlagSet;
+ unsigned OriginalAlignment =
+ getTargetData()->getABITypeAlignment(Args[i].Ty);
+
+ if (Args[i].isSExt)
+ Flags |= ISD::ParamFlags::SExt;
+ if (Args[i].isZExt)
+ Flags |= ISD::ParamFlags::ZExt;
+ if (Args[i].isInReg)
+ Flags |= ISD::ParamFlags::InReg;
+ if (Args[i].isSRet)
+ Flags |= ISD::ParamFlags::StructReturn;
+ if (Args[i].isByVal) {
+ Flags |= ISD::ParamFlags::ByVal;
+ const PointerType *Ty = cast<PointerType>(Args[i].Ty);
+ const StructType *STy = cast<StructType>(Ty->getElementType());
+ unsigned StructAlign =
+ Log2_32(getTargetData()->getCallFrameTypeAlignment(STy));
+ unsigned StructSize = getTargetData()->getABITypeSize(STy);
+ Flags |= (StructAlign << ISD::ParamFlags::ByValAlignOffs);
+ Flags |= (StructSize << ISD::ParamFlags::ByValSizeOffs);
+ }
+ if (Args[i].isNest)
+ Flags |= ISD::ParamFlags::Nest;
+ Flags |= OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs;
+
switch (getTypeAction(VT)) {
default: assert(0 && "Unknown type action!");
- case Legal:
+ case Legal:
Ops.push_back(Op);
Ops.push_back(DAG.getConstant(Flags, MVT::i32));
break;
case Promote:
if (MVT::isInteger(VT)) {
- unsigned ExtOp = isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND;
+ unsigned ExtOp;
+ if (Args[i].isSExt)
+ ExtOp = ISD::SIGN_EXTEND;
+ else if (Args[i].isZExt)
+ ExtOp = ISD::ZERO_EXTEND;
+ else
+ ExtOp = ISD::ANY_EXTEND;
Op = DAG.getNode(ExtOp, getTypeToTransformTo(VT), Op);
} else {
assert(MVT::isFloatingPoint(VT) && "Not int or FP?");
Ops.push_back(Op);
Ops.push_back(DAG.getConstant(Flags, MVT::i32));
break;
- case Expand:
- if (VT != MVT::Vector) {
- // If this is a large integer, it needs to be broken down into small
- // integers. Figure out what the source elt type is and how many small
- // integers it is.
- ExpandScalarCallArgs(VT, Op, Flags, Ops, DAG, *this);
- } else {
- // Otherwise, this is a vector type. We only support legal vectors
- // right now.
- const PackedType *PTy = cast<PackedType>(Args[i].Ty);
- unsigned NumElems = PTy->getNumElements();
- const Type *EltTy = PTy->getElementType();
-
- // Figure out if there is a Packed type corresponding to this Vector
- // type. If so, convert to the packed type.
- MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
- if (TVT != MVT::Other && isTypeLegal(TVT)) {
- // Insert a VBIT_CONVERT of the MVT::Vector type to the packed type.
- Op = DAG.getNode(ISD::VBIT_CONVERT, TVT, Op);
- Ops.push_back(Op);
- Ops.push_back(DAG.getConstant(Flags, MVT::i32));
- } else {
- assert(0 && "Don't support illegal by-val vector call args yet!");
- abort();
- }
+ case Expand: {
+ MVT::ValueType PartVT = getRegisterType(VT);
+ unsigned NumParts = getNumRegisters(VT);
+ SmallVector<SDOperand, 4> Parts(NumParts);
+ getCopyToParts(DAG, Op, &Parts[0], NumParts, PartVT);
+ for (unsigned i = 0; i != NumParts; ++i) {
+ // if it isn't first piece, alignment must be 1
+ unsigned MyFlags = Flags;
+ if (i != 0)
+ MyFlags = (MyFlags & (~ISD::ParamFlags::OrigAlignment)) |
+ (1 << ISD::ParamFlags::OrigAlignmentOffs);
+
+ Ops.push_back(Parts[i]);
+ Ops.push_back(DAG.getConstant(MyFlags, MVT::i32));
}
break;
}
+ }
}
// Figure out the result value types.
- SmallVector<MVT::ValueType, 4> RetTys;
-
- if (RetTy != Type::VoidTy) {
- MVT::ValueType VT = getValueType(RetTy);
- switch (getTypeAction(VT)) {
- default: assert(0 && "Unknown type action!");
- case Legal:
- RetTys.push_back(VT);
- break;
- case Promote:
- RetTys.push_back(getTypeToTransformTo(VT));
- break;
- case Expand:
- if (VT != MVT::Vector) {
- // If this is a large integer, it needs to be reassembled from small
- // 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);
- for (unsigned i = 0; i != NumVals; ++i)
- RetTys.push_back(NVT);
- } else {
- // Otherwise, this is a vector type. We only support legal vectors
- // right now.
- const PackedType *PTy = cast<PackedType>(RetTy);
- unsigned NumElems = PTy->getNumElements();
- const Type *EltTy = PTy->getElementType();
-
- // Figure out if there is a Packed type corresponding to this Vector
- // type. If so, convert to the packed type.
- MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems);
- if (TVT != MVT::Other && isTypeLegal(TVT)) {
- RetTys.push_back(TVT);
- } else {
- assert(0 && "Don't support illegal by-val vector call results yet!");
- abort();
- }
- }
- }
- }
+ MVT::ValueType VT = getValueType(RetTy);
+ MVT::ValueType RegisterVT = getRegisterType(VT);
+ unsigned NumRegs = getNumRegisters(VT);
+ SmallVector<MVT::ValueType, 4> RetTys(NumRegs);
+ for (unsigned i = 0; i != NumRegs; ++i)
+ RetTys[i] = RegisterVT;
RetTys.push_back(MVT::Other); // Always has a chain.
- // Finally, create the CALL node.
+ // Create the CALL node.
SDOperand Res = DAG.getNode(ISD::CALL,
- DAG.getVTList(&RetTys[0], RetTys.size()),
+ DAG.getVTList(&RetTys[0], NumRegs + 1),
&Ops[0], Ops.size());
-
- // This returns a pair of operands. The first element is the
- // return value for the function (if RetTy is not VoidTy). The second
- // element is the outgoing token chain.
- SDOperand ResVal;
- if (RetTys.size() != 1) {
- MVT::ValueType VT = getValueType(RetTy);
- if (RetTys.size() == 2) {
- ResVal = Res;
-
- // If this value was promoted, truncate it down.
- if (ResVal.getValueType() != VT) {
- if (VT == MVT::Vector) {
- // Insert a VBITCONVERT to convert from the packed result type to the
- // MVT::Vector type.
- unsigned NumElems = cast<PackedType>(RetTy)->getNumElements();
- const Type *EltTy = cast<PackedType>(RetTy)->getElementType();
-
- // Figure out if there is a Packed type corresponding to this Vector
- // type. If so, convert to the packed type.
- MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy),NumElems);
- if (TVT != MVT::Other && isTypeLegal(TVT)) {
- // Insert a VBIT_CONVERT of the FORMAL_ARGUMENTS to a
- // "N x PTyElementVT" MVT::Vector type.
- ResVal = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, ResVal,
- DAG.getConstant(NumElems, MVT::i32),
- DAG.getValueType(getValueType(EltTy)));
- } else {
- abort();
- }
- } else if (MVT::isInteger(VT)) {
- unsigned AssertOp = ISD::AssertSext;
- if (!RetTyIsSigned)
- AssertOp = ISD::AssertZext;
- ResVal = DAG.getNode(AssertOp, ResVal.getValueType(), ResVal,
- DAG.getValueType(VT));
- ResVal = DAG.getNode(ISD::TRUNCATE, VT, ResVal);
- } else {
- assert(MVT::isFloatingPoint(VT));
- if (getTypeAction(VT) == Expand)
- ResVal = DAG.getNode(ISD::BIT_CONVERT, VT, ResVal);
- else
- ResVal = DAG.getNode(ISD::FP_ROUND, VT, ResVal);
- }
- }
- } else if (RetTys.size() == 3) {
- ResVal = DAG.getNode(ISD::BUILD_PAIR, VT,
- Res.getValue(0), Res.getValue(1));
-
- } else {
- assert(0 && "Case not handled yet!");
- }
+ Chain = Res.getValue(NumRegs);
+
+ // Gather up the call result into a single value.
+ if (RetTy != Type::VoidTy) {
+ ISD::NodeType AssertOp = ISD::AssertSext;
+ if (!RetTyIsSigned)
+ AssertOp = ISD::AssertZext;
+ SmallVector<SDOperand, 4> Results(NumRegs);
+ for (unsigned i = 0; i != NumRegs; ++i)
+ Results[i] = Res.getValue(i);
+ Res = getCopyFromParts(DAG, &Results[0], NumRegs, RegisterVT, VT, AssertOp);
}
-
- return std::make_pair(ResVal, Res.getValue(Res.Val->getNumValues()-1));
+
+ return std::make_pair(Res, Chain);
}
SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
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 Align = (unsigned)cast<ConstantSDNode>(Op4)->getValue();
if (Align == 0) Align = 1;
+ // If the source and destination are known to not be aliases, we can
+ // lower memmove as memcpy.
+ if (Op == ISD::MEMMOVE) {
+ uint64_t Size = -1ULL;
+ if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op3))
+ Size = C->getValue();
+ if (AA.alias(I.getOperand(1), Size, I.getOperand(2), Size) ==
+ AliasAnalysis::NoAlias)
+ Op = ISD::MEMCPY;
+ }
+
if (ConstantSDNode *Size = dyn_cast<ConstantSDNode>(Op3)) {
std::vector<MVT::ValueType> MemOps;
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) {
I.getOperand(1), DstOff);
} else {
Value = DAG.getLoad(VT, getRoot(),
- getMemBasePlusOffset(Op2, SrcOff, DAG, TLI),
- I.getOperand(2), SrcOff);
+ getMemBasePlusOffset(Op2, SrcOff, DAG, TLI),
+ I.getOperand(2), SrcOff, false, Align);
Chain = Value.getValue(1);
Store =
DAG.getStore(Chain, Value,
getMemBasePlusOffset(Op1, DstOff, DAG, TLI),
- I.getOperand(1), DstOff);
+ I.getOperand(1), DstOff, false, Align);
}
OutChains.push_back(Store);
SrcOff += VTSize;
}
}
- DAG.setRoot(DAG.getNode(Op, MVT::Other, getRoot(), Op1, Op2, Op3, Op4));
+ SDOperand AlwaysInline = DAG.getConstant(0, MVT::i1);
+ SDOperand Node;
+ switch(Op) {
+ default:
+ assert(0 && "Unknown Op");
+ case ISD::MEMCPY:
+ Node = DAG.getMemcpy(getRoot(), Op1, Op2, Op3, Op4, AlwaysInline);
+ break;
+ case ISD::MEMMOVE:
+ Node = DAG.getMemmove(getRoot(), Op1, Op2, Op3, Op4, AlwaysInline);
+ break;
+ case ISD::MEMSET:
+ Node = DAG.getMemset(getRoot(), Op1, Op2, Op3, Op4, AlwaysInline);
+ break;
+ }
+ DAG.setRoot(Node);
}
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) {
- return RegMap->createVirtualRegister(TLI.getRegClassFor(VT));
+ return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT));
}
void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
- // FIXME: we only modify the CFG to split critical edges. This
- // updates dom and loop info.
AU.addRequired<AliasAnalysis>();
+ AU.addRequired<CollectorModuleMetadata>();
+ AU.setPreservesAll();
}
-/// OptimizeNoopCopyExpression - We have determined that the specified cast
-/// instruction is a noop copy (e.g. it's casting from one pointer type to
-/// another, int->uint, or int->sbyte on PPC.
-///
-/// Return true if any changes are made.
-static bool OptimizeNoopCopyExpression(CastInst *CI) {
- BasicBlock *DefBB = CI->getParent();
-
- /// InsertedCasts - Only insert a cast in each block once.
- std::map<BasicBlock*, CastInst*> InsertedCasts;
-
- bool MadeChange = false;
- for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end();
- UI != E; ) {
- Use &TheUse = UI.getUse();
- Instruction *User = cast<Instruction>(*UI);
-
- // Figure out which BB this cast is used in. For PHI's this is the
- // appropriate predecessor block.
- BasicBlock *UserBB = User->getParent();
- if (PHINode *PN = dyn_cast<PHINode>(User)) {
- unsigned OpVal = UI.getOperandNo()/2;
- UserBB = PN->getIncomingBlock(OpVal);
- }
-
- // Preincrement use iterator so we don't invalidate it.
- ++UI;
-
- // If this user is in the same block as the cast, don't change the cast.
- if (UserBB == DefBB) continue;
-
- // If we have already inserted a cast into this block, use it.
- CastInst *&InsertedCast = InsertedCasts[UserBB];
-
- if (!InsertedCast) {
- BasicBlock::iterator InsertPt = UserBB->begin();
- while (isa<PHINode>(InsertPt)) ++InsertPt;
-
- InsertedCast =
- CastInst::create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "",
- InsertPt);
- MadeChange = true;
- }
-
- // Replace a use of the cast with a use of the new casat.
- TheUse = InsertedCast;
- }
-
- // If we removed all uses, nuke the cast.
- if (CI->use_empty())
- CI->eraseFromParent();
-
- return MadeChange;
-}
-
-/// InsertGEPComputeCode - Insert code into BB to compute Ptr+PtrOffset,
-/// casting to the type of GEPI.
-static Instruction *InsertGEPComputeCode(Instruction *&V, BasicBlock *BB,
- Instruction *GEPI, Value *Ptr,
- Value *PtrOffset) {
- if (V) return V; // Already computed.
-
- // Figure out the insertion point
- BasicBlock::iterator InsertPt;
- if (BB == GEPI->getParent()) {
- // If GEP is already inserted into BB, insert right after the GEP.
- InsertPt = GEPI;
- ++InsertPt;
- } else {
- // Otherwise, insert at the top of BB, after any PHI nodes
- InsertPt = BB->begin();
- while (isa<PHINode>(InsertPt)) ++InsertPt;
- }
-
- // If Ptr is itself a cast, but in some other BB, emit a copy of the cast into
- // BB so that there is only one value live across basic blocks (the cast
- // operand).
- if (CastInst *CI = dyn_cast<CastInst>(Ptr))
- if (CI->getParent() != BB && isa<PointerType>(CI->getOperand(0)->getType()))
- Ptr = CastInst::create(CI->getOpcode(), CI->getOperand(0), CI->getType(),
- "", InsertPt);
-
- // Add the offset, cast it to the right type.
- Ptr = BinaryOperator::createAdd(Ptr, PtrOffset, "", InsertPt);
- // Ptr is an integer type, GEPI is pointer type ==> IntToPtr
- return V = CastInst::create(Instruction::IntToPtr, Ptr, GEPI->getType(),
- "", InsertPt);
-}
-
-/// ReplaceUsesOfGEPInst - Replace all uses of RepPtr with inserted code to
-/// compute its value. The RepPtr value can be computed with Ptr+PtrOffset. One
-/// trivial way of doing this would be to evaluate Ptr+PtrOffset in RepPtr's
-/// block, then ReplaceAllUsesWith'ing everything. However, we would prefer to
-/// sink PtrOffset into user blocks where doing so will likely allow us to fold
-/// the constant add into a load or store instruction. Additionally, if a user
-/// is a pointer-pointer cast, we look through it to find its users.
-static void ReplaceUsesOfGEPInst(Instruction *RepPtr, Value *Ptr,
- Constant *PtrOffset, BasicBlock *DefBB,
- GetElementPtrInst *GEPI,
- std::map<BasicBlock*,Instruction*> &InsertedExprs) {
- while (!RepPtr->use_empty()) {
- Instruction *User = cast<Instruction>(RepPtr->use_back());
-
- // If the user is a Pointer-Pointer cast, recurse. Only BitCast can be
- // used for a Pointer-Pointer cast.
- if (isa<BitCastInst>(User)) {
- ReplaceUsesOfGEPInst(User, Ptr, PtrOffset, DefBB, GEPI, InsertedExprs);
-
- // Drop the use of RepPtr. The cast is dead. Don't delete it now, else we
- // could invalidate an iterator.
- User->setOperand(0, UndefValue::get(RepPtr->getType()));
- continue;
- }
-
- // If this is a load of the pointer, or a store through the pointer, emit
- // the increment into the load/store block.
- Instruction *NewVal;
- if (isa<LoadInst>(User) ||
- (isa<StoreInst>(User) && User->getOperand(0) != RepPtr)) {
- NewVal = InsertGEPComputeCode(InsertedExprs[User->getParent()],
- User->getParent(), GEPI,
- Ptr, PtrOffset);
- } else {
- // If this use is not foldable into the addressing mode, use a version
- // emitted in the GEP block.
- NewVal = InsertGEPComputeCode(InsertedExprs[DefBB], DefBB, GEPI,
- Ptr, PtrOffset);
- }
-
- if (GEPI->getType() != RepPtr->getType()) {
- BasicBlock::iterator IP = NewVal;
- ++IP;
- // NewVal must be a GEP which must be pointer type, so BitCast
- NewVal = new BitCastInst(NewVal, RepPtr->getType(), "", IP);
- }
- User->replaceUsesOfWith(RepPtr, NewVal);
- }
-}
-
-
-/// OptimizeGEPExpression - Since we are doing basic-block-at-a-time instruction
-/// selection, we want to be a bit careful about some things. In particular, if
-/// we have a GEP instruction that is used in a different block than it is
-/// defined, the addressing expression of the GEP cannot be folded into loads or
-/// stores that use it. In this case, decompose the GEP and move constant
-/// indices into blocks that use it.
-static bool OptimizeGEPExpression(GetElementPtrInst *GEPI,
- const TargetData *TD) {
- // If this GEP is only used inside the block it is defined in, there is no
- // need to rewrite it.
- bool isUsedOutsideDefBB = false;
- BasicBlock *DefBB = GEPI->getParent();
- for (Value::use_iterator UI = GEPI->use_begin(), E = GEPI->use_end();
- UI != E; ++UI) {
- if (cast<Instruction>(*UI)->getParent() != DefBB) {
- isUsedOutsideDefBB = true;
- break;
- }
- }
- if (!isUsedOutsideDefBB) return false;
-
- // If this GEP has no non-zero constant indices, there is nothing we can do,
- // ignore it.
- bool hasConstantIndex = false;
- bool hasVariableIndex = false;
- for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1,
- E = GEPI->op_end(); OI != E; ++OI) {
- if (ConstantInt *CI = dyn_cast<ConstantInt>(*OI)) {
- if (CI->getZExtValue()) {
- hasConstantIndex = true;
- break;
- }
- } else {
- hasVariableIndex = true;
- }
- }
-
- // If this is a "GEP X, 0, 0, 0", turn this into a cast.
- if (!hasConstantIndex && !hasVariableIndex) {
- /// The GEP operand must be a pointer, so must its result -> BitCast
- Value *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
- GEPI->getName(), GEPI);
- GEPI->replaceAllUsesWith(NC);
- GEPI->eraseFromParent();
- return true;
- }
-
- // If this is a GEP &Alloca, 0, 0, forward subst the frame index into uses.
- if (!hasConstantIndex && !isa<AllocaInst>(GEPI->getOperand(0)))
- return false;
-
- // Otherwise, decompose the GEP instruction into multiplies and adds. Sum the
- // constant offset (which we now know is non-zero) and deal with it later.
- uint64_t ConstantOffset = 0;
- const Type *UIntPtrTy = TD->getIntPtrType();
- Value *Ptr = new PtrToIntInst(GEPI->getOperand(0), UIntPtrTy, "", GEPI);
- const Type *Ty = GEPI->getOperand(0)->getType();
-
- for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1,
- E = GEPI->op_end(); OI != E; ++OI) {
- Value *Idx = *OI;
- if (const StructType *StTy = dyn_cast<StructType>(Ty)) {
- unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
- if (Field)
- ConstantOffset += TD->getStructLayout(StTy)->getElementOffset(Field);
- Ty = StTy->getElementType(Field);
- } else {
- Ty = cast<SequentialType>(Ty)->getElementType();
-
- // Handle constant subscripts.
- if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
- if (CI->getZExtValue() == 0) continue;
- ConstantOffset += (int64_t)TD->getTypeSize(Ty)*CI->getSExtValue();
- continue;
- }
-
- // Ptr = Ptr + Idx * ElementSize;
-
- // Cast Idx to UIntPtrTy if needed.
- Idx = CastInst::createIntegerCast(Idx, UIntPtrTy, true/*SExt*/, "", GEPI);
-
- uint64_t ElementSize = TD->getTypeSize(Ty);
- // Mask off bits that should not be set.
- ElementSize &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits());
- Constant *SizeCst = ConstantInt::get(UIntPtrTy, ElementSize);
-
- // Multiply by the element size and add to the base.
- Idx = BinaryOperator::createMul(Idx, SizeCst, "", GEPI);
- Ptr = BinaryOperator::createAdd(Ptr, Idx, "", GEPI);
- }
- }
-
- // Make sure that the offset fits in uintptr_t.
- ConstantOffset &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits());
- Constant *PtrOffset = ConstantInt::get(UIntPtrTy, ConstantOffset);
-
- // Okay, we have now emitted all of the variable index parts to the BB that
- // the GEP is defined in. Loop over all of the using instructions, inserting
- // an "add Ptr, ConstantOffset" into each block that uses it and update the
- // instruction to use the newly computed value, making GEPI dead. When the
- // user is a load or store instruction address, we emit the add into the user
- // block, otherwise we use a canonical version right next to the gep (these
- // won't be foldable as addresses, so we might as well share the computation).
-
- std::map<BasicBlock*,Instruction*> InsertedExprs;
- ReplaceUsesOfGEPInst(GEPI, Ptr, PtrOffset, DefBB, GEPI, InsertedExprs);
-
- // Finally, the GEP is dead, remove it.
- GEPI->eraseFromParent();
-
- return true;
-}
-
-
-/// SplitEdgeNicely - Split the critical edge from TI to it's specified
-/// successor if it will improve codegen. We only do this if the successor has
-/// phi nodes (otherwise critical edges are ok). If there is already another
-/// predecessor of the succ that is empty (and thus has no phi nodes), use it
-/// instead of introducing a new block.
-static void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, Pass *P) {
- BasicBlock *TIBB = TI->getParent();
- BasicBlock *Dest = TI->getSuccessor(SuccNum);
- assert(isa<PHINode>(Dest->begin()) &&
- "This should only be called if Dest has a PHI!");
-
- /// TIPHIValues - This array is lazily computed to determine the values of
- /// PHIs in Dest that TI would provide.
- std::vector<Value*> TIPHIValues;
-
- // Check to see if Dest has any blocks that can be used as a split edge for
- // this terminator.
- for (pred_iterator PI = pred_begin(Dest), E = pred_end(Dest); PI != E; ++PI) {
- BasicBlock *Pred = *PI;
- // To be usable, the pred has to end with an uncond branch to the dest.
- BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator());
- if (!PredBr || !PredBr->isUnconditional() ||
- // Must be empty other than the branch.
- &Pred->front() != PredBr)
- continue;
-
- // Finally, since we know that Dest has phi nodes in it, we have to make
- // sure that jumping to Pred will have the same affect as going to Dest in
- // terms of PHI values.
- PHINode *PN;
- unsigned PHINo = 0;
- bool FoundMatch = true;
- for (BasicBlock::iterator I = Dest->begin();
- (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) {
- if (PHINo == TIPHIValues.size())
- TIPHIValues.push_back(PN->getIncomingValueForBlock(TIBB));
-
- // If the PHI entry doesn't work, we can't use this pred.
- if (TIPHIValues[PHINo] != PN->getIncomingValueForBlock(Pred)) {
- FoundMatch = false;
- break;
- }
- }
-
- // If we found a workable predecessor, change TI to branch to Succ.
- if (FoundMatch) {
- Dest->removePredecessor(TIBB);
- TI->setSuccessor(SuccNum, Pred);
- return;
- }
- }
-
- SplitCriticalEdge(TI, SuccNum, P, true);
-}
-
bool SelectionDAGISel::runOnFunction(Function &Fn) {
+ // Get alias analysis for load/store combining.
+ AA = &getAnalysis<AliasAnalysis>();
+
MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine());
- RegMap = MF.getSSARegMap();
+ if (MF.getFunction()->hasCollector())
+ GCI = &getAnalysis<CollectorModuleMetadata>().get(*MF.getFunction());
+ else
+ GCI = 0;
+ RegInfo = &MF.getRegInfo();
DOUT << "\n\n\n=== " << Fn.getName() << "\n";
- // First, split all critical edges.
- //
- // In this pass we also look for GEP and cast instructions that are used
- // across basic blocks and rewrite them to improve basic-block-at-a-time
- // selection.
- //
- bool MadeChange = true;
- while (MadeChange) {
- MadeChange = false;
- for (Function::iterator FNI = Fn.begin(), E = Fn.end(); FNI != E; ++FNI) {
- // Split all critical edges where the dest block has a PHI.
- TerminatorInst *BBTI = FNI->getTerminator();
- if (BBTI->getNumSuccessors() > 1) {
- for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i)
- if (isa<PHINode>(BBTI->getSuccessor(i)->begin()) &&
- isCriticalEdge(BBTI, i, true))
- SplitEdgeNicely(BBTI, i, this);
- }
-
-
- for (BasicBlock::iterator BBI = FNI->begin(), E = FNI->end(); BBI != E; ) {
- Instruction *I = BBI++;
-
- if (CallInst *CI = dyn_cast<CallInst>(I)) {
- // If we found an inline asm expession, and if the target knows how to
- // lower it to normal LLVM code, do so now.
- if (isa<InlineAsm>(CI->getCalledValue()))
- if (const TargetAsmInfo *TAI =
- TLI.getTargetMachine().getTargetAsmInfo()) {
- if (TAI->ExpandInlineAsm(CI))
- BBI = FNI->begin();
- }
- } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
- MadeChange |= OptimizeGEPExpression(GEPI, TLI.getTargetData());
- } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
- // If the source of the cast is a constant, then this should have
- // already been constant folded. The only reason NOT to constant fold
- // it is if something (e.g. LSR) was careful to place the constant
- // evaluation in a block other than then one that uses it (e.g. to hoist
- // the address of globals out of a loop). If this is the case, we don't
- // want to forward-subst the cast.
- if (isa<Constant>(CI->getOperand(0)))
- continue;
-
- // If this is a noop copy, sink it into user blocks to reduce the number
- // of virtual registers that must be created and coallesced.
- MVT::ValueType SrcVT = TLI.getValueType(CI->getOperand(0)->getType());
- MVT::ValueType DstVT = TLI.getValueType(CI->getType());
-
- // This is an fp<->int conversion?
- if (MVT::isInteger(SrcVT) != MVT::isInteger(DstVT))
- continue;
-
- // If this is an extension, it will be a zero or sign extension, which
- // isn't a noop.
- if (SrcVT < DstVT) continue;
-
- // If these values will be promoted, find out what they will be promoted
- // to. This helps us consider truncates on PPC as noop copies when they
- // are.
- if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote)
- SrcVT = TLI.getTypeToTransformTo(SrcVT);
- if (TLI.getTypeAction(DstVT) == TargetLowering::Promote)
- DstVT = TLI.getTypeToTransformTo(DstVT);
-
- // If, after promotion, these are the same types, this is a noop copy.
- if (SrcVT == DstVT)
- MadeChange |= OptimizeNoopCopyExpression(CI);
- }
- }
- }
- }
-
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);
// Add function live-ins to entry block live-in set.
BasicBlock *EntryBB = &Fn.getEntryBlock();
BB = FuncInfo.MBBMap[EntryBB];
- if (!MF.livein_empty())
- for (MachineFunction::livein_iterator I = MF.livein_begin(),
- E = MF.livein_end(); I != E; ++I)
+ if (!RegInfo->livein_empty())
+ for (MachineRegisterInfo::livein_iterator I = RegInfo->livein_begin(),
+ E = RegInfo->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;
}
cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) &&
"Copy from a reg to the same reg!");
- // If this type is not legal, we must make sure to not create an invalid
- // register use.
MVT::ValueType SrcVT = Op.getValueType();
- MVT::ValueType DestVT = TLI.getTypeToTransformTo(SrcVT);
- if (SrcVT == DestVT) {
- return DAG.getCopyToReg(getRoot(), Reg, Op);
- } else if (SrcVT == MVT::Vector) {
- // Handle copies from generic vectors to registers.
- MVT::ValueType PTyElementVT, PTyLegalElementVT;
- unsigned NE = TLI.getPackedTypeBreakdown(cast<PackedType>(V->getType()),
- PTyElementVT, PTyLegalElementVT);
-
- // 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.
- 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()));
- if (PTyElementVT == PTyLegalElementVT) {
- // Elements are legal.
- OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt));
- } else if (PTyLegalElementVT > PTyElementVT) {
- // Elements are promoted.
- if (MVT::isFloatingPoint(PTyLegalElementVT))
- Elt = DAG.getNode(ISD::FP_EXTEND, PTyLegalElementVT, Elt);
- else
- Elt = DAG.getNode(ISD::ANY_EXTEND, PTyLegalElementVT, Elt);
- OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt));
- } else {
- // Elements are expanded.
- // The src value is expanded into multiple registers.
- SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT,
- Elt, DAG.getConstant(0, TLI.getPointerTy()));
- SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT,
- Elt, DAG.getConstant(1, TLI.getPointerTy()));
- OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Lo));
- OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Hi));
- }
- }
- return DAG.getNode(ISD::TokenFactor, MVT::Other,
- &OutChains[0], OutChains.size());
- } else if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) {
- // The src value is promoted to the register.
- if (MVT::isFloatingPoint(SrcVT))
- Op = DAG.getNode(ISD::FP_EXTEND, DestVT, Op);
- else
- Op = DAG.getNode(ISD::ANY_EXTEND, DestVT, Op);
- return DAG.getCopyToReg(getRoot(), Reg, Op);
- } else {
- DestVT = TLI.getTypeToExpandTo(SrcVT);
- unsigned NumVals = TLI.getNumElements(SrcVT);
- if (NumVals == 1)
- return DAG.getCopyToReg(getRoot(), Reg,
- DAG.getNode(ISD::BIT_CONVERT, DestVT, Op));
- assert(NumVals == 2 && "1 to 4 (and more) expansion not implemented!");
- // The src value is expanded into multiple registers.
- SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
- Op, DAG.getConstant(0, TLI.getPointerTy()));
- SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
- Op, DAG.getConstant(1, TLI.getPointerTy()));
- Op = DAG.getCopyToReg(getRoot(), Reg, Lo);
- return DAG.getCopyToReg(Op, Reg+1, Hi);
- }
+ MVT::ValueType RegisterVT = TLI.getRegisterType(SrcVT);
+ unsigned NumRegs = TLI.getNumRegisters(SrcVT);
+ SmallVector<SDOperand, 8> Regs(NumRegs);
+ SmallVector<SDOperand, 8> Chains(NumRegs);
+
+ // Copy the value by legal parts into sequential virtual registers.
+ getCopyToParts(DAG, Op, &Regs[0], NumRegs, RegisterVT);
+ for (unsigned i = 0; i != NumRegs; ++i)
+ Chains[i] = DAG.getCopyToReg(getRoot(), Reg + i, Regs[i]);
+ return DAG.getNode(ISD::TokenFactor, MVT::Other, &Chains[0], NumRegs);
}
void SelectionDAGISel::
// If this argument is live outside of the entry block, insert a copy from
// whereever we got it to the vreg that other BB's will reference it as.
- if (FuncInfo.ValueMap.count(AI)) {
- SDOperand Copy =
- SDL.CopyValueToVirtualRegister(AI, FuncInfo.ValueMap[AI]);
+ DenseMap<const Value*, unsigned>::iterator VMI=FuncInfo.ValueMap.find(AI);
+ if (VMI != FuncInfo.ValueMap.end()) {
+ SDOperand Copy = SDL.CopyValueToVirtualRegister(AI, VMI->second);
UnorderedChains.push_back(Copy);
}
}
EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction());
}
+static void copyCatchInfo(BasicBlock *SrcBB, BasicBlock *DestBB,
+ MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) {
+ for (BasicBlock::iterator I = SrcBB->begin(), E = --SrcBB->end(); I != E; ++I)
+ if (isSelector(I)) {
+ // Apply the catch info to DestBB.
+ addCatchInfo(cast<CallInst>(*I), MMI, FLI.MBBMap[DestBB]);
+#ifndef NDEBUG
+ if (!FLI.MBBMap[SrcBB]->isLandingPad())
+ FLI.CatchInfoFound.insert(I);
+#endif
+ }
+}
+
+/// CheckDAGForTailCallsAndFixThem - This Function looks for CALL nodes in the
+/// DAG and fixes their tailcall attribute operand.
+static void CheckDAGForTailCallsAndFixThem(SelectionDAG &DAG,
+ TargetLowering& TLI) {
+ SDNode * Ret = NULL;
+ SDOperand Terminator = DAG.getRoot();
+
+ // Find RET node.
+ if (Terminator.getOpcode() == ISD::RET) {
+ Ret = Terminator.Val;
+ }
+
+ // Fix tail call attribute of CALL nodes.
+ for (SelectionDAG::allnodes_iterator BE = DAG.allnodes_begin(),
+ BI = prior(DAG.allnodes_end()); BI != BE; --BI) {
+ if (BI->getOpcode() == ISD::CALL) {
+ SDOperand OpRet(Ret, 0);
+ SDOperand OpCall(static_cast<SDNode*>(BI), 0);
+ bool isMarkedTailCall =
+ cast<ConstantSDNode>(OpCall.getOperand(3))->getValue() != 0;
+ // If CALL node has tail call attribute set to true and the call is not
+ // eligible (no RET or the target rejects) the attribute is fixed to
+ // false. The TargetLowering::IsEligibleForTailCallOptimization function
+ // must correctly identify tail call optimizable calls.
+ if (isMarkedTailCall &&
+ (Ret==NULL ||
+ !TLI.IsEligibleForTailCallOptimization(OpCall, OpRet, DAG))) {
+ SmallVector<SDOperand, 32> Ops;
+ unsigned idx=0;
+ for(SDNode::op_iterator I =OpCall.Val->op_begin(),
+ E=OpCall.Val->op_end(); I!=E; I++, idx++) {
+ if (idx!=3)
+ Ops.push_back(*I);
+ else
+ Ops.push_back(DAG.getConstant(false, TLI.getPointerTy()));
+ }
+ DAG.UpdateNodeOperands(OpCall, Ops.begin(), Ops.size());
+ }
+ }
+ }
+}
+
void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB,
std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate,
FunctionLoweringInfo &FuncInfo) {
- SelectionDAGLowering SDL(DAG, TLI, FuncInfo);
+ SelectionDAGLowering SDL(DAG, TLI, *AA, FuncInfo, GCI);
std::vector<SDOperand> UnorderedChains;
// Lower any arguments needed in this block if this is the entry block.
- if (LLVMBB == &LLVMBB->getParent()->front())
+ if (LLVMBB == &LLVMBB->getParent()->getEntryBlock())
LowerArguments(LLVMBB, SDL, UnorderedChains);
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)));
+
+ // Mark exception register as live in.
+ unsigned Reg = TLI.getExceptionAddressRegister();
+ if (Reg) BB->addLiveIn(Reg);
+
+ // Mark exception selector register as live in.
+ Reg = TLI.getExceptionSelectorRegister();
+ if (Reg) BB->addLiveIn(Reg);
+
+ // 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 an intrinsic (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 (isSelector(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);
-
+
// 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(
if (TI->getNumSuccessors())
SuccsHandled.resize(BB->getParent()->getNumBlockIDs());
- // Check successor nodes PHI nodes that expect a constant to be available from
- // this block.
+ // Check successor nodes' PHI nodes that expect a constant to be available
+ // from this block.
for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
BasicBlock *SuccBB = TI->getSuccessor(succ);
if (!isa<PHINode>(SuccBB->begin())) continue;
// 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;
- if (VT != MVT::Vector)
- NumElements = TLI.getNumElements(VT);
- else {
- MVT::ValueType VT1,VT2;
- NumElements =
- TLI.getPackedTypeBreakdown(cast<PackedType>(PN->getType()),
- VT1, VT2);
- }
- for (unsigned i = 0, e = NumElements; i != e; ++i)
+ unsigned NumRegisters = TLI.getNumRegisters(VT);
+ for (unsigned i = 0, e = NumRegisters; i != e; ++i)
PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i));
}
}
// lowering, as well as any jump table information.
SwitchCases.clear();
SwitchCases = SDL.SwitchCases;
- JT = SDL.JT;
-
+ 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());
+
+ // Check whether calls in this block are real tail calls. Fix up CALL nodes
+ // with correct tailcall attribute so that the target can rely on the tailcall
+ // attribute indicating whether the call is really eligible for tail call
+ // optimization.
+ CheckDAGForTailCallsAndFixThem(DAG, TLI);
}
void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) {
- // Get alias analysis for load/store combining.
- AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
+ DOUT << "Lowered selection DAG:\n";
+ DEBUG(DAG.dump());
// Run the DAG combiner in pre-legalize mode.
- DAG.Combine(false, AA);
+ DAG.Combine(false, *AA);
- DOUT << "Lowered selection DAG:\n";
+ DOUT << "Optimized lowered selection DAG:\n";
DEBUG(DAG.dump());
// Second step, hack on the DAG until it only uses operations and types that
// the target supports.
+#if 0 // Enable this some day.
+ DAG.LegalizeTypes();
+ // Someday even later, enable a dag combine pass here.
+#endif
DAG.Legalize();
DOUT << "Legalized selection DAG:\n";
DEBUG(DAG.dump());
// Run the DAG combiner in post-legalize mode.
- DAG.Combine(true, AA);
+ DAG.Combine(true, *AA);
+ DOUT << "Optimized legalized selection DAG:\n";
+ DEBUG(DAG.dump());
+
if (ViewISelDAGs) DAG.viewGraph();
// Third, instruction select all of the operations to machine code, adding the
// 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() && JT.Reg == 0) {
+ 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 &&
"This is not a machine PHI node that we are updating!");
- PHI->addRegOperand(PHINodesToUpdate[i].second, false);
- PHI->addMachineBasicBlockOperand(BB);
+ PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[i].second,
+ false));
+ PHI->addOperand(MachineOperand::CreateMBB(BB));
}
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, *AA, FuncInfo, GCI);
+ // 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, *AA, FuncInfo, GCI);
+ // 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->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second,
+ false));
+ PHI->addOperand(MachineOperand::CreateMBB(BitTestCases[i].Parent));
+ PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second,
+ false));
+ PHI->addOperand(MachineOperand::CreateMBB(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->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second,
+ false));
+ PHI->addOperand(MachineOperand::CreateMBB(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
- if (JT.Reg) {
- assert(SwitchCases.empty() && "Cannot have jump table and lowered switch");
- SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
- CurDAG = &SDAG;
- SelectionDAGLowering SDL(SDAG, TLI, FuncInfo);
- MachineBasicBlock *RangeBB = BB;
+ for (unsigned i = 0, e = JTCases.size(); i != e; ++i) {
+ // Lower header first, if it wasn't already lowered
+ if (!JTCases[i].first.Emitted) {
+ SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
+ CurDAG = &HSDAG;
+ SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI);
+ // Set the current basic block to the mbb we wish to insert the code into
+ BB = JTCases[i].first.HeaderBB;
+ HSDL.setCurrentBasicBlock(BB);
+ // Emit the code
+ HSDL.visitJumpTableHeader(JTCases[i].second, JTCases[i].first);
+ HSDAG.setRoot(HSDL.getRoot());
+ CodeGenAndEmitDAG(HSDAG);
+ }
+
+ SelectionDAG JSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
+ CurDAG = &JSDAG;
+ SelectionDAGLowering JSDL(JSDAG, TLI, *AA, FuncInfo, GCI);
// Set the current basic block to the mbb we wish to insert the code into
- BB = JT.MBB;
- SDL.setCurrentBasicBlock(BB);
+ BB = JTCases[i].second.MBB;
+ JSDL.setCurrentBasicBlock(BB);
// Emit the code
- SDL.visitJumpTable(JT);
- SDAG.setRoot(SDL.getRoot());
- CodeGenAndEmitDAG(SDAG);
+ JSDL.visitJumpTable(JTCases[i].second);
+ JSDAG.setRoot(JSDL.getRoot());
+ CodeGenAndEmitDAG(JSDAG);
+
// 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!");
- if (PHIBB == JT.Default) {
- PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
- PHI->addMachineBasicBlockOperand(RangeBB);
+ // "default" BB. We can go there only from header BB.
+ if (PHIBB == JTCases[i].second.Default) {
+ PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second,
+ false));
+ PHI->addOperand(MachineOperand::CreateMBB(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);
+ PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second,
+ false));
+ PHI->addOperand(MachineOperand::CreateMBB(BB));
}
}
- return;
}
// If the switch block involved a branch to one of the actual successors, we
assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
"This is not a machine PHI node that we are updating!");
if (BB->isSuccessor(PHI->getParent())) {
- PHI->addRegOperand(PHINodesToUpdate[i].second, false);
- PHI->addMachineBasicBlockOperand(BB);
+ PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[i].second,
+ false));
+ PHI->addOperand(MachineOperand::CreateMBB(BB));
}
}
for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) {
SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
CurDAG = &SDAG;
- SelectionDAGLowering SDL(SDAG, TLI, FuncInfo);
+ SelectionDAGLowering SDL(SDAG, TLI, *AA, FuncInfo, GCI);
// Set the current basic block to the mbb we wish to insert the code into
BB = SwitchCases[i].ThisBB;
for (unsigned pn = 0; ; ++pn) {
assert(pn != PHINodesToUpdate.size() && "Didn't find PHI entry!");
if (PHINodesToUpdate[pn].first == Phi) {
- Phi->addRegOperand(PHINodesToUpdate[pn].second, false);
- Phi->addMachineBasicBlockOperand(SwitchCases[i].ThisBB);
+ Phi->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pn].
+ second, false));
+ Phi->addOperand(MachineOperand::CreateMBB(SwitchCases[i].ThisBB));
break;
}
}
ScheduleDAG *SL = Ctor(this, &DAG, BB);
BB = SL->Run();
+
+ if (ViewSUnitDAGs) SL->viewGraph();
+
delete SL;
}
/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
/// specified in the .td file (e.g. 255).
bool SelectionDAGISel::CheckAndMask(SDOperand LHS, ConstantSDNode *RHS,
- int64_t DesiredMaskS) {
+ int64_t DesiredMaskS) const {
uint64_t ActualMask = RHS->getValue();
uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType());
// Otherwise, the DAG Combiner may have proven that the value coming in is
// either already zero or is not demanded. Check for known zero input bits.
uint64_t NeededMask = DesiredMask & ~ActualMask;
- if (getTargetLowering().MaskedValueIsZero(LHS, NeededMask))
+ if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
return true;
// TODO: check to see if missing bits are just not demanded.
/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
/// specified in the .td file (e.g. 255).
bool SelectionDAGISel::CheckOrMask(SDOperand LHS, ConstantSDNode *RHS,
- int64_t DesiredMaskS) {
+ int64_t DesiredMaskS) const {
uint64_t ActualMask = RHS->getValue();
uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType());
uint64_t NeededMask = DesiredMask & ~ActualMask;
uint64_t KnownZero, KnownOne;
- getTargetLowering().ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne);
+ CurDAG->ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne);
// If all the missing bits in the or are already known to be set, match!
if ((NeededMask & KnownOne) == NeededMask)
}
// 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