aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/llvm/Analysis/ValueTracking.h21
-rw-r--r--include/llvm/Instruction.h20
-rw-r--r--lib/Analysis/LoopInfo.cpp3
-rw-r--r--lib/Analysis/PHITransAddr.cpp7
-rw-r--r--lib/Analysis/ValueTracking.cpp61
-rw-r--r--lib/CodeGen/Analysis.cpp5
-rw-r--r--lib/Transforms/Scalar/LICM.cpp3
-rw-r--r--lib/Transforms/Scalar/Sink.cpp3
-rw-r--r--lib/Transforms/Utils/SimplifyCFG.cpp4
-rw-r--r--lib/VMCore/Instruction.cpp53
-rw-r--r--test/Transforms/LICM/speculate.ll167
11 files changed, 264 insertions, 83 deletions
diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h
index 6f82b2cd98..85c659c631 100644
--- a/include/llvm/Analysis/ValueTracking.h
+++ b/include/llvm/Analysis/ValueTracking.h
@@ -156,6 +156,27 @@ namespace llvm {
/// are lifetime markers.
bool onlyUsedByLifetimeMarkers(const Value *V);
+ /// isSafeToSpeculativelyExecute - Return true if the instruction does not
+ /// have any effects besides calculating the result and does not have
+ /// undefined behavior.
+ ///
+ /// This method never returns true for an instruction that returns true for
+ /// mayHaveSideEffects; however, this method also does some other checks in
+ /// addition. It checks for undefined behavior, like dividing by zero or
+ /// loading from an invalid pointer (but not for undefined results, like a
+ /// shift with a shift amount larger than the width of the result). It checks
+ /// for malloc and alloca because speculatively executing them might cause a
+ /// memory leak. It also returns false for instructions related to control
+ /// flow, specifically terminators and PHI nodes.
+ ///
+ /// This method only looks at the instruction itself and its operands, so if
+ /// this method returns true, it is safe to move the instruction as long as
+ /// the correct dominance relationships for the operands and users hold.
+ /// However, this method can return true for instructions that read memory;
+ /// for such instructions, moving them may change the resulting value.
+ bool isSafeToSpeculativelyExecute(const Instruction *Inst,
+ const TargetData *TD = 0);
+
} // end namespace llvm
#endif
diff --git a/include/llvm/Instruction.h b/include/llvm/Instruction.h
index 38973b7177..9c5ac4430f 100644
--- a/include/llvm/Instruction.h
+++ b/include/llvm/Instruction.h
@@ -244,26 +244,6 @@ public:
return mayWriteToMemory() || mayThrow();
}
- /// isSafeToSpeculativelyExecute - Return true if the instruction does not
- /// have any effects besides calculating the result and does not have
- /// undefined behavior.
- ///
- /// This method never returns true for an instruction that returns true for
- /// mayHaveSideEffects; however, this method also does some other checks in
- /// addition. It checks for undefined behavior, like dividing by zero or
- /// loading from an invalid pointer (but not for undefined results, like a
- /// shift with a shift amount larger than the width of the result). It checks
- /// for malloc and alloca because speculatively executing them might cause a
- /// memory leak. It also returns false for instructions related to control
- /// flow, specifically terminators and PHI nodes.
- ///
- /// This method only looks at the instruction itself and its operands, so if
- /// this method returns true, it is safe to move the instruction as long as
- /// the correct dominance relationships for the operands and users hold.
- /// However, this method can return true for instructions that read memory;
- /// for such instructions, moving them may change the resulting value.
- bool isSafeToSpeculativelyExecute() const;
-
/// clone() - Create a copy of 'this' instruction that is identical in all
/// ways except the following:
/// * The instruction has no parent
diff --git a/lib/Analysis/LoopInfo.cpp b/lib/Analysis/LoopInfo.cpp
index eb355537f7..858cc642f4 100644
--- a/lib/Analysis/LoopInfo.cpp
+++ b/lib/Analysis/LoopInfo.cpp
@@ -19,6 +19,7 @@
#include "llvm/Instructions.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopIterator.h"
+#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/CommandLine.h"
@@ -95,7 +96,7 @@ bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
// Test if the value is already loop-invariant.
if (isLoopInvariant(I))
return true;
- if (!I->isSafeToSpeculativelyExecute())
+ if (!isSafeToSpeculativelyExecute(I))
return false;
if (I->mayReadFromMemory())
return false;
diff --git a/lib/Analysis/PHITransAddr.cpp b/lib/Analysis/PHITransAddr.cpp
index 86d915ff0a..80ea219cd8 100644
--- a/lib/Analysis/PHITransAddr.cpp
+++ b/lib/Analysis/PHITransAddr.cpp
@@ -12,6 +12,7 @@
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/PHITransAddr.h"
+#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/Analysis/Dominators.h"
@@ -27,7 +28,7 @@ static bool CanPHITrans(Instruction *Inst) {
return true;
if (isa<CastInst>(Inst) &&
- Inst->isSafeToSpeculativelyExecute())
+ isSafeToSpeculativelyExecute(Inst))
return true;
if (Inst->getOpcode() == Instruction::Add &&
@@ -186,7 +187,7 @@ Value *PHITransAddr::PHITranslateSubExpr(Value *V, BasicBlock *CurBB,
// operands need to be phi translated, and if so, reconstruct it.
if (CastInst *Cast = dyn_cast<CastInst>(Inst)) {
- if (!Cast->isSafeToSpeculativelyExecute()) return 0;
+ if (!isSafeToSpeculativelyExecute(Cast)) return 0;
Value *PHIIn = PHITranslateSubExpr(Cast->getOperand(0), CurBB, PredBB, DT);
if (PHIIn == 0) return 0;
if (PHIIn == Cast->getOperand(0))
@@ -381,7 +382,7 @@ InsertPHITranslatedSubExpr(Value *InVal, BasicBlock *CurBB,
// Handle cast of PHI translatable value.
if (CastInst *Cast = dyn_cast<CastInst>(Inst)) {
- if (!Cast->isSafeToSpeculativelyExecute()) return 0;
+ if (!isSafeToSpeculativelyExecute(Cast)) return 0;
Value *OpVal = InsertPHITranslatedSubExpr(Cast->getOperand(0),
CurBB, PredBB, DT, NewInsts);
if (OpVal == 0) return 0;
diff --git a/lib/Analysis/ValueTracking.cpp b/lib/Analysis/ValueTracking.cpp
index ecc83dfceb..ef19e065b7 100644
--- a/lib/Analysis/ValueTracking.cpp
+++ b/lib/Analysis/ValueTracking.cpp
@@ -1875,3 +1875,64 @@ bool llvm::onlyUsedByLifetimeMarkers(const Value *V) {
}
return true;
}
+
+bool llvm::isSafeToSpeculativelyExecute(const Instruction *Inst,
+ const TargetData *TD) {
+ for (unsigned i = 0, e = Inst->getNumOperands(); i != e; ++i)
+ if (Constant *C = dyn_cast<Constant>(Inst->getOperand(i)))
+ if (C->canTrap())
+ return false;
+
+ switch (Inst->getOpcode()) {
+ default:
+ return true;
+ case Instruction::UDiv:
+ case Instruction::URem:
+ // x / y is undefined if y == 0, but calcuations like x / 3 are safe.
+ return isKnownNonZero(Inst->getOperand(1), TD);
+ case Instruction::SDiv:
+ case Instruction::SRem: {
+ Value *Op = Inst->getOperand(1);
+ // x / y is undefined if y == 0
+ if (!isKnownNonZero(Op, TD))
+ return false;
+ // x / y might be undefined if y == -1
+ unsigned BitWidth = getBitWidth(Op->getType(), TD);
+ if (BitWidth == 0)
+ return false;
+ APInt KnownZero(BitWidth, 0);
+ APInt KnownOne(BitWidth, 0);
+ ComputeMaskedBits(Op, APInt::getAllOnesValue(BitWidth),
+ KnownZero, KnownOne, TD);
+ return !!KnownZero;
+ }
+ case Instruction::Load: {
+ const LoadInst *LI = cast<LoadInst>(Inst);
+ if (!LI->isUnordered())
+ return false;
+ return LI->getPointerOperand()->isDereferenceablePointer();
+ }
+ case Instruction::Call:
+ return false; // The called function could have undefined behavior or
+ // side-effects.
+ // FIXME: We should special-case some intrinsics (bswap,
+ // overflow-checking arithmetic, etc.)
+ case Instruction::VAArg:
+ case Instruction::Alloca:
+ case Instruction::Invoke:
+ case Instruction::PHI:
+ case Instruction::Store:
+ case Instruction::Ret:
+ case Instruction::Br:
+ case Instruction::IndirectBr:
+ case Instruction::Switch:
+ case Instruction::Unwind:
+ case Instruction::Unreachable:
+ case Instruction::Fence:
+ case Instruction::LandingPad:
+ case Instruction::AtomicRMW:
+ case Instruction::AtomicCmpXchg:
+ case Instruction::Resume:
+ return false; // Misc instructions which have effects
+ }
+}
diff --git a/lib/CodeGen/Analysis.cpp b/lib/CodeGen/Analysis.cpp
index fc28b21194..0c84be5fab 100644
--- a/lib/CodeGen/Analysis.cpp
+++ b/lib/CodeGen/Analysis.cpp
@@ -12,6 +12,7 @@
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/Analysis.h"
+#include "llvm/Analysis/ValueTracking.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
@@ -234,7 +235,7 @@ bool llvm::isInTailCallPosition(ImmutableCallSite CS, Attributes CalleeRetAttr,
// If I will have a chain, make sure no other instruction that will have a
// chain interposes between I and the return.
if (I->mayHaveSideEffects() || I->mayReadFromMemory() ||
- !I->isSafeToSpeculativelyExecute())
+ !isSafeToSpeculativelyExecute(I))
for (BasicBlock::const_iterator BBI = prior(prior(ExitBB->end())); ;
--BBI) {
if (&*BBI == I)
@@ -243,7 +244,7 @@ bool llvm::isInTailCallPosition(ImmutableCallSite CS, Attributes CalleeRetAttr,
if (isa<DbgInfoIntrinsic>(BBI))
continue;
if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() ||
- !BBI->isSafeToSpeculativelyExecute())
+ !isSafeToSpeculativelyExecute(BBI))
return false;
}
diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp
index 65d8c6bc30..8795cd853f 100644
--- a/lib/Transforms/Scalar/LICM.cpp
+++ b/lib/Transforms/Scalar/LICM.cpp
@@ -43,6 +43,7 @@
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include "llvm/Target/TargetData.h"
@@ -591,7 +592,7 @@ void LICM::hoist(Instruction &I) {
///
bool LICM::isSafeToExecuteUnconditionally(Instruction &Inst) {
// If it is not a trapping instruction, it is always safe to hoist.
- if (Inst.isSafeToSpeculativelyExecute())
+ if (isSafeToSpeculativelyExecute(&Inst))
return true;
return isGuaranteedToExecute(Inst);
diff --git a/lib/Transforms/Scalar/Sink.cpp b/lib/Transforms/Scalar/Sink.cpp
index c83f56c4d2..ef65c0a3a9 100644
--- a/lib/Transforms/Scalar/Sink.cpp
+++ b/lib/Transforms/Scalar/Sink.cpp
@@ -18,6 +18,7 @@
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/CFG.h"
@@ -240,7 +241,7 @@ bool Sinking::SinkInstruction(Instruction *Inst,
if (SuccToSinkTo->getUniquePredecessor() != ParentBlock) {
// We cannot sink a load across a critical edge - there may be stores in
// other code paths.
- if (!Inst->isSafeToSpeculativelyExecute()) {
+ if (!isSafeToSpeculativelyExecute(Inst)) {
DEBUG(dbgs() << " *** PUNTING: Wont sink load along critical edge.\n");
return false;
}
diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index b8c3ab4c60..bf2cb49bdc 100644
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -257,7 +257,7 @@ static bool DominatesMergePoint(Value *V, BasicBlock *BB,
// Okay, it looks like the instruction IS in the "condition". Check to
// see if it's a cheap instruction to unconditionally compute, and if it
// only uses stuff defined outside of the condition. If so, hoist it out.
- if (!I->isSafeToSpeculativelyExecute())
+ if (!isSafeToSpeculativelyExecute(I))
return false;
unsigned Cost = 0;
@@ -1487,7 +1487,7 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI) {
Instruction *BonusInst = 0;
if (&*FrontIt != Cond &&
FrontIt->hasOneUse() && *FrontIt->use_begin() == Cond &&
- FrontIt->isSafeToSpeculativelyExecute()) {
+ isSafeToSpeculativelyExecute(FrontIt)) {
BonusInst = &*FrontIt;
++FrontIt;
diff --git a/lib/VMCore/Instruction.cpp b/lib/VMCore/Instruction.cpp
index 73191c1965..8c8fbf9acd 100644
--- a/lib/VMCore/Instruction.cpp
+++ b/lib/VMCore/Instruction.cpp
@@ -391,59 +391,6 @@ bool Instruction::isCommutative(unsigned op) {
}
}
-bool Instruction::isSafeToSpeculativelyExecute() const {
- for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
- if (Constant *C = dyn_cast<Constant>(getOperand(i)))
- if (C->canTrap())
- return false;
-
- switch (getOpcode()) {
- default:
- return true;
- case UDiv:
- case URem: {
- // x / y is undefined if y == 0, but calcuations like x / 3 are safe.
- ConstantInt *Op = dyn_cast<ConstantInt>(getOperand(1));
- return Op && !Op->isNullValue();
- }
- case SDiv:
- case SRem: {
- // x / y is undefined if y == 0, and might be undefined if y == -1,
- // but calcuations like x / 3 are safe.
- ConstantInt *Op = dyn_cast<ConstantInt>(getOperand(1));
- return Op && !Op->isNullValue() && !Op->isAllOnesValue();
- }
- case Load: {
- const LoadInst *LI = cast<LoadInst>(this);
- if (!LI->isUnordered())
- return false;
- return LI->getPointerOperand()->isDereferenceablePointer();
- }
- case Call:
- return false; // The called function could have undefined behavior or
- // side-effects.
- // FIXME: We should special-case some intrinsics (bswap,
- // overflow-checking arithmetic, etc.)
- case VAArg:
- case Alloca:
- case Invoke:
- case PHI:
- case Store:
- case Ret:
- case Br:
- case IndirectBr:
- case Switch:
- case Unwind:
- case Unreachable:
- case Fence:
- case LandingPad:
- case AtomicRMW:
- case AtomicCmpXchg:
- case Resume:
- return false; // Misc instructions which have effects
- }
-}
-
Instruction *Instruction::clone() const {
Instruction *New = clone_impl();
New->SubclassOptionalData = SubclassOptionalData;
diff --git a/test/Transforms/LICM/speculate.ll b/test/Transforms/LICM/speculate.ll
new file mode 100644
index 0000000000..507b193e6b
--- /dev/null
+++ b/test/Transforms/LICM/speculate.ll
@@ -0,0 +1,167 @@
+; RUN: opt -S -licm < %s | FileCheck %s
+
+; UDiv is safe to speculate if the denominator is known non-zero.
+
+; CHECK: @safe_udiv
+; CHECK: %div = udiv i64 %x, %or
+; CHECK-NEXT: br label %for.body
+
+define void @safe_udiv(i64 %x, i64 %m, i64 %n, i32* %p, i64* %q) nounwind {
+entry:
+ %or = or i64 %m, 1
+ br label %for.body
+
+for.body: ; preds = %entry, %for.inc
+ %i.02 = phi i64 [ %inc, %for.inc ], [ 0, %entry ]
+ %arrayidx = getelementptr inbounds i32* %p, i64 %i.02
+ %0 = load i32* %arrayidx, align 4
+ %tobool = icmp eq i32 %0, 0
+ br i1 %tobool, label %for.inc, label %if.then
+
+if.then: ; preds = %for.body
+ %div = udiv i64 %x, %or
+ %arrayidx1 = getelementptr inbounds i64* %q, i64 %i.02
+ store i64 %div, i64* %arrayidx1, align 8
+ br label %for.inc
+
+for.inc: ; preds = %if.then, %for.body
+ %inc = add i64 %i.02, 1
+ %cmp = icmp slt i64 %inc, %n
+ br i1 %cmp, label %for.body, label %for.end
+
+for.end: ; preds = %for.inc, %entry
+ ret void
+}
+
+; UDiv is unsafe to speculate if the denominator is not known non-zero.
+
+; CHECK: @unsafe_udiv
+; CHECK-NOT: udiv
+; CHECK: for.body:
+
+define void @unsafe_udiv(i64 %x, i64 %m, i64 %n, i32* %p, i64* %q) nounwind {
+entry:
+ br label %for.body
+
+for.body: ; preds = %entry, %for.inc
+ %i.02 = phi i64 [ %inc, %for.inc ], [ 0, %entry ]
+ %arrayidx = getelementptr inbounds i32* %p, i64 %i.02
+ %0 = load i32* %arrayidx, align 4
+ %tobool = icmp eq i32 %0, 0
+ br i1 %tobool, label %for.inc, label %if.then
+
+if.then: ; preds = %for.body
+ %div = udiv i64 %x, %m
+ %arrayidx1 = getelementptr inbounds i64* %q, i64 %i.02
+ store i64 %div, i64* %arrayidx1, align 8
+ br label %for.inc
+
+for.inc: ; preds = %if.then, %for.body
+ %inc = add i64 %i.02, 1
+ %cmp = icmp slt i64 %inc, %n
+ br i1 %cmp, label %for.body, label %for.end
+
+for.end: ; preds = %for.inc, %entry
+ ret void
+}
+
+; SDiv is safe to speculate if the denominator is known non-zero and
+; known to have at least one zero bit.
+
+; CHECK: @safe_sdiv
+; CHECK: %div = sdiv i64 %x, %or
+; CHECK-NEXT: br label %for.body
+
+define void @safe_sdiv(i64 %x, i64 %m, i64 %n, i32* %p, i64* %q) nounwind {
+entry:
+ %and = and i64 %m, -3
+ %or = or i64 %and, 1
+ br label %for.body
+
+for.body: ; preds = %entry, %for.inc
+ %i.02 = phi i64 [ %inc, %for.inc ], [ 0, %entry ]
+ %arrayidx = getelementptr inbounds i32* %p, i64 %i.02
+ %0 = load i32* %arrayidx, align 4
+ %tobool = icmp eq i32 %0, 0
+ br i1 %tobool, label %for.inc, label %if.then
+
+if.then: ; preds = %for.body
+ %div = sdiv i64 %x, %or
+ %arrayidx1 = getelementptr inbounds i64* %q, i64 %i.02
+ store i64 %div, i64* %arrayidx1, align 8
+ br label %for.inc
+
+for.inc: ; preds = %if.then, %for.body
+ %inc = add i64 %i.02, 1
+ %cmp = icmp slt i64 %inc, %n
+ br i1 %cmp, label %for.body, label %for.end
+
+for.end: ; preds = %for.inc, %entry
+ ret void
+}
+
+; SDiv is unsafe to speculate if the denominator is not known non-zero.
+
+; CHECK: @unsafe_sdiv_a
+; CHECK-NOT: sdiv
+; CHECK: for.body:
+
+define void @unsafe_sdiv_a(i64 %x, i64 %m, i64 %n, i32* %p, i64* %q) nounwind {
+entry:
+ %or = or i64 %m, 1
+ br label %for.body
+
+for.body: ; preds = %entry, %for.inc
+ %i.02 = phi i64 [ %inc, %for.inc ], [ 0, %entry ]
+ %arrayidx = getelementptr inbounds i32* %p, i64 %i.02
+ %0 = load i32* %arrayidx, align 4
+ %tobool = icmp eq i32 %0, 0
+ br i1 %tobool, label %for.inc, label %if.then
+
+if.then: ; preds = %for.body
+ %div = sdiv i64 %x, %or
+ %arrayidx1 = getelementptr inbounds i64* %q, i64 %i.02
+ store i64 %div, i64* %arrayidx1, align 8
+ br label %for.inc
+
+for.inc: ; preds = %if.then, %for.body
+ %inc = add i64 %i.02, 1
+ %cmp = icmp slt i64 %inc, %n
+ br i1 %cmp, label %for.body, label %for.end
+
+for.end: ; preds = %for.inc, %entry
+ ret void
+}
+
+; SDiv is unsafe to speculate if the denominator is not known to have a zero bit.
+
+; CHECK: @unsafe_sdiv_b
+; CHECK-NOT: sdiv
+; CHECK: for.body:
+
+define void @unsafe_sdiv_b(i64 %x, i64 %m, i64 %n, i32* %p, i64* %q) nounwind {
+entry:
+ %and = and i64 %m, -3
+ br label %for.body
+
+for.body: ; preds = %entry, %for.inc
+ %i.02 = phi i64 [ %inc, %for.inc ], [ 0, %entry ]
+ %arrayidx = getelementptr inbounds i32* %p, i64 %i.02
+ %0 = load i32* %arrayidx, align 4
+ %tobool = icmp eq i32 %0, 0
+ br i1 %tobool, label %for.inc, label %if.then
+
+if.then: ; preds = %for.body
+ %div = sdiv i64 %x, %and
+ %arrayidx1 = getelementptr inbounds i64* %q, i64 %i.02
+ store i64 %div, i64* %arrayidx1, align 8
+ br label %for.inc
+
+for.inc: ; preds = %if.then, %for.body
+ %inc = add i64 %i.02, 1
+ %cmp = icmp slt i64 %inc, %n
+ br i1 %cmp, label %for.body, label %for.end
+
+for.end: ; preds = %for.inc, %entry
+ ret void
+}
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-08-04 18:00:55 +0000