summaryrefslogtreecommitdiffstats
path: root/gnu/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'gnu/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp')
-rw-r--r--gnu/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp115
1 files changed, 94 insertions, 21 deletions
diff --git a/gnu/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/gnu/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
index 28157783daa..8f468ebf894 100644
--- a/gnu/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
+++ b/gnu/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp
@@ -12,22 +12,41 @@
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Scalar/CorrelatedValuePropagation.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LazyValueInfo.h"
+#include "llvm/IR/Attributes.h"
+#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/Constant.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Constants.h"
+#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
+#include "llvm/IR/InstrTypes.h"
+#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
-#include "llvm/IR/Module.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Operator.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
+#include <cassert>
+#include <utility>
+
using namespace llvm;
#define DEBUG_TYPE "correlated-value-propagation"
@@ -41,13 +60,16 @@ STATISTIC(NumDeadCases, "Number of switch cases removed");
STATISTIC(NumSDivs, "Number of sdiv converted to udiv");
STATISTIC(NumAShrs, "Number of ashr converted to lshr");
STATISTIC(NumSRems, "Number of srem converted to urem");
+STATISTIC(NumOverflows, "Number of overflow checks removed");
static cl::opt<bool> DontProcessAdds("cvp-dont-process-adds", cl::init(true));
namespace {
+
class CorrelatedValuePropagation : public FunctionPass {
public:
static char ID;
+
CorrelatedValuePropagation(): FunctionPass(ID) {
initializeCorrelatedValuePropagationPass(*PassRegistry::getPassRegistry());
}
@@ -59,9 +81,11 @@ namespace {
AU.addPreserved<GlobalsAAWrapperPass>();
}
};
-}
+
+} // end anonymous namespace
char CorrelatedValuePropagation::ID = 0;
+
INITIALIZE_PASS_BEGIN(CorrelatedValuePropagation, "correlated-propagation",
"Value Propagation", false, false)
INITIALIZE_PASS_DEPENDENCY(LazyValueInfoWrapperPass)
@@ -302,11 +326,72 @@ static bool processSwitch(SwitchInst *SI, LazyValueInfo *LVI) {
return Changed;
}
+// See if we can prove that the given overflow intrinsic will not overflow.
+static bool willNotOverflow(IntrinsicInst *II, LazyValueInfo *LVI) {
+ using OBO = OverflowingBinaryOperator;
+ auto NoWrap = [&] (Instruction::BinaryOps BinOp, unsigned NoWrapKind) {
+ Value *RHS = II->getOperand(1);
+ ConstantRange RRange = LVI->getConstantRange(RHS, II->getParent(), II);
+ ConstantRange NWRegion = ConstantRange::makeGuaranteedNoWrapRegion(
+ BinOp, RRange, NoWrapKind);
+ // As an optimization, do not compute LRange if we do not need it.
+ if (NWRegion.isEmptySet())
+ return false;
+ Value *LHS = II->getOperand(0);
+ ConstantRange LRange = LVI->getConstantRange(LHS, II->getParent(), II);
+ return NWRegion.contains(LRange);
+ };
+ switch (II->getIntrinsicID()) {
+ default:
+ break;
+ case Intrinsic::uadd_with_overflow:
+ return NoWrap(Instruction::Add, OBO::NoUnsignedWrap);
+ case Intrinsic::sadd_with_overflow:
+ return NoWrap(Instruction::Add, OBO::NoSignedWrap);
+ case Intrinsic::usub_with_overflow:
+ return NoWrap(Instruction::Sub, OBO::NoUnsignedWrap);
+ case Intrinsic::ssub_with_overflow:
+ return NoWrap(Instruction::Sub, OBO::NoSignedWrap);
+ }
+ return false;
+}
+
+static void processOverflowIntrinsic(IntrinsicInst *II) {
+ Value *NewOp = nullptr;
+ switch (II->getIntrinsicID()) {
+ default:
+ llvm_unreachable("Unexpected instruction.");
+ case Intrinsic::uadd_with_overflow:
+ case Intrinsic::sadd_with_overflow:
+ NewOp = BinaryOperator::CreateAdd(II->getOperand(0), II->getOperand(1),
+ II->getName(), II);
+ break;
+ case Intrinsic::usub_with_overflow:
+ case Intrinsic::ssub_with_overflow:
+ NewOp = BinaryOperator::CreateSub(II->getOperand(0), II->getOperand(1),
+ II->getName(), II);
+ break;
+ }
+ ++NumOverflows;
+ IRBuilder<> B(II);
+ Value *NewI = B.CreateInsertValue(UndefValue::get(II->getType()), NewOp, 0);
+ NewI = B.CreateInsertValue(NewI, ConstantInt::getFalse(II->getContext()), 1);
+ II->replaceAllUsesWith(NewI);
+ II->eraseFromParent();
+}
+
/// Infer nonnull attributes for the arguments at the specified callsite.
static bool processCallSite(CallSite CS, LazyValueInfo *LVI) {
SmallVector<unsigned, 4> ArgNos;
unsigned ArgNo = 0;
+ if (auto *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
+ if (willNotOverflow(II, LVI)) {
+ processOverflowIntrinsic(II);
+ return true;
+ }
+ }
+
for (Value *V : CS.args()) {
PointerType *Type = dyn_cast<PointerType>(V->getType());
// Try to mark pointer typed parameters as non-null. We skip the
@@ -335,18 +420,6 @@ static bool processCallSite(CallSite CS, LazyValueInfo *LVI) {
return true;
}
-// Helper function to rewrite srem and sdiv. As a policy choice, we choose not
-// to waste compile time on anything where the operands are local defs. While
-// LVI can sometimes reason about such cases, it's not its primary purpose.
-static bool hasLocalDefs(BinaryOperator *SDI) {
- for (Value *O : SDI->operands()) {
- auto *I = dyn_cast<Instruction>(O);
- if (I && I->getParent() == SDI->getParent())
- return true;
- }
- return false;
-}
-
static bool hasPositiveOperands(BinaryOperator *SDI, LazyValueInfo *LVI) {
Constant *Zero = ConstantInt::get(SDI->getType(), 0);
for (Value *O : SDI->operands()) {
@@ -358,7 +431,7 @@ static bool hasPositiveOperands(BinaryOperator *SDI, LazyValueInfo *LVI) {
}
static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
- if (SDI->getType()->isVectorTy() || hasLocalDefs(SDI) ||
+ if (SDI->getType()->isVectorTy() ||
!hasPositiveOperands(SDI, LVI))
return false;
@@ -376,7 +449,7 @@ static bool processSRem(BinaryOperator *SDI, LazyValueInfo *LVI) {
/// conditions, this can sometimes prove conditions instcombine can't by
/// exploiting range information.
static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
- if (SDI->getType()->isVectorTy() || hasLocalDefs(SDI) ||
+ if (SDI->getType()->isVectorTy() ||
!hasPositiveOperands(SDI, LVI))
return false;
@@ -391,7 +464,7 @@ static bool processSDiv(BinaryOperator *SDI, LazyValueInfo *LVI) {
}
static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
- if (SDI->getType()->isVectorTy() || hasLocalDefs(SDI))
+ if (SDI->getType()->isVectorTy())
return false;
Constant *Zero = ConstantInt::get(SDI->getType(), 0);
@@ -410,12 +483,12 @@ static bool processAShr(BinaryOperator *SDI, LazyValueInfo *LVI) {
}
static bool processAdd(BinaryOperator *AddOp, LazyValueInfo *LVI) {
- typedef OverflowingBinaryOperator OBO;
+ using OBO = OverflowingBinaryOperator;
if (DontProcessAdds)
return false;
- if (AddOp->getType()->isVectorTy() || hasLocalDefs(AddOp))
+ if (AddOp->getType()->isVectorTy())
return false;
bool NSW = AddOp->hasNoSignedWrap();
@@ -492,7 +565,7 @@ static bool runImpl(Function &F, LazyValueInfo *LVI, const SimplifyQuery &SQ) {
// blocks before querying later blocks (which require us to analyze early
// blocks). Eagerly simplifying shallow blocks means there is strictly less
// work to do for deep blocks. This also means we don't visit unreachable
- // blocks.
+ // blocks.
for (BasicBlock *BB : depth_first(&F.getEntryBlock())) {
bool BBChanged = false;
for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
Copyright © 1996 – 2023 Jason A. Donenfeld. All Rights Reverse Engineered.