-bool LoopStrengthReduce::FindIVUserForCond(ICmpInst *Cond, IVStrideUse *&CondUse,
- const SCEVHandle *&CondStride) {
- for (unsigned Stride = 0, e = IU->StrideOrder.size();
- Stride != e && !CondUse; ++Stride) {
- std::map<SCEVHandle, IVUsersOfOneStride *>::iterator SI =
- IU->IVUsesByStride.find(IU->StrideOrder[Stride]);
- assert(SI != IU->IVUsesByStride.end() && "Stride doesn't exist!");
-
- for (ilist<IVStrideUse>::iterator UI = SI->second->Users.begin(),
- E = SI->second->Users.end(); UI != E; ++UI)
- if (UI->getUser() == Cond) {
- // NOTE: we could handle setcc instructions with multiple uses here, but
- // InstCombine does it as well for simple uses, it's not clear that it
- // occurs enough in real life to handle.
- CondUse = UI;
- CondStride = &SI->first;
- return true;
- }
- }
- return false;
-}
-
-namespace {
- // Constant strides come first which in turns are sorted by their absolute
- // values. If absolute values are the same, then positive strides comes first.
- // e.g.
- // 4, -1, X, 1, 2 ==> 1, -1, 2, 4, X
- struct StrideCompare {
- const ScalarEvolution *SE;
- explicit StrideCompare(const ScalarEvolution *se) : SE(se) {}
-
- bool operator()(const SCEVHandle &LHS, const SCEVHandle &RHS) {
- const SCEVConstant *LHSC = dyn_cast<SCEVConstant>(LHS);
- const SCEVConstant *RHSC = dyn_cast<SCEVConstant>(RHS);
- if (LHSC && RHSC) {
- int64_t LV = LHSC->getValue()->getSExtValue();
- int64_t RV = RHSC->getValue()->getSExtValue();
- uint64_t ALV = (LV < 0) ? -LV : LV;
- uint64_t ARV = (RV < 0) ? -RV : RV;
- if (ALV == ARV) {
- if (LV != RV)
- return LV > RV;
- } else {
- return ALV < ARV;
- }
-
- // If it's the same value but different type, sort by bit width so
- // that we emit larger induction variables before smaller
- // ones, letting the smaller be re-written in terms of larger ones.
- return SE->getTypeSizeInBits(RHS->getType()) <
- SE->getTypeSizeInBits(LHS->getType());
- }
- return LHSC && !RHSC;
- }
- };
-}
-
-/// ChangeCompareStride - If a loop termination compare instruction is the
-/// only use of its stride, and the compaison is against a constant value,
-/// try eliminate the stride by moving the compare instruction to another
-/// stride and change its constant operand accordingly. e.g.
-///
-/// loop:
-/// ...
-/// v1 = v1 + 3
-/// v2 = v2 + 1
-/// if (v2 < 10) goto loop
-/// =>
-/// loop:
-/// ...
-/// v1 = v1 + 3
-/// if (v1 < 30) goto loop
-ICmpInst *LoopStrengthReduce::ChangeCompareStride(Loop *L, ICmpInst *Cond,
- IVStrideUse* &CondUse,
- const SCEVHandle* &CondStride) {
- // If there's only one stride in the loop, there's nothing to do here.
- if (IU->StrideOrder.size() < 2)
- return Cond;
- // If there are other users of the condition's stride, don't bother
- // trying to change the condition because the stride will still
- // remain.
- std::map<SCEVHandle, IVUsersOfOneStride *>::iterator I =
- IU->IVUsesByStride.find(*CondStride);
- if (I == IU->IVUsesByStride.end() ||
- I->second->Users.size() != 1)
- return Cond;
- // Only handle constant strides for now.
- const SCEVConstant *SC = dyn_cast<SCEVConstant>(*CondStride);
- if (!SC) return Cond;
-
- ICmpInst::Predicate Predicate = Cond->getPredicate();
- int64_t CmpSSInt = SC->getValue()->getSExtValue();
- unsigned BitWidth = SE->getTypeSizeInBits((*CondStride)->getType());
- uint64_t SignBit = 1ULL << (BitWidth-1);
- const Type *CmpTy = Cond->getOperand(0)->getType();
- const Type *NewCmpTy = NULL;
- unsigned TyBits = SE->getTypeSizeInBits(CmpTy);
- unsigned NewTyBits = 0;
- SCEVHandle *NewStride = NULL;
- Value *NewCmpLHS = NULL;
- Value *NewCmpRHS = NULL;
- int64_t Scale = 1;
- SCEVHandle NewOffset = SE->getIntegerSCEV(0, CmpTy);
-
- if (ConstantInt *C = dyn_cast<ConstantInt>(Cond->getOperand(1))) {
- int64_t CmpVal = C->getValue().getSExtValue();
-
- // Check stride constant and the comparision constant signs to detect
- // overflow.
- if ((CmpVal & SignBit) != (CmpSSInt & SignBit))
- return Cond;
-
- // Look for a suitable stride / iv as replacement.
- for (unsigned i = 0, e = IU->StrideOrder.size(); i != e; ++i) {
- std::map<SCEVHandle, IVUsersOfOneStride *>::iterator SI =
- IU->IVUsesByStride.find(IU->StrideOrder[i]);
- if (!isa<SCEVConstant>(SI->first))
- continue;
- int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue();
- if (SSInt == CmpSSInt ||
- abs64(SSInt) < abs64(CmpSSInt) ||
- (SSInt % CmpSSInt) != 0)
- continue;
-
- Scale = SSInt / CmpSSInt;
- int64_t NewCmpVal = CmpVal * Scale;
- APInt Mul = APInt(BitWidth*2, CmpVal, true);
- Mul = Mul * APInt(BitWidth*2, Scale, true);
- // Check for overflow.
- if (!Mul.isSignedIntN(BitWidth))
- continue;
- // Check for overflow in the stride's type too.
- if (!Mul.isSignedIntN(SE->getTypeSizeInBits(SI->first->getType())))
- continue;
-
- // Watch out for overflow.
- if (ICmpInst::isSignedPredicate(Predicate) &&
- (CmpVal & SignBit) != (NewCmpVal & SignBit))
- continue;
-
- if (NewCmpVal == CmpVal)
- continue;
- // Pick the best iv to use trying to avoid a cast.
- NewCmpLHS = NULL;
- for (ilist<IVStrideUse>::iterator UI = SI->second->Users.begin(),
- E = SI->second->Users.end(); UI != E; ++UI) {
- Value *Op = UI->getOperandValToReplace();
-
- // If the IVStrideUse implies a cast, check for an actual cast which
- // can be used to find the original IV expression.
- if (SE->getEffectiveSCEVType(Op->getType()) !=
- SE->getEffectiveSCEVType(SI->first->getType())) {
- CastInst *CI = dyn_cast<CastInst>(Op);
- // If it's not a simple cast, it's complicated.
- if (!CI)
- continue;
- // If it's a cast from a type other than the stride type,
- // it's complicated.
- if (CI->getOperand(0)->getType() != SI->first->getType())
- continue;
- // Ok, we found the IV expression in the stride's type.
- Op = CI->getOperand(0);
- }
-
- NewCmpLHS = Op;
- if (NewCmpLHS->getType() == CmpTy)
- break;
- }
- if (!NewCmpLHS)
- continue;
-
- NewCmpTy = NewCmpLHS->getType();
- NewTyBits = SE->getTypeSizeInBits(NewCmpTy);
- const Type *NewCmpIntTy = IntegerType::get(NewTyBits);
- if (RequiresTypeConversion(NewCmpTy, CmpTy)) {
- // Check if it is possible to rewrite it using
- // an iv / stride of a smaller integer type.
- unsigned Bits = NewTyBits;
- if (ICmpInst::isSignedPredicate(Predicate))
- --Bits;
- uint64_t Mask = (1ULL << Bits) - 1;
- if (((uint64_t)NewCmpVal & Mask) != (uint64_t)NewCmpVal)
- continue;
- }
-
- // Don't rewrite if use offset is non-constant and the new type is
- // of a different type.
- // FIXME: too conservative?
- if (NewTyBits != TyBits && !isa<SCEVConstant>(CondUse->getOffset()))
- continue;
-
- bool AllUsesAreAddresses = true;
- bool AllUsesAreOutsideLoop = true;
- std::vector<BasedUser> UsersToProcess;
- SCEVHandle CommonExprs = CollectIVUsers(SI->first, *SI->second, L,
- AllUsesAreAddresses,
- AllUsesAreOutsideLoop,
- UsersToProcess);
- // Avoid rewriting the compare instruction with an iv of new stride
- // if it's likely the new stride uses will be rewritten using the
- // stride of the compare instruction.
- if (AllUsesAreAddresses &&
- ValidScale(!CommonExprs->isZero(), Scale, UsersToProcess))
- continue;
-
- // Avoid rewriting the compare instruction with an iv which has
- // implicit extension or truncation built into it.
- // TODO: This is over-conservative.
- if (SE->getTypeSizeInBits(CondUse->getOffset()->getType()) != TyBits)
- continue;
-
- // If scale is negative, use swapped predicate unless it's testing
- // for equality.
- if (Scale < 0 && !Cond->isEquality())
- Predicate = ICmpInst::getSwappedPredicate(Predicate);
-
- NewStride = &IU->StrideOrder[i];
- if (!isa<PointerType>(NewCmpTy))
- NewCmpRHS = ConstantInt::get(NewCmpTy, NewCmpVal);
- else {
- Constant *CI = ConstantInt::get(NewCmpIntTy, NewCmpVal);
- NewCmpRHS = ConstantExpr::getIntToPtr(CI, NewCmpTy);
- }
- NewOffset = TyBits == NewTyBits
- ? SE->getMulExpr(CondUse->getOffset(),
- SE->getConstant(CmpTy, Scale))
- : SE->getConstant(NewCmpIntTy,
- cast<SCEVConstant>(CondUse->getOffset())->getValue()
- ->getSExtValue()*Scale);
- break;