summaryrefslogtreecommitdiffstats
path: root/gnu/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'gnu/llvm/lib/Transforms/Scalar/EarlyCSE.cpp')
-rw-r--r--gnu/llvm/lib/Transforms/Scalar/EarlyCSE.cpp142
1 files changed, 86 insertions, 56 deletions
diff --git a/gnu/llvm/lib/Transforms/Scalar/EarlyCSE.cpp b/gnu/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
index 7ef062e71ff..0b16e2703dc 100644
--- a/gnu/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
+++ b/gnu/llvm/lib/Transforms/Scalar/EarlyCSE.cpp
@@ -16,8 +16,8 @@
#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/ScopedHashTable.h"
#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
@@ -40,6 +40,7 @@ using namespace llvm::PatternMatch;
STATISTIC(NumSimplify, "Number of instructions simplified or DCE'd");
STATISTIC(NumCSE, "Number of instructions CSE'd");
+STATISTIC(NumCSECVP, "Number of compare instructions CVP'd");
STATISTIC(NumCSELoad, "Number of load instructions CSE'd");
STATISTIC(NumCSECall, "Number of call instructions CSE'd");
STATISTIC(NumDSE, "Number of trivial dead stores removed");
@@ -97,15 +98,6 @@ unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {
if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
std::swap(LHS, RHS);
- if (isa<OverflowingBinaryOperator>(BinOp)) {
- // Hash the overflow behavior
- unsigned Overflow =
- BinOp->hasNoSignedWrap() * OverflowingBinaryOperator::NoSignedWrap |
- BinOp->hasNoUnsignedWrap() *
- OverflowingBinaryOperator::NoUnsignedWrap;
- return hash_combine(BinOp->getOpcode(), Overflow, LHS, RHS);
- }
-
return hash_combine(BinOp->getOpcode(), LHS, RHS);
}
@@ -152,7 +144,7 @@ bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
if (LHSI->getOpcode() != RHSI->getOpcode())
return false;
- if (LHSI->isIdenticalTo(RHSI))
+ if (LHSI->isIdenticalToWhenDefined(RHSI))
return true;
// If we're not strictly identical, we still might be a commutable instruction
@@ -164,15 +156,6 @@ bool DenseMapInfo<SimpleValue>::isEqual(SimpleValue LHS, SimpleValue RHS) {
"same opcode, but different instruction type?");
BinaryOperator *RHSBinOp = cast<BinaryOperator>(RHSI);
- // Check overflow attributes
- if (isa<OverflowingBinaryOperator>(LHSBinOp)) {
- assert(isa<OverflowingBinaryOperator>(RHSBinOp) &&
- "same opcode, but different operator type?");
- if (LHSBinOp->hasNoUnsignedWrap() != RHSBinOp->hasNoUnsignedWrap() ||
- LHSBinOp->hasNoSignedWrap() != RHSBinOp->hasNoSignedWrap())
- return false;
- }
-
// Commuted equality
return LHSBinOp->getOperand(0) == RHSBinOp->getOperand(1) &&
LHSBinOp->getOperand(1) == RHSBinOp->getOperand(0);
@@ -296,16 +279,18 @@ public:
/// present the table; it is the responsibility of the consumer to inspect
/// the atomicity/volatility if needed.
struct LoadValue {
- Value *Data;
+ Instruction *DefInst;
unsigned Generation;
int MatchingId;
bool IsAtomic;
+ bool IsInvariant;
LoadValue()
- : Data(nullptr), Generation(0), MatchingId(-1), IsAtomic(false) {}
- LoadValue(Value *Data, unsigned Generation, unsigned MatchingId,
- bool IsAtomic)
- : Data(Data), Generation(Generation), MatchingId(MatchingId),
- IsAtomic(IsAtomic) {}
+ : DefInst(nullptr), Generation(0), MatchingId(-1), IsAtomic(false),
+ IsInvariant(false) {}
+ LoadValue(Instruction *Inst, unsigned Generation, unsigned MatchingId,
+ bool IsAtomic, bool IsInvariant)
+ : DefInst(Inst), Generation(Generation), MatchingId(MatchingId),
+ IsAtomic(IsAtomic), IsInvariant(IsInvariant) {}
};
typedef RecyclingAllocator<BumpPtrAllocator,
ScopedHashTableVal<Value *, LoadValue>>
@@ -318,7 +303,8 @@ public:
/// values.
///
/// It uses the same generation count as loads.
- typedef ScopedHashTable<CallValue, std::pair<Value *, unsigned>> CallHTType;
+ typedef ScopedHashTable<CallValue, std::pair<Instruction *, unsigned>>
+ CallHTType;
CallHTType AvailableCalls;
/// \brief This is the current generation of the memory value.
@@ -354,7 +340,7 @@ private:
// Contains all the needed information to create a stack for doing a depth
// first tranversal of the tree. This includes scopes for values, loads, and
// calls as well as the generation. There is a child iterator so that the
- // children do not need to be store spearately.
+ // children do not need to be store separately.
class StackNode {
public:
StackNode(ScopedHTType &AvailableValues, LoadHTType &AvailableLoads,
@@ -446,7 +432,12 @@ private:
return true;
}
-
+ bool isInvariantLoad() const {
+ if (auto *LI = dyn_cast<LoadInst>(Inst))
+ return LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr;
+ return false;
+ }
+
bool isMatchingMemLoc(const ParseMemoryInst &Inst) const {
return (getPointerOperand() == Inst.getPointerOperand() &&
getMatchingId() == Inst.getMatchingId());
@@ -500,6 +491,7 @@ private:
}
bool EarlyCSE::processNode(DomTreeNode *Node) {
+ bool Changed = false;
BasicBlock *BB = Node->getBlock();
// If this block has a single predecessor, then the predecessor is the parent
@@ -513,7 +505,7 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
// If this node has a single predecessor which ends in a conditional branch,
// we can infer the value of the branch condition given that we took this
- // path. We need the single predeccesor to ensure there's not another path
+ // path. We need the single predecessor to ensure there's not another path
// which reaches this block where the condition might hold a different
// value. Since we're adding this to the scoped hash table (like any other
// def), it will have been popped if we encounter a future merge block.
@@ -530,9 +522,13 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
DEBUG(dbgs() << "EarlyCSE CVP: Add conditional value for '"
<< CondInst->getName() << "' as " << *ConditionalConstant
<< " in " << BB->getName() << "\n");
- // Replace all dominated uses with the known value
- replaceDominatedUsesWith(CondInst, ConditionalConstant, DT,
- BasicBlockEdge(Pred, BB));
+ // Replace all dominated uses with the known value.
+ if (unsigned Count =
+ replaceDominatedUsesWith(CondInst, ConditionalConstant, DT,
+ BasicBlockEdge(Pred, BB))) {
+ Changed = true;
+ NumCSECVP = NumCSECVP + Count;
+ }
}
/// LastStore - Keep track of the last non-volatile store that we saw... for
@@ -541,7 +537,6 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
/// stores which can occur in bitfield code among other things.
Instruction *LastStore = nullptr;
- bool Changed = false;
const DataLayout &DL = BB->getModule()->getDataLayout();
// See if any instructions in the block can be eliminated. If so, do it. If
@@ -567,15 +562,40 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
continue;
}
+ if (match(Inst, m_Intrinsic<Intrinsic::experimental_guard>())) {
+ if (auto *CondI =
+ dyn_cast<Instruction>(cast<CallInst>(Inst)->getArgOperand(0))) {
+ // The condition we're on guarding here is true for all dominated
+ // locations.
+ if (SimpleValue::canHandle(CondI))
+ AvailableValues.insert(CondI, ConstantInt::getTrue(BB->getContext()));
+ }
+
+ // Guard intrinsics read all memory, but don't write any memory.
+ // Accordingly, don't update the generation but consume the last store (to
+ // avoid an incorrect DSE).
+ LastStore = nullptr;
+ continue;
+ }
+
// If the instruction can be simplified (e.g. X+0 = X) then replace it with
// its simpler value.
if (Value *V = SimplifyInstruction(Inst, DL, &TLI, &DT, &AC)) {
DEBUG(dbgs() << "EarlyCSE Simplify: " << *Inst << " to: " << *V << '\n');
- Inst->replaceAllUsesWith(V);
- Inst->eraseFromParent();
- Changed = true;
- ++NumSimplify;
- continue;
+ bool Killed = false;
+ if (!Inst->use_empty()) {
+ Inst->replaceAllUsesWith(V);
+ Changed = true;
+ }
+ if (isInstructionTriviallyDead(Inst, &TLI)) {
+ Inst->eraseFromParent();
+ Changed = true;
+ Killed = true;
+ }
+ if (Changed)
+ ++NumSimplify;
+ if (Killed)
+ continue;
}
// If this is a simple instruction that we can value number, process it.
@@ -583,6 +603,8 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
// See if the instruction has an available value. If so, use it.
if (Value *V = AvailableValues.lookup(Inst)) {
DEBUG(dbgs() << "EarlyCSE CSE: " << *Inst << " to: " << *V << '\n');
+ if (auto *I = dyn_cast<Instruction>(V))
+ I->andIRFlags(Inst);
Inst->replaceAllUsesWith(V);
Inst->eraseFromParent();
Changed = true;
@@ -606,18 +628,25 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
}
// If we have an available version of this load, and if it is the right
- // generation, replace this instruction.
+ // generation or the load is known to be from an invariant location,
+ // replace this instruction.
+ //
+ // A dominating invariant load implies that the location loaded from is
+ // unchanging beginning at the point of the invariant load, so the load
+ // we're CSE'ing _away_ does not need to be invariant, only the available
+ // load we're CSE'ing _to_ does.
LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
- if (InVal.Data != nullptr && InVal.Generation == CurrentGeneration &&
+ if (InVal.DefInst != nullptr &&
+ (InVal.Generation == CurrentGeneration || InVal.IsInvariant) &&
InVal.MatchingId == MemInst.getMatchingId() &&
// We don't yet handle removing loads with ordering of any kind.
!MemInst.isVolatile() && MemInst.isUnordered() &&
// We can't replace an atomic load with one which isn't also atomic.
InVal.IsAtomic >= MemInst.isAtomic()) {
- Value *Op = getOrCreateResult(InVal.Data, Inst->getType());
+ Value *Op = getOrCreateResult(InVal.DefInst, Inst->getType());
if (Op != nullptr) {
DEBUG(dbgs() << "EarlyCSE CSE LOAD: " << *Inst
- << " to: " << *InVal.Data << '\n');
+ << " to: " << *InVal.DefInst << '\n');
if (!Inst->use_empty())
Inst->replaceAllUsesWith(Op);
Inst->eraseFromParent();
@@ -631,7 +660,7 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
AvailableLoads.insert(
MemInst.getPointerOperand(),
LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
- MemInst.isAtomic()));
+ MemInst.isAtomic(), MemInst.isInvariantLoad()));
LastStore = nullptr;
continue;
}
@@ -649,7 +678,7 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
if (CallValue::canHandle(Inst)) {
// If we have an available version of this call, and if it is the right
// generation, replace this instruction.
- std::pair<Value *, unsigned> InVal = AvailableCalls.lookup(Inst);
+ std::pair<Instruction *, unsigned> InVal = AvailableCalls.lookup(Inst);
if (InVal.first != nullptr && InVal.second == CurrentGeneration) {
DEBUG(dbgs() << "EarlyCSE CSE CALL: " << *Inst
<< " to: " << *InVal.first << '\n');
@@ -663,7 +692,7 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
// Otherwise, remember that we have this instruction.
AvailableCalls.insert(
- Inst, std::pair<Value *, unsigned>(Inst, CurrentGeneration));
+ Inst, std::pair<Instruction *, unsigned>(Inst, CurrentGeneration));
continue;
}
@@ -673,7 +702,7 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
// to advance the generation. We do need to prevent DSE across the fence,
// but that's handled above.
if (FenceInst *FI = dyn_cast<FenceInst>(Inst))
- if (FI->getOrdering() == Release) {
+ if (FI->getOrdering() == AtomicOrdering::Release) {
assert(Inst->mayReadFromMemory() && "relied on to prevent DSE above");
continue;
}
@@ -685,8 +714,8 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
// the store originally was.
if (MemInst.isValid() && MemInst.isStore()) {
LoadValue InVal = AvailableLoads.lookup(MemInst.getPointerOperand());
- if (InVal.Data &&
- InVal.Data == getOrCreateResult(Inst, InVal.Data->getType()) &&
+ if (InVal.DefInst &&
+ InVal.DefInst == getOrCreateResult(Inst, InVal.DefInst->getType()) &&
InVal.Generation == CurrentGeneration &&
InVal.MatchingId == MemInst.getMatchingId() &&
// We don't yet handle removing stores with ordering of any kind.
@@ -743,7 +772,7 @@ bool EarlyCSE::processNode(DomTreeNode *Node) {
AvailableLoads.insert(
MemInst.getPointerOperand(),
LoadValue(Inst, CurrentGeneration, MemInst.getMatchingId(),
- MemInst.isAtomic()));
+ MemInst.isAtomic(), /*IsInvariant=*/false));
// Remember that this was the last unordered store we saw for DSE. We
// don't yet handle DSE on ordered or volatile stores since we don't
@@ -818,11 +847,11 @@ bool EarlyCSE::run() {
}
PreservedAnalyses EarlyCSEPass::run(Function &F,
- AnalysisManager<Function> *AM) {
- auto &TLI = AM->getResult<TargetLibraryAnalysis>(F);
- auto &TTI = AM->getResult<TargetIRAnalysis>(F);
- auto &DT = AM->getResult<DominatorTreeAnalysis>(F);
- auto &AC = AM->getResult<AssumptionAnalysis>(F);
+ AnalysisManager<Function> &AM) {
+ auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
+ auto &TTI = AM.getResult<TargetIRAnalysis>(F);
+ auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+ auto &AC = AM.getResult<AssumptionAnalysis>(F);
EarlyCSE CSE(TLI, TTI, DT, AC);
@@ -833,6 +862,7 @@ PreservedAnalyses EarlyCSEPass::run(Function &F,
// FIXME: Bundle this with other CFG-preservation.
PreservedAnalyses PA;
PA.preserve<DominatorTreeAnalysis>();
+ PA.preserve<GlobalsAA>();
return PA;
}
@@ -853,7 +883,7 @@ public:
}
bool runOnFunction(Function &F) override {
- if (skipOptnoneFunction(F))
+ if (skipFunction(F))
return false;
auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
Copyright © 1996 – 2023 Jason A. Donenfeld. All Rights Reverse Engineered.