#define DEBUG_TYPE "isel"
#include "llvm/CodeGen/SelectionDAGISel.h"
+#include "llvm/CallingConv.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
#include "llvm/Target/TargetMachine.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include <map>
// Initialize the mapping of values to registers. This is only set up for
// instruction values that are used outside of the block that defines
// them.
- for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end(); AI != E; ++AI)
+ for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end();
+ AI != E; ++AI)
InitializeRegForValue(AI);
Function::iterator BB = Fn.begin(), E = Fn.end();
const Type *Ty = AI->getAllocatedType();
uint64_t TySize = TLI.getTargetData().getTypeSize(Ty);
unsigned Align = TLI.getTargetData().getTypeAlignment(Ty);
+
+ // If the alignment of the value is smaller than the size of the value,
+ // and if the size of the value is particularly small (<= 8 bytes),
+ // round up to the size of the value for potentially better performance.
+ //
+ // FIXME: This could be made better with a preferred alignment hook in
+ // TargetData. It serves primarily to 8-byte align doubles for X86.
+ if (Align < TySize && TySize <= 8) Align = TySize;
+
TySize *= CUI->getValue(); // Get total allocated size.
StaticAllocaMap[AI] =
MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align);
FuncInfo.ValueMap.find(V);
assert(VMI != FuncInfo.ValueMap.end() && "Value not in map!");
- return N = DAG.getCopyFromReg(VMI->second, VT, DAG.getEntryNode());
+ unsigned InReg = VMI->second;
+
+ // If this type is not legal, make it so now.
+ MVT::ValueType DestVT = TLI.getTypeToTransformTo(VT);
+
+ N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT);
+ if (DestVT < VT) {
+ // Source must be expanded. This input value is actually coming from the
+ // register pair VMI->second and VMI->second+1.
+ N = DAG.getNode(ISD::BUILD_PAIR, VT, N,
+ DAG.getCopyFromReg(DAG.getEntryNode(), InReg+1, DestVT));
+ } else {
+ if (DestVT > VT) { // Promotion case
+ if (MVT::isFloatingPoint(VT))
+ N = DAG.getNode(ISD::FP_ROUND, VT, N);
+ else
+ N = DAG.getNode(ISD::TRUNCATE, VT, N);
+ }
+ }
+
+ return N;
}
const SDOperand &setValue(const Value *V, SDOperand NewN) {
void visitUnwind(UnwindInst &I) { assert(0 && "TODO"); }
//
- void visitBinary(User &I, unsigned Opcode);
+ void visitBinary(User &I, unsigned Opcode, bool isShift = false);
void visitAdd(User &I) { visitBinary(I, ISD::ADD); }
void visitSub(User &I);
void visitMul(User &I) { visitBinary(I, ISD::MUL); }
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) { visitBinary(I, ISD::SHL); }
+ void visitShl(User &I) { visitBinary(I, ISD::SHL, true); }
void visitShr(User &I) {
- visitBinary(I, I.getType()->isUnsigned() ? ISD::SRL : ISD::SRA);
+ visitBinary(I, I.getType()->isUnsigned() ? ISD::SRL : ISD::SRA, true);
}
void visitSetCC(User &I, ISD::CondCode SignedOpc, ISD::CondCode UnsignedOpc);
void visitCall(CallInst &I);
void visitVAStart(CallInst &I);
- void visitVANext(VANextInst &I);
void visitVAArg(VAArgInst &I);
void visitVAEnd(CallInst &I);
void visitVACopy(CallInst &I);
Op1 = DAG.getNode(ISD::ZERO_EXTEND, TmpVT, Op1);
break;
case MVT::f32:
- // Extend float to double.
- Op1 = DAG.getNode(ISD::FP_EXTEND, MVT::f64, Op1);
- break;
case MVT::i64:
case MVT::f64:
break; // No extension needed!
visitBinary(I, ISD::SUB);
}
-void SelectionDAGLowering::visitBinary(User &I, unsigned Opcode) {
+void SelectionDAGLowering::visitBinary(User &I, unsigned Opcode, bool isShift) {
SDOperand Op1 = getValue(I.getOperand(0));
SDOperand Op2 = getValue(I.getOperand(1));
- if (isa<ShiftInst>(I))
+ if (isShift)
Op2 = DAG.getNode(ISD::ZERO_EXTEND, TLI.getShiftAmountTy(), Op2);
setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2));
ISD::CondCode Opcode = SignedOpcode;
if (I.getOperand(0)->getType()->isUnsigned())
Opcode = UnsignedOpcode;
- setValue(&I, DAG.getSetCC(Opcode, MVT::i1, Op1, Op2));
+ setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Opcode));
}
void SelectionDAGLowering::visitSelect(User &I) {
if (N.getValueType() == DestTy) {
setValue(&I, N); // noop cast.
+ } else if (DestTy == MVT::i1) {
+ // Cast to bool is a comparison against zero, not truncation to zero.
+ SDOperand Zero = isInteger(SrcTy) ? DAG.getConstant(0, N.getValueType()) :
+ DAG.getConstantFP(0.0, N.getValueType());
+ setValue(&I, DAG.getSetCC(MVT::i1, N, Zero, ISD::SETNE));
} else if (isInteger(SrcTy)) {
if (isInteger(DestTy)) { // Int -> Int cast
if (DestTy < SrcTy) // Truncating cast?
getIntPtrConstant(~(uint64_t)(StackAlign-1)));
}
- SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, AllocSize.getValueType(),
- getRoot(), AllocSize,
- getIntPtrConstant(Align));
+ std::vector<MVT::ValueType> VTs;
+ VTs.push_back(AllocSize.getValueType());
+ VTs.push_back(MVT::Other);
+ std::vector<SDOperand> Ops;
+ Ops.push_back(getRoot());
+ Ops.push_back(AllocSize);
+ Ops.push_back(getIntPtrConstant(Align));
+ SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, Ops);
DAG.setRoot(setValue(&I, DSA).getValue(1));
// Inform the Frame Information that we have just allocated a variable-sized
Value *SrcV = I.getOperand(0);
SDOperand Src = getValue(SrcV);
SDOperand Ptr = getValue(I.getOperand(1));
- // DAG.setRoot(DAG.getNode(ISD::STORE, MVT::Other, getRoot(), Src, Ptr));
DAG.setRoot(DAG.getNode(ISD::STORE, MVT::Other, getRoot(), Src, Ptr,
DAG.getSrcValue(I.getOperand(1))));
}
void SelectionDAGLowering::visitCall(CallInst &I) {
const char *RenameFn = 0;
+ SDOperand Tmp;
if (Function *F = I.getCalledFunction())
if (F->isExternal())
switch (F->getIntrinsicID()) {
if (I.getNumOperands() == 2 && // Basic sanity checks.
I.getOperand(1)->getType()->isFloatingPoint() &&
I.getType() == I.getOperand(1)->getType()) {
- SDOperand Tmp = getValue(I.getOperand(1));
+ Tmp = getValue(I.getOperand(1));
setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp));
return;
}
if (I.getNumOperands() == 2 && // Basic sanity checks.
I.getOperand(1)->getType()->isFloatingPoint() &&
I.getType() == I.getOperand(1)->getType()) {
- SDOperand Tmp = getValue(I.getOperand(1));
+ Tmp = getValue(I.getOperand(1));
setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp));
return;
}
if (I.getNumOperands() == 2 && // Basic sanity checks.
I.getOperand(1)->getType()->isFloatingPoint() &&
I.getType() == I.getOperand(1)->getType()) {
- SDOperand Tmp = getValue(I.getOperand(1));
+ Tmp = getValue(I.getOperand(1));
setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp));
return;
}
case Intrinsic::vacopy: visitVACopy(I); return;
case Intrinsic::returnaddress: visitFrameReturnAddress(I, false); return;
case Intrinsic::frameaddress: visitFrameReturnAddress(I, true); return;
- default:
- // FIXME: IMPLEMENT THESE.
- // readport, writeport, readio, writeio
- std::cerr << I;
- assert(0 && "This intrinsic is not implemented yet!");
- return;
+
case Intrinsic::setjmp: RenameFn = "setjmp"; break;
case Intrinsic::longjmp: RenameFn = "longjmp"; break;
case Intrinsic::memcpy: visitMemIntrinsic(I, ISD::MEMCPY); return;
case Intrinsic::memset: visitMemIntrinsic(I, ISD::MEMSET); return;
case Intrinsic::memmove: visitMemIntrinsic(I, ISD::MEMMOVE); return;
+ case Intrinsic::readport:
+ case Intrinsic::readio: {
+ std::vector<MVT::ValueType> VTs;
+ VTs.push_back(TLI.getValueType(I.getType()));
+ VTs.push_back(MVT::Other);
+ std::vector<SDOperand> Ops;
+ Ops.push_back(getRoot());
+ Ops.push_back(getValue(I.getOperand(1)));
+ Tmp = DAG.getNode(F->getIntrinsicID() == Intrinsic::readport ?
+ ISD::READPORT : ISD::READIO, VTs, Ops);
+
+ setValue(&I, Tmp);
+ DAG.setRoot(Tmp.getValue(1));
+ return;
+ }
+ case Intrinsic::writeport:
+ case Intrinsic::writeio:
+ DAG.setRoot(DAG.getNode(F->getIntrinsicID() == Intrinsic::writeport ?
+ ISD::WRITEPORT : ISD::WRITEIO, MVT::Other,
+ getRoot(), getValue(I.getOperand(1)),
+ getValue(I.getOperand(2))));
+ return;
case Intrinsic::dbg_stoppoint:
case Intrinsic::dbg_region_start:
case Intrinsic::dbg_region_end:
return;
case Intrinsic::isunordered:
- setValue(&I, DAG.getSetCC(ISD::SETUO, MVT::i1,getValue(I.getOperand(1)),
- getValue(I.getOperand(2))));
+ setValue(&I, DAG.getSetCC(MVT::i1,getValue(I.getOperand(1)),
+ getValue(I.getOperand(2)), ISD::SETUO));
return;
case Intrinsic::sqrt:
getValue(I.getOperand(1))));
return;
- case Intrinsic::pcmarker: {
- SDOperand Num = getValue(I.getOperand(1));
- DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Num));
+ case Intrinsic::pcmarker:
+ Tmp = getValue(I.getOperand(1));
+ DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Tmp));
return;
- }
case Intrinsic::cttz:
setValue(&I, DAG.getNode(ISD::CTTZ,
getValue(I.getOperand(1)).getValueType(),
getValue(I.getOperand(1)).getValueType(),
getValue(I.getOperand(1))));
return;
+ default:
+ std::cerr << I;
+ assert(0 && "This intrinsic is not implemented yet!");
+ return;
}
SDOperand Callee;
const FunctionType *FTy = cast<FunctionType>(PT->getElementType());
std::pair<SDOperand,SDOperand> Result =
- TLI.LowerCallTo(getRoot(), I.getType(), FTy->isVarArg(), Callee, Args, DAG);
+ TLI.LowerCallTo(getRoot(), I.getType(), FTy->isVarArg(), I.getCallingConv(),
+ I.isTailCall(), Callee, Args, DAG);
if (I.getType() != Type::VoidTy)
setValue(&I, Result.first);
DAG.setRoot(Result.second);
Args.push_back(std::make_pair(Src, TLI.getTargetData().getIntPtrType()));
std::pair<SDOperand,SDOperand> Result =
- TLI.LowerCallTo(getRoot(), I.getType(), false,
+ TLI.LowerCallTo(getRoot(), I.getType(), false, CallingConv::C, true,
DAG.getExternalSymbol("malloc", IntPtr),
Args, DAG);
setValue(&I, Result.first); // Pointers always fit in registers
TLI.getTargetData().getIntPtrType()));
MVT::ValueType IntPtr = TLI.getPointerTy();
std::pair<SDOperand,SDOperand> Result =
- TLI.LowerCallTo(getRoot(), Type::VoidTy, false,
+ TLI.LowerCallTo(getRoot(), Type::VoidTy, false, CallingConv::C, true,
DAG.getExternalSymbol("free", IntPtr), Args, DAG);
DAG.setRoot(Result.second);
}
-std::pair<SDOperand, SDOperand>
-TargetLowering::LowerVAStart(SDOperand Chain, SelectionDAG &DAG) {
+// InsertAtEndOfBasicBlock - This method should be implemented by targets that
+// mark instructions with the 'usesCustomDAGSchedInserter' flag. These
+// instructions are special in various ways, which require special support to
+// insert. The specified MachineInstr is created but not inserted into any
+// basic blocks, and the scheduler passes ownership of it to this method.
+MachineBasicBlock *TargetLowering::InsertAtEndOfBasicBlock(MachineInstr *MI,
+ MachineBasicBlock *MBB) {
+ std::cerr << "If a target marks an instruction with "
+ "'usesCustomDAGSchedInserter', it must implement "
+ "TargetLowering::InsertAtEndOfBasicBlock!\n";
+ abort();
+ return 0;
+}
+
+SDOperand TargetLowering::LowerVAStart(SDOperand Chain,
+ SDOperand VAListP, Value *VAListV,
+ SelectionDAG &DAG) {
// We have no sane default behavior, just emit a useful error message and bail
// out.
std::cerr << "Variable arguments handling not implemented on this target!\n";
abort();
- return std::make_pair(SDOperand(), SDOperand());
+ return SDOperand();
}
-SDOperand TargetLowering::LowerVAEnd(SDOperand Chain, SDOperand L,
+SDOperand TargetLowering::LowerVAEnd(SDOperand Chain, SDOperand LP, Value *LV,
SelectionDAG &DAG) {
// Default to a noop.
return Chain;
}
-std::pair<SDOperand,SDOperand>
-TargetLowering::LowerVACopy(SDOperand Chain, SDOperand L, SelectionDAG &DAG) {
- // Default to returning the input list.
- return std::make_pair(L, Chain);
+SDOperand TargetLowering::LowerVACopy(SDOperand Chain,
+ SDOperand SrcP, Value *SrcV,
+ SDOperand DestP, Value *DestV,
+ SelectionDAG &DAG) {
+ // Default to copying the input list.
+ SDOperand Val = DAG.getLoad(getPointerTy(), Chain,
+ SrcP, DAG.getSrcValue(SrcV));
+ SDOperand Result = DAG.getNode(ISD::STORE, MVT::Other, Val.getValue(1),
+ Val, DestP, DAG.getSrcValue(DestV));
+ return Result;
}
std::pair<SDOperand,SDOperand>
-TargetLowering::LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
- const Type *ArgTy, SelectionDAG &DAG) {
+TargetLowering::LowerVAArg(SDOperand Chain, SDOperand VAListP, Value *VAListV,
+ const Type *ArgTy, SelectionDAG &DAG) {
// We have no sane default behavior, just emit a useful error message and bail
// out.
std::cerr << "Variable arguments handling not implemented on this target!\n";
void SelectionDAGLowering::visitVAStart(CallInst &I) {
- std::pair<SDOperand,SDOperand> Result = TLI.LowerVAStart(getRoot(), DAG);
- setValue(&I, Result.first);
- DAG.setRoot(Result.second);
+ DAG.setRoot(TLI.LowerVAStart(getRoot(), getValue(I.getOperand(1)),
+ I.getOperand(1), DAG));
}
void SelectionDAGLowering::visitVAArg(VAArgInst &I) {
std::pair<SDOperand,SDOperand> Result =
- TLI.LowerVAArgNext(false, getRoot(), getValue(I.getOperand(0)),
- I.getType(), DAG);
- setValue(&I, Result.first);
- DAG.setRoot(Result.second);
-}
-
-void SelectionDAGLowering::visitVANext(VANextInst &I) {
- std::pair<SDOperand,SDOperand> Result =
- TLI.LowerVAArgNext(true, getRoot(), getValue(I.getOperand(0)),
- I.getArgType(), DAG);
+ TLI.LowerVAArg(getRoot(), getValue(I.getOperand(0)), I.getOperand(0),
+ I.getType(), DAG);
setValue(&I, Result.first);
DAG.setRoot(Result.second);
}
void SelectionDAGLowering::visitVAEnd(CallInst &I) {
- DAG.setRoot(TLI.LowerVAEnd(getRoot(), getValue(I.getOperand(1)), DAG));
+ DAG.setRoot(TLI.LowerVAEnd(getRoot(), getValue(I.getOperand(1)),
+ I.getOperand(1), DAG));
}
void SelectionDAGLowering::visitVACopy(CallInst &I) {
- std::pair<SDOperand,SDOperand> Result =
- TLI.LowerVACopy(getRoot(), getValue(I.getOperand(1)), DAG);
- setValue(&I, Result.first);
- DAG.setRoot(Result.second);
+ SDOperand Result =
+ TLI.LowerVACopy(getRoot(), getValue(I.getOperand(2)), I.getOperand(2),
+ getValue(I.getOperand(1)), I.getOperand(1), DAG);
+ DAG.setRoot(Result);
}
return std::make_pair(DAG.getConstant(0, getPointerTy()), Chain);
}
-SDOperand TargetLowering::LowerOperation(SDOperand Op) {
+SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
assert(0 && "LowerOperation not implemented for this target!");
abort();
return SDOperand();
return RegMap->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.
+}
bool SelectionDAGISel::runOnFunction(Function &Fn) {
RegMap = MF.getSSARegMap();
DEBUG(std::cerr << "\n\n\n=== " << Fn.getName() << "\n");
+ // First pass, split all critical edges for PHI nodes with incoming values
+ // that are constants, this way the load of the constant into a vreg will not
+ // be placed into MBBs that are used some other way.
+ for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
+ PHINode *PN;
+ for (BasicBlock::iterator BBI = BB->begin();
+ (PN = dyn_cast<PHINode>(BBI)); ++BBI)
+ for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
+ if (isa<Constant>(PN->getIncomingValue(i)))
+ SplitCriticalEdge(PN->getIncomingBlock(i), BB);
+ }
+
FunctionLoweringInfo FuncInfo(TLI, Fn, MF);
for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
SDOperand SelectionDAGISel::
CopyValueToVirtualRegister(SelectionDAGLowering &SDL, Value *V, unsigned Reg) {
- SelectionDAG &DAG = SDL.DAG;
SDOperand Op = SDL.getValue(V);
assert((Op.getOpcode() != ISD::CopyFromReg ||
- cast<RegSDNode>(Op)->getReg() != Reg) &&
+ cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) &&
"Copy from a reg to the same reg!");
- return DAG.getCopyToReg(SDL.getRoot(), Op, 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);
+ SelectionDAG &DAG = SDL.DAG;
+ if (SrcVT == DestVT) {
+ return DAG.getCopyToReg(SDL.getRoot(), Reg, Op);
+ } else if (SrcVT < DestVT) {
+ // 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::ZERO_EXTEND, DestVT, Op);
+ return DAG.getCopyToReg(SDL.getRoot(), Reg, Op);
+ } else {
+ // The src value is expanded into multiple registers.
+ SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
+ Op, DAG.getConstant(0, MVT::i32));
+ SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT,
+ Op, DAG.getConstant(1, MVT::i32));
+ Op = DAG.getCopyToReg(SDL.getRoot(), Reg, Lo);
+ return DAG.getCopyToReg(Op, Reg+1, Hi);
+ }
}
/// IsOnlyUsedInOneBasicBlock - If the specified argument is only used in a
AI != E; ++AI,++a)
if (!AI->use_empty()) {
SDL.setValue(AI, Args[a]);
- SDOperand Copy =
- CopyValueToVirtualRegister(SDL, AI, FuncInfo.ValueMap[AI]);
- UnorderedChains.push_back(Copy);
+
+ if (0 && IsOnlyUsedInOneBasicBlock(AI) == F.begin()) {
+ // Only used in the entry block, no need to copy it to a vreg for
+ // other blocks.
+ } else {
+ SDOperand Copy =
+ CopyValueToVirtualRegister(SDL, AI, FuncInfo.ValueMap[AI]);
+ UnorderedChains.push_back(Copy);
+ }
}
} else {
// Otherwise, if any argument is only accessed in a single basic block,
}
}
}
+
+ EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction());
}
// See if there are any block-local arguments that need to be emitted in this
DEBUG(std::cerr << "Legalized selection DAG:\n");
DEBUG(DAG.dump());
+ if (ViewDAGs) DAG.viewGraph();
+
// Third, instruction select all of the operations to machine code, adding the
// code to the MachineBasicBlock.
InstructionSelectBasicBlock(DAG);
- if (ViewDAGs) DAG.viewGraph();
-
DEBUG(std::cerr << "Selected machine code:\n");
DEBUG(BB->dump());