Go to the documentation of this file.
91 using namespace PatternMatch;
98 class StraightLineStrengthReduceLegacyPass :
public FunctionPass {
117 bool doInitialization(
Module &M)
override {
118 DL = &
M.getDataLayout();
125 class StraightLineStrengthReduce {
141 Candidate() =
default;
155 Value *Stride =
nullptr;
175 Candidate *Basis =
nullptr;
183 bool isBasisFor(
const Candidate &Basis,
const Candidate &
C);
191 bool isSimplestForm(
const Candidate &
C);
198 void allocateCandidatesAndFindBasisForAdd(
Instruction *
I);
205 void allocateCandidatesAndFindBasisForMul(
Instruction *
I);
228 void rewriteCandidateWithBasis(
const Candidate &
C,
const Candidate &Basis);
240 static Value *emitBump(
const Candidate &Basis,
const Candidate &
C,
242 bool &BumpWithUglyGEP);
248 std::list<Candidate> Candidates;
253 std::vector<Instruction *> UnlinkedInstructions;
261 "Straight line strength reduction",
false,
false)
269 return new StraightLineStrengthReduceLegacyPass();
272 bool StraightLineStrengthReduce::isBasisFor(
const Candidate &Basis,
273 const Candidate &
C) {
274 return (Basis.Ins !=
C.Ins &&
277 Basis.Ins->getType() ==
C.Ins->getType() &&
279 DT->dominates(Basis.Ins->getParent(),
C.Ins->getParent()) &&
281 Basis.Base ==
C.Base && Basis.Stride ==
C.Stride &&
282 Basis.CandidateKind ==
C.CandidateKind);
296 return Index->getBitWidth() <= 64 &&
301 bool StraightLineStrengthReduce::isFoldable(
const Candidate &
C,
313 unsigned NumNonZeroIndices = 0;
314 for (
Use &Idx :
GEP->indices()) {
315 ConstantInt *ConstIdx = dyn_cast<ConstantInt>(Idx);
316 if (ConstIdx ==
nullptr || !ConstIdx->
isZero())
319 return NumNonZeroIndices <= 1;
322 bool StraightLineStrengthReduce::isSimplestForm(
const Candidate &
C) {
325 return C.Index->isOne() ||
C.Index->isMinusOne();
329 return C.Index->isZero();
333 return ((
C.Index->isOne() ||
C.Index->isMinusOne()) &&
346 void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
349 Candidate
C(CT,
B, Idx,
S,
I);
363 if (!isFoldable(
C,
TTI,
DL) && !isSimplestForm(
C)) {
365 unsigned NumIterations = 0;
367 static const unsigned MaxNumIterations = 50;
368 for (
auto Basis = Candidates.rbegin();
369 Basis != Candidates.rend() && NumIterations < MaxNumIterations;
370 ++Basis, ++NumIterations) {
371 if (isBasisFor(*Basis,
C)) {
379 Candidates.push_back(
C);
382 void StraightLineStrengthReduce::allocateCandidatesAndFindBasis(
384 switch (
I->getOpcode()) {
386 allocateCandidatesAndFindBasisForAdd(
I);
389 allocateCandidatesAndFindBasisForMul(
I);
391 case Instruction::GetElementPtr:
392 allocateCandidatesAndFindBasisForGEP(cast<GetElementPtrInst>(
I));
397 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
400 if (!isa<IntegerType>(
I->getType()))
403 assert(
I->getNumOperands() == 2 &&
"isn't I an add?");
405 allocateCandidatesAndFindBasisForAdd(
LHS,
RHS,
I);
407 allocateCandidatesAndFindBasisForAdd(
RHS,
LHS,
I);
410 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForAdd(
442 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
464 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForMul(
468 if (!isa<IntegerType>(
I->getType()))
471 assert(
I->getNumOperands() == 2 &&
"isn't I a mul?");
473 allocateCandidatesAndFindBasisForMul(
LHS,
RHS,
I);
476 allocateCandidatesAndFindBasisForMul(
RHS,
LHS,
I);
480 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
487 IntegerType *IntPtrTy = cast<IntegerType>(
DL->getIntPtrType(
I->getType()));
489 IntPtrTy, Idx->
getSExtValue() * (int64_t)ElementSize,
true);
493 void StraightLineStrengthReduce::factorArrayIndex(
Value *ArrayIdx,
498 allocateCandidatesAndFindBasisForGEP(
500 ArrayIdx, ElementSize,
GEP);
517 allocateCandidatesAndFindBasisForGEP(
Base,
RHS,
LHS, ElementSize,
GEP);
524 allocateCandidatesAndFindBasisForGEP(
Base, PowerOf2,
LHS, ElementSize,
GEP);
528 void StraightLineStrengthReduce::allocateCandidatesAndFindBasisForGEP(
531 if (
GEP->getType()->isVectorTy())
535 for (
Use &Idx :
GEP->indices())
536 IndexExprs.push_back(SE->getSCEV(Idx));
539 for (
unsigned I = 1,
E =
GEP->getNumOperands();
I !=
E; ++
I, ++GTI) {
543 const SCEV *OrigIndexExpr = IndexExprs[
I - 1];
544 IndexExprs[
I - 1] = SE->getZero(OrigIndexExpr->
getType());
548 const SCEV *BaseExpr = SE->getGEPExpr(cast<GEPOperator>(
GEP), IndexExprs);
552 DL->getPointerSizeInBits(
GEP->getAddressSpace())) {
555 factorArrayIndex(ArrayIdx, BaseExpr, ElementSize,
GEP);
560 Value *TruncatedArrayIdx =
nullptr;
563 DL->getPointerSizeInBits(
GEP->getAddressSpace())) {
566 factorArrayIndex(TruncatedArrayIdx, BaseExpr, ElementSize,
GEP);
569 IndexExprs[
I - 1] = OrigIndexExpr;
575 if (A.getBitWidth() <
B.getBitWidth())
576 A = A.sext(
B.getBitWidth());
577 else if (A.getBitWidth() >
B.getBitWidth())
578 B =
B.sext(A.getBitWidth());
581 Value *StraightLineStrengthReduce::emitBump(
const Candidate &Basis,
585 bool &BumpWithUglyGEP) {
586 APInt Idx =
C.Index->
getValue(), BasisIdx = Basis.Index->getValue();
588 APInt IndexOffset = Idx - BasisIdx;
590 BumpWithUglyGEP =
false;
594 DL->getTypeAllocSize(
595 cast<GetElementPtrInst>(Basis.Ins)->getResultElementType()));
601 BumpWithUglyGEP =
true;
606 if (IndexOffset == 1)
616 Value *ExtendedStride =
Builder.CreateSExtOrTrunc(
C.Stride, DeltaType);
620 return Builder.CreateShl(ExtendedStride, Exponent);
626 return Builder.CreateNeg(
Builder.CreateShl(ExtendedStride, Exponent));
629 return Builder.CreateMul(ExtendedStride, Delta);
632 void StraightLineStrengthReduce::rewriteCandidateWithBasis(
633 const Candidate &
C,
const Candidate &Basis) {
634 assert(
C.CandidateKind == Basis.CandidateKind &&
C.Base == Basis.Base &&
635 C.Stride == Basis.Stride);
638 assert(Basis.Ins->getParent() !=
nullptr &&
"the basis is unlinked");
644 if (!
C.Ins->getParent())
648 bool BumpWithUglyGEP;
650 Value *Reduced =
nullptr;
651 switch (
C.CandidateKind) {
658 Reduced =
Builder.CreateSub(Basis.Ins, NegBump);
672 Reduced =
Builder.CreateAdd(Basis.Ins, Bump);
678 Type *IntPtrTy =
DL->getIntPtrType(
C.Ins->getType());
679 bool InBounds = cast<GetElementPtrInst>(
C.Ins)->isInBounds();
680 if (BumpWithUglyGEP) {
682 unsigned AS = Basis.Ins->getType()->getPointerAddressSpace();
684 Reduced =
Builder.CreateBitCast(Basis.Ins, CharTy);
686 Builder.CreateGEP(
Builder.getInt8Ty(), Reduced, Bump,
"", InBounds);
687 Reduced =
Builder.CreateBitCast(Reduced,
C.Ins->getType());
691 Bump =
Builder.CreateSExtOrTrunc(Bump, IntPtrTy);
693 cast<GetElementPtrInst>(Basis.Ins)->getResultElementType(),
694 Basis.Ins, Bump,
"", InBounds);
702 C.Ins->replaceAllUsesWith(Reduced);
705 C.Ins->removeFromParent();
706 UnlinkedInstructions.push_back(
C.Ins);
713 auto *
TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
714 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
715 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
716 return StraightLineStrengthReduce(
DL, DT, SE,
TTI).runOnFunction(
F);
723 for (
auto &
I : *(Node->getBlock()))
724 allocateCandidatesAndFindBasis(&
I);
728 while (!Candidates.empty()) {
729 const Candidate &
C = Candidates.back();
730 if (
C.Basis !=
nullptr) {
731 rewriteCandidateWithBasis(
C, *
C.Basis);
733 Candidates.pop_back();
737 for (
auto *UnlinkedInst : UnlinkedInstructions) {
738 for (
unsigned I = 0,
E = UnlinkedInst->getNumOperands();
I !=
E; ++
I) {
739 Value *
Op = UnlinkedInst->getOperand(
I);
740 UnlinkedInst->setOperand(
I,
nullptr);
743 UnlinkedInst->deleteValue();
745 bool Ret = !UnlinkedInstructions.empty();
746 UnlinkedInstructions.clear();
759 if (!StraightLineStrengthReduce(
DL, DT, SE,
TTI).runOnFunction(
F))
A set of analyses that are preserved following a run of a transformation pass.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Analysis pass providing the TargetTransformInfo.
Analysis pass that exposes the ScalarEvolution for a function.
This is an optimization pass for GlobalISel generic memory operations.
bool haveNoCommonBitsSet(const Value *LHS, const Value *RHS, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if LHS and RHS have no common bits set.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
A parsed version of the target data layout string in and methods for querying it.
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
unsigned getBitWidth() const
getBitWidth - Return the bitwidth of this constant.
static bool isAddFoldable(const SCEV *Base, ConstantInt *Index, Value *Stride, TargetTransformInfo *TTI)
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
const APInt & getValue() const
Return the constant as an APInt value reference.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
static bool matchesOr(Value *A, Value *&B, ConstantInt *&C)
The main scalar evolution driver.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
@ Invalid
Invalid file type.
static void unifyBitWidth(APInt &A, APInt &B)
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getBitWidth() const
Return the number of bits in the APInt.
gep_type_iterator gep_type_begin(const User *GEP)
static bool isGEPFoldable(GetElementPtrInst *GEP, const TargetTransformInfo *TTI)
static bool matchesAdd(Value *A, Value *&B, ConstantInt *&C)
void initializeStraightLineStrengthReduceLegacyPassPass(PassRegistry &)
This is the shared class of boolean and integer constants.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool match(Val *V, const Pattern &P)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static bool hasOnlyOneNonZeroIndex(GetElementPtrInst *GEP)
(vector float) vec_cmpeq(*A, *B) C
Represent the analysis usage information of a pass.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Class to represent integer types.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoSignedWrap > m_NSWMul(const LHS &L, const RHS &R)
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Legacy analysis pass which computes a DominatorTree.
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
unsigned getIntegerBitWidth() const
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
This class represents an analyzed expression in the program.
This is an important base class in LLVM.
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
void preserve()
Mark an analysis as preserved.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
unsigned logBase2() const
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Type * getIndexedType() const
Straight line strength reduction
INITIALIZE_PASS_BEGIN(StraightLineStrengthReduceLegacyPass, "slsr", "Straight line strength reduction", false, false) INITIALIZE_PASS_END(StraightLineStrengthReduceLegacyPass
static const unsigned UnknownAddressSpace
A Module instance is used to store all the information related to an LLVM module.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Class for arbitrary precision integers.
CastClass_match< OpTy, Instruction::SExt > m_SExt(const OpTy &Op)
Matches SExt.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Type * getType() const
All values are typed, get the type of this value.
Represents analyses that only rely on functions' control flow.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
LLVMContext & getContext() const
All values hold a context through their type.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
iterator_range< df_iterator< T > > depth_first(const T &G)
static bool runOnFunction(Function &F, bool PostInlining)
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
bool isNegatedPowerOf2() const
Check if this APInt's negated value is a power of two greater than zero.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Shl, OverflowingBinaryOperator::NoSignedWrap > m_NSWShl(const LHS &L, const RHS &R)
Analysis pass which computes a DominatorTree.
void preserveSet()
Mark an analysis set as preserved.
FunctionPass * createStraightLineStrengthReducePass()
Align max(MaybeAlign Lhs, Align Rhs)
Type * getType() const
Return the LLVM type of this SCEV expression.
A container for analyses that lazily runs them and caches their results.
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
FunctionPass class - This class is used to implement most global optimizations.
AnalysisUsage & addRequired()
void takeName(Value *V)
Transfer the name from V to this value.
LLVM Value Representation.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
A Use represents the edge between a Value definition and its users.