#include "llvm/Support/Debug.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/ValueHandle.h"
#include "llvm/Target/TargetLowering.h"
#include <algorithm>
using namespace llvm;
AU.addPreserved<ScalarEvolution>();
}
-private:
+ private:
bool AddUsersIfInteresting(Instruction *I, Loop *L,
SmallPtrSet<Instruction*,16> &Processed);
ICmpInst *ChangeCompareStride(Loop *L, ICmpInst *Cond,
return containsAddRecFromDifferentLoop(DE->getLHS(), L) ||
containsAddRecFromDifferentLoop(DE->getRHS(), L);
#endif
- if (const SCEVTruncateExpr *TE = dyn_cast<SCEVTruncateExpr>(S))
- return containsAddRecFromDifferentLoop(TE->getOperand(), L);
- if (const SCEVZeroExtendExpr *ZE = dyn_cast<SCEVZeroExtendExpr>(S))
- return containsAddRecFromDifferentLoop(ZE->getOperand(), L);
- if (const SCEVSignExtendExpr *SE = dyn_cast<SCEVSignExtendExpr>(S))
- return containsAddRecFromDifferentLoop(SE->getOperand(), L);
+ if (const SCEVCastExpr *CE = dyn_cast<SCEVCastExpr>(S))
+ return containsAddRecFromDifferentLoop(CE->getOperand(), L);
return false;
}
// for a nested AddRecExpr.
if (const SCEVAddExpr *AE = dyn_cast<SCEVAddExpr>(SH)) {
for (unsigned i = 0, e = AE->getNumOperands(); i != e; ++i)
- if (SCEVAddRecExpr *AddRec =
+ if (const SCEVAddRecExpr *AddRec =
dyn_cast<SCEVAddRecExpr>(AE->getOperand(i))) {
if (AddRec->getLoop() == L)
TheAddRec = SE->getAddExpr(AddRec, TheAddRec);
}
// Okay, all uses of IV by PN are in predecessor blocks that really are
- // dominated by the latch block. Split the critical edges and use the
- // 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, 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.push_back(User);
-
+ // dominated by the latch block. Use the post-incremented value.
return true;
}
if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(V))
if (GlobalValue *GV = dyn_cast<GlobalValue>(SU->getValue())) {
- TargetLowering::AddrMode AM;
- AM.BaseGV = GV;
- AM.HasBaseReg = HasBaseReg;
- return TLI->isLegalAddressingMode(AM, UseTy);
+ if (TLI) {
+ TargetLowering::AddrMode AM;
+ AM.BaseGV = GV;
+ AM.HasBaseReg = HasBaseReg;
+ return TLI->isLegalAddressingMode(AM, UseTy);
+ } else {
+ // Default: assume global addresses are not legal.
+ }
}
return false;
const Type *Ty2) {
if (Ty1 == Ty2)
return false;
- if (SE->getEffectiveSCEVType(Ty1) == SE->getEffectiveSCEVType(Ty2))
+ Ty1 = SE->getEffectiveSCEVType(Ty1);
+ Ty2 = SE->getEffectiveSCEVType(Ty2);
+ if (Ty1 == Ty2)
return false;
if (Ty1->canLosslesslyBitCastTo(Ty2))
return false;
// Iterate through the uses to find conditions that automatically rule out
// full-lsr mode.
for (unsigned i = 0, e = UsersToProcess.size(); i != e; ) {
- SCEV *Base = UsersToProcess[i].Base;
- SCEV *Imm = UsersToProcess[i].Imm;
+ const SCEV *Base = UsersToProcess[i].Base;
+ const SCEV *Imm = UsersToProcess[i].Imm;
// If any users have a loop-variant component, they can't be fully
// strength-reduced.
if (Imm && !Imm->isLoopInvariant(L))
// the two Imm values can't be folded into the address, full
// strength reduction would increase register pressure.
do {
- SCEV *CurImm = UsersToProcess[i].Imm;
+ const SCEV *CurImm = UsersToProcess[i].Imm;
if ((CurImm || Imm) && CurImm != Imm) {
if (!CurImm) CurImm = SE->getIntegerSCEV(0, Stride->getType());
if (!Imm) Imm = SE->getIntegerSCEV(0, Stride->getType());
DOUT << " Examining use ";
DEBUG(WriteAsOperand(*DOUT, UsersToProcess.back().OperandValToReplace,
/*PrintType=*/false));
- DOUT << " in Inst: " << *Inst;
+ DOUT << " in Inst: " << *(User.Inst);
// If this instruction wants to use the post-incremented value, move it
// after the post-inc and use its value instead of the PHI.
if (!isa<SCEVConstant>(SI->first))
continue;
int64_t SSInt = cast<SCEVConstant>(SI->first)->getValue()->getSExtValue();
- if (abs(SSInt) <= abs(CmpSSInt) || (SSInt % CmpSSInt) != 0)
+ if (SSInt == CmpSSInt ||
+ abs(SSInt) < abs(CmpSSInt) ||
+ (SSInt % CmpSSInt) != 0)
continue;
Scale = SSInt / CmpSSInt;
CondUse = &IVUsesByStride[*NewStride].Users.back();
CondStride = NewStride;
++NumEliminated;
+ Changed = true;
}
return Cond;
StrideOrder.clear();
// Clean up after ourselves
- if (!DeadInsts.empty()) {
+ if (!DeadInsts.empty())
DeleteTriviallyDeadInstructions();
- BasicBlock::iterator I = L->getHeader()->begin();
- while (PHINode *PN = dyn_cast<PHINode>(I++)) {
- // At this point, we know that we have killed one or more IV users.
- // It is worth checking to see if the cannonical indvar is also
- // dead, so that we can remove it as well.
- //
- // We can remove a PHI if it is on a cycle in the def-use graph
- // where each node in the cycle has degree one, i.e. only one use,
- // and is an instruction with no side effects.
- //
- // FIXME: this needs to eliminate an induction variable even if it's being
- // compared against some value to decide loop termination.
- if (!PN->hasOneUse())
- continue;
-
- SmallPtrSet<PHINode *, 4> PHIs;
- for (Instruction *J = dyn_cast<Instruction>(*PN->use_begin());
- J && J->hasOneUse() && !J->mayWriteToMemory();
- J = dyn_cast<Instruction>(*J->use_begin())) {
- // If we find the original PHI, we've discovered a cycle.
- if (J == PN) {
- // Break the cycle and mark the PHI for deletion.
- SE->deleteValueFromRecords(PN);
- PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
- DeadInsts.push_back(PN);
- Changed = true;
- break;
- }
- // If we find a PHI more than once, we're on a cycle that
- // won't prove fruitful.
- if (isa<PHINode>(J) && !PHIs.insert(cast<PHINode>(J)))
- break;
- }
+ // At this point, it is worth checking to see if any recurrence PHIs are also
+ // dead, so that we can remove them as well. To keep ScalarEvolution
+ // current, use a ValueDeletionListener class.
+ struct LSRListener : public ValueDeletionListener {
+ ScalarEvolution &SE;
+ explicit LSRListener(ScalarEvolution &se) : SE(se) {}
+
+ virtual void ValueWillBeDeleted(Value *V) {
+ SE.deleteValueFromRecords(V);
}
- DeleteTriviallyDeadInstructions();
- }
+ } VDL(*SE);
+ DeleteDeadPHIs(L->getHeader(), &VDL);
+
return Changed;
}