#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
-#include "llvm/Support/IntegersSubsetMapping.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetFrameLowering.h"
} else
Cond = DAG.getSetCC(dl, MVT::i1, CondLHS, getValue(CB.CmpRHS), CB.CC);
} else {
- assert(CB.CC == ISD::SETCC_INVALID &&
- "Condition is undefined for to-the-range belonging check.");
+ assert(CB.CC == ISD::SETLE && "Can handle only LE ranges now");
const APInt& Low = cast<ConstantInt>(CB.CmpLHS)->getValue();
const APInt& High = cast<ConstantInt>(CB.CmpRHS)->getValue();
SDValue CmpOp = getValue(CB.CmpMHS);
EVT VT = CmpOp.getValueType();
- if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(false)) {
+ if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) {
Cond = DAG.getSetCC(dl, MVT::i1, CmpOp, DAG.getConstant(High, VT),
- ISD::SETULE);
+ ISD::SETLE);
} else {
SDValue SUB = DAG.getNode(ISD::SUB, dl,
VT, CmpOp, DAG.getConstant(Low, VT));
DAG.setRoot(BrCond);
}
+/// Codegen a new tail for a stack protector check ParentMBB which has had its
+/// tail spliced into a stack protector check success bb.
+///
+/// For a high level explanation of how this fits into the stack protector
+/// generation see the comment on the declaration of class
+/// StackProtectorDescriptor.
+void SelectionDAGBuilder::visitSPDescriptorParent(StackProtectorDescriptor &SPD,
+ MachineBasicBlock *ParentBB) {
+
+ // First create the loads to the guard/stack slot for the comparison.
+ const TargetLowering *TLI = TM.getTargetLowering();
+ EVT PtrTy = TLI->getPointerTy();
+
+ MachineFrameInfo *MFI = ParentBB->getParent()->getFrameInfo();
+ int FI = MFI->getStackProtectorIndex();
+
+ const Value *IRGuard = SPD.getGuard();
+ SDValue GuardPtr = getValue(IRGuard);
+ SDValue StackSlotPtr = DAG.getFrameIndex(FI, PtrTy);
+
+ unsigned Align =
+ TLI->getDataLayout()->getPrefTypeAlignment(IRGuard->getType());
+ SDValue Guard = DAG.getLoad(PtrTy, getCurSDLoc(), DAG.getEntryNode(),
+ GuardPtr, MachinePointerInfo(IRGuard, 0),
+ true, false, false, Align);
+
+ SDValue StackSlot = DAG.getLoad(PtrTy, getCurSDLoc(), DAG.getEntryNode(),
+ StackSlotPtr,
+ MachinePointerInfo::getFixedStack(FI),
+ true, false, false, Align);
+
+ // Perform the comparison via a subtract/getsetcc.
+ EVT VT = Guard.getValueType();
+ SDValue Sub = DAG.getNode(ISD::SUB, getCurSDLoc(), VT, Guard, StackSlot);
+
+ SDValue Cmp = DAG.getSetCC(getCurSDLoc(),
+ TLI->getSetCCResultType(*DAG.getContext(),
+ Sub.getValueType()),
+ Sub, DAG.getConstant(0, VT),
+ ISD::SETNE);
+
+ // If the sub is not 0, then we know the guard/stackslot do not equal, so
+ // branch to failure MBB.
+ SDValue BrCond = DAG.getNode(ISD::BRCOND, getCurSDLoc(),
+ MVT::Other, StackSlot.getOperand(0),
+ Cmp, DAG.getBasicBlock(SPD.getFailureMBB()));
+ // Otherwise branch to success MBB.
+ SDValue Br = DAG.getNode(ISD::BR, getCurSDLoc(),
+ MVT::Other, BrCond,
+ DAG.getBasicBlock(SPD.getSuccessMBB()));
+
+ DAG.setRoot(Br);
+}
+
+/// Codegen the failure basic block for a stack protector check.
+///
+/// A failure stack protector machine basic block consists simply of a call to
+/// __stack_chk_fail().
+///
+/// For a high level explanation of how this fits into the stack protector
+/// generation see the comment on the declaration of class
+/// StackProtectorDescriptor.
+void
+SelectionDAGBuilder::visitSPDescriptorFailure(StackProtectorDescriptor &SPD) {
+ const TargetLowering *TLI = TM.getTargetLowering();
+ SDValue Chain = TLI->makeLibCall(DAG, RTLIB::STACKPROTECTOR_CHECK_FAIL,
+ MVT::isVoid, 0, 0, false, getCurSDLoc(),
+ false, false).second;
+ DAG.setRoot(Chain);
+}
+
/// visitBitTestHeader - This function emits necessary code to produce value
/// suitable for "bit tests"
void SelectionDAGBuilder::visitBitTestHeader(BitTestBlock &B,
CC = ISD::SETEQ;
LHS = SV; RHS = I->High; MHS = NULL;
} else {
- CC = ISD::SETCC_INVALID;
+ CC = ISD::SETLE;
LHS = I->Low; MHS = SV; RHS = I->High;
}
static APInt ComputeRange(const APInt &First, const APInt &Last) {
uint32_t BitWidth = std::max(Last.getBitWidth(), First.getBitWidth()) + 1;
- APInt LastExt = Last.zext(BitWidth), FirstExt = First.zext(BitWidth);
+ APInt LastExt = Last.sext(BitWidth), FirstExt = First.sext(BitWidth);
return (LastExt - FirstExt + 1ULL);
}
const APInt &Low = cast<ConstantInt>(I->Low)->getValue();
const APInt &High = cast<ConstantInt>(I->High)->getValue();
- if (Low.ule(TEI) && TEI.ule(High)) {
+ if (Low.sle(TEI) && TEI.sle(High)) {
DestBBs.push_back(I->BB);
if (TEI==High)
++I;
// 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.
- CaseBlock CB(ISD::SETULT, SV, C, NULL, TrueBB, FalseBB, CR.CaseBB);
+ CaseBlock CB(ISD::SETLT, SV, C, NULL, TrueBB, FalseBB, CR.CaseBB);
if (CR.CaseBB == SwitchBB)
visitSwitchCase(CB, SwitchBB);
MachineFunction *CurMF = FuncInfo.MF;
// If target does not have legal shift left, do not emit bit tests at all.
- if (!TLI->isOperationLegal(ISD::SHL, TLI->getPointerTy()))
+ if (!TLI->isOperationLegal(ISD::SHL, PTy))
return false;
size_t numCmps = 0;
// Optimize the case where all the case values fit in a
// word without having to subtract minValue. In this case,
// we can optimize away the subtraction.
- if (maxValue.ult(IntPtrBits)) {
+ if (minValue.isNonNegative() && maxValue.slt(IntPtrBits)) {
cmpRange = maxValue;
} else {
lowBound = minValue;
/// Clusterify - Transform simple list of Cases into list of CaseRange's
size_t SelectionDAGBuilder::Clusterify(CaseVector& Cases,
const SwitchInst& SI) {
-
- /// Use a shorter form of declaration, and also
- /// show the we want to use CRSBuilder as Clusterifier.
- typedef IntegersSubsetMapping<MachineBasicBlock> Clusterifier;
-
- Clusterifier TheClusterifier;
+ size_t numCmps = 0;
BranchProbabilityInfo *BPI = FuncInfo.BPI;
// Start with "simple" cases
const BasicBlock *SuccBB = i.getCaseSuccessor();
MachineBasicBlock *SMBB = FuncInfo.MBBMap[SuccBB];
- TheClusterifier.add(i.getCaseValueEx(), SMBB,
- BPI ? BPI->getEdgeWeight(SI.getParent(), i.getSuccessorIndex()) : 0);
- }
-
- TheClusterifier.optimize();
-
- size_t numCmps = 0;
- for (Clusterifier::RangeIterator i = TheClusterifier.begin(),
- e = TheClusterifier.end(); i != e; ++i, ++numCmps) {
- Clusterifier::Cluster &C = *i;
- // Update edge weight for the cluster.
- unsigned W = C.first.Weight;
-
- // FIXME: Currently work with ConstantInt based numbers.
- // Changing it to APInt based is a pretty heavy for this commit.
- Cases.push_back(Case(C.first.getLow().toConstantInt(),
- C.first.getHigh().toConstantInt(), C.second, W));
+ uint32_t ExtraWeight =
+ BPI ? BPI->getEdgeWeight(SI.getParent(), i.getSuccessorIndex()) : 0;
+
+ Cases.push_back(Case(i.getCaseValue(), i.getCaseValue(),
+ SMBB, ExtraWeight));
+ }
+ std::sort(Cases.begin(), Cases.end(), CaseCmp());
+
+ // Merge case into clusters
+ if (Cases.size() >= 2)
+ // Must recompute end() each iteration because it may be
+ // invalidated by erase if we hold on to it
+ for (CaseItr I = Cases.begin(), J = llvm::next(Cases.begin());
+ J != Cases.end(); ) {
+ const APInt& nextValue = cast<ConstantInt>(J->Low)->getValue();
+ const APInt& currentValue = cast<ConstantInt>(I->High)->getValue();
+ 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;
+ I->ExtraWeight += J->ExtraWeight;
+ J = Cases.erase(J);
+ } else {
+ I = J++;
+ }
+ }
- if (C.first.getLow() != C.first.getHigh())
- // A range counts double, since it requires two compares.
- ++numCmps;
+ for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) {
+ if (I->Low != I->High)
+ // A range counts double, since it requires two compares.
+ ++numCmps;
}
return numCmps;
}
void SelectionDAGBuilder::visitGetElementPtr(const User &I) {
- SDValue N = getValue(I.getOperand(0));
+ Value *Op0 = I.getOperand(0);
// Note that the pointer operand may be a vector of pointers. Take the scalar
// element which holds a pointer.
- Type *Ty = I.getOperand(0)->getType()->getScalarType();
+ Type *Ty = Op0->getType()->getScalarType();
+ unsigned AS = Ty->getPointerAddressSpace();
+ SDValue N = getValue(Op0);
for (GetElementPtrInst::const_op_iterator OI = I.op_begin()+1, E = I.op_end();
OI != E; ++OI) {
uint64_t Offs =
TD->getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
SDValue OffsVal;
- EVT PTy = TLI->getPointerTy();
+ EVT PTy = TLI->getPointerTy(AS);
unsigned PtrBits = PTy.getSizeInBits();
if (PtrBits < 64)
- OffsVal = DAG.getNode(ISD::TRUNCATE, getCurSDLoc(),
- TLI->getPointerTy(),
+ OffsVal = DAG.getNode(ISD::TRUNCATE, getCurSDLoc(), PTy,
DAG.getConstant(Offs, MVT::i64));
else
- OffsVal = DAG.getIntPtrConstant(Offs);
+ OffsVal = DAG.getConstant(Offs, PTy);
N = DAG.getNode(ISD::ADD, getCurSDLoc(), N.getValueType(), N,
OffsVal);
}
// N = N + Idx * ElementSize;
- APInt ElementSize = APInt(TLI->getPointerTy().getSizeInBits(),
+ APInt ElementSize = APInt(TLI->getPointerSizeInBits(AS),
TD->getTypeAllocSize(Ty));
SDValue IdxN = getValue(Idx);
SDValue CfaArg = DAG.getSExtOrTrunc(getValue(I.getArgOperand(0)), sdl,
TLI->getPointerTy());
SDValue Offset = DAG.getNode(ISD::ADD, sdl,
- TLI->getPointerTy(),
+ CfaArg.getValueType(),
DAG.getNode(ISD::FRAME_TO_ARGS_OFFSET, sdl,
- TLI->getPointerTy()),
+ CfaArg.getValueType()),
CfaArg);
SDValue FA = DAG.getNode(ISD::FRAMEADDR, sdl,
TLI->getPointerTy(),
DAG.getConstant(0, TLI->getPointerTy()));
- setValue(&I, DAG.getNode(ISD::ADD, sdl, TLI->getPointerTy(),
+ setValue(&I, DAG.getNode(ISD::ADD, sdl, FA.getValueType(),
FA, Offset));
return 0;
}
getValue(I.getArgOperand(0))));
return 0;
}
+ case Intrinsic::copysign:
+ setValue(&I, DAG.getNode(ISD::FCOPYSIGN, sdl,
+ getValue(I.getArgOperand(0)).getValueType(),
+ getValue(I.getArgOperand(0)),
+ getValue(I.getArgOperand(1))));
+ return 0;
case Intrinsic::fma:
setValue(&I, DAG.getNode(ISD::FMA, sdl,
getValue(I.getArgOperand(0)).getValueType(),
case Intrinsic::invariant_end:
// Discard region information.
return 0;
+ case Intrinsic::stackprotectorcheck: {
+ // Do not actually emit anything for this basic block. Instead we initialize
+ // the stack protector descriptor and export the guard variable so we can
+ // access it in FinishBasicBlock.
+ const BasicBlock *BB = I.getParent();
+ SPDescriptor.initialize(BB, FuncInfo.MBBMap[BB], I);
+ ExportFromCurrentBlock(SPDescriptor.getGuard());
+
+ // Flush our exports since we are going to process a terminator.
+ (void)getControlRoot();
+ return 0;
+ }
case Intrinsic::donothing:
// ignore
return 0;
return false;
}
+/// visitMemChrCall -- See if we can lower a memchr call into an optimized
+/// form. If so, return true and lower it, otherwise return false and it
+/// will be lowered like a normal call.
+bool SelectionDAGBuilder::visitMemChrCall(const CallInst &I) {
+ // Verify that the prototype makes sense. void *memchr(void *, int, size_t)
+ if (I.getNumArgOperands() != 3)
+ return false;
+
+ const Value *Src = I.getArgOperand(0);
+ const Value *Char = I.getArgOperand(1);
+ const Value *Length = I.getArgOperand(2);
+ if (!Src->getType()->isPointerTy() ||
+ !Char->getType()->isIntegerTy() ||
+ !Length->getType()->isIntegerTy() ||
+ !I.getType()->isPointerTy())
+ return false;
+
+ const TargetSelectionDAGInfo &TSI = DAG.getSelectionDAGInfo();
+ std::pair<SDValue, SDValue> Res =
+ TSI.EmitTargetCodeForMemchr(DAG, getCurSDLoc(), DAG.getRoot(),
+ getValue(Src), getValue(Char), getValue(Length),
+ MachinePointerInfo(Src));
+ if (Res.first.getNode()) {
+ setValue(&I, Res.first);
+ PendingLoads.push_back(Res.second);
+ return true;
+ }
+
+ return false;
+}
+
/// visitStrCpyCall -- See if we can lower a strcpy or stpcpy call into an
/// optimized form. If so, return true and lower it, otherwise return false
/// and it will be lowered like a normal call.
return false;
}
+/// visitStrLenCall -- See if we can lower a strlen call into an optimized
+/// form. If so, return true and lower it, otherwise return false and it
+/// will be lowered like a normal call.
+bool SelectionDAGBuilder::visitStrLenCall(const CallInst &I) {
+ // Verify that the prototype makes sense. size_t strlen(char *)
+ if (I.getNumArgOperands() != 1)
+ return false;
+
+ const Value *Arg0 = I.getArgOperand(0);
+ if (!Arg0->getType()->isPointerTy() || !I.getType()->isIntegerTy())
+ return false;
+
+ const TargetSelectionDAGInfo &TSI = DAG.getSelectionDAGInfo();
+ std::pair<SDValue, SDValue> Res =
+ TSI.EmitTargetCodeForStrlen(DAG, getCurSDLoc(), DAG.getRoot(),
+ getValue(Arg0), MachinePointerInfo(Arg0));
+ if (Res.first.getNode()) {
+ processIntegerCallValue(I, Res.first, false);
+ PendingLoads.push_back(Res.second);
+ return true;
+ }
+
+ return false;
+}
+
+/// visitStrNLenCall -- See if we can lower a strnlen call into an optimized
+/// form. If so, return true and lower it, otherwise return false and it
+/// will be lowered like a normal call.
+bool SelectionDAGBuilder::visitStrNLenCall(const CallInst &I) {
+ // Verify that the prototype makes sense. size_t strnlen(char *, size_t)
+ if (I.getNumArgOperands() != 2)
+ return false;
+
+ const Value *Arg0 = I.getArgOperand(0), *Arg1 = I.getArgOperand(1);
+ if (!Arg0->getType()->isPointerTy() ||
+ !Arg1->getType()->isIntegerTy() ||
+ !I.getType()->isIntegerTy())
+ return false;
+
+ const TargetSelectionDAGInfo &TSI = DAG.getSelectionDAGInfo();
+ std::pair<SDValue, SDValue> Res =
+ TSI.EmitTargetCodeForStrnlen(DAG, getCurSDLoc(), DAG.getRoot(),
+ getValue(Arg0), getValue(Arg1),
+ MachinePointerInfo(Arg0));
+ if (Res.first.getNode()) {
+ processIntegerCallValue(I, Res.first, false);
+ PendingLoads.push_back(Res.second);
+ return true;
+ }
+
+ return false;
+}
+
/// visitUnaryFloatCall - If a call instruction is a unary floating-point
/// operation (as expected), translate it to an SDNode with the specified opcode
/// and return true.
if (visitMemCmpCall(I))
return;
break;
+ case LibFunc::memchr:
+ if (visitMemChrCall(I))
+ return;
+ break;
case LibFunc::strcpy:
if (visitStrCpyCall(I, false))
return;
if (visitStrCmpCall(I))
return;
break;
+ case LibFunc::strlen:
+ if (visitStrLenCall(I))
+ return;
+ break;
+ case LibFunc::strnlen:
+ if (visitStrNLenCall(I))
+ return;
+ break;
}
}
}
ConstantsOut.clear();
}
+
+/// Add a successor MBB to ParentMBB< creating a new MachineBB for BB if SuccMBB
+/// is 0.
+MachineBasicBlock *
+SelectionDAGBuilder::StackProtectorDescriptor::
+AddSuccessorMBB(const BasicBlock *BB,
+ MachineBasicBlock *ParentMBB,
+ MachineBasicBlock *SuccMBB) {
+ // If SuccBB has not been created yet, create it.
+ if (!SuccMBB) {
+ MachineFunction *MF = ParentMBB->getParent();
+ MachineFunction::iterator BBI = ParentMBB;
+ SuccMBB = MF->CreateMachineBasicBlock(BB);
+ MF->insert(++BBI, SuccMBB);
+ }
+ // Add it as a successor of ParentMBB.
+ ParentMBB->addSuccessor(SuccMBB);
+ return SuccMBB;
+}