#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/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;
bool StraightLineStrengthReduce::isBasisFor(const Candidate &Basis,
const Candidate &C) {
return (Basis.Ins != C.Ins && // skip the same instruction
+ // They must have the same type too. Basis.Base == C.Base doesn't
+ // guarantee their types are the same (PR23975).
+ Basis.Ins->getType() == C.Ins->getType() &&
// Basis must dominate C in order to rewrite C with respect to Basis.
DT->dominates(Basis.Ins->getParent(), C.Ins->getParent()) &&
// They share the same base, stride, and candidate kind.
- Basis.Base == C.Base &&
- Basis.Stride == C.Stride &&
+ Basis.Base == C.Base && Basis.Stride == C.Stride &&
Basis.CandidateKind == C.CandidateKind);
}
+// TODO: use TTI->getGEPCost.
static bool isGEPFoldable(GetElementPtrInst *GEP,
const TargetTransformInfo *TTI,
const DataLayout *DL) {
BaseOffset += DL->getStructLayout(STy)->getElementOffset(Field);
}
}
+
+ unsigned AddrSpace = GEP->getPointerAddressSpace();
return TTI->isLegalAddressingMode(GEP->getType()->getElementType(), BaseGV,
- BaseOffset, HasBaseReg, Scale);
+ BaseOffset, HasBaseReg, Scale, AddrSpace);
}
// Returns whether (Base + Index * Stride) can be folded to an addressing mode.
}
}
+// Returns true if A matches B + C where C is constant.
+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))));
+}
+
+// Returns true if A matches B | C where C is constant.
+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;
- // Only handle the canonical operand ordering.
- if (match(LHS, m_Add(m_Value(B), m_ConstantInt(Idx)))) {
+ if (matchesAdd(LHS, B, Idx)) {
// If LHS is in the form of "Base + Index", then I is in the form of
// "(Base + Index) * RHS".
allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I);
+ } else if (matchesOr(LHS, B, Idx) && haveNoCommonBitsSet(B, Idx, *DL)) {
+ // If LHS is in the form of "Base | Index" and Base and Index have no common
+ // bits set, then
+ // Base | Index = Base + Index
+ // and I is thus in the form of "(Base + Index) * RHS".
+ allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(B), Idx, RHS, I);
} else {
// Otherwise, at least try the form (LHS + 0) * RHS.
ConstantInt *Zero = ConstantInt::get(cast<IntegerType>(I->getType()), 0);
allocateCandidatesAndFindBasis(Candidate::Mul, SE->getSCEV(LHS), Zero, RHS,
- I);
+ I);
}
}
if (GEP->getType()->isVectorTy())
return;
- const SCEV *GEPExpr = SE->getSCEV(GEP);
- Type *IntPtrTy = DL->getIntPtrType(GEP->getType());
+ 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 (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I) {
+ for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I) {
if (!isa<SequentialType>(*GTI++))
continue;
- Value *ArrayIdx = *I;
- // Compute the byte offset of this index.
+
+ const SCEV *OrigIndexExpr = IndexExprs[I - 1];
+ IndexExprs[I - 1] = SE->getConstant(OrigIndexExpr->getType(), 0);
+
+ // The base of this candidate is GEP's base plus the offsets of all
+ // indices except this current one.
+ 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);
- const SCEV *ElementSizeExpr = SE->getSizeOfExpr(IntPtrTy, *GTI);
- const SCEV *ArrayIdxExpr = SE->getSCEV(ArrayIdx);
- ArrayIdxExpr = SE->getTruncateOrSignExtend(ArrayIdxExpr, IntPtrTy);
- const SCEV *LocalOffset =
- SE->getMulExpr(ArrayIdxExpr, ElementSizeExpr, SCEV::FlagNSW);
- // The base of this candidate equals GEPExpr less the byte offset of this
- // index.
- const SCEV *Base = SE->getMinusSCEV(GEPExpr, LocalOffset);
- factorArrayIndex(ArrayIdx, Base, ElementSize, GEP);
+ factorArrayIndex(ArrayIdx, BaseExpr, ElementSize, GEP);
// When ArrayIdx is the sext of a value, we try to factor that value as
// well. Handling this case is important because array indices are
// typically sign-extended to the pointer size.
Value *TruncatedArrayIdx = nullptr;
if (match(ArrayIdx, m_SExt(m_Value(TruncatedArrayIdx))))
- factorArrayIndex(TruncatedArrayIdx, Base, ElementSize, GEP);
+ factorArrayIndex(TruncatedArrayIdx, BaseExpr, ElementSize, GEP);
+
+ IndexExprs[I - 1] = OrigIndexExpr;
}
}
switch (C.CandidateKind) {
case Candidate::Add:
case Candidate::Mul:
+ // C = Basis + Bump
if (BinaryOperator::isNeg(Bump)) {
+ // If Bump is a neg instruction, emit C = Basis - (-Bump).
Reduced =
Builder.CreateSub(Basis.Ins, BinaryOperator::getNegArgument(Bump));
+ // We only use the negative argument of Bump, and Bump itself may be
+ // trivially dead.
+ RecursivelyDeleteTriviallyDeadInstructions(Bump);
} else {
+ // It's tempting to preserve nsw on Bump and/or Reduced. However, it's
+ // usually unsound, e.g.,
+ //
+ // X = (-2 +nsw 1) *nsw INT_MAX
+ // Y = (-2 +nsw 3) *nsw INT_MAX
+ // =>
+ // Y = X + 2 * INT_MAX
+ //
+ // Neither + and * in the resultant expression are nsw.
Reduced = Builder.CreateAdd(Basis.Ins, Bump);
}
break;
};
Reduced->takeName(C.Ins);
C.Ins->replaceAllUsesWith(Reduced);
- C.Ins->dropAllReferences();
// Unlink C.Ins so that we can skip other candidates also corresponding to
// C.Ins. The actual deletion is postponed to the end of runOnFunction.
C.Ins->removeFromParent();
}
// Delete all unlink instructions.
- for (auto I : UnlinkedInstructions) {
- delete I;
+ 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();