//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "isel"
+#include "llvm/ADT/BitVector.h"
#include "llvm/Analysis/AliasAnalysis.h"
-#include "llvm/Analysis/LoopInfo.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/ParameterAttributes.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFrameInfo.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"
/// 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)->getSExtValue() <
- cast<const ConstantInt>(C2.first)->getSExtValue();
+ 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
/// 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.
///
SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli,
FunctionLoweringInfo &funcinfo)
: TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()),
- JT(0,0,0,0), FuncInfo(funcinfo) {
+ FuncInfo(funcinfo) {
}
/// getRoot - Return the current virtual root of the Selection DAG.
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);
else
TmpVT = MVT::i32;
const FunctionType *FTy = I.getParent()->getParent()->getFunctionType();
+ const ParamAttrsList *Attrs = FTy->getParamAttrs();
ISD::NodeType ExtendKind = ISD::ANY_EXTEND;
- if (FTy->paramHasAttr(0, FunctionType::SExtAttribute))
+ if (Attrs && Attrs->paramHasAttr(0, SExtAttribute))
ExtendKind = ISD::SIGN_EXTEND;
- if (FTy->paramHasAttr(0, FunctionType::ZExtAttribute))
+ if (Attrs && Attrs->paramHasAttr(0, ZExtAttribute))
ExtendKind = ISD::ZERO_EXTEND;
RetOp = DAG.getNode(ExtendKind, TmpVT, RetOp);
}
}
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;
}
// 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 != -1UL && "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;
}
+/// 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 (VT > 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 (VT > TLI.getShiftAmountTy())
+ ShiftOp = DAG.getNode(ISD::TRUNCATE, TLI.getShiftAmountTy(), SUB);
+ else
+ ShiftOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getShiftAmountTy(), SUB);
+
+ // Make desired shift
+ SDOperand SwitchVal = DAG.getNode(ISD::SHL, TLI.getPointerTy(),
+ DAG.getConstant(1, TLI.getPointerTy()),
+ ShiftOp);
+
+ unsigned SwitchReg = FuncInfo.MakeReg(TLI.getPointerTy());
+ SDOperand CopyTo = DAG.getCopyToReg(getRoot(), SwitchReg, SwitchVal);
+ B.Reg = SwitchReg;
+
+ SDOperand BrRange = DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, RangeCmp,
+ DAG.getBasicBlock(B.Default));
+
+ // Set NextBlock to be the MBB immediately after the current one, if any.
+ // This is used to avoid emitting unnecessary branches to the next block.
+ MachineBasicBlock *NextBlock = 0;
+ MachineFunction::iterator BBI = CurMBB;
+ if (++BBI != CurMBB->getParent()->end())
+ NextBlock = BBI;
+
+ MachineBasicBlock* MBB = B.Cases[0].ThisBB;
+ if (MBB == NextBlock)
+ DAG.setRoot(BrRange);
+ else
+ DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, CopyTo,
+ DAG.getBasicBlock(MBB)));
+
+ CurMBB->addSuccessor(B.Default);
+ CurMBB->addSuccessor(MBB);
+
+ return;
+}
+
+/// visitBitTestCase - this function produces one "bit test"
+void SelectionDAGLowering::visitBitTestCase(MachineBasicBlock* NextMBB,
+ unsigned Reg,
+ SelectionDAGISel::BitTestCase &B) {
+ // Emit bit tests and jumps
+ SDOperand SwitchVal = DAG.getCopyFromReg(getRoot(), Reg, TLI.getPointerTy());
+
+ SDOperand AndOp = DAG.getNode(ISD::AND, TLI.getPointerTy(),
+ SwitchVal,
+ DAG.getConstant(B.Mask,
+ TLI.getPointerTy()));
+ SDOperand AndCmp = DAG.getSetCC(TLI.getSetCCResultTy(), AndOp,
+ DAG.getConstant(0, TLI.getPointerTy()),
+ ISD::SETNE);
+ SDOperand BrAnd = DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(),
+ AndCmp, DAG.getBasicBlock(B.TargetBB));
+
+ // Set NextBlock to be the MBB immediately after the current one, if any.
+ // This is used to avoid emitting unnecessary branches to the next block.
+ MachineBasicBlock *NextBlock = 0;
+ MachineFunction::iterator BBI = CurMBB;
+ if (++BBI != CurMBB->getParent()->end())
+ NextBlock = BBI;
+
+ if (NextMBB == NextBlock)
+ DAG.setRoot(BrAnd);
+ else
+ DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrAnd,
+ DAG.getBasicBlock(NextMBB)));
+
+ CurMBB->addSuccessor(B.TargetBB);
+ CurMBB->addSuccessor(NextMBB);
+
+ return;
+}
+
void SelectionDAGLowering::visitInvoke(InvokeInst &I) {
assert(0 && "Should never be visited directly");
}
void SelectionDAGLowering::visitUnwind(UnwindInst &I) {
}
-void SelectionDAGLowering::visitSwitch(SwitchInst &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);
+
+ // 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();
+
// Figure out which block is immediately after the current one.
MachineBasicBlock *NextBlock = 0;
- MachineFunction::iterator BBI = CurMBB;
+ MachineFunction::iterator BBI = CR.CaseBB;
if (++BBI != CurMBB->getParent()->end())
NextBlock = BBI;
+
+ // 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;
+ }
+ }
+ }
- MachineBasicBlock *Default = FuncInfo.MBBMap[I.getDefaultDest()];
+ // 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 {
+ // If the last case doesn't match, go to the default block.
+ FallThrough = Default;
+ }
- // 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.
+ 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;
+ }
- // 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)));
+ return true;
+}
- CurMBB->addSuccessor(Default);
- return;
- }
+/// 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 ((!TLI.isOperationLegal(ISD::BR_JT, MVT::Other) &&
+ !TLI.isOperationLegal(ISD::BRIND, MVT::Other)) ||
+ TSize <= 3)
+ return false;
- // 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;
+ double Density = (double)TSize / (double)((Last - First) + 1ULL);
+ if (Density < 0.4)
+ return false;
+
+ DOUT << "Lowering jump table\n"
+ << "First entry: " << First << ". Last entry: " << Last << "\n"
+ << "Size: " << TSize << ". Density: " << Density << "\n\n";
+
+ // Get the MachineFunction which holds the current MBB. This is used when
+ // inserting any additional MBBs necessary to represent the switch.
+ MachineFunction *CurMF = CurMBB->getParent();
+
+ // Figure out which block is immediately after the current one.
+ MachineBasicBlock *NextBlock = 0;
+ MachineFunction::iterator BBI = CR.CaseBB;
- for (unsigned i = 1; i < I.getNumSuccessors(); ++i) {
- MachineBasicBlock *SMBB = FuncInfo.MBBMap[I.getSuccessor(i)];
- Cases.push_back(Case(I.getSuccessorValue(i), SMBB));
+ 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(-1UL, 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";
+ }
- std::sort(Cases.begin(), Cases.end(), CaseCmp());
+ LSize += J->size();
+ RSize -= J->size();
+ }
+ // If our case is dense we *really* should handle it earlier!
+ assert((FMetric > 0) && "Should handle dense range earlier!");
- // 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);
+ 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));
+ }
- // 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();
+ // 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 = 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 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)"
+ 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;
- // 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;
- }
- }
+ // 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++;
}
- // 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);
+ uint64_t lo = cast<ConstantInt>(I->Low)->getSExtValue() - lowBound;
+ uint64_t hi = cast<ConstantInt>(I->High)->getSExtValue() - lowBound;
- // 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;
+ for (uint64_t j = lo; j <= hi; j++) {
+ CasesBits[i].Mask |= 1 << j;
+ CasesBits[i].Bits++;
}
- return;
+
}
+ std::sort(CasesBits.begin(), CasesBits.end(), CaseBitsCmp());
+
+ SelectionDAGISel::BitTestInfo BTC;
- // 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)->getSExtValue();
- uint64_t Last = cast<ConstantInt>(Cases.back().first)->getSExtValue();
- 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.
+ MachineFunction::iterator BBI = CR.CaseBB;
+ ++BBI;
- 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)));
+ const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock();
- // 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 ii = Cases.begin(), ee = Cases.end(); ii != ee; ++TEI)
- if (cast<ConstantInt>(ii->first)->getSExtValue() == 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);
- }
- }
-
- // 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;
- }
+ 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));
}
- // Push the initial CaseRec onto the worklist
- std::vector<CaseRec> CaseVec;
- CaseVec.push_back(CaseRec(CurMBB,0,0,CaseRange(Cases.begin(),Cases.end())));
+ SelectionDAGISel::BitTestBlock BTB(lowBound, range, SV,
+ -1U, (CR.CaseBB == CurMBB),
+ CR.CaseBB, Default, BTC);
+
+ if (CR.CaseBB == CurMBB)
+ visitBitTestHeader(BTB);
- 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);
- } 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));
- }
+ 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;
- // 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;
+ // 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));
+ }
+ sort(Cases.begin(), Cases.end(), CaseCmp());
+
+ // Merge case into clusters
+ if (Cases.size()>=2)
+ for (CaseItr I=Cases.begin(), J=++(Cases.begin()), E=Cases.end(); J!=E; ) {
+ 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 {
- FalseBB = new MachineBasicBlock(LLVMBB);
- CurMF->getBasicBlockList().insert(BBI, FalseBB);
- CaseVec.push_back(CaseRec(FalseBB,CR.LT,C,RHSR));
+ I = J++;
}
+ }
- // 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, TrueBB, FalseBB,
- CR.CaseBB);
+ 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;
+ }
- if (CR.CaseBB == CurMBB)
- visitSwitchCase(CB);
- else
- SwitchCases.push_back(CB);
- }
+ 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();
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 && "bit_part_select 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);
+ if (Ty < MVT::i32)
+ result = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, result);
+ else if (Ty > MVT::i32)
+ result = DAG.getNode(ISD::TRUNCATE, MVT::i32, result);
+ 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);
+ if (Ty < MVT::i32)
+ result = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, result);
+ else if (Ty > MVT::i32)
+ result = DAG.getNode(ISD::TRUNCATE, MVT::i32, result);
+ 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);
+ if (Ty < MVT::i32)
+ result = DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, result);
+ else if (Ty > MVT::i32)
+ result = DAG.getNode(ISD::TRUNCATE, MVT::i32, result);
+ setValue(&I, result);
return 0;
+ }
case Intrinsic::stacksave: {
SDOperand Op = getRoot();
SDOperand Tmp = DAG.getNode(ISD::STACKSAVE,
SDOperand Callee, unsigned OpIdx) {
const PointerType *PT = cast<PointerType>(CalledValueTy);
const FunctionType *FTy = cast<FunctionType>(PT->getElementType());
+ const ParamAttrsList *Attrs = FTy->getParamAttrs();
TargetLowering::ArgListTy Args;
TargetLowering::ArgListEntry Entry;
Value *Arg = I.getOperand(i);
SDOperand ArgNode = getValue(Arg);
Entry.Node = ArgNode; Entry.Ty = Arg->getType();
- Entry.isSExt = FTy->paramHasAttr(i, FunctionType::SExtAttribute);
- Entry.isZExt = FTy->paramHasAttr(i, FunctionType::ZExtAttribute);
- Entry.isInReg = FTy->paramHasAttr(i, FunctionType::InRegAttribute);
- Entry.isSRet = FTy->paramHasAttr(i, FunctionType::StructRetAttribute);
+ Entry.isSExt = Attrs && Attrs->paramHasAttr(i, SExtAttribute);
+ Entry.isZExt = Attrs && Attrs->paramHasAttr(i, ZExtAttribute);
+ Entry.isInReg = Attrs && Attrs->paramHasAttr(i, InRegAttribute);
+ Entry.isSRet = Attrs && Attrs->paramHasAttr(i, StructRetAttribute);
Args.push_back(Entry);
}
std::pair<SDOperand,SDOperand> Result =
TLI.LowerCallTo(getRoot(), I.getType(),
- FTy->paramHasAttr(0,FunctionType::SExtAttribute),
+ Attrs && Attrs->paramHasAttr(0, SExtAttribute),
FTy->isVarArg(), CallingConv, IsTailCall,
Callee, Args, DAG);
if (I.getType() != Type::VoidTy)
if (RegVT == ValueVT)
return Val;
+ if (MVT::isVector(RegVT)) {
+ assert(ValueVT == MVT::Vector && "Unknown vector conversion!");
+ return DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Val,
+ DAG.getConstant(MVT::getVectorNumElements(RegVT),
+ MVT::i32),
+ DAG.getValueType(MVT::getVectorBaseType(RegVT)));
+ }
+
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);
}
+
+ assert(MVT::isFloatingPoint(RegVT) && MVT::isFloatingPoint(ValueVT));
+ return DAG.getNode(ISD::FP_ROUND, ValueVT, Val);
}
/// getCopyToRegs - Emit a series of CopyToReg nodes that copies the
// If there is a single register and the types differ, this must be
// a promotion.
if (RegVT != ValueVT) {
- if (MVT::isInteger(RegVT)) {
+ if (MVT::isVector(RegVT)) {
+ assert(Val.getValueType() == MVT::Vector &&"Not a vector-vector cast?");
+ Val = DAG.getNode(ISD::VBIT_CONVERT, RegVT, Val);
+ } else if (MVT::isInteger(RegVT) && MVT::isInteger(Val.getValueType())) {
if (RegVT < ValueVT)
Val = DAG.getNode(ISD::TRUNCATE, RegVT, Val);
else
Val = DAG.getNode(ISD::ANY_EXTEND, RegVT, Val);
- } else
+ } else if (MVT::isFloatingPoint(RegVT) &&
+ MVT::isFloatingPoint(Val.getValueType())) {
Val = DAG.getNode(ISD::FP_EXTEND, RegVT, Val);
+ } else if (MVT::getSizeInBits(RegVT) ==
+ MVT::getSizeInBits(Val.getValueType())) {
+ Val = DAG.getNode(ISD::BIT_CONVERT, RegVT, Val);
+ } else {
+ assert(0 && "Unknown mismatch!");
+ }
}
Chain = DAG.getCopyToReg(Chain, Regs[0], Val, Flag);
Flag = Chain.getValue(1);
/// values added into it.
void RegsForValue::AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG,
std::vector<SDOperand> &Ops) const {
- Ops.push_back(DAG.getConstant(Code | (Regs.size() << 3), MVT::i32));
+ MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy();
+ Ops.push_back(DAG.getTargetConstant(Code | (Regs.size() << 3), IntPtrTy));
for (unsigned i = 0, e = Regs.size(); i != e; ++i)
Ops.push_back(DAG.getRegister(Regs[i], RegVT));
}
// 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;
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]);
+ TargetLowering::ConstraintType Flavor = TLI.getConstraintType(Current[0]);
for (unsigned j = 1, e = C.size(); j != e; ++j) {
- TargetLowering::ConstraintType ThisFlavor = TLI.getConstraintType(C[j][0]);
+ TargetLowering::ConstraintType ThisFlavor = TLI.getConstraintType(C[j]);
if (getConstraintGenerality(ThisFlavor) >
getConstraintGenerality(Flavor)) {
// This constraint letter is more general than the previous one,
case InlineAsm::isOutput: {
TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
if (ConstraintCode.size() == 1) // not a physreg name.
- CTy = TLI.getConstraintType(ConstraintCode[0]);
+ CTy = TLI.getConstraintType(ConstraintCode);
if (CTy == TargetLowering::C_Memory) {
// Memory output.
TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass;
if (ConstraintCode.size() == 1) // not a physreg name.
- CTy = TLI.getConstraintType(ConstraintCode[0]);
+ CTy = TLI.getConstraintType(ConstraintCode);
if (CTy == TargetLowering::C_Other) {
InOperandVal = TLI.isOperandValidForConstraint(InOperandVal,
std::vector<SDOperand>
TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
const FunctionType *FTy = F.getFunctionType();
+ const ParamAttrsList *Attrs = FTy->getParamAttrs();
// Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node.
std::vector<SDOperand> Ops;
Ops.push_back(DAG.getRoot());
// FIXME: Distinguish between a formal with no [sz]ext attribute from one
// that is zero extended!
- if (FTy->paramHasAttr(j, FunctionType::ZExtAttribute))
+ if (Attrs && Attrs->paramHasAttr(j, ZExtAttribute))
Flags &= ~(ISD::ParamFlags::SExt);
- if (FTy->paramHasAttr(j, FunctionType::SExtAttribute))
+ if (Attrs && Attrs->paramHasAttr(j, SExtAttribute))
Flags |= ISD::ParamFlags::SExt;
- if (FTy->paramHasAttr(j, FunctionType::InRegAttribute))
+ if (Attrs && Attrs->paramHasAttr(j, InRegAttribute))
Flags |= ISD::ParamFlags::InReg;
- if (FTy->paramHasAttr(j, FunctionType::StructRetAttribute))
+ if (Attrs && Attrs->paramHasAttr(j, StructRetAttribute))
Flags |= ISD::ParamFlags::StructReturn;
Flags |= (OriginalAlignment << ISD::ParamFlags::OrigAlignmentOffs);
case Promote: {
SDOperand Op(Result, i++);
if (MVT::isInteger(VT)) {
- if (FTy->paramHasAttr(Idx, FunctionType::SExtAttribute))
+ if (Attrs && Attrs->paramHasAttr(Idx, SExtAttribute))
Op = DAG.getNode(ISD::AssertSext, Op.getValueType(), Op,
DAG.getValueType(VT));
- else if (FTy->paramHasAttr(Idx, FunctionType::ZExtAttribute))
+ else if (Attrs && Attrs->paramHasAttr(Idx, ZExtAttribute))
Op = DAG.getNode(ISD::AssertZext, Op.getValueType(), Op,
DAG.getValueType(VT));
Op = DAG.getNode(ISD::TRUNCATE, VT, Op);
// 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
+ // Insert a VBIT_CONVERT to convert from the packed result type to the
// MVT::Vector type.
unsigned NumElems = cast<VectorType>(RetTy)->getNumElements();
const Type *EltTy = cast<VectorType>(RetTy)->getElementType();
}
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<LoopInfo>();
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;
-}
-
-/// isLoopInvariantInst - Returns true if all operands of the instruction are
-/// loop invariants in the specified loop.
-static bool isLoopInvariantInst(Instruction *I, Loop *L) {
- // The instruction is loop invariant if all of its operands are loop-invariant
- for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
- if (!L->isLoopInvariant(I->getOperand(i)))
- return false;
- return true;
-}
-
-/// SinkInvariantGEPIndex - If a GEP instruction has a variable index that has
-/// been hoisted out of the loop by LICM pass, sink it back into the use BB
-/// if it can be determined that the index computation can be folded into the
-/// addressing mode of the load / store uses.
-static bool SinkInvariantGEPIndex(BinaryOperator *BinOp, LoopInfo *loopInfo,
- const TargetLowering &TLI) {
- // Only look at Add / Sub for now.
- if (BinOp->getOpcode() != Instruction::Add &&
- BinOp->getOpcode() != Instruction::Sub)
- return false;
-
- // DestBBs - These are the blocks where a copy of BinOp will be inserted.
- SmallSet<BasicBlock*, 8> DestBBs;
- BasicBlock *DefBB = BinOp->getParent();
- bool MadeChange = false;
- for (Value::use_iterator UI = BinOp->use_begin(), E = BinOp->use_end();
- UI != E; ++UI) {
- Instruction *User = cast<Instruction>(*UI);
- // Only look for GEP use in another block.
- if (User->getParent() == DefBB) continue;
-
- if (isa<GetElementPtrInst>(User)) {
- BasicBlock *UserBB = User->getParent();
- Loop *L = loopInfo->getLoopFor(UserBB);
-
- // Only sink if expression is a loop invariant in the use BB.
- if (L && isLoopInvariantInst(BinOp, L) && !User->use_empty()) {
- const Type *UseTy = NULL;
- // FIXME: We are assuming all the uses of the GEP will have the
- // same type.
- Instruction *GEPUser = cast<Instruction>(*User->use_begin());
- if (LoadInst *Load = dyn_cast<LoadInst>(GEPUser))
- UseTy = Load->getType();
- else if (StoreInst *Store = dyn_cast<StoreInst>(GEPUser))
- UseTy = Store->getOperand(0)->getType();
-
- // Check if it is possible to fold the expression to address mode.
- if (UseTy &&
- TLI.isLegalAddressExpression(BinOp->getOpcode(),
- BinOp->getOperand(0),
- BinOp->getOperand(1), UseTy)) {
- DestBBs.insert(UserBB);
- MadeChange = true;
- }
- }
- }
- }
-
- // Nothing to do.
- if (!MadeChange)
- return false;
-
- /// InsertedOps - Only insert a duplicate in each block once.
- std::map<BasicBlock*, BinaryOperator*> InsertedOps;
- for (Value::use_iterator UI = BinOp->use_begin(), E = BinOp->use_end();
- UI != E; ) {
- Instruction *User = cast<Instruction>(*UI);
- BasicBlock *UserBB = User->getParent();
-
- // Preincrement use iterator so we don't invalidate it.
- ++UI;
-
- // If any user in this BB wants it, replace all the uses in the BB.
- if (DestBBs.count(UserBB)) {
- // Sink it into user block.
- BinaryOperator *&InsertedOp = InsertedOps[UserBB];
- if (!InsertedOp) {
- BasicBlock::iterator InsertPt = UserBB->begin();
- while (isa<PHINode>(InsertPt)) ++InsertPt;
-
- InsertedOp =
- BinaryOperator::create(BinOp->getOpcode(), BinOp->getOperand(0),
- BinOp->getOperand(1), "", InsertPt);
- }
-
- User->replaceUsesOfWith(BinOp, InsertedOp);
- }
- }
-
- if (BinOp->use_empty())
- BinOp->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) {
MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine());
RegMap = MF.getSSARegMap();
DOUT << "\n\n\n=== " << Fn.getName() << "\n";
- LoopInfo *loopInfo = &getAnalysis<LoopInfo>();
-
- // 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);
- } else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(I)) {
- MadeChange |= SinkInvariantGEPIndex(BinOp, loopInfo, TLI);
- }
- }
- }
- }
-
FunctionLoweringInfo FuncInfo(TLI, Fn, MF);
for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++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());
}
// 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 &&
}
return;
}
-
+
+ for (unsigned i = 0, e = BitTestCases.size(); i != e; ++i) {
+ // Lower header first, if it wasn't already lowered
+ if (!BitTestCases[i].Emitted) {
+ SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
+ CurDAG = &HSDAG;
+ SelectionDAGLowering HSDL(HSDAG, TLI, FuncInfo);
+ // Set the current basic block to the mbb we wish to insert the code into
+ BB = BitTestCases[i].Parent;
+ HSDL.setCurrentBasicBlock(BB);
+ // Emit the code
+ HSDL.visitBitTestHeader(BitTestCases[i]);
+ HSDAG.setRoot(HSDL.getRoot());
+ CodeGenAndEmitDAG(HSDAG);
+ }
+
+ for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) {
+ SelectionDAG BSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>());
+ CurDAG = &BSDAG;
+ SelectionDAGLowering BSDL(BSDAG, TLI, FuncInfo);
+ // Set the current basic block to the mbb we wish to insert the code into
+ BB = BitTestCases[i].Cases[j].ThisBB;
+ BSDL.setCurrentBasicBlock(BB);
+ // Emit the code
+ if (j+1 != ej)
+ BSDL.visitBitTestCase(BitTestCases[i].Cases[j+1].ThisBB,
+ BitTestCases[i].Reg,
+ BitTestCases[i].Cases[j]);
+ else
+ BSDL.visitBitTestCase(BitTestCases[i].Default,
+ BitTestCases[i].Reg,
+ BitTestCases[i].Cases[j]);
+
+
+ BSDAG.setRoot(BSDL.getRoot());
+ CodeGenAndEmitDAG(BSDAG);
+ }
+
+ // Update PHI Nodes
+ for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) {
+ MachineInstr *PHI = PHINodesToUpdate[pi].first;
+ MachineBasicBlock *PHIBB = PHI->getParent();
+ assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
+ "This is not a machine PHI node that we are updating!");
+ // This is "default" BB. We have two jumps to it. From "header" BB and
+ // from last "case" BB.
+ if (PHIBB == BitTestCases[i].Default) {
+ PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
+ PHI->addMachineBasicBlockOperand(BitTestCases[i].Parent);
+ PHI->addMachineBasicBlockOperand(BitTestCases[i].Cases.back().ThisBB);
+ }
+ // One of "cases" BB.
+ for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) {
+ MachineBasicBlock* cBB = BitTestCases[i].Cases[j].ThisBB;
+ if (cBB->succ_end() !=
+ std::find(cBB->succ_begin(),cBB->succ_end(), PHIBB)) {
+ PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
+ PHI->addMachineBasicBlockOperand(cBB);
+ }
+ }
+ }
+ }
+
// If the JumpTable record is filled in, then we need to emit a jump table.
// Updating the PHI nodes is tricky in this case, since we need to determine
// whether the PHI is a successor of the range check MBB or the jump table MBB
- 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, FuncInfo);
+ // 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, FuncInfo);
// 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) {
+ // "default" BB. We can go there only from header BB.
+ if (PHIBB == JTCases[i].second.Default) {
PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
- PHI->addMachineBasicBlockOperand(RangeBB);
+ PHI->addMachineBasicBlockOperand(JTCases[i].first.HeaderBB);
}
+ // JT BB. Just iterate over successors here
if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) {
PHI->addRegOperand(PHINodesToUpdate[pi].second, false);
PHI->addMachineBasicBlockOperand(BB);
}
}
- return;
}
// If the switch block involved a branch to one of the actual successors, we
}
// 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;
}
projects / oota-llvm.git / blobdiff