#define DEBUG_TYPE "loop-unswitch"
#include "llvm/Transforms/Scalar.h"
-#include "llvm/Constants.h"
-#include "llvm/DerivedTypes.h"
-#include "llvm/Function.h"
-#include "llvm/Instructions.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/CodeMetrics.h"
+#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/LoopPass.h"
-#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/ScalarEvolution.h"
-#include "llvm/Transforms/Utils/Cloning.h"
-#include "llvm/Transforms/Utils/Local.h"
-#include "llvm/Transforms/Utils/BasicBlockUtils.h"
-#include "llvm/ADT/Statistic.h"
-#include "llvm/ADT/SmallPtrSet.h"
-#include "llvm/ADT/STLExtras.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/DerivedTypes.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
#include <map>
#include <set>
typedef LoopPropsMap::iterator LoopPropsMapIt;
LoopPropsMap LoopsProperties;
- UnswitchedValsMap* CurLoopInstructions;
- LoopProperties* CurrentLoopProperties;
+ UnswitchedValsMap *CurLoopInstructions;
+ LoopProperties *CurrentLoopProperties;
// Max size of code we can produce on remained iterations.
unsigned MaxSize;
public:
LUAnalysisCache() :
- CurLoopInstructions(NULL), CurrentLoopProperties(NULL),
+ CurLoopInstructions(0), CurrentLoopProperties(0),
MaxSize(Threshold)
{}
// Analyze loop. Check its size, calculate is it possible to unswitch
// it. Returns true if we can unswitch this loop.
- bool countLoop(const Loop* L);
+ bool countLoop(const Loop *L, const TargetTransformInfo &TTI);
// Clean all data related to given loop.
- void forgetLoop(const Loop* L);
+ void forgetLoop(const Loop *L);
// Mark case value as unswitched.
// Since SI instruction can be partly unswitched, in order to avoid
// extra unswitching in cloned loops keep track all unswitched values.
- void setUnswitched(const SwitchInst* SI, const Value* V);
+ void setUnswitched(const SwitchInst *SI, const Value *V);
// Check was this case value unswitched before or not.
- bool isUnswitched(const SwitchInst* SI, const Value* V);
+ bool isUnswitched(const SwitchInst *SI, const Value *V);
// Clone all loop-unswitch related loop properties.
// Redistribute unswitching quotas.
// Note, that new loop data is stored inside the VMap.
- void cloneData(const Loop* NewLoop, const Loop* OldLoop,
- const ValueToValueMapTy& VMap);
+ void cloneData(const Loop *NewLoop, const Loop *OldLoop,
+ const ValueToValueMapTy &VMap);
};
class LoopUnswitch : public LoopPass {
static char ID; // Pass ID, replacement for typeid
explicit LoopUnswitch(bool Os = false) :
LoopPass(ID), OptimizeForSize(Os), redoLoop(false),
- currentLoop(NULL), DT(NULL), loopHeader(NULL),
- loopPreheader(NULL) {
+ currentLoop(0), DT(0), loopHeader(0),
+ loopPreheader(0) {
initializeLoopUnswitchPass(*PassRegistry::getPassRegistry());
}
AU.addPreservedID(LCSSAID);
AU.addPreserved<DominatorTree>();
AU.addPreserved<ScalarEvolution>();
+ AU.addRequired<TargetTransformInfo>();
}
private:
/// Split all of the edges from inside the loop to their exit blocks.
/// Update the appropriate Phi nodes as we do so.
- void SplitExitEdges(Loop *L, const SmallVector<BasicBlock *, 8> &ExitBlocks);
+ void SplitExitEdges(Loop *L, const SmallVectorImpl<BasicBlock *> &ExitBlocks);
bool UnswitchIfProfitable(Value *LoopCond, Constant *Val);
void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val,
// Analyze loop. Check its size, calculate is it possible to unswitch
// it. Returns true if we can unswitch this loop.
-bool LUAnalysisCache::countLoop(const Loop* L) {
+bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI) {
- std::pair<LoopPropsMapIt, bool> InsertRes =
+ LoopPropsMapIt PropsIt;
+ bool Inserted;
+ llvm::tie(PropsIt, Inserted) =
LoopsProperties.insert(std::make_pair(L, LoopProperties()));
- LoopProperties& Props = InsertRes.first->second;
+ LoopProperties &Props = PropsIt->second;
- if (InsertRes.second) {
+ if (Inserted) {
// New loop.
// Limit the number of instructions to avoid causing significant code
// consideration code simplification opportunities and code that can
// be shared by the resultant unswitched loops.
CodeMetrics Metrics;
- for (Loop::block_iterator I = L->block_begin(),
- E = L->block_end();
+ for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
I != E; ++I)
- Metrics.analyzeBasicBlock(*I);
+ Metrics.analyzeBasicBlock(*I, TTI);
Props.SizeEstimation = std::min(Metrics.NumInsts, Metrics.NumBlocks * 5);
Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation);
MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount;
+
+ if (Metrics.notDuplicatable) {
+ DEBUG(dbgs() << "NOT unswitching loop %"
+ << L->getHeader()->getName() << ", contents cannot be "
+ << "duplicated!\n");
+ return false;
+ }
}
if (!Props.CanBeUnswitchedCount) {
DEBUG(dbgs() << "NOT unswitching loop %"
- << L->getHeader()->getName() << ", cost too high: "
- << L->getBlocks().size() << "\n");
-
+ << L->getHeader()->getName() << ", cost too high: "
+ << L->getBlocks().size() << "\n");
return false;
}
}
// Clean all data related to given loop.
-void LUAnalysisCache::forgetLoop(const Loop* L) {
+void LUAnalysisCache::forgetLoop(const Loop *L) {
LoopPropsMapIt LIt = LoopsProperties.find(L);
if (LIt != LoopsProperties.end()) {
- LoopProperties& Props = LIt->second;
+ LoopProperties &Props = LIt->second;
MaxSize += Props.CanBeUnswitchedCount * Props.SizeEstimation;
LoopsProperties.erase(LIt);
}
- CurrentLoopProperties = NULL;
- CurLoopInstructions = NULL;
+ CurrentLoopProperties = 0;
+ CurLoopInstructions = 0;
}
// Mark case value as unswitched.
// Since SI instruction can be partly unswitched, in order to avoid
// extra unswitching in cloned loops keep track all unswitched values.
-void LUAnalysisCache::setUnswitched(const SwitchInst* SI, const Value* V) {
+void LUAnalysisCache::setUnswitched(const SwitchInst *SI, const Value *V) {
(*CurLoopInstructions)[SI].insert(V);
}
// Check was this case value unswitched before or not.
-bool LUAnalysisCache::isUnswitched(const SwitchInst* SI, const Value* V) {
+bool LUAnalysisCache::isUnswitched(const SwitchInst *SI, const Value *V) {
return (*CurLoopInstructions)[SI].count(V);
}
// Clone all loop-unswitch related loop properties.
// Redistribute unswitching quotas.
// Note, that new loop data is stored inside the VMap.
-void LUAnalysisCache::cloneData(const Loop* NewLoop, const Loop* OldLoop,
- const ValueToValueMapTy& VMap) {
+void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop,
+ const ValueToValueMapTy &VMap) {
- LoopProperties& NewLoopProps = LoopsProperties[NewLoop];
- LoopProperties& OldLoopProps = *CurrentLoopProperties;
- UnswitchedValsMap& Insts = OldLoopProps.UnswitchedVals;
+ LoopProperties &NewLoopProps = LoopsProperties[NewLoop];
+ LoopProperties &OldLoopProps = *CurrentLoopProperties;
+ UnswitchedValsMap &Insts = OldLoopProps.UnswitchedVals;
// Reallocate "can-be-unswitched quota"
// for new loop switches we clone info about values that was
// already unswitched and has redundant successors.
for (UnswitchedValsIt I = Insts.begin(); I != Insts.end(); ++I) {
- const SwitchInst* OldInst = I->first;
- Value* NewI = VMap.lookup(OldInst);
- const SwitchInst* NewInst = cast_or_null<SwitchInst>(NewI);
+ const SwitchInst *OldInst = I->first;
+ Value *NewI = VMap.lookup(OldInst);
+ const SwitchInst *NewInst = cast_or_null<SwitchInst>(NewI);
assert(NewInst && "All instructions that are in SrcBB must be in VMap.");
NewLoopProps.UnswitchedVals[NewInst] = OldLoopProps.UnswitchedVals[OldInst];
char LoopUnswitch::ID = 0;
INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",
false, false)
+INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
INITIALIZE_PASS_DEPENDENCY(LoopInfo)
INITIALIZE_PASS_DEPENDENCY(LCSSA)
// Probably we reach the quota of branches for this loop. If so
// stop unswitching.
- if (!BranchesInfo.countLoop(currentLoop))
+ if (!BranchesInfo.countLoop(currentLoop, getAnalysis<TargetTransformInfo>()))
return false;
// Loop over all of the basic blocks in the loop. If we find an interior
// Find a value to unswitch on:
// FIXME: this should chose the most expensive case!
// FIXME: scan for a case with a non-critical edge?
- Constant *UnswitchVal = NULL;
+ Constant *UnswitchVal = 0;
// Do not process same value again and again.
// At this point we have some cases already unswitched and
// some not yet unswitched. Let's find the first not yet unswitched one.
for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
i != e; ++i) {
- Constant* UnswitchValCandidate = i.getCaseValue();
+ Constant *UnswitchValCandidate = i.getCaseValue();
if (!BranchesInfo.isUnswitched(SI, UnswitchValCandidate)) {
UnswitchVal = UnswitchValCandidate;
break;
// Already visited. Without more analysis, this could indicate an infinite
// loop.
return false;
- } else if (!L->contains(BB)) {
+ }
+ if (!L->contains(BB)) {
// Otherwise, this is a loop exit, this is fine so long as this is the
// first exit.
if (ExitBB != 0) return false;
// on already unswitched cases.
for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
i != e; ++i) {
- BasicBlock* LoopExitCandidate;
+ BasicBlock *LoopExitCandidate;
if ((LoopExitCandidate = isTrivialLoopExitBlock(currentLoop,
i.getCaseSuccessor()))) {
// Okay, we found a trivial case, remember the value that is trivial.
- ConstantInt* CaseVal = i.getCaseValue();
+ ConstantInt *CaseVal = i.getCaseValue();
// Check that it was not unswitched before, since already unswitched
// trivial vals are looks trivial too.
// Check to see if it would be profitable to unswitch current loop.
// Do not do non-trivial unswitch while optimizing for size.
- if (OptimizeForSize || F->hasFnAttr(Attribute::OptimizeForSize))
+ if (OptimizeForSize ||
+ F->getAttributes().hasAttribute(AttributeSet::FunctionIndex,
+ Attribute::OptimizeForSize))
return false;
UnswitchNontrivialCondition(LoopCond, Val, currentLoop);
/// SplitExitEdges - Split all of the edges from inside the loop to their exit
/// blocks. Update the appropriate Phi nodes as we do so.
void LoopUnswitch::SplitExitEdges(Loop *L,
- const SmallVector<BasicBlock *, 8> &ExitBlocks){
+ const SmallVectorImpl<BasicBlock *> &ExitBlocks){
for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) {
BasicBlock *ExitBlock = ExitBlocks[i];
// If the successor of the exit block had PHI nodes, add an entry for
// NewExit.
- PHINode *PN;
- for (BasicBlock::iterator I = ExitSucc->begin(); isa<PHINode>(I); ++I) {
- PN = cast<PHINode>(I);
+ for (BasicBlock::iterator I = ExitSucc->begin();
+ PHINode *PN = dyn_cast<PHINode>(I); ++I) {
Value *V = PN->getIncomingValueForBlock(ExitBlocks[i]);
ValueToValueMapTy::iterator It = VMap.find(V);
if (It != VMap.end()) V = It->second;
}
if (LandingPadInst *LPad = NewExit->getLandingPadInst()) {
- PN = PHINode::Create(LPad->getType(), 0, "",
- ExitSucc->getFirstInsertionPt());
+ PHINode *PN = PHINode::Create(LPad->getType(), 0, "",
+ ExitSucc->getFirstInsertionPt());
for (pred_iterator I = pred_begin(ExitSucc), E = pred_end(ExitSucc);
I != E; ++I) {
/// specified.
static void RemoveFromWorklist(Instruction *I,
std::vector<Instruction*> &Worklist) {
- std::vector<Instruction*>::iterator WI = std::find(Worklist.begin(),
- Worklist.end(), I);
- while (WI != Worklist.end()) {
- unsigned Offset = WI-Worklist.begin();
- Worklist.erase(WI);
- WI = std::find(Worklist.begin()+Offset, Worklist.end(), I);
- }
+
+ Worklist.erase(std::remove(Worklist.begin(), Worklist.end(), I),
+ Worklist.end());
}
/// ReplaceUsesOfWith - When we find that I really equals V, remove I from the
// are any easy simplifications we can do now.
if (BasicBlock *Pred = BB->getSinglePredecessor()) {
// If it has one pred, fold phi nodes in BB.
- while (isa<PHINode>(BB->begin()))
- ReplaceUsesOfWith(BB->begin(),
- cast<PHINode>(BB->begin())->getIncomingValue(0),
- Worklist, L, LPM);
+ while (PHINode *PN = dyn_cast<PHINode>(BB->begin()))
+ ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist, L, LPM);
// If this is the header of a loop and the only pred is the latch, we now
// have an unreachable loop.
// was in.
LI->removeBlock(BB);
-
// Remove phi node entries in successors for this block.
TerminatorInst *TI = BB->getTerminator();
SmallVector<BasicBlock*, 4> Succs;
std::vector<Instruction*> Worklist;
LLVMContext &Context = Val->getContext();
-
// If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC
// in the loop with the appropriate one directly.
if (IsEqual || (isa<ConstantInt>(Val) &&
Worklist.push_back(U);
}
- for (std::vector<Instruction*>::iterator UI = Worklist.begin();
- UI != Worklist.end(); ++UI)
+ for (std::vector<Instruction*>::iterator UI = Worklist.begin(),
+ UE = Worklist.end(); UI != UE; ++UI)
(*UI)->replaceUsesOfWith(LIC, Replacement);
SimplifyCode(Worklist, L);
projects / oota-llvm.git / blobdiff