X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolutionExpander.cpp;h=e55ca53c9505770d9249ecfd0d8e2765a4e18ebe;hb=faa75f6e47350f491a44d5e8773acd9457185d51;hp=e26e9dd8b5ac74bca71339aa90eb5003ef3fd871;hpb=c4f7ec85ecb760fff2b702c6deb06506b968ba4f;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index e26e9dd8b5a..e55ca53c950 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -15,6 +15,7 @@ #include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/IntrinsicInst.h" #include "llvm/LLVMContext.h" #include "llvm/Target/TargetData.h" #include "llvm/ADT/STLExtras.h" @@ -137,6 +138,10 @@ Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, if (IP != BlockBegin) { --IP; for (; ScanLimit; --IP, --ScanLimit) { + // Don't count dbg.value against the ScanLimit, to avoid perturbing the + // generated code. + if (isa(IP)) + ScanLimit++; if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS && IP->getOperand(1) == RHS) return IP; @@ -144,9 +149,28 @@ Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, } } + // Save the original insertion point so we can restore it when we're done. + BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); + BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); + + // Move the insertion point out of as many loops as we can. + while (const Loop *L = SE.LI->getLoopFor(Builder.GetInsertBlock())) { + if (!L->isLoopInvariant(LHS) || !L->isLoopInvariant(RHS)) break; + BasicBlock *Preheader = L->getLoopPreheader(); + if (!Preheader) break; + + // Ok, move up a level. + Builder.SetInsertPoint(Preheader, Preheader->getTerminator()); + } + // If we haven't found this binop, insert it. Value *BO = Builder.CreateBinOp(Opcode, LHS, RHS, "tmp"); rememberInstruction(BO); + + // Restore the original insert point. + if (SaveInsertBB) + restoreInsertPoint(SaveInsertBB, SaveInsertPt); + return BO; } @@ -208,9 +232,7 @@ static bool FactorOutConstant(const SCEV *&S, const SCEVConstant *FC = cast(Factor); if (const SCEVConstant *C = dyn_cast(M->getOperand(0))) if (!C->getValue()->getValue().srem(FC->getValue()->getValue())) { - const SmallVectorImpl &MOperands = M->getOperands(); - SmallVector NewMulOps(MOperands.begin(), - MOperands.end()); + SmallVector NewMulOps(M->op_begin(), M->op_end()); NewMulOps[0] = SE.getConstant(C->getValue()->getValue().sdiv( FC->getValue()->getValue())); @@ -225,9 +247,7 @@ static bool FactorOutConstant(const SCEV *&S, const SCEV *Remainder = SE.getIntegerSCEV(0, SOp->getType()); if (FactorOutConstant(SOp, Remainder, Factor, SE, TD) && Remainder->isZero()) { - const SmallVectorImpl &MOperands = M->getOperands(); - SmallVector NewMulOps(MOperands.begin(), - MOperands.end()); + SmallVector NewMulOps(M->op_begin(), M->op_end()); NewMulOps[i] = SOp; S = SE.getMulExpr(NewMulOps); return true; @@ -273,13 +293,11 @@ static void SimplifyAddOperands(SmallVectorImpl &Ops, SE.getAddExpr(NoAddRecs); // If it returned an add, use the operands. Otherwise it simplified // the sum into a single value, so just use that. + Ops.clear(); if (const SCEVAddExpr *Add = dyn_cast(Sum)) - Ops = Add->getOperands(); - else { - Ops.clear(); - if (!Sum->isZero()) - Ops.push_back(Sum); - } + Ops.insert(Ops.end(), Add->op_begin(), Add->op_end()); + else if (!Sum->isZero()) + Ops.push_back(Sum); // Then append the addrecs. Ops.insert(Ops.end(), AddRecs.begin(), AddRecs.end()); } @@ -486,6 +504,10 @@ Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, if (IP != BlockBegin) { --IP; for (; ScanLimit; --IP, --ScanLimit) { + // Don't count dbg.value against the ScanLimit, to avoid perturbing the + // generated code. + if (isa(IP)) + ScanLimit++; if (IP->getOpcode() == Instruction::GetElementPtr && IP->getOperand(0) == V && IP->getOperand(1) == Idx) return IP; @@ -493,12 +515,56 @@ Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, } } + // Save the original insertion point so we can restore it when we're done. + BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); + BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); + + // Move the insertion point out of as many loops as we can. + while (const Loop *L = SE.LI->getLoopFor(Builder.GetInsertBlock())) { + if (!L->isLoopInvariant(V) || !L->isLoopInvariant(Idx)) break; + BasicBlock *Preheader = L->getLoopPreheader(); + if (!Preheader) break; + + // Ok, move up a level. + Builder.SetInsertPoint(Preheader, Preheader->getTerminator()); + } + // Emit a GEP. Value *GEP = Builder.CreateGEP(V, Idx, "uglygep"); rememberInstruction(GEP); + + // Restore the original insert point. + if (SaveInsertBB) + restoreInsertPoint(SaveInsertBB, SaveInsertPt); + return GEP; } + // Save the original insertion point so we can restore it when we're done. + BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); + BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); + + // Move the insertion point out of as many loops as we can. + while (const Loop *L = SE.LI->getLoopFor(Builder.GetInsertBlock())) { + if (!L->isLoopInvariant(V)) break; + + bool AnyIndexNotLoopInvariant = false; + for (SmallVectorImpl::const_iterator I = GepIndices.begin(), + E = GepIndices.end(); I != E; ++I) + if (!L->isLoopInvariant(*I)) { + AnyIndexNotLoopInvariant = true; + break; + } + if (AnyIndexNotLoopInvariant) + break; + + BasicBlock *Preheader = L->getLoopPreheader(); + if (!Preheader) break; + + // Ok, move up a level. + Builder.SetInsertPoint(Preheader, Preheader->getTerminator()); + } + // Insert a pretty getelementptr. Note that this GEP is not marked inbounds, // because ScalarEvolution may have changed the address arithmetic to // compute a value which is beyond the end of the allocated object. @@ -511,6 +577,11 @@ Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, "scevgep"); Ops.push_back(SE.getUnknown(GEP)); rememberInstruction(GEP); + + // Restore the original insert point. + if (SaveInsertBB) + restoreInsertPoint(SaveInsertBB, SaveInsertPt); + return expand(SE.getAddExpr(Ops)); } @@ -571,8 +642,6 @@ static const Loop *GetRelevantLoop(const SCEV *S, LoopInfo &LI, llvm_unreachable("Unexpected SCEV type!"); } -namespace { - /// LoopCompare - Compare loops by PickMostRelevantLoop. class LoopCompare { DominatorTree &DT; @@ -583,7 +652,7 @@ public: std::pair RHS) const { // Compare loops with PickMostRelevantLoop. if (LHS.first != RHS.first) - return PickMostRelevantLoop(LHS.first, RHS.first, DT) == LHS.first; + return PickMostRelevantLoop(LHS.first, RHS.first, DT) != LHS.first; // If one operand is a non-constant negative and the other is not, // put the non-constant negative on the right so that a sub can @@ -599,8 +668,6 @@ public: } }; -} - Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { const Type *Ty = SE.getEffectiveSCEVType(S->getType()); @@ -654,6 +721,8 @@ Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { // A simple add. Value *W = expandCodeFor(Op, Ty); Sum = InsertNoopCastOfTo(Sum, Ty); + // Canonicalize a constant to the RHS. + if (isa(Sum)) std::swap(Sum, W); Sum = InsertBinop(Instruction::Add, Sum, W); ++I; } @@ -664,24 +733,45 @@ Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { const Type *Ty = SE.getEffectiveSCEVType(S->getType()); - int FirstOp = 0; // Set if we should emit a subtract. - if (const SCEVConstant *SC = dyn_cast(S->getOperand(0))) - if (SC->getValue()->isAllOnesValue()) - FirstOp = 1; - - int i = S->getNumOperands()-2; - Value *V = expandCodeFor(S->getOperand(i+1), Ty); - - // Emit a bunch of multiply instructions - for (; i >= FirstOp; --i) { - Value *W = expandCodeFor(S->getOperand(i), Ty); - V = InsertBinop(Instruction::Mul, V, W); + + // Collect all the mul operands in a loop, along with their associated loops. + // Iterate in reverse so that constants are emitted last, all else equal. + SmallVector, 8> OpsAndLoops; + for (std::reverse_iterator I(S->op_end()), + E(S->op_begin()); I != E; ++I) + OpsAndLoops.push_back(std::make_pair(GetRelevantLoop(*I, *SE.LI, *SE.DT), + *I)); + + // Sort by loop. Use a stable sort so that constants follow non-constants. + std::stable_sort(OpsAndLoops.begin(), OpsAndLoops.end(), LoopCompare(*SE.DT)); + + // Emit instructions to mul all the operands. Hoist as much as possible + // out of loops. + Value *Prod = 0; + for (SmallVectorImpl >::iterator + I = OpsAndLoops.begin(), E = OpsAndLoops.end(); I != E; ) { + const SCEV *Op = I->second; + if (!Prod) { + // This is the first operand. Just expand it. + Prod = expand(Op); + ++I; + } else if (Op->isAllOnesValue()) { + // Instead of doing a multiply by negative one, just do a negate. + Prod = InsertNoopCastOfTo(Prod, Ty); + Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod); + ++I; + } else { + // A simple mul. + Value *W = expandCodeFor(Op, Ty); + Prod = InsertNoopCastOfTo(Prod, Ty); + // Canonicalize a constant to the RHS. + if (isa(Prod)) std::swap(Prod, W); + Prod = InsertBinop(Instruction::Mul, Prod, W); + ++I; + } } - // -1 * ... ---> 0 - ... - if (FirstOp == 1) - V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V); - return V; + return Prod; } Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) { @@ -964,10 +1054,9 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { if (CanonicalIV && SE.getTypeSizeInBits(CanonicalIV->getType()) > SE.getTypeSizeInBits(Ty)) { - const SmallVectorImpl &Ops = S->getOperands(); - SmallVector NewOps(Ops.size()); - for (unsigned i = 0, e = Ops.size(); i != e; ++i) - NewOps[i] = SE.getAnyExtendExpr(Ops[i], CanonicalIV->getType()); + SmallVector NewOps(S->getNumOperands()); + for (unsigned i = 0, e = S->getNumOperands(); i != e; ++i) + NewOps[i] = SE.getAnyExtendExpr(S->op_begin()[i], CanonicalIV->getType()); Value *V = expand(SE.getAddRecExpr(NewOps, S->getLoop())); BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); @@ -982,8 +1071,7 @@ Value *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { // {X,+,F} --> X + {0,+,F} if (!S->getStart()->isZero()) { - const SmallVectorImpl &SOperands = S->getOperands(); - SmallVector NewOps(SOperands.begin(), SOperands.end()); + SmallVector NewOps(S->op_begin(), S->op_end()); NewOps[0] = SE.getIntegerSCEV(0, Ty); const SCEV *Rest = SE.getAddRecExpr(NewOps, L); @@ -1171,14 +1259,27 @@ Value *SCEVExpander::expand(const SCEV *S) { L = L->getParentLoop()) if (S->isLoopInvariant(L)) { if (!L) break; - if (BasicBlock *Preheader = L->getLoopPreheader()) + if (BasicBlock *Preheader = L->getLoopPreheader()) { InsertPt = Preheader->getTerminator(); + BasicBlock::iterator IP = InsertPt; + // Back past any debug info instructions. Sometimes we inserted + // something earlier before debug info but after any real instructions. + // This should behave the same as if debug info was not present. + while (IP != Preheader->begin()) { + --IP; + if (!isa(IP)) + break; + InsertPt = IP; + } + } } else { // If the SCEV is computable at this level, insert it into the header // after the PHIs (and after any other instructions that we've inserted // there) so that it is guaranteed to dominate any user inside the loop. if (L && S->hasComputableLoopEvolution(L) && L != PostIncLoop) InsertPt = L->getHeader()->getFirstNonPHI(); + while (isa(InsertPt)) + InsertPt = llvm::next(BasicBlock::iterator(InsertPt)); while (isInsertedInstruction(InsertPt)) InsertPt = llvm::next(BasicBlock::iterator(InsertPt)); break;