X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolutionExpander.cpp;h=62710c5e8b84433cfbca890cc3a434c358f6c909;hb=c8e41c591741b3da1077f7000274ad040bef8002;hp=a03e371daa8ea9aba2f722ca0fbc1ee1cfe3aa26;hpb=7481d07a076420e192f95c22e4866c4aee243c80;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index a03e371daa8..62710c5e8b8 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -34,17 +34,15 @@ Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty, // This function must be called with the builder having a valid insertion // point. It doesn't need to be the actual IP where the uses of the returned // cast will be added, but it must dominate such IP. - // We use this precondition to assert that we can produce a cast that will - // dominate all its uses. In particular, this is crucial for the case - // where the builder's insertion point *is* the point where we were asked - // to put the cast. - // Since we don't know the the builder's insertion point is actually + // We use this precondition to produce a cast that will dominate all its + // uses. In particular, this is crucial for the case where the builder's + // insertion point *is* the point where we were asked to put the cast. + // Since we don't know the builder's insertion point is actually // where the uses will be added (only that it dominates it), we are // not allowed to move it. BasicBlock::iterator BIP = Builder.GetInsertPoint(); - // FIXME: enable once our implementation of dominates is fixed. - // assert(BIP == IP || SE.DT->dominates(IP, BIP)); + Instruction *Ret = NULL; // Check to see if there is already a cast! for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); @@ -60,22 +58,28 @@ Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty, // Create a new cast, and leave the old cast in place in case // it is being used as an insert point. Clear its operand // so that it doesn't hold anything live. - Instruction *NewCI = CastInst::Create(Op, V, Ty, "", IP); - NewCI->takeName(CI); - CI->replaceAllUsesWith(NewCI); + Ret = CastInst::Create(Op, V, Ty, "", IP); + Ret->takeName(CI); + CI->replaceAllUsesWith(Ret); CI->setOperand(0, UndefValue::get(V->getType())); - rememberInstruction(NewCI); - return NewCI; + break; } - rememberInstruction(CI); - return CI; + Ret = CI; + break; } } // Create a new cast. - Instruction *I = CastInst::Create(Op, V, Ty, V->getName(), IP); - rememberInstruction(I); - return I; + if (!Ret) + Ret = CastInst::Create(Op, V, Ty, V->getName(), IP); + + // We assert at the end of the function since IP might point to an + // instruction with different dominance properties than a cast + // (an invoke for example) and not dominate BIP (but the cast does). + assert(SE.DT->dominates(Ret, BIP)); + + rememberInstruction(Ret); + return Ret; } /// InsertNoopCastOfTo - Insert a cast of V to the specified type, @@ -515,8 +519,7 @@ Value *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, Type::getInt8PtrTy(Ty->getContext(), PTy->getAddressSpace())); assert(!isa(V) || - SE.DT->properlyDominates(cast(V), - Builder.GetInsertPoint())); + SE.DT->dominates(cast(V), Builder.GetInsertPoint())); // Expand the operands for a plain byte offset. Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty); @@ -908,7 +911,7 @@ Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV, case Instruction::Add: case Instruction::Sub: { Instruction *OInst = dyn_cast(IncV->getOperand(1)); - if (!OInst || SE.DT->properlyDominates(OInst, InsertPos)) + if (!OInst || SE.DT->dominates(OInst, InsertPos)) return dyn_cast(IncV->getOperand(0)); return NULL; } @@ -920,7 +923,7 @@ Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV, if (isa(*I)) continue; if (Instruction *OInst = dyn_cast(*I)) { - if (!SE.DT->properlyDominates(OInst, InsertPos)) + if (!SE.DT->dominates(OInst, InsertPos)) return NULL; } if (allowScale) { @@ -947,12 +950,13 @@ Instruction *SCEVExpander::getIVIncOperand(Instruction *IncV, /// it available to other uses in this loop. Recursively hoist any operands, /// until we reach a value that dominates InsertPos. bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) { - if (SE.DT->properlyDominates(IncV, InsertPos)) + if (SE.DT->dominates(IncV, InsertPos)) return true; // InsertPos must itself dominate IncV so that IncV's new position satisfies // its existing users. - if (!SE.DT->dominates(InsertPos->getParent(), IncV->getParent())) + if (isa(InsertPos) + || !SE.DT->dominates(InsertPos->getParent(), IncV->getParent())) return false; // Check that the chain of IV operands leading back to Phi can be hoisted. @@ -964,7 +968,7 @@ bool SCEVExpander::hoistIVInc(Instruction *IncV, Instruction *InsertPos) { // IncV is safe to hoist. IVIncs.push_back(IncV); IncV = Oper; - if (SE.DT->properlyDominates(IncV, InsertPos)) + if (SE.DT->dominates(IncV, InsertPos)) break; } for (SmallVectorImpl::reverse_iterator I = IVIncs.rbegin(), @@ -1696,3 +1700,44 @@ unsigned SCEVExpander::replaceCongruentIVs(Loop *L, const DominatorTree *DT, } return NumElim; } + +namespace { +// Search for a SCEV subexpression that is not safe to expand. Any expression +// that may expand to a !isSafeToSpeculativelyExecute value is unsafe, namely +// UDiv expressions. We don't know if the UDiv is derived from an IR divide +// instruction, but the important thing is that we prove the denominator is +// nonzero before expansion. +// +// IVUsers already checks that IV-derived expressions are safe. So this check is +// only needed when the expression includes some subexpression that is not IV +// derived. +// +// Currently, we only allow division by a nonzero constant here. If this is +// inadequate, we could easily allow division by SCEVUnknown by using +// ValueTracking to check isKnownNonZero(). +struct SCEVFindUnsafe { + bool IsUnsafe; + + SCEVFindUnsafe(): IsUnsafe(false) {} + + bool follow(const SCEV *S) { + const SCEVUDivExpr *D = dyn_cast(S); + if (!D) + return true; + const SCEVConstant *SC = dyn_cast(D->getRHS()); + if (SC && !SC->getValue()->isZero()) + return true; + IsUnsafe = true; + return false; + } + bool isDone() const { return IsUnsafe; } +}; +} + +namespace llvm { +bool isSafeToExpand(const SCEV *S) { + SCEVFindUnsafe Search; + visitAll(S, Search); + return !Search.IsUnsafe; +} +}