//
// The LLVM Compiler Infrastructure
//
-// This file was developed by Nate Begeman and is distributed under the
-// University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Target/TargetLowering.h"
#include <algorithm>
STATISTIC(NumVariable, "Number of PHIs with variable strides");
STATISTIC(NumEliminated , "Number of strides eliminated");
+namespace {
+ // Hidden options for help debugging.
+ cl::opt<bool> AllowPHIIVReuse("lsr-allow-phi-iv-reuse",
+ cl::init(true), cl::Hidden);
+}
+
namespace {
struct BasedUser;
/// StrideOrder - An ordering of the keys in IVUsesByStride that is stable:
/// We use this to iterate over the IVUsesByStride collection without being
/// dependent on random ordering of pointers in the process.
- std::vector<SCEVHandle> StrideOrder;
+ SmallVector<SCEVHandle, 16> StrideOrder;
/// CastedValues - As we need to cast values to uintptr_t, this keeps track
/// of the casted version of each value. This is accessed by
/// getCastedVersionOf.
- std::map<Value*, Value*> CastedPointers;
+ DenseMap<Value*, Value*> CastedPointers;
/// DeadInsts - Keep track of instructions we may have made dead, so that
/// we can remove them after we are done working.
while (!Insts.empty()) {
Instruction *I = *Insts.begin();
Insts.erase(I);
+
+ if (PHINode *PN = dyn_cast<PHINode>(I)) {
+ // If all incoming values to the Phi are the same, we can replace the Phi
+ // with that value.
+ if (Value *PNV = PN->hasConstantValue()) {
+ if (Instruction *U = dyn_cast<Instruction>(PNV))
+ Insts.insert(U);
+ PN->replaceAllUsesWith(PNV);
+ SE->deleteValueFromRecords(PN);
+ PN->eraseFromParent();
+ Changed = true;
+ continue;
+ }
+ }
+
if (isInstructionTriviallyDead(I)) {
for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
if (Instruction *U = dyn_cast<Instruction>(I->getOperand(i)))
/// the loop, resulting in reg-reg copies (if we use the pre-inc value when we
/// should use the post-inc value).
static bool IVUseShouldUsePostIncValue(Instruction *User, Instruction *IV,
- Loop *L, DominatorTree *DT, Pass *P) {
+ Loop *L, DominatorTree *DT, Pass *P,
+ SmallPtrSet<Instruction*,16> &DeadInsts){
// If the user is in the loop, use the preinc value.
if (L->contains(User->getParent())) return false;
// post-incremented value.
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
if (PN->getIncomingValue(i) == IV) {
- SplitCriticalEdge(PN->getIncomingBlock(i), PN->getParent(), P,
- true);
+ SplitCriticalEdge(PN->getIncomingBlock(i), PN->getParent(), P, false);
// Splitting the critical edge can reduce the number of entries in this
// PHI.
e = PN->getNumIncomingValues();
if (--NumUses == 0) break;
}
+
+ // PHI node might have become a constant value after SplitCriticalEdge.
+ DeadInsts.insert(User);
return true;
}
// Okay, we found a user that we cannot reduce. Analyze the instruction
// and decide what to do with it. If we are a use inside of the loop, use
// the value before incrementation, otherwise use it after incrementation.
- if (IVUseShouldUsePostIncValue(User, I, L, DT, this)) {
+ if (IVUseShouldUsePostIncValue(User, I, L, DT, this, DeadInsts)) {
// The value used will be incremented by the stride more than we are
// expecting, so subtract this off.
SCEVHandle NewStart = SE->getMinusSCEV(Start, Stride);
// operands of Inst to use the new expression 'NewBase', with 'Imm' added
// to it.
void RewriteInstructionToUseNewBase(const SCEVHandle &NewBase,
- SCEVExpander &Rewriter, Loop *L,
- Pass *P);
+ SCEVExpander &Rewriter, Loop *L, Pass *P,
+ SmallPtrSet<Instruction*,16> &DeadInsts);
Value *InsertCodeForBaseAtPosition(const SCEVHandle &NewBase,
SCEVExpander &Rewriter,
// operands of Inst to use the new expression 'NewBase', with 'Imm' added
// to it.
void BasedUser::RewriteInstructionToUseNewBase(const SCEVHandle &NewBase,
- SCEVExpander &Rewriter,
- Loop *L, Pass *P) {
+ SCEVExpander &Rewriter, Loop *L, Pass *P,
+ SmallPtrSet<Instruction*,16> &DeadInsts) {
if (!isa<PHINode>(Inst)) {
// By default, insert code at the user instruction.
BasicBlock::iterator InsertPt = Inst;
// have multiple entries for the same predecessor. We use a map to make sure
// that a PHI node only has a single Value* for each predecessor (which also
// prevents us from inserting duplicate code in some blocks).
- std::map<BasicBlock*, Value*> InsertedCode;
+ DenseMap<BasicBlock*, Value*> InsertedCode;
PHINode *PN = cast<PHINode>(Inst);
for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
if (PN->getIncomingValue(i) == OperandValToReplace) {
(PN->getParent() != L->getHeader() || !L->contains(PHIPred))) {
// First step, split the critical edge.
- SplitCriticalEdge(PHIPred, PN->getParent(), P, true);
+ SplitCriticalEdge(PHIPred, PN->getParent(), P, false);
// Next step: move the basic block. In particular, if the PHI node
// is outside of the loop, and PredTI is in the loop, we want to
Rewriter.clear();
}
}
+
+ // PHI node might have become a constant value after SplitCriticalEdge.
+ DeadInsts.insert(Inst);
+
DOUT << " CHANGED: IMM =" << *Imm << " Inst = " << *Inst;
}
bool LoopStrengthReduce::ValidStride(bool HasBaseReg,
int64_t Scale,
const std::vector<BasedUser>& UsersToProcess) {
+ if (!TLI)
+ return true;
+
for (unsigned i=0, e = UsersToProcess.size(); i!=e; ++i) {
// If this is a load or other access, pass the type of the access in.
const Type *AccessTy = Type::VoidTy;
AccessTy = SI->getOperand(0)->getType();
else if (LoadInst *LI = dyn_cast<LoadInst>(UsersToProcess[i].Inst))
AccessTy = LI->getType();
+ else if (isa<PHINode>(UsersToProcess[i].Inst)) {
+ if (AllowPHIIVReuse)
+ continue;
+ return false;
+ }
TargetLowering::AddrMode AM;
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(UsersToProcess[i].Imm))
AM.Scale = Scale;
// If load[imm+r*scale] is illegal, bail out.
- if (TLI && !TLI->isLegalAddressingMode(AM, AccessTy))
+ if (!TLI->isLegalAddressingMode(AM, AccessTy))
return false;
}
return true;
const std::vector<BasedUser>& UsersToProcess) {
if (SCEVConstant *SC = dyn_cast<SCEVConstant>(Stride)) {
int64_t SInt = SC->getValue()->getSExtValue();
- for (std::map<SCEVHandle, IVsOfOneStride>::iterator SI= IVsByStride.begin(),
- SE = IVsByStride.end(); SI != SE; ++SI) {
+ for (unsigned NewStride = 0, e = StrideOrder.size(); NewStride != e;
+ ++NewStride) {
+ std::map<SCEVHandle, IVsOfOneStride>::iterator SI =
+ IVsByStride.find(StrideOrder[NewStride]);
+ if (SI == IVsByStride.end())
+ continue;
int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue();
if (SI->first != Stride &&
(unsigned(abs(SInt)) < SSInt || (SInt % SSInt) != 0))
return SC->getValue()->getValue().isNegative();
}
+/// isAddress - Returns true if the specified instruction is using the
+/// specified value as an address.
+static bool isAddressUse(Instruction *Inst, Value *OperandVal) {
+ bool isAddress = isa<LoadInst>(Inst);
+ if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
+ if (SI->getOperand(1) == OperandVal)
+ isAddress = true;
+ } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
+ // Addressing modes can also be folded into prefetches and a variety
+ // of intrinsics.
+ switch (II->getIntrinsicID()) {
+ default: break;
+ case Intrinsic::prefetch:
+ case Intrinsic::x86_sse2_loadu_dq:
+ case Intrinsic::x86_sse2_loadu_pd:
+ case Intrinsic::x86_sse_loadu_ps:
+ case Intrinsic::x86_sse_storeu_ps:
+ case Intrinsic::x86_sse2_storeu_pd:
+ case Intrinsic::x86_sse2_storeu_dq:
+ case Intrinsic::x86_sse2_storel_dq:
+ if (II->getOperand(1) == OperandVal)
+ isAddress = true;
+ break;
+ case Intrinsic::x86_sse2_loadh_pd:
+ case Intrinsic::x86_sse2_loadl_pd:
+ if (II->getOperand(2) == OperandVal)
+ isAddress = true;
+ break;
+ }
+ }
+ return isAddress;
+}
+
// CollectIVUsers - Transform our list of users and offsets to a bit more
// complex table. In this new vector, each 'BasedUser' contains 'Base' the base
// of the strided accessas well as the old information from Uses. We
// instructions. If we can represent anything there, move it to the imm
// fields of the BasedUsers. We do this so that it increases the commonality
// of the remaining uses.
+ unsigned NumPHI = 0;
for (unsigned i = 0, e = UsersToProcess.size(); i != e; ++i) {
// If the user is not in the current loop, this means it is using the exit
// value of the IV. Do not put anything in the base, make sure it's all in
// Addressing modes can be folded into loads and stores. Be careful that
// the store is through the expression, not of the expression though.
- bool isAddress = isa<LoadInst>(UsersToProcess[i].Inst);
- if (StoreInst *SI = dyn_cast<StoreInst>(UsersToProcess[i].Inst)) {
- if (SI->getOperand(1) == UsersToProcess[i].OperandValToReplace)
- isAddress = true;
- } else if (IntrinsicInst *II =
- dyn_cast<IntrinsicInst>(UsersToProcess[i].Inst)) {
- // Addressing modes can also be folded into prefetches and a variety
- // of intrinsics.
- switch (II->getIntrinsicID()) {
- default: break;
- case Intrinsic::prefetch:
- case Intrinsic::x86_sse2_loadu_dq:
- case Intrinsic::x86_sse2_loadu_pd:
- case Intrinsic::x86_sse_loadu_ps:
- case Intrinsic::x86_sse_storeu_ps:
- case Intrinsic::x86_sse2_storeu_pd:
- case Intrinsic::x86_sse2_storeu_dq:
- case Intrinsic::x86_sse2_storel_dq:
- if (II->getOperand(1) == UsersToProcess[i].OperandValToReplace)
- isAddress = true;
- break;
- case Intrinsic::x86_sse2_loadh_pd:
- case Intrinsic::x86_sse2_loadl_pd:
- if (II->getOperand(2) == UsersToProcess[i].OperandValToReplace)
- isAddress = true;
- break;
- }
+ bool isPHI = false;
+ bool isAddress = isAddressUse(UsersToProcess[i].Inst,
+ UsersToProcess[i].OperandValToReplace);
+ if (isa<PHINode>(UsersToProcess[i].Inst)) {
+ isPHI = true;
+ ++NumPHI;
}
// If this use isn't an address, then not all uses are addresses.
- if (!isAddress)
+ if (!isAddress && !(AllowPHIIVReuse && isPHI))
AllUsesAreAddresses = false;
MoveImmediateValues(TLI, UsersToProcess[i].Inst, UsersToProcess[i].Base,
}
}
+ // If one of the use if a PHI node and all other uses are addresses, still
+ // allow iv reuse. Essentially we are trading one constant multiplication
+ // for one fewer iv.
+ if (NumPHI > 1)
+ AllUsesAreAddresses = false;
+
return CommonExprs;
}
Loop *L,
bool isOnlyStride) {
// If all the users are moved to another stride, then there is nothing to do.
- if (Uses.Users.size() == 0)
+ if (Uses.Users.empty())
return;
// Keep track if every use in UsersToProcess is an address. If they all are,
// Get a base value.
SCEVHandle Base = UsersToProcess[i].Base;
- // Compact everything with this base to be consequetive with this one.
+ // Compact everything with this base to be consequtive with this one.
for (unsigned j = i+1; j != e; ++j) {
if (UsersToProcess[j].Base == Base) {
std::swap(UsersToProcess[i+1], UsersToProcess[j]);
// If we are reusing the iv, then it must be multiplied by a constant
// factor take advantage of addressing mode scale component.
if (RewriteFactor != 0) {
- RewriteExpr =
- SE->getMulExpr(SE->getIntegerSCEV(RewriteFactor,
- RewriteExpr->getType()),
- RewriteExpr);
+ RewriteExpr = SE->getMulExpr(SE->getIntegerSCEV(RewriteFactor,
+ RewriteExpr->getType()),
+ RewriteExpr);
// The common base is emitted in the loop preheader. But since we
// are reusing an IV, it has not been used to initialize the PHI node.
// Add BaseV to the PHI value if needed.
RewriteExpr = SE->getAddExpr(RewriteExpr, SE->getUnknown(BaseV));
- User.RewriteInstructionToUseNewBase(RewriteExpr, Rewriter, L, this);
+ User.RewriteInstructionToUseNewBase(RewriteExpr, Rewriter, L, this,
+ DeadInsts);
// Mark old value we replaced as possibly dead, so that it is elminated
// if we just replaced the last use of that value.
/// v1 = v1 + 3
/// if (v1 < 30) goto loop
ICmpInst *LoopStrengthReduce::ChangeCompareStride(Loop *L, ICmpInst *Cond,
- IVStrideUse* &CondUse,
+ IVStrideUse* &CondUse,
const SCEVHandle* &CondStride) {
if (StrideOrder.size() < 2 ||
IVUsesByStride[*CondStride].Users.size() != 1)
PHINode *PN;
while ((PN = dyn_cast<PHINode>(I))) {
++I; // Preincrement iterator to avoid invalidating it when deleting PN.
-
+
// At this point, we know that we have killed one or more GEP
// instructions. It is worth checking to see if the cann indvar is also
// dead, so that we can remove it as well. The requirements for the cann
projects / oota-llvm.git / blobdiff