diff options
Diffstat (limited to 'lib/Analysis/ScalarEvolutionExpander.cpp')
| -rw-r--r-- | lib/Analysis/ScalarEvolutionExpander.cpp | 267 |
1 files changed, 184 insertions, 83 deletions
diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index ca5cf1663b83..e8a95d35482c 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -1,9 +1,8 @@ //===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis ------------===// // -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // @@ -61,12 +60,10 @@ Value *SCEVExpander::ReuseOrCreateCast(Value *V, Type *Ty, // instructions that might be inserted before BIP. if (BasicBlock::iterator(CI) != IP || BIP == IP) { // 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. + // it is being used as an insert point. Ret = CastInst::Create(Op, V, Ty, "", &*IP); Ret->takeName(CI); CI->replaceAllUsesWith(Ret); - CI->setOperand(0, UndefValue::get(V->getType())); break; } Ret = CI; @@ -167,9 +164,11 @@ Value *SCEVExpander::InsertNoopCastOfTo(Value *V, Type *Ty) { } /// InsertBinop - Insert the specified binary operator, doing a small amount -/// of work to avoid inserting an obviously redundant operation. +/// of work to avoid inserting an obviously redundant operation, and hoisting +/// to an outer loop when the opportunity is there and it is safe. Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, - Value *LHS, Value *RHS) { + Value *LHS, Value *RHS, + SCEV::NoWrapFlags Flags, bool IsSafeToHoist) { // Fold a binop with constant operands. if (Constant *CLHS = dyn_cast<Constant>(LHS)) if (Constant *CRHS = dyn_cast<Constant>(RHS)) @@ -188,20 +187,22 @@ Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, if (isa<DbgInfoIntrinsic>(IP)) ScanLimit++; - // Conservatively, do not use any instruction which has any of wrap/exact - // flags installed. - // TODO: Instead of simply disable poison instructions we can be clever - // here and match SCEV to this instruction. - auto canGeneratePoison = [](Instruction *I) { - if (isa<OverflowingBinaryOperator>(I) && - (I->hasNoSignedWrap() || I->hasNoUnsignedWrap())) - return true; + auto canGenerateIncompatiblePoison = [&Flags](Instruction *I) { + // Ensure that no-wrap flags match. + if (isa<OverflowingBinaryOperator>(I)) { + if (I->hasNoSignedWrap() != (Flags & SCEV::FlagNSW)) + return true; + if (I->hasNoUnsignedWrap() != (Flags & SCEV::FlagNUW)) + return true; + } + // Conservatively, do not use any instruction which has any of exact + // flags installed. if (isa<PossiblyExactOperator>(I) && I->isExact()) return true; return false; }; if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS && - IP->getOperand(1) == RHS && !canGeneratePoison(&*IP)) + IP->getOperand(1) == RHS && !canGenerateIncompatiblePoison(&*IP)) return &*IP; if (IP == BlockBegin) break; } @@ -211,19 +212,25 @@ Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, DebugLoc Loc = Builder.GetInsertPoint()->getDebugLoc(); SCEVInsertPointGuard Guard(Builder, this); - // 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; + if (IsSafeToHoist) { + // 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->getTerminator()); + // Ok, move up a level. + Builder.SetInsertPoint(Preheader->getTerminator()); + } } // If we haven't found this binop, insert it. Instruction *BO = cast<Instruction>(Builder.CreateBinOp(Opcode, LHS, RHS)); BO->setDebugLoc(Loc); + if (Flags & SCEV::FlagNUW) + BO->setHasNoUnsignedWrap(); + if (Flags & SCEV::FlagNSW) + BO->setHasNoSignedWrap(); rememberInstruction(BO); return BO; @@ -695,7 +702,7 @@ Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { // Sort by loop. Use a stable sort so that constants follow non-constants and // pointer operands precede non-pointer operands. - std::stable_sort(OpsAndLoops.begin(), OpsAndLoops.end(), LoopCompare(SE.DT)); + llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT)); // Emit instructions to add all the operands. Hoist as much as possible // out of loops, and form meaningful getelementptrs where possible. @@ -735,7 +742,8 @@ Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { // Instead of doing a negate and add, just do a subtract. Value *W = expandCodeFor(SE.getNegativeSCEV(Op), Ty); Sum = InsertNoopCastOfTo(Sum, Ty); - Sum = InsertBinop(Instruction::Sub, Sum, W); + Sum = InsertBinop(Instruction::Sub, Sum, W, SCEV::FlagAnyWrap, + /*IsSafeToHoist*/ true); ++I; } else { // A simple add. @@ -743,7 +751,8 @@ Value *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { Sum = InsertNoopCastOfTo(Sum, Ty); // Canonicalize a constant to the RHS. if (isa<Constant>(Sum)) std::swap(Sum, W); - Sum = InsertBinop(Instruction::Add, Sum, W); + Sum = InsertBinop(Instruction::Add, Sum, W, S->getNoWrapFlags(), + /*IsSafeToHoist*/ true); ++I; } } @@ -762,7 +771,7 @@ Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { OpsAndLoops.push_back(std::make_pair(getRelevantLoop(*I), *I)); // Sort by loop. Use a stable sort so that constants follow non-constants. - std::stable_sort(OpsAndLoops.begin(), OpsAndLoops.end(), LoopCompare(SE.DT)); + llvm::stable_sort(OpsAndLoops, LoopCompare(SE.DT)); // Emit instructions to mul all the operands. Hoist as much as possible // out of loops. @@ -795,9 +804,13 @@ Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { if (Exponent & 1) Result = P; for (uint64_t BinExp = 2; BinExp <= Exponent; BinExp <<= 1) { - P = InsertBinop(Instruction::Mul, P, P); + P = InsertBinop(Instruction::Mul, P, P, SCEV::FlagAnyWrap, + /*IsSafeToHoist*/ true); if (Exponent & BinExp) - Result = Result ? InsertBinop(Instruction::Mul, Result, P) : P; + Result = Result ? InsertBinop(Instruction::Mul, Result, P, + SCEV::FlagAnyWrap, + /*IsSafeToHoist*/ true) + : P; } I = E; @@ -812,7 +825,8 @@ Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { } else if (I->second->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); + Prod = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), Prod, + SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true); ++I; } else { // A simple mul. @@ -824,10 +838,16 @@ Value *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { if (match(W, m_Power2(RHS))) { // Canonicalize Prod*(1<<C) to Prod<<C. assert(!Ty->isVectorTy() && "vector types are not SCEVable"); + auto NWFlags = S->getNoWrapFlags(); + // clear nsw flag if shl will produce poison value. + if (RHS->logBase2() == RHS->getBitWidth() - 1) + NWFlags = ScalarEvolution::clearFlags(NWFlags, SCEV::FlagNSW); Prod = InsertBinop(Instruction::Shl, Prod, - ConstantInt::get(Ty, RHS->logBase2())); + ConstantInt::get(Ty, RHS->logBase2()), NWFlags, + /*IsSafeToHoist*/ true); } else { - Prod = InsertBinop(Instruction::Mul, Prod, W); + Prod = InsertBinop(Instruction::Mul, Prod, W, S->getNoWrapFlags(), + /*IsSafeToHoist*/ true); } } } @@ -843,11 +863,13 @@ Value *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) { const APInt &RHS = SC->getAPInt(); if (RHS.isPowerOf2()) return InsertBinop(Instruction::LShr, LHS, - ConstantInt::get(Ty, RHS.logBase2())); + ConstantInt::get(Ty, RHS.logBase2()), + SCEV::FlagAnyWrap, /*IsSafeToHoist*/ true); } Value *RHS = expandCodeFor(S->getRHS(), Ty); - return InsertBinop(Instruction::UDiv, LHS, RHS); + return InsertBinop(Instruction::UDiv, LHS, RHS, SCEV::FlagAnyWrap, + /*IsSafeToHoist*/ SE.isKnownNonZero(S->getRHS())); } /// Move parts of Base into Rest to leave Base with the minimal @@ -1634,7 +1656,8 @@ Value *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) { for (int i = S->getNumOperands()-2; i >= 0; --i) { // In the case of mixed integer and pointer types, do the // rest of the comparisons as integer. - if (S->getOperand(i)->getType() != Ty) { + Type *OpTy = S->getOperand(i)->getType(); + if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { Ty = SE.getEffectiveSCEVType(Ty); LHS = InsertNoopCastOfTo(LHS, Ty); } @@ -1658,7 +1681,8 @@ Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { for (int i = S->getNumOperands()-2; i >= 0; --i) { // In the case of mixed integer and pointer types, do the // rest of the comparisons as integer. - if (S->getOperand(i)->getType() != Ty) { + Type *OpTy = S->getOperand(i)->getType(); + if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { Ty = SE.getEffectiveSCEVType(Ty); LHS = InsertNoopCastOfTo(LHS, Ty); } @@ -1676,6 +1700,56 @@ Value *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { return LHS; } +Value *SCEVExpander::visitSMinExpr(const SCEVSMinExpr *S) { + Value *LHS = expand(S->getOperand(S->getNumOperands() - 1)); + Type *Ty = LHS->getType(); + for (int i = S->getNumOperands() - 2; i >= 0; --i) { + // In the case of mixed integer and pointer types, do the + // rest of the comparisons as integer. + Type *OpTy = S->getOperand(i)->getType(); + if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { + Ty = SE.getEffectiveSCEVType(Ty); + LHS = InsertNoopCastOfTo(LHS, Ty); + } + Value *RHS = expandCodeFor(S->getOperand(i), Ty); + Value *ICmp = Builder.CreateICmpSLT(LHS, RHS); + rememberInstruction(ICmp); + Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smin"); + rememberInstruction(Sel); + LHS = Sel; + } + // In the case of mixed integer and pointer types, cast the + // final result back to the pointer type. + if (LHS->getType() != S->getType()) + LHS = InsertNoopCastOfTo(LHS, S->getType()); + return LHS; +} + +Value *SCEVExpander::visitUMinExpr(const SCEVUMinExpr *S) { + Value *LHS = expand(S->getOperand(S->getNumOperands() - 1)); + Type *Ty = LHS->getType(); + for (int i = S->getNumOperands() - 2; i >= 0; --i) { + // In the case of mixed integer and pointer types, do the + // rest of the comparisons as integer. + Type *OpTy = S->getOperand(i)->getType(); + if (OpTy->isIntegerTy() != Ty->isIntegerTy()) { + Ty = SE.getEffectiveSCEVType(Ty); + LHS = InsertNoopCastOfTo(LHS, Ty); + } + Value *RHS = expandCodeFor(S->getOperand(i), Ty); + Value *ICmp = Builder.CreateICmpULT(LHS, RHS); + rememberInstruction(ICmp); + Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umin"); + rememberInstruction(Sel); + LHS = Sel; + } + // In the case of mixed integer and pointer types, cast the + // final result back to the pointer type. + if (LHS->getType() != S->getType()) + LHS = InsertNoopCastOfTo(LHS, S->getType()); + return LHS; +} + Value *SCEVExpander::expandCodeFor(const SCEV *SH, Type *Ty, Instruction *IP) { setInsertPoint(IP); @@ -1732,49 +1806,55 @@ Value *SCEVExpander::expand(const SCEV *S) { // Compute an insertion point for this SCEV object. Hoist the instructions // as far out in the loop nest as possible. Instruction *InsertPt = &*Builder.GetInsertPoint(); - for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());; - L = L->getParentLoop()) - if (SE.isLoopInvariant(S, L)) { - if (!L) break; - if (BasicBlock *Preheader = L->getLoopPreheader()) - InsertPt = Preheader->getTerminator(); - else { - // LSR sets the insertion point for AddRec start/step values to the - // block start to simplify value reuse, even though it's an invalid - // position. SCEVExpander must correct for this in all cases. - InsertPt = &*L->getHeader()->getFirstInsertionPt(); - } - } else { - // We can move insertion point only if there is no div or rem operations - // otherwise we are risky to move it over the check for zero denominator. - auto SafeToHoist = [](const SCEV *S) { - return !SCEVExprContains(S, [](const SCEV *S) { - if (const auto *D = dyn_cast<SCEVUDivExpr>(S)) { - if (const auto *SC = dyn_cast<SCEVConstant>(D->getRHS())) - // Division by non-zero constants can be hoisted. - return SC->getValue()->isZero(); - // All other divisions should not be moved as they may be - // divisions by zero and should be kept within the - // conditions of the surrounding loops that guard their - // execution (see PR35406). - return true; - } - return false; - }); - }; - // 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 && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L) && - SafeToHoist(S)) - InsertPt = &*L->getHeader()->getFirstInsertionPt(); - while (InsertPt->getIterator() != Builder.GetInsertPoint() && - (isInsertedInstruction(InsertPt) || - isa<DbgInfoIntrinsic>(InsertPt))) { - InsertPt = &*std::next(InsertPt->getIterator()); + + // We can move insertion point only if there is no div or rem operations + // otherwise we are risky to move it over the check for zero denominator. + auto SafeToHoist = [](const SCEV *S) { + return !SCEVExprContains(S, [](const SCEV *S) { + if (const auto *D = dyn_cast<SCEVUDivExpr>(S)) { + if (const auto *SC = dyn_cast<SCEVConstant>(D->getRHS())) + // Division by non-zero constants can be hoisted. + return SC->getValue()->isZero(); + // All other divisions should not be moved as they may be + // divisions by zero and should be kept within the + // conditions of the surrounding loops that guard their + // execution (see PR35406). + return true; + } + return false; + }); + }; + if (SafeToHoist(S)) { + for (Loop *L = SE.LI.getLoopFor(Builder.GetInsertBlock());; + L = L->getParentLoop()) { + if (SE.isLoopInvariant(S, L)) { + if (!L) break; + if (BasicBlock *Preheader = L->getLoopPreheader()) + InsertPt = Preheader->getTerminator(); + else + // LSR sets the insertion point for AddRec start/step values to the + // block start to simplify value reuse, even though it's an invalid + // position. SCEVExpander must correct for this in all cases. + InsertPt = &*L->getHeader()->getFirstInsertionPt(); + } 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 && SE.hasComputableLoopEvolution(S, L) && !PostIncLoops.count(L)) + InsertPt = &*L->getHeader()->getFirstInsertionPt(); + while (InsertPt->getIterator() != Builder.GetInsertPoint() && + (isInsertedInstruction(InsertPt) || + isa<DbgInfoIntrinsic>(InsertPt))) + InsertPt = &*std::next(InsertPt->getIterator()); + break; } - break; } + } + + // IndVarSimplify sometimes sets the insertion point at the block start, even + // when there are PHIs at that point. We must correct for this. + if (isa<PHINode>(*InsertPt)) + InsertPt = &*InsertPt->getParent()->getFirstInsertionPt(); // Check to see if we already expanded this here. auto I = InsertedExpressions.find(std::make_pair(S, InsertPt)); @@ -2071,10 +2151,13 @@ bool SCEVExpander::isHighCostExpansionHelper( if (auto *UDivExpr = dyn_cast<SCEVUDivExpr>(S)) { // If the divisor is a power of two and the SCEV type fits in a native - // integer, consider the division cheap irrespective of whether it occurs in - // the user code since it can be lowered into a right shift. + // integer (and the LHS not expensive), consider the division cheap + // irrespective of whether it occurs in the user code since it can be + // lowered into a right shift. if (auto *SC = dyn_cast<SCEVConstant>(UDivExpr->getRHS())) if (SC->getAPInt().isPowerOf2()) { + if (isHighCostExpansionHelper(UDivExpr->getLHS(), L, At, Processed)) + return true; const DataLayout &DL = L->getHeader()->getParent()->getParent()->getDataLayout(); unsigned Width = cast<IntegerType>(UDivExpr->getType())->getBitWidth(); @@ -2102,7 +2185,7 @@ bool SCEVExpander::isHighCostExpansionHelper( // HowManyLessThans uses a Max expression whenever the loop is not guarded by // the exit condition. - if (isa<SCEVSMaxExpr>(S) || isa<SCEVUMaxExpr>(S)) + if (isa<SCEVMinMaxExpr>(S)) return true; // Recurse past nary expressions, which commonly occur in the @@ -2339,6 +2422,24 @@ bool isSafeToExpand(const SCEV *S, ScalarEvolution &SE) { bool isSafeToExpandAt(const SCEV *S, const Instruction *InsertionPoint, ScalarEvolution &SE) { - return isSafeToExpand(S, SE) && SE.dominates(S, InsertionPoint->getParent()); + if (!isSafeToExpand(S, SE)) + return false; + // We have to prove that the expanded site of S dominates InsertionPoint. + // This is easy when not in the same block, but hard when S is an instruction + // to be expanded somewhere inside the same block as our insertion point. + // What we really need here is something analogous to an OrderedBasicBlock, + // but for the moment, we paper over the problem by handling two common and + // cheap to check cases. + if (SE.properlyDominates(S, InsertionPoint->getParent())) + return true; + if (SE.dominates(S, InsertionPoint->getParent())) { + if (InsertionPoint->getParent()->getTerminator() == InsertionPoint) + return true; + if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) + for (const Value *V : InsertionPoint->operand_values()) + if (V == U->getValue()) + return true; + } + return false; } } |