summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/Scalar
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Transforms/Scalar')
-rw-r--r--llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp102
-rw-r--r--llvm/lib/Transforms/Scalar/MergeICmps.cpp93
-rw-r--r--llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp60
3 files changed, 175 insertions, 80 deletions
diff --git a/llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp b/llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp
index c23d891b650..53b25e688e8 100644
--- a/llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopVersioningLICM.cpp
@@ -1,4 +1,4 @@
-//===----------- LoopVersioningLICM.cpp - LICM Loop Versioning ------------===//
+//===- LoopVersioningLICM.cpp - LICM Loop Versioning ----------------------===//
//
// The LLVM Compiler Infrastructure
//
@@ -60,41 +60,41 @@
//
//===----------------------------------------------------------------------===//
-#include "llvm/ADT/MapVector.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AliasSetTracker.h"
-#include "llvm/Analysis/ConstantFolding.h"
#include "llvm/Analysis/GlobalsModRef.h"
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
-#include "llvm/Analysis/ScalarEvolutionExpander.h"
-#include "llvm/Analysis/TargetLibraryInfo.h"
-#include "llvm/Analysis/ValueTracking.h"
-#include "llvm/Analysis/VectorUtils.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
-#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/MDBuilder.h"
-#include "llvm/IR/PatternMatch.h"
-#include "llvm/IR/PredIteratorCache.h"
+#include "llvm/IR/Metadata.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/BasicBlockUtils.h"
-#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/LoopVersioning.h"
-#include "llvm/Transforms/Utils/ValueMapper.h"
+#include <cassert>
+#include <memory>
+
+using namespace llvm;
#define DEBUG_TYPE "loop-versioning-licm"
-static const char *LICMVersioningMetaData = "llvm.loop.licm_versioning.disable";
-using namespace llvm;
+static const char *LICMVersioningMetaData = "llvm.loop.licm_versioning.disable";
/// Threshold minimum allowed percentage for possible
/// invariant instructions in a loop.
@@ -143,9 +143,16 @@ void llvm::addStringMetadataToLoop(Loop *TheLoop, const char *MDString,
}
namespace {
+
struct LoopVersioningLICM : public LoopPass {
static char ID;
+ LoopVersioningLICM()
+ : LoopPass(ID), LoopDepthThreshold(LVLoopDepthThreshold),
+ InvariantThreshold(LVInvarThreshold) {
+ initializeLoopVersioningLICMPass(*PassRegistry::getPassRegistry());
+ }
+
bool runOnLoop(Loop *L, LPPassManager &LPM) override;
void getAnalysisUsage(AnalysisUsage &AU) const override {
@@ -161,13 +168,6 @@ struct LoopVersioningLICM : public LoopPass {
AU.addPreserved<GlobalsAAWrapperPass>();
}
- LoopVersioningLICM()
- : LoopPass(ID), AA(nullptr), SE(nullptr), LAA(nullptr), LAI(nullptr),
- CurLoop(nullptr), LoopDepthThreshold(LVLoopDepthThreshold),
- InvariantThreshold(LVInvarThreshold), LoadAndStoreCounter(0),
- InvariantCounter(0), IsReadOnlyLoop(true) {
- initializeLoopVersioningLICMPass(*PassRegistry::getPassRegistry());
- }
StringRef getPassName() const override { return "Loop Versioning for LICM"; }
void reset() {
@@ -191,30 +191,49 @@ struct LoopVersioningLICM : public LoopPass {
};
private:
- AliasAnalysis *AA; // Current AliasAnalysis information
- ScalarEvolution *SE; // Current ScalarEvolution
- LoopAccessLegacyAnalysis *LAA; // Current LoopAccessAnalysis
- const LoopAccessInfo *LAI; // Current Loop's LoopAccessInfo
+ // Current AliasAnalysis information
+ AliasAnalysis *AA = nullptr;
+
+ // Current ScalarEvolution
+ ScalarEvolution *SE = nullptr;
+
+ // Current LoopAccessAnalysis
+ LoopAccessLegacyAnalysis *LAA = nullptr;
+
+ // Current Loop's LoopAccessInfo
+ const LoopAccessInfo *LAI = nullptr;
+
+ // The current loop we are working on.
+ Loop *CurLoop = nullptr;
+
+ // AliasSet information for the current loop.
+ std::unique_ptr<AliasSetTracker> CurAST;
- Loop *CurLoop; // The current loop we are working on.
- std::unique_ptr<AliasSetTracker>
- CurAST; // AliasSet information for the current loop.
+ // Maximum loop nest threshold
+ unsigned LoopDepthThreshold;
- unsigned LoopDepthThreshold; // Maximum loop nest threshold
- float InvariantThreshold; // Minimum invariant threshold
- unsigned LoadAndStoreCounter; // Counter to track num of load & store
- unsigned InvariantCounter; // Counter to track num of invariant
- bool IsReadOnlyLoop; // Read only loop marker.
+ // Minimum invariant threshold
+ float InvariantThreshold;
+
+ // Counter to track num of load & store
+ unsigned LoadAndStoreCounter = 0;
+
+ // Counter to track num of invariant
+ unsigned InvariantCounter = 0;
+
+ // Read only loop marker.
+ bool IsReadOnlyLoop = true;
bool isLegalForVersioning();
bool legalLoopStructure();
bool legalLoopInstructions();
bool legalLoopMemoryAccesses();
bool isLoopAlreadyVisited();
- void setNoAliasToLoop(Loop *);
- bool instructionSafeForVersioning(Instruction *);
+ void setNoAliasToLoop(Loop *VerLoop);
+ bool instructionSafeForVersioning(Instruction *I);
};
-}
+
+} // end anonymous namespace
/// \brief Check loop structure and confirms it's good for LoopVersioningLICM.
bool LoopVersioningLICM::legalLoopStructure() {
@@ -225,7 +244,7 @@ bool LoopVersioningLICM::legalLoopStructure() {
return false;
}
// Loop should be innermost loop, if not return false.
- if (CurLoop->getSubLoops().size()) {
+ if (!CurLoop->getSubLoops().empty()) {
DEBUG(dbgs() << " loop is not innermost\n");
return false;
}
@@ -562,6 +581,7 @@ bool LoopVersioningLICM::runOnLoop(Loop *L, LPPassManager &LPM) {
}
char LoopVersioningLICM::ID = 0;
+
INITIALIZE_PASS_BEGIN(LoopVersioningLICM, "loop-versioning-licm",
"Loop Versioning For LICM", false, false)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
diff --git a/llvm/lib/Transforms/Scalar/MergeICmps.cpp b/llvm/lib/Transforms/Scalar/MergeICmps.cpp
index 1244a9776fa..62fa49b8860 100644
--- a/llvm/lib/Transforms/Scalar/MergeICmps.cpp
+++ b/llvm/lib/Transforms/Scalar/MergeICmps.cpp
@@ -19,33 +19,47 @@
// - Code size is smaller, both because jumps are removed and because the
// encoding of a 2*n byte compare is smaller than that of two n-byte
// compares.
-
+//
//===----------------------------------------------------------------------===//
-#include <algorithm>
-#include <numeric>
-#include <utility>
-#include <vector>
-#include "llvm/ADT/APSInt.h"
+#include "llvm/ADT/APInt.h"
+#include "llvm/ADT/ArrayRef.h"
#include "llvm/Analysis/Loads.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/IRBuilder.h"
-#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.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/Debug.h"
+#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/BuildLibCalls.h"
+#include <algorithm>
+#include <cassert>
+#include <cstddef>
+#include <numeric>
+#include <utility>
+#include <vector>
using namespace llvm;
-namespace {
-
#define DEBUG_TYPE "mergeicmps"
+namespace {
+
// A BCE atom.
struct BCEAtom {
- BCEAtom() : GEP(nullptr), LoadI(nullptr), Offset() {}
+ BCEAtom() = default;
const Value *Base() const { return GEP ? GEP->getPointerOperand() : nullptr; }
@@ -67,15 +81,17 @@ struct BCEAtom {
return NameCmp < 0;
}
- GetElementPtrInst *GEP;
- LoadInst *LoadI;
+ GetElementPtrInst *GEP = nullptr;
+ LoadInst *LoadI = nullptr;
APInt Offset;
};
+} // end anonymous namespace
+
// If this value is a load from a constant offset w.r.t. a base address, and
// there are no othe rusers of the load or address, returns the base address and
// the offset.
-BCEAtom visitICmpLoadOperand(Value *const Val) {
+static BCEAtom visitICmpLoadOperand(Value *const Val) {
BCEAtom Result;
if (auto *const LoadI = dyn_cast<LoadInst>(Val)) {
DEBUG(dbgs() << "load\n");
@@ -111,14 +127,16 @@ BCEAtom visitICmpLoadOperand(Value *const Val) {
return Result;
}
+namespace {
+
// A basic block with a comparison between two BCE atoms.
// Note: the terminology is misleading: the comparison is symmetric, so there
// is no real {l/r}hs. What we want though is to have the same base on the
// left (resp. right), so that we can detect consecutive loads. To ensure this
// we put the smallest atom on the left.
class BCECmpBlock {
- public:
- BCECmpBlock() {}
+public:
+ BCECmpBlock() = default;
BCECmpBlock(BCEAtom L, BCEAtom R, int SizeBits)
: Lhs_(L), Rhs_(R), SizeBits_(SizeBits) {
@@ -148,17 +166,21 @@ class BCECmpBlock {
// The basic block where this comparison happens.
BasicBlock *BB = nullptr;
+
// The ICMP for this comparison.
ICmpInst *CmpI = nullptr;
+
// The terminating branch.
BranchInst *BranchI = nullptr;
- private:
+private:
BCEAtom Lhs_;
BCEAtom Rhs_;
int SizeBits_ = 0;
};
+} // end anonymous namespace
+
bool BCECmpBlock::doesOtherWork() const {
AssertConsistent();
// TODO(courbet): Can we allow some other things ? This is very conservative.
@@ -183,8 +205,8 @@ bool BCECmpBlock::doesOtherWork() const {
// Visit the given comparison. If this is a comparison between two valid
// BCE atoms, returns the comparison.
-BCECmpBlock visitICmp(const ICmpInst *const CmpI,
- const ICmpInst::Predicate ExpectedPredicate) {
+static BCECmpBlock visitICmp(const ICmpInst *const CmpI,
+ const ICmpInst::Predicate ExpectedPredicate) {
if (CmpI->getPredicate() == ExpectedPredicate) {
DEBUG(dbgs() << "cmp "
<< (ExpectedPredicate == ICmpInst::ICMP_EQ ? "eq" : "ne")
@@ -201,8 +223,8 @@ BCECmpBlock visitICmp(const ICmpInst *const CmpI,
// Visit the given comparison block. If this is a comparison between two valid
// BCE atoms, returns the comparison.
-BCECmpBlock visitCmpBlock(Value *const Val, BasicBlock *const Block,
- const BasicBlock *const PhiBlock) {
+static BCECmpBlock visitCmpBlock(Value *const Val, BasicBlock *const Block,
+ const BasicBlock *const PhiBlock) {
if (Block->empty()) return {};
auto *const BranchI = dyn_cast<BranchInst>(Block->getTerminator());
if (!BranchI) return {};
@@ -240,9 +262,11 @@ BCECmpBlock visitCmpBlock(Value *const Val, BasicBlock *const Block,
return {};
}
+namespace {
+
// A chain of comparisons.
class BCECmpChain {
- public:
+public:
BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi);
int size() const { return Comparisons_.size(); }
@@ -253,7 +277,7 @@ class BCECmpChain {
bool simplify(const TargetLibraryInfo *const TLI);
- private:
+private:
static bool IsContiguous(const BCECmpBlock &First,
const BCECmpBlock &Second) {
return First.Lhs().Base() == Second.Lhs().Base() &&
@@ -271,10 +295,13 @@ class BCECmpChain {
PHINode &Phi_;
std::vector<BCECmpBlock> Comparisons_;
+
// The original entry block (before sorting);
BasicBlock *EntryBlock_;
};
+} // end anonymous namespace
+
BCECmpChain::BCECmpChain(const std::vector<BasicBlock *> &Blocks, PHINode &Phi)
: Phi_(Phi) {
// Now look inside blocks to check for BCE comparisons.
@@ -447,7 +474,8 @@ void BCECmpChain::mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
IRBuilder<> Builder(BB);
const auto &DL = Phi.getModule()->getDataLayout();
Value *const MemCmpCall = emitMemCmp(
- FirstComparison.Lhs().GEP, FirstComparison.Rhs().GEP, ConstantInt::get(DL.getIntPtrType(Context), TotalSize),
+ FirstComparison.Lhs().GEP, FirstComparison.Rhs().GEP,
+ ConstantInt::get(DL.getIntPtrType(Context), TotalSize),
Builder, DL, TLI);
Value *const MemCmpIsZero = Builder.CreateICmpEQ(
MemCmpCall, ConstantInt::get(Type::getInt32Ty(Context), 0));
@@ -504,9 +532,9 @@ void BCECmpChain::mergeComparisons(ArrayRef<BCECmpBlock> Comparisons,
}
}
-std::vector<BasicBlock *> getOrderedBlocks(PHINode &Phi,
- BasicBlock *const LastBlock,
- int NumBlocks) {
+static std::vector<BasicBlock *> getOrderedBlocks(PHINode &Phi,
+ BasicBlock *const LastBlock,
+ int NumBlocks) {
// Walk up from the last block to find other blocks.
std::vector<BasicBlock *> Blocks(NumBlocks);
BasicBlock *CurBlock = LastBlock;
@@ -538,7 +566,7 @@ std::vector<BasicBlock *> getOrderedBlocks(PHINode &Phi,
return Blocks;
}
-bool processPhi(PHINode &Phi, const TargetLibraryInfo *const TLI) {
+static bool processPhi(PHINode &Phi, const TargetLibraryInfo *const TLI) {
DEBUG(dbgs() << "processPhi()\n");
if (Phi.getNumIncomingValues() <= 1) {
DEBUG(dbgs() << "skip: only one incoming value in phi\n");
@@ -593,8 +621,10 @@ bool processPhi(PHINode &Phi, const TargetLibraryInfo *const TLI) {
return CmpChain.simplify(TLI);
}
+namespace {
+
class MergeICmps : public FunctionPass {
- public:
+public:
static char ID;
MergeICmps() : FunctionPass(ID) {
@@ -609,16 +639,18 @@ class MergeICmps : public FunctionPass {
return !PA.areAllPreserved();
}
- private:
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<TargetLibraryInfoWrapperPass>();
AU.addRequired<TargetTransformInfoWrapperPass>();
}
+private:
PreservedAnalyses runImpl(Function &F, const TargetLibraryInfo *TLI,
const TargetTransformInfo *TTI);
};
+} // end anonymous namespace
+
PreservedAnalyses MergeICmps::runImpl(Function &F, const TargetLibraryInfo *TLI,
const TargetTransformInfo *TTI) {
DEBUG(dbgs() << "MergeICmpsPass: " << F.getName() << "\n");
@@ -640,9 +672,8 @@ PreservedAnalyses MergeICmps::runImpl(Function &F, const TargetLibraryInfo *TLI,
return PreservedAnalyses::all();
}
-} // namespace
-
char MergeICmps::ID = 0;
+
INITIALIZE_PASS_BEGIN(MergeICmps, "mergeicmps",
"Merge contiguous icmps into a memcmp", false, false)
INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
diff --git a/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp b/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp
index 84675f41cdd..4593f235122 100644
--- a/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp
+++ b/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp
@@ -1,4 +1,4 @@
-//===-- SeparateConstOffsetFromGEP.cpp - ------------------------*- C++ -*-===//
+//===- SeparateConstOffsetFromGEP.cpp -------------------------------------===//
//
// The LLVM Compiler Infrastructure
//
@@ -156,27 +156,44 @@
//
//===----------------------------------------------------------------------===//
+#include "llvm/ADT/APInt.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Constant.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/GetElementPtrTypeIterator.h"
#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
-#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
-#include "llvm/IR/Operator.h"
#include "llvm/IR/PatternMatch.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/User.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetSubtargetInfo.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
+#include <cassert>
+#include <cstdint>
+#include <string>
using namespace llvm;
using namespace llvm::PatternMatch;
@@ -185,6 +202,7 @@ static cl::opt<bool> DisableSeparateConstOffsetFromGEP(
"disable-separate-const-offset-from-gep", cl::init(false),
cl::desc("Do not separate the constant offset from a GEP instruction"),
cl::Hidden);
+
// Setting this flag may emit false positives when the input module already
// contains dead instructions. Therefore, we set it only in unit tests that are
// free of dead code.
@@ -219,6 +237,7 @@ public:
/// garbage-collect unused instructions in UserChain.
static Value *Extract(Value *Idx, GetElementPtrInst *GEP,
User *&UserChainTail, const DominatorTree *DT);
+
/// Looks for a constant offset from the given GEP index without extracting
/// it. It returns the numeric value of the extracted constant offset (0 if
/// failed). The meaning of the arguments are the same as Extract.
@@ -229,6 +248,7 @@ private:
ConstantOffsetExtractor(Instruction *InsertionPt, const DominatorTree *DT)
: IP(InsertionPt), DL(InsertionPt->getModule()->getDataLayout()), DT(DT) {
}
+
/// Searches the expression that computes V for a non-zero constant C s.t.
/// V can be reassociated into the form V' + C. If the searching is
/// successful, returns C and update UserChain as a def-use chain from C to V;
@@ -244,9 +264,11 @@ private:
/// non-negative. Levaraging this, we can better split
/// inbounds GEPs.
APInt find(Value *V, bool SignExtended, bool ZeroExtended, bool NonNegative);
+
/// A helper function to look into both operands of a binary operator.
APInt findInEitherOperand(BinaryOperator *BO, bool SignExtended,
bool ZeroExtended);
+
/// After finding the constant offset C from the GEP index I, we build a new
/// index I' s.t. I' + C = I. This function builds and returns the new
/// index I' according to UserChain produced by function "find".
@@ -263,6 +285,7 @@ private:
/// (sext(a) + sext(b)) + 5.
/// Given this form, we know I' is sext(a) + sext(b).
Value *rebuildWithoutConstOffset();
+
/// After the first step of rebuilding the GEP index without the constant
/// offset, distribute s/zext to the operands of all operators in UserChain.
/// e.g., zext(sext(a + (b + 5)) (assuming no overflow) =>
@@ -279,8 +302,10 @@ private:
/// UserChain.size() - 1, and is decremented during
/// the recursion.
Value *distributeExtsAndCloneChain(unsigned ChainIndex);
+
/// Reassociates the GEP index to the form I' + C and returns I'.
Value *removeConstOffset(unsigned ChainIndex);
+
/// A helper function to apply ExtInsts, a list of s/zext, to value V.
/// e.g., if ExtInsts = [sext i32 to i64, zext i16 to i32], this function
/// returns "sext i32 (zext i16 V to i32) to i64".
@@ -303,10 +328,14 @@ private:
///
/// This path helps to rebuild the new GEP index.
SmallVector<User *, 8> UserChain;
+
/// A data structure used in rebuildWithoutConstOffset. Contains all
/// sext/zext instructions along UserChain.
SmallVector<CastInst *, 16> ExtInsts;
- Instruction *IP; /// Insertion position of cloned instructions.
+
+ /// Insertion position of cloned instructions.
+ Instruction *IP;
+
const DataLayout &DL;
const DominatorTree *DT;
};
@@ -317,9 +346,10 @@ private:
class SeparateConstOffsetFromGEP : public FunctionPass {
public:
static char ID;
+
SeparateConstOffsetFromGEP(const TargetMachine *TM = nullptr,
bool LowerGEP = false)
- : FunctionPass(ID), DL(nullptr), DT(nullptr), TM(TM), LowerGEP(LowerGEP) {
+ : FunctionPass(ID), TM(TM), LowerGEP(LowerGEP) {
initializeSeparateConstOffsetFromGEPPass(*PassRegistry::getPassRegistry());
}
@@ -336,12 +366,14 @@ public:
DL = &M.getDataLayout();
return false;
}
+
bool runOnFunction(Function &F) override;
private:
/// Tries to split the given GEP into a variadic base and a constant offset,
/// and returns true if the splitting succeeds.
bool splitGEP(GetElementPtrInst *GEP);
+
/// Lower a GEP with multiple indices into multiple GEPs with a single index.
/// Function splitGEP already split the original GEP into a variadic part and
/// a constant offset (i.e., AccumulativeByteOffset). This function lowers the
@@ -351,6 +383,7 @@ private:
/// \p AccumulativeByteOffset The constant offset.
void lowerToSingleIndexGEPs(GetElementPtrInst *Variadic,
int64_t AccumulativeByteOffset);
+
/// Lower a GEP with multiple indices into ptrtoint+arithmetics+inttoptr form.
/// Function splitGEP already split the original GEP into a variadic part and
/// a constant offset (i.e., AccumulativeByteOffset). This function lowers the
@@ -360,12 +393,14 @@ private:
/// \p AccumulativeByteOffset The constant offset.
void lowerToArithmetics(GetElementPtrInst *Variadic,
int64_t AccumulativeByteOffset);
+
/// Finds the constant offset within each index and accumulates them. If
/// LowerGEP is true, it finds in indices of both sequential and structure
/// types, otherwise it only finds in sequential indices. The output
/// NeedsExtraction indicates whether we successfully find a non-zero constant
/// offset.
int64_t accumulateByteOffset(GetElementPtrInst *GEP, bool &NeedsExtraction);
+
/// Canonicalize array indices to pointer-size integers. This helps to
/// simplify the logic of splitting a GEP. For example, if a + b is a
/// pointer-size integer, we have
@@ -382,6 +417,7 @@ private:
///
/// Verified in @i32_add in split-gep.ll
bool canonicalizeArrayIndicesToPointerSize(GetElementPtrInst *GEP);
+
/// Optimize sext(a)+sext(b) to sext(a+b) when a+b can't sign overflow.
/// SeparateConstOffsetFromGEP distributes a sext to leaves before extracting
/// the constant offset. After extraction, it becomes desirable to reunion the
@@ -392,8 +428,10 @@ private:
/// => constant extraction &a[sext(i) + sext(j)] + 5
/// => reunion &a[sext(i +nsw j)] + 5
bool reuniteExts(Function &F);
+
/// A helper that reunites sexts in an instruction.
bool reuniteExts(Instruction *I);
+
/// Find the closest dominator of <Dominatee> that is equivalent to <Key>.
Instruction *findClosestMatchingDominator(const SCEV *Key,
Instruction *Dominatee);
@@ -401,27 +439,33 @@ private:
void verifyNoDeadCode(Function &F);
bool hasMoreThanOneUseInLoop(Value *v, Loop *L);
+
// Swap the index operand of two GEP.
void swapGEPOperand(GetElementPtrInst *First, GetElementPtrInst *Second);
+
// Check if it is safe to swap operand of two GEP.
bool isLegalToSwapOperand(GetElementPtrInst *First, GetElementPtrInst *Second,
Loop *CurLoop);
- const DataLayout *DL;
- DominatorTree *DT;
+ const DataLayout *DL = nullptr;
+ DominatorTree *DT = nullptr;
ScalarEvolution *SE;
const TargetMachine *TM;
LoopInfo *LI;
TargetLibraryInfo *TLI;
+
/// Whether to lower a GEP with multiple indices into arithmetic operations or
/// multiple GEPs with a single index.
bool LowerGEP;
+
DenseMap<const SCEV *, SmallVector<Instruction *, 2>> DominatingExprs;
};
-} // anonymous namespace
+
+} // end anonymous namespace
char SeparateConstOffsetFromGEP::ID = 0;
+
INITIALIZE_PASS_BEGIN(
SeparateConstOffsetFromGEP, "separate-const-offset-from-gep",
"Split GEPs to a variadic base and a constant offset for better CSE", false,
OpenPOWER on IntegriCloud