summaryrefslogtreecommitdiff
path: root/lib/Transforms/Scalar/ConstantHoisting.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms/Scalar/ConstantHoisting.cpp')
-rw-r--r--lib/Transforms/Scalar/ConstantHoisting.cpp302
1 files changed, 162 insertions, 140 deletions
diff --git a/lib/Transforms/Scalar/ConstantHoisting.cpp b/lib/Transforms/Scalar/ConstantHoisting.cpp
index 84f7f5fff5b59..913e939c2bd40 100644
--- a/lib/Transforms/Scalar/ConstantHoisting.cpp
+++ b/lib/Transforms/Scalar/ConstantHoisting.cpp
@@ -33,20 +33,20 @@
// %0 = load i64* inttoptr (i64 big_constant to i64*)
//===----------------------------------------------------------------------===//
-#include "llvm/Transforms/Scalar.h"
+#include "llvm/Transforms/Scalar/ConstantHoisting.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
-#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/Constants.h"
-#include "llvm/IR/Dominators.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Scalar.h"
#include <tuple>
using namespace llvm;
+using namespace consthoist;
#define DEBUG_TYPE "consthoist"
@@ -54,75 +54,12 @@ STATISTIC(NumConstantsHoisted, "Number of constants hoisted");
STATISTIC(NumConstantsRebased, "Number of constants rebased");
namespace {
-struct ConstantUser;
-struct RebasedConstantInfo;
-
-typedef SmallVector<ConstantUser, 8> ConstantUseListType;
-typedef SmallVector<RebasedConstantInfo, 4> RebasedConstantListType;
-
-/// \brief Keeps track of the user of a constant and the operand index where the
-/// constant is used.
-struct ConstantUser {
- Instruction *Inst;
- unsigned OpndIdx;
-
- ConstantUser(Instruction *Inst, unsigned Idx) : Inst(Inst), OpndIdx(Idx) { }
-};
-
-/// \brief Keeps track of a constant candidate and its uses.
-struct ConstantCandidate {
- ConstantUseListType Uses;
- ConstantInt *ConstInt;
- unsigned CumulativeCost;
-
- ConstantCandidate(ConstantInt *ConstInt)
- : ConstInt(ConstInt), CumulativeCost(0) { }
-
- /// \brief Add the user to the use list and update the cost.
- void addUser(Instruction *Inst, unsigned Idx, unsigned Cost) {
- CumulativeCost += Cost;
- Uses.push_back(ConstantUser(Inst, Idx));
- }
-};
-
-/// \brief This represents a constant that has been rebased with respect to a
-/// base constant. The difference to the base constant is recorded in Offset.
-struct RebasedConstantInfo {
- ConstantUseListType Uses;
- Constant *Offset;
-
- RebasedConstantInfo(ConstantUseListType &&Uses, Constant *Offset)
- : Uses(std::move(Uses)), Offset(Offset) { }
-};
-
-/// \brief A base constant and all its rebased constants.
-struct ConstantInfo {
- ConstantInt *BaseConstant;
- RebasedConstantListType RebasedConstants;
-};
-
/// \brief The constant hoisting pass.
-class ConstantHoisting : public FunctionPass {
- typedef DenseMap<ConstantInt *, unsigned> ConstCandMapType;
- typedef std::vector<ConstantCandidate> ConstCandVecType;
-
- const TargetTransformInfo *TTI;
- DominatorTree *DT;
- BasicBlock *Entry;
-
- /// Keeps track of constant candidates found in the function.
- ConstCandVecType ConstCandVec;
-
- /// Keep track of cast instructions we already cloned.
- SmallDenseMap<Instruction *, Instruction *> ClonedCastMap;
-
- /// These are the final constants we decided to hoist.
- SmallVector<ConstantInfo, 8> ConstantVec;
+class ConstantHoistingLegacyPass : public FunctionPass {
public:
static char ID; // Pass identification, replacement for typeid
- ConstantHoisting() : FunctionPass(ID), TTI(nullptr), DT(nullptr),
- Entry(nullptr) {
- initializeConstantHoistingPass(*PassRegistry::getPassRegistry());
+ ConstantHoistingLegacyPass() : FunctionPass(ID) {
+ initializeConstantHoistingLegacyPassPass(*PassRegistry::getPassRegistry());
}
bool runOnFunction(Function &Fn) override;
@@ -135,67 +72,36 @@ public:
AU.addRequired<TargetTransformInfoWrapperPass>();
}
-private:
- /// \brief Initialize the pass.
- void setup(Function &Fn) {
- DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
- TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(Fn);
- Entry = &Fn.getEntryBlock();
- }
+ void releaseMemory() override { Impl.releaseMemory(); }
- /// \brief Cleanup.
- void cleanup() {
- ConstantVec.clear();
- ClonedCastMap.clear();
- ConstCandVec.clear();
-
- TTI = nullptr;
- DT = nullptr;
- Entry = nullptr;
- }
-
- Instruction *findMatInsertPt(Instruction *Inst, unsigned Idx = ~0U) const;
- Instruction *findConstantInsertionPoint(const ConstantInfo &ConstInfo) const;
- void collectConstantCandidates(ConstCandMapType &ConstCandMap,
- Instruction *Inst, unsigned Idx,
- ConstantInt *ConstInt);
- void collectConstantCandidates(ConstCandMapType &ConstCandMap,
- Instruction *Inst);
- void collectConstantCandidates(Function &Fn);
- void findAndMakeBaseConstant(ConstCandVecType::iterator S,
- ConstCandVecType::iterator E);
- void findBaseConstants();
- void emitBaseConstants(Instruction *Base, Constant *Offset,
- const ConstantUser &ConstUser);
- bool emitBaseConstants();
- void deleteDeadCastInst() const;
- bool optimizeConstants(Function &Fn);
+private:
+ ConstantHoistingPass Impl;
};
}
-char ConstantHoisting::ID = 0;
-INITIALIZE_PASS_BEGIN(ConstantHoisting, "consthoist", "Constant Hoisting",
- false, false)
+char ConstantHoistingLegacyPass::ID = 0;
+INITIALIZE_PASS_BEGIN(ConstantHoistingLegacyPass, "consthoist",
+ "Constant Hoisting", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
-INITIALIZE_PASS_END(ConstantHoisting, "consthoist", "Constant Hoisting",
- false, false)
+INITIALIZE_PASS_END(ConstantHoistingLegacyPass, "consthoist",
+ "Constant Hoisting", false, false)
FunctionPass *llvm::createConstantHoistingPass() {
- return new ConstantHoisting();
+ return new ConstantHoistingLegacyPass();
}
/// \brief Perform the constant hoisting optimization for the given function.
-bool ConstantHoisting::runOnFunction(Function &Fn) {
- if (skipOptnoneFunction(Fn))
+bool ConstantHoistingLegacyPass::runOnFunction(Function &Fn) {
+ if (skipFunction(Fn))
return false;
DEBUG(dbgs() << "********** Begin Constant Hoisting **********\n");
DEBUG(dbgs() << "********** Function: " << Fn.getName() << '\n');
- setup(Fn);
-
- bool MadeChange = optimizeConstants(Fn);
+ bool MadeChange = Impl.runImpl(
+ Fn, getAnalysis<TargetTransformInfoWrapperPass>().getTTI(Fn),
+ getAnalysis<DominatorTreeWrapperPass>().getDomTree(), Fn.getEntryBlock());
if (MadeChange) {
DEBUG(dbgs() << "********** Function after Constant Hoisting: "
@@ -204,15 +110,13 @@ bool ConstantHoisting::runOnFunction(Function &Fn) {
}
DEBUG(dbgs() << "********** End Constant Hoisting **********\n");
- cleanup();
-
return MadeChange;
}
/// \brief Find the constant materialization insertion point.
-Instruction *ConstantHoisting::findMatInsertPt(Instruction *Inst,
- unsigned Idx) const {
+Instruction *ConstantHoistingPass::findMatInsertPt(Instruction *Inst,
+ unsigned Idx) const {
// If the operand is a cast instruction, then we have to materialize the
// constant before the cast instruction.
if (Idx != ~0U) {
@@ -237,8 +141,8 @@ Instruction *ConstantHoisting::findMatInsertPt(Instruction *Inst,
}
/// \brief Find an insertion point that dominates all uses.
-Instruction *ConstantHoisting::
-findConstantInsertionPoint(const ConstantInfo &ConstInfo) const {
+Instruction *ConstantHoistingPass::findConstantInsertionPoint(
+ const ConstantInfo &ConstInfo) const {
assert(!ConstInfo.RebasedConstants.empty() && "Invalid constant info entry.");
// Collect all basic blocks.
SmallPtrSet<BasicBlock *, 8> BBs;
@@ -272,10 +176,9 @@ findConstantInsertionPoint(const ConstantInfo &ConstInfo) const {
/// The operand at index Idx is not necessarily the constant integer itself. It
/// could also be a cast instruction or a constant expression that uses the
// constant integer.
-void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap,
- Instruction *Inst,
- unsigned Idx,
- ConstantInt *ConstInt) {
+void ConstantHoistingPass::collectConstantCandidates(
+ ConstCandMapType &ConstCandMap, Instruction *Inst, unsigned Idx,
+ ConstantInt *ConstInt) {
unsigned Cost;
// Ask the target about the cost of materializing the constant for the given
// instruction and operand index.
@@ -309,8 +212,8 @@ void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap,
/// \brief Scan the instruction for expensive integer constants and record them
/// in the constant candidate vector.
-void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap,
- Instruction *Inst) {
+void ConstantHoistingPass::collectConstantCandidates(
+ ConstCandMapType &ConstCandMap, Instruction *Inst) {
// Skip all cast instructions. They are visited indirectly later on.
if (Inst->isCast())
return;
@@ -320,6 +223,18 @@ void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap,
if (isa<InlineAsm>(Call->getCalledValue()))
return;
+ // Switch cases must remain constant, and if the value being tested is
+ // constant the entire thing should disappear.
+ if (isa<SwitchInst>(Inst))
+ return;
+
+ // Static allocas (constant size in the entry block) are handled by
+ // prologue/epilogue insertion so they're free anyway. We definitely don't
+ // want to make them non-constant.
+ auto AI = dyn_cast<AllocaInst>(Inst);
+ if (AI && AI->isStaticAlloca())
+ return;
+
// Scan all operands.
for (unsigned Idx = 0, E = Inst->getNumOperands(); Idx != E; ++Idx) {
Value *Opnd = Inst->getOperand(Idx);
@@ -363,25 +278,116 @@ void ConstantHoisting::collectConstantCandidates(ConstCandMapType &ConstCandMap,
/// \brief Collect all integer constants in the function that cannot be folded
/// into an instruction itself.
-void ConstantHoisting::collectConstantCandidates(Function &Fn) {
+void ConstantHoistingPass::collectConstantCandidates(Function &Fn) {
ConstCandMapType ConstCandMap;
for (BasicBlock &BB : Fn)
for (Instruction &Inst : BB)
collectConstantCandidates(ConstCandMap, &Inst);
}
-/// \brief Find the base constant within the given range and rebase all other
-/// constants with respect to the base constant.
-void ConstantHoisting::findAndMakeBaseConstant(ConstCandVecType::iterator S,
- ConstCandVecType::iterator E) {
- auto MaxCostItr = S;
+// This helper function is necessary to deal with values that have different
+// bit widths (APInt Operator- does not like that). If the value cannot be
+// represented in uint64 we return an "empty" APInt. This is then interpreted
+// as the value is not in range.
+static llvm::Optional<APInt> calculateOffsetDiff(APInt V1, APInt V2)
+{
+ llvm::Optional<APInt> Res = None;
+ unsigned BW = V1.getBitWidth() > V2.getBitWidth() ?
+ V1.getBitWidth() : V2.getBitWidth();
+ uint64_t LimVal1 = V1.getLimitedValue();
+ uint64_t LimVal2 = V2.getLimitedValue();
+
+ if (LimVal1 == ~0ULL || LimVal2 == ~0ULL)
+ return Res;
+
+ uint64_t Diff = LimVal1 - LimVal2;
+ return APInt(BW, Diff, true);
+}
+
+// From a list of constants, one needs to picked as the base and the other
+// constants will be transformed into an offset from that base constant. The
+// question is which we can pick best? For example, consider these constants
+// and their number of uses:
+//
+// Constants| 2 | 4 | 12 | 42 |
+// NumUses | 3 | 2 | 8 | 7 |
+//
+// Selecting constant 12 because it has the most uses will generate negative
+// offsets for constants 2 and 4 (i.e. -10 and -8 respectively). If negative
+// offsets lead to less optimal code generation, then there might be better
+// solutions. Suppose immediates in the range of 0..35 are most optimally
+// supported by the architecture, then selecting constant 2 is most optimal
+// because this will generate offsets: 0, 2, 10, 40. Offsets 0, 2 and 10 are in
+// range 0..35, and thus 3 + 2 + 8 = 13 uses are in range. Selecting 12 would
+// have only 8 uses in range, so choosing 2 as a base is more optimal. Thus, in
+// selecting the base constant the range of the offsets is a very important
+// factor too that we take into account here. This algorithm calculates a total
+// costs for selecting a constant as the base and substract the costs if
+// immediates are out of range. It has quadratic complexity, so we call this
+// function only when we're optimising for size and there are less than 100
+// constants, we fall back to the straightforward algorithm otherwise
+// which does not do all the offset calculations.
+unsigned
+ConstantHoistingPass::maximizeConstantsInRange(ConstCandVecType::iterator S,
+ ConstCandVecType::iterator E,
+ ConstCandVecType::iterator &MaxCostItr) {
unsigned NumUses = 0;
- // Use the constant that has the maximum cost as base constant.
+
+ if(!Entry->getParent()->optForSize() || std::distance(S,E) > 100) {
+ for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
+ NumUses += ConstCand->Uses.size();
+ if (ConstCand->CumulativeCost > MaxCostItr->CumulativeCost)
+ MaxCostItr = ConstCand;
+ }
+ return NumUses;
+ }
+
+ DEBUG(dbgs() << "== Maximize constants in range ==\n");
+ int MaxCost = -1;
for (auto ConstCand = S; ConstCand != E; ++ConstCand) {
+ auto Value = ConstCand->ConstInt->getValue();
+ Type *Ty = ConstCand->ConstInt->getType();
+ int Cost = 0;
NumUses += ConstCand->Uses.size();
- if (ConstCand->CumulativeCost > MaxCostItr->CumulativeCost)
+ DEBUG(dbgs() << "= Constant: " << ConstCand->ConstInt->getValue() << "\n");
+
+ for (auto User : ConstCand->Uses) {
+ unsigned Opcode = User.Inst->getOpcode();
+ unsigned OpndIdx = User.OpndIdx;
+ Cost += TTI->getIntImmCost(Opcode, OpndIdx, Value, Ty);
+ DEBUG(dbgs() << "Cost: " << Cost << "\n");
+
+ for (auto C2 = S; C2 != E; ++C2) {
+ llvm::Optional<APInt> Diff = calculateOffsetDiff(
+ C2->ConstInt->getValue(),
+ ConstCand->ConstInt->getValue());
+ if (Diff) {
+ const int ImmCosts =
+ TTI->getIntImmCodeSizeCost(Opcode, OpndIdx, Diff.getValue(), Ty);
+ Cost -= ImmCosts;
+ DEBUG(dbgs() << "Offset " << Diff.getValue() << " "
+ << "has penalty: " << ImmCosts << "\n"
+ << "Adjusted cost: " << Cost << "\n");
+ }
+ }
+ }
+ DEBUG(dbgs() << "Cumulative cost: " << Cost << "\n");
+ if (Cost > MaxCost) {
+ MaxCost = Cost;
MaxCostItr = ConstCand;
+ DEBUG(dbgs() << "New candidate: " << MaxCostItr->ConstInt->getValue()
+ << "\n");
+ }
}
+ return NumUses;
+}
+
+/// \brief Find the base constant within the given range and rebase all other
+/// constants with respect to the base constant.
+void ConstantHoistingPass::findAndMakeBaseConstant(
+ ConstCandVecType::iterator S, ConstCandVecType::iterator E) {
+ auto MaxCostItr = S;
+ unsigned NumUses = maximizeConstantsInRange(S, E, MaxCostItr);
// Don't hoist constants that have only one use.
if (NumUses <= 1)
@@ -404,7 +410,7 @@ void ConstantHoisting::findAndMakeBaseConstant(ConstCandVecType::iterator S,
/// \brief Finds and combines constant candidates that can be easily
/// rematerialized with an add from a common base constant.
-void ConstantHoisting::findBaseConstants() {
+void ConstantHoistingPass::findBaseConstants() {
// Sort the constants by value and type. This invalidates the mapping!
std::sort(ConstCandVec.begin(), ConstCandVec.end(),
[](const ConstantCandidate &LHS, const ConstantCandidate &RHS) {
@@ -466,8 +472,9 @@ static bool updateOperand(Instruction *Inst, unsigned Idx, Instruction *Mat) {
/// \brief Emit materialization code for all rebased constants and update their
/// users.
-void ConstantHoisting::emitBaseConstants(Instruction *Base, Constant *Offset,
- const ConstantUser &ConstUser) {
+void ConstantHoistingPass::emitBaseConstants(Instruction *Base,
+ Constant *Offset,
+ const ConstantUser &ConstUser) {
Instruction *Mat = Base;
if (Offset) {
Instruction *InsertionPt = findMatInsertPt(ConstUser.Inst,
@@ -538,7 +545,7 @@ void ConstantHoisting::emitBaseConstants(Instruction *Base, Constant *Offset,
/// \brief Hoist and hide the base constant behind a bitcast and emit
/// materialization code for derived constants.
-bool ConstantHoisting::emitBaseConstants() {
+bool ConstantHoistingPass::emitBaseConstants() {
bool MadeChange = false;
for (auto const &ConstInfo : ConstantVec) {
// Hoist and hide the base constant behind a bitcast.
@@ -572,14 +579,18 @@ bool ConstantHoisting::emitBaseConstants() {
/// \brief Check all cast instructions we made a copy of and remove them if they
/// have no more users.
-void ConstantHoisting::deleteDeadCastInst() const {
+void ConstantHoistingPass::deleteDeadCastInst() const {
for (auto const &I : ClonedCastMap)
if (I.first->use_empty())
I.first->eraseFromParent();
}
/// \brief Optimize expensive integer constants in the given function.
-bool ConstantHoisting::optimizeConstants(Function &Fn) {
+bool ConstantHoistingPass::runImpl(Function &Fn, TargetTransformInfo &TTI,
+ DominatorTree &DT, BasicBlock &Entry) {
+ this->TTI = &TTI;
+ this->DT = &DT;
+ this->Entry = &Entry;
// Collect all constant candidates.
collectConstantCandidates(Fn);
@@ -604,3 +615,14 @@ bool ConstantHoisting::optimizeConstants(Function &Fn) {
return MadeChange;
}
+
+PreservedAnalyses ConstantHoistingPass::run(Function &F,
+ FunctionAnalysisManager &AM) {
+ auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+ auto &TTI = AM.getResult<TargetIRAnalysis>(F);
+ if (!runImpl(F, TTI, DT, F.getEntryBlock()))
+ return PreservedAnalyses::all();
+
+ // FIXME: This should also 'preserve the CFG'.
+ return PreservedAnalyses::none();
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-17 12:19:52 +0000