diff options
Diffstat (limited to 'llvm/lib')
-rw-r--r-- | llvm/lib/Bitcode/Reader/BitcodeReader.cpp | 27 | ||||
-rw-r--r-- | llvm/lib/Bitcode/Writer/BitcodeWriter.cpp | 115 | ||||
-rw-r--r-- | llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp | 78 | ||||
-rw-r--r-- | llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h | 11 | ||||
-rw-r--r-- | llvm/lib/ExecutionEngine/Interpreter/Execution.cpp | 37 | ||||
-rw-r--r-- | llvm/lib/IR/Instructions.cpp | 30 | ||||
-rw-r--r-- | llvm/lib/IR/Verifier.cpp | 25 | ||||
-rw-r--r-- | llvm/lib/Target/CppBackend/CPPBackend.cpp | 2 | ||||
-rw-r--r-- | llvm/lib/Transforms/Instrumentation/DebugIR.cpp | 1 | ||||
-rw-r--r-- | llvm/lib/Transforms/Utils/CodeExtractor.cpp | 3 | ||||
-rw-r--r-- | llvm/lib/Transforms/Utils/Local.cpp | 45 | ||||
-rw-r--r-- | llvm/lib/Transforms/Utils/LowerSwitch.cpp | 62 |
12 files changed, 167 insertions, 269 deletions
diff --git a/llvm/lib/Bitcode/Reader/BitcodeReader.cpp b/llvm/lib/Bitcode/Reader/BitcodeReader.cpp index b77c3489baf..3ac6e038fda 100644 --- a/llvm/lib/Bitcode/Reader/BitcodeReader.cpp +++ b/llvm/lib/Bitcode/Reader/BitcodeReader.cpp @@ -2491,7 +2491,10 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { case bitc::FUNC_CODE_INST_SWITCH: { // SWITCH: [opty, op0, op1, ...] // Check magic if ((Record[0] >> 16) == SWITCH_INST_MAGIC) { - // New SwitchInst format with case ranges. + // "New" SwitchInst format with case ranges. The changes to write this + // format were reverted but we still recognize bitcode that uses it. + // Hopefully someday we will have support for case ranges and can use + // this format again. Type *OpTy = getTypeByID(Record[1]); unsigned ValueBitWidth = cast<IntegerType>(OpTy)->getBitWidth(); @@ -2508,7 +2511,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { unsigned CurIdx = 5; for (unsigned i = 0; i != NumCases; ++i) { - IntegersSubsetToBB CaseBuilder; + SmallVector<ConstantInt*, 1> CaseVals; unsigned NumItems = Record[CurIdx++]; for (unsigned ci = 0; ci != NumItems; ++ci) { bool isSingleNumber = Record[CurIdx++]; @@ -2528,20 +2531,22 @@ bool BitcodeReader::ParseFunctionBody(Function *F) { APInt High = ReadWideAPInt(makeArrayRef(&Record[CurIdx], ActiveWords), ValueBitWidth); - - CaseBuilder.add(IntItem::fromType(OpTy, Low), - IntItem::fromType(OpTy, High)); CurIdx += ActiveWords; + + // FIXME: It is not clear whether values in the range should be + // compared as signed or unsigned values. The partially + // implemented changes that used this format in the past used + // unsigned comparisons. + for ( ; Low.ule(High); ++Low) + CaseVals.push_back(ConstantInt::get(Context, Low)); } else - CaseBuilder.add(IntItem::fromType(OpTy, Low)); + CaseVals.push_back(ConstantInt::get(Context, Low)); } BasicBlock *DestBB = getBasicBlock(Record[CurIdx++]); - IntegersSubset Case = CaseBuilder.getCase(); - SI->addCase(Case, DestBB); + for (SmallVector<ConstantInt*, 1>::iterator cvi = CaseVals.begin(), + cve = CaseVals.end(); cvi != cve; ++cvi) + SI->addCase(*cvi, DestBB); } - uint16_t Hash = SI->hash(); - if (Hash != (Record[0] & 0xFFFF)) - return Error("Invalid SWITCH record"); I = SI; break; } diff --git a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp index 0aa919c55be..ed3c267b2dd 100644 --- a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp +++ b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp @@ -60,10 +60,7 @@ enum { FUNCTION_INST_CAST_ABBREV, FUNCTION_INST_RET_VOID_ABBREV, FUNCTION_INST_RET_VAL_ABBREV, - FUNCTION_INST_UNREACHABLE_ABBREV, - - // SwitchInst Magic - SWITCH_INST_MAGIC = 0x4B5 // May 2012 => 1205 => Hex + FUNCTION_INST_UNREACHABLE_ABBREV }; static unsigned GetEncodedCastOpcode(unsigned Opcode) { @@ -865,34 +862,6 @@ static void emitSignedInt64(SmallVectorImpl<uint64_t> &Vals, uint64_t V) { Vals.push_back((-V << 1) | 1); } -static void EmitAPInt(SmallVectorImpl<uint64_t> &Vals, - unsigned &Code, unsigned &AbbrevToUse, const APInt &Val, - bool EmitSizeForWideNumbers = false - ) { - if (Val.getBitWidth() <= 64) { - uint64_t V = Val.getSExtValue(); - emitSignedInt64(Vals, V); - Code = bitc::CST_CODE_INTEGER; - AbbrevToUse = CONSTANTS_INTEGER_ABBREV; - } else { - // Wide integers, > 64 bits in size. - // We have an arbitrary precision integer value to write whose - // bit width is > 64. However, in canonical unsigned integer - // format it is likely that the high bits are going to be zero. - // So, we only write the number of active words. - unsigned NWords = Val.getActiveWords(); - - if (EmitSizeForWideNumbers) - Vals.push_back(NWords); - - const uint64_t *RawWords = Val.getRawData(); - for (unsigned i = 0; i != NWords; ++i) { - emitSignedInt64(Vals, RawWords[i]); - } - Code = bitc::CST_CODE_WIDE_INTEGER; - } -} - static void WriteConstants(unsigned FirstVal, unsigned LastVal, const ValueEnumerator &VE, BitstreamWriter &Stream, bool isGlobal) { @@ -976,7 +945,23 @@ static void WriteConstants(unsigned FirstVal, unsigned LastVal, } else if (isa<UndefValue>(C)) { Code = bitc::CST_CODE_UNDEF; } else if (const ConstantInt *IV = dyn_cast<ConstantInt>(C)) { - EmitAPInt(Record, Code, AbbrevToUse, IV->getValue()); + if (IV->getBitWidth() <= 64) { + uint64_t V = IV->getSExtValue(); + emitSignedInt64(Record, V); + Code = bitc::CST_CODE_INTEGER; + AbbrevToUse = CONSTANTS_INTEGER_ABBREV; + } else { // Wide integers, > 64 bits in size. + // We have an arbitrary precision integer value to write whose + // bit width is > 64. However, in canonical unsigned integer + // format it is likely that the high bits are going to be zero. + // So, we only write the number of active words. + unsigned NWords = IV->getValue().getActiveWords(); + const uint64_t *RawWords = IV->getValue().getRawData(); + for (unsigned i = 0; i != NWords; ++i) { + emitSignedInt64(Record, RawWords[i]); + } + Code = bitc::CST_CODE_WIDE_INTEGER; + } } else if (const ConstantFP *CFP = dyn_cast<ConstantFP>(C)) { Code = bitc::CST_CODE_FLOAT; Type *Ty = CFP->getType(); @@ -1184,13 +1169,6 @@ static void pushValue(const Value *V, unsigned InstID, Vals.push_back(InstID - ValID); } -static void pushValue64(const Value *V, unsigned InstID, - SmallVectorImpl<uint64_t> &Vals, - ValueEnumerator &VE) { - uint64_t ValID = VE.getValueID(V); - Vals.push_back(InstID - ValID); -} - static void pushValueSigned(const Value *V, unsigned InstID, SmallVectorImpl<uint64_t> &Vals, ValueEnumerator &VE) { @@ -1314,63 +1292,16 @@ static void WriteInstruction(const Instruction &I, unsigned InstID, break; case Instruction::Switch: { - // Redefine Vals, since here we need to use 64 bit values - // explicitly to store large APInt numbers. - SmallVector<uint64_t, 128> Vals64; - Code = bitc::FUNC_CODE_INST_SWITCH; const SwitchInst &SI = cast<SwitchInst>(I); - - uint32_t SwitchRecordHeader = SI.hash() | (SWITCH_INST_MAGIC << 16); - Vals64.push_back(SwitchRecordHeader); - - Vals64.push_back(VE.getTypeID(SI.getCondition()->getType())); - pushValue64(SI.getCondition(), InstID, Vals64, VE); - Vals64.push_back(VE.getValueID(SI.getDefaultDest())); - Vals64.push_back(SI.getNumCases()); + Vals.push_back(VE.getTypeID(SI.getCondition()->getType())); + pushValue(SI.getCondition(), InstID, Vals, VE); + Vals.push_back(VE.getValueID(SI.getDefaultDest())); for (SwitchInst::ConstCaseIt i = SI.case_begin(), e = SI.case_end(); i != e; ++i) { - const IntegersSubset& CaseRanges = i.getCaseValueEx(); - unsigned Code, Abbrev; // will unused. - - if (CaseRanges.isSingleNumber()) { - Vals64.push_back(1/*NumItems = 1*/); - Vals64.push_back(true/*IsSingleNumber = true*/); - EmitAPInt(Vals64, Code, Abbrev, CaseRanges.getSingleNumber(0), true); - } else { - - Vals64.push_back(CaseRanges.getNumItems()); - - if (CaseRanges.isSingleNumbersOnly()) { - for (unsigned ri = 0, rn = CaseRanges.getNumItems(); - ri != rn; ++ri) { - - Vals64.push_back(true/*IsSingleNumber = true*/); - - EmitAPInt(Vals64, Code, Abbrev, - CaseRanges.getSingleNumber(ri), true); - } - } else - for (unsigned ri = 0, rn = CaseRanges.getNumItems(); - ri != rn; ++ri) { - IntegersSubset::Range r = CaseRanges.getItem(ri); - bool IsSingleNumber = CaseRanges.isSingleNumber(ri); - - Vals64.push_back(IsSingleNumber); - - EmitAPInt(Vals64, Code, Abbrev, r.getLow(), true); - if (!IsSingleNumber) - EmitAPInt(Vals64, Code, Abbrev, r.getHigh(), true); - } - } - Vals64.push_back(VE.getValueID(i.getCaseSuccessor())); + Vals.push_back(VE.getValueID(i.getCaseValue())); + Vals.push_back(VE.getValueID(i.getCaseSuccessor())); } - - Stream.EmitRecord(Code, Vals64, AbbrevToUse); - - // Also do expected action - clear external Vals collection: - Vals.clear(); - return; } break; case Instruction::IndirectBr: diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp index 086313b7334..0971e8a926d 100644 --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp @@ -49,7 +49,6 @@ #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" @@ -1618,8 +1617,7 @@ void SelectionDAGBuilder::visitSwitchCase(CaseBlock &CB, } 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(); @@ -1627,9 +1625,9 @@ void SelectionDAGBuilder::visitSwitchCase(CaseBlock &CB, 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)); @@ -2145,7 +2143,7 @@ bool SelectionDAGBuilder::handleSmallSwitchRange(CaseRec& CR, 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; } @@ -2179,7 +2177,7 @@ static inline bool areJTsAllowed(const TargetLowering &TLI) { 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); } @@ -2246,7 +2244,7 @@ bool SelectionDAGBuilder::handleJTSwitchCase(CaseRec &CR, 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; @@ -2420,7 +2418,7 @@ bool SelectionDAGBuilder::handleBTSplitSwitchCase(CaseRec& CR, // 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); @@ -2493,7 +2491,7 @@ bool SelectionDAGBuilder::handleBitTestsSwitchCase(CaseRec& CR, // 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; @@ -2568,12 +2566,7 @@ bool SelectionDAGBuilder::handleBitTestsSwitchCase(CaseRec& CR, /// 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 @@ -2582,27 +2575,40 @@ size_t SelectionDAGBuilder::Clusterify(CaseVector& 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(); + 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++; + } + } - 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)); - - 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; diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h index e995424527d..6463ecaca5a 100644 --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h @@ -182,6 +182,17 @@ private: 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.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; diff --git a/llvm/lib/ExecutionEngine/Interpreter/Execution.cpp b/llvm/lib/ExecutionEngine/Interpreter/Execution.cpp index e02ba15ab10..fb86cb2e782 100644 --- a/llvm/lib/ExecutionEngine/Interpreter/Execution.cpp +++ b/llvm/lib/ExecutionEngine/Interpreter/Execution.cpp @@ -898,40 +898,11 @@ void Interpreter::visitSwitchInst(SwitchInst &I) { // Check to see if any of the cases match... BasicBlock *Dest = 0; for (SwitchInst::CaseIt i = I.case_begin(), e = I.case_end(); i != e; ++i) { - IntegersSubset& Case = i.getCaseValueEx(); - if (Case.isSingleNumber()) { - // FIXME: Currently work with ConstantInt based numbers. - const ConstantInt *CI = Case.getSingleNumber(0).toConstantInt(); - GenericValue Val = getOperandValue(const_cast<ConstantInt*>(CI), SF); - if (executeICMP_EQ(Val, CondVal, ElTy).IntVal != 0) { - Dest = cast<BasicBlock>(i.getCaseSuccessor()); - break; - } + GenericValue CaseVal = getOperandValue(i.getCaseValue(), SF); + if (executeICMP_EQ(CondVal, CaseVal, ElTy).IntVal != 0) { + Dest = cast<BasicBlock>(i.getCaseSuccessor()); + break; } - if (Case.isSingleNumbersOnly()) { - for (unsigned n = 0, en = Case.getNumItems(); n != en; ++n) { - // FIXME: Currently work with ConstantInt based numbers. - const ConstantInt *CI = Case.getSingleNumber(n).toConstantInt(); - GenericValue Val = getOperandValue(const_cast<ConstantInt*>(CI), SF); - if (executeICMP_EQ(Val, CondVal, ElTy).IntVal != 0) { - Dest = cast<BasicBlock>(i.getCaseSuccessor()); - break; - } - } - } else - for (unsigned n = 0, en = Case.getNumItems(); n != en; ++n) { - IntegersSubset::Range r = Case.getItem(n); - // FIXME: Currently work with ConstantInt based numbers. - const ConstantInt *LowCI = r.getLow().toConstantInt(); - const ConstantInt *HighCI = r.getHigh().toConstantInt(); - GenericValue Low = getOperandValue(const_cast<ConstantInt*>(LowCI), SF); - GenericValue High = getOperandValue(const_cast<ConstantInt*>(HighCI), SF); - if (executeICMP_ULE(Low, CondVal, ElTy).IntVal != 0 && - executeICMP_ULE(CondVal, High, ElTy).IntVal != 0) { - Dest = cast<BasicBlock>(i.getCaseSuccessor()); - break; - } - } } if (!Dest) Dest = I.getDefaultDest(); // No cases matched: use default SwitchToNewBasicBlock(Dest, SF); diff --git a/llvm/lib/IR/Instructions.cpp b/llvm/lib/IR/Instructions.cpp index 205cb43e394..37b67825803 100644 --- a/llvm/lib/IR/Instructions.cpp +++ b/llvm/lib/IR/Instructions.cpp @@ -3267,7 +3267,6 @@ SwitchInst::SwitchInst(const SwitchInst &SI) OL[i] = InOL[i]; OL[i+1] = InOL[i+1]; } - TheSubsets = SI.TheSubsets; SubclassOptionalData = SI.SubclassOptionalData; } @@ -3279,16 +3278,6 @@ SwitchInst::~SwitchInst() { /// addCase - Add an entry to the switch instruction... /// void SwitchInst::addCase(ConstantInt *OnVal, BasicBlock *Dest) { - IntegersSubsetToBB Mapping; - - // FIXME: Currently we work with ConstantInt based cases. - // So inititalize IntItem container directly from ConstantInt. - Mapping.add(IntItem::fromConstantInt(OnVal)); - IntegersSubset CaseRanges = Mapping.getCase(); - addCase(CaseRanges, Dest); -} - -void SwitchInst::addCase(IntegersSubset& OnVal, BasicBlock *Dest) { unsigned NewCaseIdx = getNumCases(); unsigned OpNo = NumOperands; if (OpNo+2 > ReservedSpace) @@ -3296,17 +3285,14 @@ void SwitchInst::addCase(IntegersSubset& OnVal, BasicBlock *Dest) { // Initialize some new operands. assert(OpNo+1 < ReservedSpace && "Growing didn't work!"); NumOperands = OpNo+2; - - SubsetsIt TheSubsetsIt = TheSubsets.insert(TheSubsets.end(), OnVal); - - CaseIt Case(this, NewCaseIdx, TheSubsetsIt); - Case.updateCaseValueOperand(OnVal); + CaseIt Case(this, NewCaseIdx); + Case.setValue(OnVal); Case.setSuccessor(Dest); } /// removeCase - This method removes the specified case and its successor /// from the switch instruction. -void SwitchInst::removeCase(CaseIt& i) { +void SwitchInst::removeCase(CaseIt i) { unsigned idx = i.getCaseIndex(); assert(2 + idx*2 < getNumOperands() && "Case index out of range!!!"); @@ -3323,16 +3309,6 @@ void SwitchInst::removeCase(CaseIt& i) { // Nuke the last value. OL[NumOps-2].set(0); OL[NumOps-2+1].set(0); - - // Do the same with TheCases collection: - if (i.SubsetIt != --TheSubsets.end()) { - *i.SubsetIt = TheSubsets.back(); - TheSubsets.pop_back(); - } else { - TheSubsets.pop_back(); - i.SubsetIt = TheSubsets.end(); - } - NumOperands = NumOps-2; } diff --git a/llvm/lib/IR/Verifier.cpp b/llvm/lib/IR/Verifier.cpp index 64b7aaa9a75..d939084052e 100644 --- a/llvm/lib/IR/Verifier.cpp +++ b/llvm/lib/IR/Verifier.cpp @@ -1168,27 +1168,12 @@ void Verifier::visitSwitchInst(SwitchInst &SI) { // Check to make sure that all of the constants in the switch instruction // have the same type as the switched-on value. Type *SwitchTy = SI.getCondition()->getType(); - IntegerType *IntTy = cast<IntegerType>(SwitchTy); - IntegersSubsetToBB Mapping; - std::map<IntegersSubset::Range, unsigned> RangeSetMap; + SmallPtrSet<ConstantInt*, 32> Constants; for (SwitchInst::CaseIt i = SI.case_begin(), e = SI.case_end(); i != e; ++i) { - IntegersSubset CaseRanges = i.getCaseValueEx(); - for (unsigned ri = 0, rie = CaseRanges.getNumItems(); ri < rie; ++ri) { - IntegersSubset::Range r = CaseRanges.getItem(ri); - Assert1(((const APInt&)r.getLow()).getBitWidth() == IntTy->getBitWidth(), - "Switch constants must all be same type as switch value!", &SI); - Assert1(((const APInt&)r.getHigh()).getBitWidth() == IntTy->getBitWidth(), - "Switch constants must all be same type as switch value!", &SI); - Mapping.add(r); - RangeSetMap[r] = i.getCaseIndex(); - } - } - - IntegersSubsetToBB::RangeIterator errItem; - if (!Mapping.verify(errItem)) { - unsigned CaseIndex = RangeSetMap[errItem->first]; - SwitchInst::CaseIt i(&SI, CaseIndex); - Assert2(false, "Duplicate integer as switch case", &SI, i.getCaseValueEx()); + Assert1(i.getCaseValue()->getType() == SwitchTy, + "Switch constants must all be same type as switch value!", &SI); + Assert2(Constants.insert(i.getCaseValue()), + "Duplicate integer as switch case", &SI, i.getCaseValue()); } visitTerminatorInst(SI); diff --git a/llvm/lib/Target/CppBackend/CPPBackend.cpp b/llvm/lib/Target/CppBackend/CPPBackend.cpp index ace4b746db2..6f27af45a14 100644 --- a/llvm/lib/Target/CppBackend/CPPBackend.cpp +++ b/llvm/lib/Target/CppBackend/CPPBackend.cpp @@ -1140,7 +1140,7 @@ void CppWriter::printInstruction(const Instruction *I, nl(Out); for (SwitchInst::ConstCaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i) { - const IntegersSubset CaseVal = i.getCaseValueEx(); + const ConstantInt* CaseVal = i.getCaseValue(); const BasicBlock *BB = i.getCaseSuccessor(); Out << iName << "->addCase(" << getOpName(CaseVal) << ", " diff --git a/llvm/lib/Transforms/Instrumentation/DebugIR.cpp b/llvm/lib/Transforms/Instrumentation/DebugIR.cpp index 651381d88b5..9489bb2556f 100644 --- a/llvm/lib/Transforms/Instrumentation/DebugIR.cpp +++ b/llvm/lib/Transforms/Instrumentation/DebugIR.cpp @@ -25,6 +25,7 @@ #include "llvm/InstVisitor.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Instruction.h" +#include "llvm/IR/LLVMContext.h" #include "llvm/IR/Module.h" #include "llvm/Transforms/Instrumentation.h" #include "llvm/Transforms/Utils/Cloning.h" diff --git a/llvm/lib/Transforms/Utils/CodeExtractor.cpp b/llvm/lib/Transforms/Utils/CodeExtractor.cpp index 82013f95f2d..6f008644369 100644 --- a/llvm/lib/Transforms/Utils/CodeExtractor.cpp +++ b/llvm/lib/Transforms/Utils/CodeExtractor.cpp @@ -665,8 +665,7 @@ emitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, TheSwitch->setCondition(call); TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks)); // Remove redundant case - SwitchInst::CaseIt ToBeRemoved(TheSwitch, NumExitBlocks-1); - TheSwitch->removeCase(ToBeRemoved); + TheSwitch->removeCase(SwitchInst::CaseIt(TheSwitch, NumExitBlocks-1)); break; } } diff --git a/llvm/lib/Transforms/Utils/Local.cpp b/llvm/lib/Transforms/Utils/Local.cpp index f2fac5e9300..8f7314d9ca7 100644 --- a/llvm/lib/Transforms/Utils/Local.cpp +++ b/llvm/lib/Transforms/Utils/Local.cpp @@ -196,33 +196,28 @@ bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions, // Otherwise, we can fold this switch into a conditional branch // instruction if it has only one non-default destination. SwitchInst::CaseIt FirstCase = SI->case_begin(); - IntegersSubset& Case = FirstCase.getCaseValueEx(); - if (Case.isSingleNumber()) { - // FIXME: Currently work with ConstantInt based numbers. - Value *Cond = Builder.CreateICmpEQ(SI->getCondition(), - Case.getSingleNumber(0).toConstantInt(), - "cond"); - - // Insert the new branch. - BranchInst *NewBr = Builder.CreateCondBr(Cond, - FirstCase.getCaseSuccessor(), - SI->getDefaultDest()); - MDNode* MD = SI->getMetadata(LLVMContext::MD_prof); - if (MD && MD->getNumOperands() == 3) { - ConstantInt *SICase = dyn_cast<ConstantInt>(MD->getOperand(2)); - ConstantInt *SIDef = dyn_cast<ConstantInt>(MD->getOperand(1)); - assert(SICase && SIDef); - // The TrueWeight should be the weight for the single case of SI. - NewBr->setMetadata(LLVMContext::MD_prof, - MDBuilder(BB->getContext()). - createBranchWeights(SICase->getValue().getZExtValue(), - SIDef->getValue().getZExtValue())); - } + Value *Cond = Builder.CreateICmpEQ(SI->getCondition(), + FirstCase.getCaseValue(), "cond"); - // Delete the old switch. - SI->eraseFromParent(); - return true; + // Insert the new branch. + BranchInst *NewBr = Builder.CreateCondBr(Cond, + FirstCase.getCaseSuccessor(), + SI->getDefaultDest()); + MDNode* MD = SI->getMetadata(LLVMContext::MD_prof); + if (MD && MD->getNumOperands() == 3) { + ConstantInt *SICase = dyn_cast<ConstantInt>(MD->getOperand(2)); + ConstantInt *SIDef = dyn_cast<ConstantInt>(MD->getOperand(1)); + assert(SICase && SIDef); + // The TrueWeight should be the weight for the single case of SI. + NewBr->setMetadata(LLVMContext::MD_prof, + MDBuilder(BB->getContext()). + createBranchWeights(SICase->getValue().getZExtValue(), + SIDef->getValue().getZExtValue())); } + + // Delete the old switch. + SI->eraseFromParent(); + return true; } return false; } diff --git a/llvm/lib/Transforms/Utils/LowerSwitch.cpp b/llvm/lib/Transforms/Utils/LowerSwitch.cpp index 955b853533b..2d2a8a54a0f 100644 --- a/llvm/lib/Transforms/Utils/LowerSwitch.cpp +++ b/llvm/lib/Transforms/Utils/LowerSwitch.cpp @@ -66,6 +66,18 @@ namespace { BasicBlock* OrigBlock, BasicBlock* Default); unsigned Clusterify(CaseVector& Cases, SwitchInst *SI); }; + + /// The comparison function for sorting the switch case values in the vector. + /// WARNING: Case ranges should be disjoint! + struct CaseCmp { + bool operator () (const LowerSwitch::CaseRange& C1, + const LowerSwitch::CaseRange& C2) { + + const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); + const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); + return CI1->getValue().slt(CI2->getValue()); + } + }; } char LowerSwitch::ID = 0; @@ -147,7 +159,7 @@ BasicBlock* LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, Function::iterator FI = OrigBlock; F->getBasicBlockList().insert(++FI, NewNode); - ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_ULT, + ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT, Val, Pivot.Low, "Pivot"); NewNode->getInstList().push_back(Comp); BranchInst::Create(LBranch, RBranch, Comp, NewNode); @@ -222,34 +234,40 @@ BasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val, // Clusterify - Transform simple list of Cases into list of CaseRange's unsigned LowerSwitch::Clusterify(CaseVector& Cases, SwitchInst *SI) { - - IntegersSubsetToBB TheClusterifier; + unsigned numCmps = 0; // Start with "simple" cases - for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); - i != e; ++i) { - BasicBlock *SuccBB = i.getCaseSuccessor(); - IntegersSubset CaseRanges = i.getCaseValueEx(); - TheClusterifier.add(CaseRanges, SuccBB); - } - - TheClusterifier.optimize(); + for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); i != e; ++i) + Cases.push_back(CaseRange(i.getCaseValue(), i.getCaseValue(), + i.getCaseSuccessor())); - size_t numCmps = 0; - for (IntegersSubsetToBB::RangeIterator i = TheClusterifier.begin(), - e = TheClusterifier.end(); i != e; ++i, ++numCmps) { - IntegersSubsetToBB::Cluster &C = *i; - - // FIXME: Currently work with ConstantInt based numbers. - // Changing it to APInt based is a pretty heavy for this commit. - Cases.push_back(CaseRange(C.first.getLow().toConstantInt(), - C.first.getHigh().toConstantInt(), C.second)); - if (C.first.isSingleNumber()) + std::sort(Cases.begin(), Cases.end(), CaseCmp()); + + // Merge case into clusters + if (Cases.size()>=2) + for (CaseItr I=Cases.begin(), J=llvm::next(Cases.begin()); J!=Cases.end(); ) { + int64_t nextValue = cast<ConstantInt>(J->Low)->getSExtValue(); + int64_t currentValue = cast<ConstantInt>(I->High)->getSExtValue(); + BasicBlock* nextBB = J->BB; + BasicBlock* currentBB = I->BB; + + // If the two neighboring cases go to the same destination, merge them + // into a single case. + if ((nextValue-currentValue==1) && (currentBB == nextBB)) { + I->High = J->High; + J = Cases.erase(J); + } else { + I = J++; + } + } + + for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { + if (I->Low != I->High) // A range counts double, since it requires two compares. ++numCmps; } - return numCmps; + return numCmps; } // processSwitchInst - Replace the specified switch instruction with a sequence |