StraightLineStrengthReduce.cpp [plain text]
#include <vector>
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
using namespace llvm;
using namespace PatternMatch;
namespace {
class StraightLineStrengthReduce : public FunctionPass {
public:
struct Candidate : public ilist_node<Candidate> {
enum Kind {
Invalid, Add, Mul, GEP, };
Candidate()
: CandidateKind(Invalid), Base(nullptr), Index(nullptr),
Stride(nullptr), Ins(nullptr), Basis(nullptr) {}
Candidate(Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,
Instruction *I)
: CandidateKind(CT), Base(B), Index(Idx), Stride(S), Ins(I),
Basis(nullptr) {}
Kind CandidateKind;
const SCEV *Base;
ConstantInt *Index;
Value *Stride;
Instruction *Ins;
Candidate *Basis;
};
static char ID;
StraightLineStrengthReduce()
: FunctionPass(ID), DL(nullptr), DT(nullptr), TTI(nullptr) {
initializeStraightLineStrengthReducePass(*PassRegistry::getPassRegistry());
}
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<DominatorTreeWrapperPass>();
AU.addRequired<ScalarEvolutionWrapperPass>();
AU.addRequired<TargetTransformInfoWrapperPass>();
AU.setPreservesCFG();
}
bool doInitialization(Module &M) override {
DL = &M.getDataLayout();
return false;
}
bool runOnFunction(Function &F) override;
private:
bool isBasisFor(const Candidate &Basis, const Candidate &C);
bool isFoldable(const Candidate &C, TargetTransformInfo *TTI,
const DataLayout *DL);
bool isSimplestForm(const Candidate &C);
void allocateCandidatesAndFindBasis(Instruction *I);
void allocateCandidatesAndFindBasisForAdd(Instruction *I);
void allocateCandidatesAndFindBasisForAdd(Value *LHS, Value *RHS,
Instruction *I);
void allocateCandidatesAndFindBasisForMul(Instruction *I);
void allocateCandidatesAndFindBasisForMul(Value *LHS, Value *RHS,
Instruction *I);
void allocateCandidatesAndFindBasisForGEP(GetElementPtrInst *GEP);
void allocateCandidatesAndFindBasisForGEP(const SCEV *B, ConstantInt *Idx,
Value *S, uint64_t ElementSize,
Instruction *I);
void allocateCandidatesAndFindBasis(Candidate::Kind CT, const SCEV *B,
ConstantInt *Idx, Value *S,
Instruction *I);
void rewriteCandidateWithBasis(const Candidate &C, const Candidate &Basis);
void factorArrayIndex(Value *ArrayIdx, const SCEV *Base, uint64_t ElementSize,
GetElementPtrInst *GEP);
static Value *emitBump(const Candidate &Basis, const Candidate &C,
IRBuilder<> &Builder, const DataLayout *DL,
bool &BumpWithUglyGEP);
const DataLayout *DL;
DominatorTree *DT;
ScalarEvolution *SE;
TargetTransformInfo *TTI;
ilist<Candidate> Candidates;
std::vector<Instruction *> UnlinkedInstructions;
};
}
char StraightLineStrengthReduce::ID = 0;
INITIALIZE_PASS_BEGIN(StraightLineStrengthReduce, "slsr",
"Straight line strength reduction", false, false)
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
INITIALIZE_PASS_END(StraightLineStrengthReduce, "slsr",
"Straight line strength reduction", false, false)
FunctionPass *llvm::createStraightLineStrengthReducePass() {
return new StraightLineStrengthReduce();
}
bool StraightLineStrengthReduce::isBasisFor(const Candidate &Basis,
const Candidate &C) {
return (Basis.Ins != C.Ins && Basis.Ins->getType() == C.Ins->getType() &&
DT->dominates(Basis.Ins->getParent(), C.Ins->getParent()) &&
Basis.Base == C.Base && Basis.Stride == C.Stride &&
Basis.CandidateKind == C.CandidateKind);
}
static bool isGEPFoldable(GetElementPtrInst *GEP,
const TargetTransformInfo *TTI,
const DataLayout *DL) {
GlobalVariable *BaseGV = nullptr;
int64_t BaseOffset = 0;
bool HasBaseReg = false;
int64_t Scale = 0;
if (GlobalVariable *GV = dyn_cast<GlobalVariable>(GEP->getPointerOperand()))
BaseGV = GV;
else
HasBaseReg = true;
gep_type_iterator GTI = gep_type_begin(GEP);
for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I, ++GTI) {
if (isa<SequentialType>(*GTI)) {
int64_t ElementSize = DL->getTypeAllocSize(GTI.getIndexedType());
if (ConstantInt *ConstIdx = dyn_cast<ConstantInt>(*I)) {
BaseOffset += ConstIdx->getSExtValue() * ElementSize;
} else {
if (Scale != 0) {
return false;
}
Scale = ElementSize;
}
} else {
StructType *STy = cast<StructType>(*GTI);
uint64_t Field = cast<ConstantInt>(*I)->getZExtValue();
BaseOffset += DL->getStructLayout(STy)->getElementOffset(Field);
}
}
unsigned AddrSpace = GEP->getPointerAddressSpace();
return TTI->isLegalAddressingMode(GEP->getType()->getElementType(), BaseGV,
BaseOffset, HasBaseReg, Scale, AddrSpace);
}
static bool isAddFoldable(const SCEV *Base, ConstantInt *Index, Value *Stride,
TargetTransformInfo *TTI) {
return TTI->isLegalAddressingMode(Base->getType(), nullptr, 0, true,
Index->getSExtValue());
}
bool StraightLineStrengthReduce::isFoldable(const Candidate &C,
TargetTransformInfo *TTI,
const DataLayout *DL) {
if (C.CandidateKind == Candidate::Add)
return isAddFoldable(C.Base, C.Index, C.Stride, TTI);
if (C.CandidateKind == Candidate::GEP)
return isGEPFoldable(cast<GetElementPtrInst>(C.Ins), TTI, DL);
return false;
}
static bool hasOnlyOneNonZeroIndex(GetElementPtrInst *GEP) {
unsigned NumNonZeroIndices = 0;
for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I) {
ConstantInt *ConstIdx = dyn_cast<ConstantInt>(*I);
if (ConstIdx == nullptr || !ConstIdx->isZero())
++NumNonZeroIndices;
}
return NumNonZeroIndices <= 1;
}
bool StraightLineStrengthReduce::isSimplestForm(const Candidate &C) {
if (C.CandidateKind == Candidate::Add) {
return C.Index->isOne() || C.Index->isMinusOne();
}
if (C.CandidateKind == Candidate::Mul) {
return C.Index->isZero();
}
if (C.CandidateKind == Candidate::GEP) {
return ((C.Index->isOne() || C.Index->isMinusOne()) &&
hasOnlyOneNonZeroIndex(cast<GetElementPtrInst>(C.Ins)));
}
return false;
}
void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
Candidate::Kind CT, const SCEV *B, ConstantInt *Idx, Value *S,
Instruction *I) {
Candidate C(CT, B, Idx, S, I);
if (!isFoldable(C, TTI, DL) && !isSimplestForm(C)) {
unsigned NumIterations = 0;
static const unsigned MaxNumIterations = 50;
for (auto Basis = Candidates.rbegin();
Basis != Candidates.rend() && NumIterations < MaxNumIterations;
++Basis, ++NumIterations) {
if (isBasisFor(*Basis, C)) {
C.Basis = &(*Basis);
break;
}
}
}
Candidates.push_back(C);
}
void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
Instruction *I) {
switch (I->getOpcode()) {
case Instruction::Add:
allocateCandidatesAndFindBasisForAdd(I);
break;
case Instruction::Mul:
allocateCandidatesAndFindBasisForMul(I);
break;
case Instruction::GetElementPtr:
allocateCandidatesAndFindBasisForGEP(cast<GetElementPtrInst>(I));
break;
}
}
void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
Instruction *I) {
if (!isa<IntegerType>(I->getType()))
return;
assert(I->getNumOperands() == 2 && "isn't I an add?");
Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
allocateCandidatesAndFindBasisForAdd(LHS, RHS, I);
if (LHS != RHS)
allocateCandidatesAndFindBasisForAdd(RHS, LHS, I);
}
void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
Value *LHS, Value *RHS, Instruction *I) {
Value *S = nullptr;
ConstantInt *Idx = nullptr;
if (match(RHS, m_Mul(m_Value(S), m_ConstantInt(Idx)))) {
allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), Idx, S, I);
} else if (match(RHS, m_Shl(m_Value(S), m_ConstantInt(Idx)))) {
APInt One(Idx->getBitWidth(), 1);
Idx = ConstantInt::get(Idx->getContext(), One << Idx->getValue());
allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), Idx, S, I);
} else {
ConstantInt *One = ConstantInt::get(cast<IntegerType>(I->getType()), 1);
allocateCandidatesAndFindBasis(Candidate::Add, SE->getSCEV(LHS), One, RHS,
I);
}
}
static bool matchesAdd(Value *A, Value *&B, ConstantInt *&C) {
return (match(A, m_Add(m_Value(B), m_ConstantInt(C))) ||
match(A, m_Add(m_ConstantInt(C), m_Value(B))));
}
static bool matchesOr(Value *A, Value *&B, ConstantInt *&C) {
return (match(A, m_Or(m_Value(B), m_ConstantInt(C))) ||
match(A, m_Or(m_ConstantInt(C), m_Value(B))));
}
void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
Value *LHS, Value *RHS, Instruction *I) {
Value *B = nullptr;
ConstantInt *Idx = nullptr;
if (matchesAdd(LHS, B, Idx)) {
allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I);
} else if (matchesOr(LHS, B, Idx) && haveNoCommonBitsSet(B, Idx, *DL)) {
allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I);
} else {
ConstantInt *Zero = ConstantInt::get(cast<IntegerType>(I->getType()), 0);
allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(LHS), Zero, RHS,
I);
}
}
void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
Instruction *I) {
if (!isa<IntegerType>(I->getType()))
return;
assert(I->getNumOperands() == 2 && "isn't I a mul?");
Value *LHS = I->getOperand(0), *RHS = I->getOperand(1);
allocateCandidatesAndFindBasisForMul(LHS, RHS, I);
if (LHS != RHS) {
allocateCandidatesAndFindBasisForMul(RHS, LHS, I);
}
}
void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
const SCEV *B, ConstantInt *Idx, Value *S, uint64_t ElementSize,
Instruction *I) {
IntegerType *IntPtrTy = cast<IntegerType>(DL->getIntPtrType(I->getType()));
ConstantInt *ScaledIdx = ConstantInt::get(
IntPtrTy, Idx->getSExtValue() * (int64_t)ElementSize, true);
allocateCandidatesAndFindBasis(Candidate::GEP, B, ScaledIdx, S, I);
}
void StraightLineStrengthReduce::factorArrayIndex(Value *ArrayIdx,
const SCEV *Base,
uint64_t ElementSize,
GetElementPtrInst *GEP) {
allocateCandidatesAndFindBasisForGEP(
Base, ConstantInt::get(cast<IntegerType>(ArrayIdx->getType()), 1),
ArrayIdx, ElementSize, GEP);
Value *LHS = nullptr;
ConstantInt *RHS = nullptr;
if (match(ArrayIdx, m_NSWMul(m_Value(LHS), m_ConstantInt(RHS)))) {
allocateCandidatesAndFindBasisForGEP(Base, RHS, LHS, ElementSize, GEP);
} else if (match(ArrayIdx, m_NSWShl(m_Value(LHS), m_ConstantInt(RHS)))) {
APInt One(RHS->getBitWidth(), 1);
ConstantInt *PowerOf2 =
ConstantInt::get(RHS->getContext(), One << RHS->getValue());
allocateCandidatesAndFindBasisForGEP(Base, PowerOf2, LHS, ElementSize, GEP);
}
}
void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
GetElementPtrInst *GEP) {
if (GEP->getType()->isVectorTy())
return;
SmallVector<const SCEV *, 4> IndexExprs;
for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I)
IndexExprs.push_back(SE->getSCEV(*I));
gep_type_iterator GTI = gep_type_begin(GEP);
for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I) {
if (!isa<SequentialType>(*GTI++))
continue;
const SCEV *OrigIndexExpr = IndexExprs[I - 1];
IndexExprs[I - 1] = SE->getZero(OrigIndexExpr->getType());
const SCEV *BaseExpr = SE->getGEPExpr(GEP->getSourceElementType(),
SE->getSCEV(GEP->getPointerOperand()),
IndexExprs, GEP->isInBounds());
Value *ArrayIdx = GEP->getOperand(I);
uint64_t ElementSize = DL->getTypeAllocSize(*GTI);
factorArrayIndex(ArrayIdx, BaseExpr, ElementSize, GEP);
Value *TruncatedArrayIdx = nullptr;
if (match(ArrayIdx, m_SExt(m_Value(TruncatedArrayIdx))))
factorArrayIndex(TruncatedArrayIdx, BaseExpr, ElementSize, GEP);
IndexExprs[I - 1] = OrigIndexExpr;
}
}
static void unifyBitWidth(APInt &A, APInt &B) {
if (A.getBitWidth() < B.getBitWidth())
A = A.sext(B.getBitWidth());
else if (A.getBitWidth() > B.getBitWidth())
B = B.sext(A.getBitWidth());
}
Value *StraightLineStrengthReduce::emitBump(const Candidate &Basis,
const Candidate &C,
IRBuilder<> &Builder,
const DataLayout *DL,
bool &BumpWithUglyGEP) {
APInt Idx = C.Index->getValue(), BasisIdx = Basis.Index->getValue();
unifyBitWidth(Idx, BasisIdx);
APInt IndexOffset = Idx - BasisIdx;
BumpWithUglyGEP = false;
if (Basis.CandidateKind == Candidate::GEP) {
APInt ElementSize(
IndexOffset.getBitWidth(),
DL->getTypeAllocSize(
cast<GetElementPtrInst>(Basis.Ins)->getType()->getElementType()));
APInt Q, R;
APInt::sdivrem(IndexOffset, ElementSize, Q, R);
if (R.getSExtValue() == 0)
IndexOffset = Q;
else
BumpWithUglyGEP = true;
}
if (IndexOffset.getSExtValue() == 1)
return C.Stride;
if (IndexOffset.getSExtValue() == -1)
return Builder.CreateNeg(C.Stride);
IntegerType *DeltaType =
IntegerType::get(Basis.Ins->getContext(), IndexOffset.getBitWidth());
Value *ExtendedStride = Builder.CreateSExtOrTrunc(C.Stride, DeltaType);
if (IndexOffset.isPowerOf2()) {
ConstantInt *Exponent = ConstantInt::get(DeltaType, IndexOffset.logBase2());
return Builder.CreateShl(ExtendedStride, Exponent);
}
if ((-IndexOffset).isPowerOf2()) {
ConstantInt *Exponent =
ConstantInt::get(DeltaType, (-IndexOffset).logBase2());
return Builder.CreateNeg(Builder.CreateShl(ExtendedStride, Exponent));
}
Constant *Delta = ConstantInt::get(DeltaType, IndexOffset);
return Builder.CreateMul(ExtendedStride, Delta);
}
void StraightLineStrengthReduce::rewriteCandidateWithBasis(
const Candidate &C, const Candidate &Basis) {
assert(C.CandidateKind == Basis.CandidateKind && C.Base == Basis.Base &&
C.Stride == Basis.Stride);
assert(Basis.Ins->getParent() != nullptr && "the basis is unlinked");
if (!C.Ins->getParent())
return;
IRBuilder<> Builder(C.Ins);
bool BumpWithUglyGEP;
Value *Bump = emitBump(Basis, C, Builder, DL, BumpWithUglyGEP);
Value *Reduced = nullptr; switch (C.CandidateKind) {
case Candidate::Add:
case Candidate::Mul:
if (BinaryOperator::isNeg(Bump)) {
Reduced =
Builder.CreateSub(Basis.Ins, BinaryOperator::getNegArgument(Bump));
RecursivelyDeleteTriviallyDeadInstructions(Bump);
} else {
Reduced = Builder.CreateAdd(Basis.Ins, Bump);
}
break;
case Candidate::GEP:
{
Type *IntPtrTy = DL->getIntPtrType(C.Ins->getType());
bool InBounds = cast<GetElementPtrInst>(C.Ins)->isInBounds();
if (BumpWithUglyGEP) {
unsigned AS = Basis.Ins->getType()->getPointerAddressSpace();
Type *CharTy = Type::getInt8PtrTy(Basis.Ins->getContext(), AS);
Reduced = Builder.CreateBitCast(Basis.Ins, CharTy);
if (InBounds)
Reduced =
Builder.CreateInBoundsGEP(Builder.getInt8Ty(), Reduced, Bump);
else
Reduced = Builder.CreateGEP(Builder.getInt8Ty(), Reduced, Bump);
Reduced = Builder.CreateBitCast(Reduced, C.Ins->getType());
} else {
Bump = Builder.CreateSExtOrTrunc(Bump, IntPtrTy);
if (InBounds)
Reduced = Builder.CreateInBoundsGEP(nullptr, Basis.Ins, Bump);
else
Reduced = Builder.CreateGEP(nullptr, Basis.Ins, Bump);
}
}
break;
default:
llvm_unreachable("C.CandidateKind is invalid");
};
Reduced->takeName(C.Ins);
C.Ins->replaceAllUsesWith(Reduced);
C.Ins->removeFromParent();
UnlinkedInstructions.push_back(C.Ins);
}
bool StraightLineStrengthReduce::runOnFunction(Function &F) {
if (skipOptnoneFunction(F))
return false;
TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
for (auto node = GraphTraits<DominatorTree *>::nodes_begin(DT);
node != GraphTraits<DominatorTree *>::nodes_end(DT); ++node) {
for (auto &I : *node->getBlock())
allocateCandidatesAndFindBasis(&I);
}
while (!Candidates.empty()) {
const Candidate &C = Candidates.back();
if (C.Basis != nullptr) {
rewriteCandidateWithBasis(C, *C.Basis);
}
Candidates.pop_back();
}
for (auto *UnlinkedInst : UnlinkedInstructions) {
for (unsigned I = 0, E = UnlinkedInst->getNumOperands(); I != E; ++I) {
Value *Op = UnlinkedInst->getOperand(I);
UnlinkedInst->setOperand(I, nullptr);
RecursivelyDeleteTriviallyDeadInstructions(Op);
}
delete UnlinkedInst;
}
bool Ret = !UnlinkedInstructions.empty();
UnlinkedInstructions.clear();
return Ret;
}