#define DEBUG_TYPE "loop-rotate"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Function.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
#include "llvm/Support/Debug.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;
#define MAX_HEADER_SIZE 16
STATISTIC(NumRotated, "Number of loops rotated");
namespace {
class LoopRotate : public LoopPass {
public:
static char ID; LoopRotate() : LoopPass(ID) {
initializeLoopRotatePass(*PassRegistry::getPassRegistry());
}
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.addPreserved<DominatorTree>();
AU.addRequired<LoopInfo>();
AU.addPreserved<LoopInfo>();
AU.addRequiredID(LoopSimplifyID);
AU.addPreservedID(LoopSimplifyID);
AU.addRequiredID(LCSSAID);
AU.addPreservedID(LCSSAID);
AU.addPreserved<ScalarEvolution>();
}
bool runOnLoop(Loop *L, LPPassManager &LPM);
void simplifyLoopLatch(Loop *L);
bool rotateLoop(Loop *L);
private:
LoopInfo *LI;
};
}
char LoopRotate::ID = 0;
INITIALIZE_PASS_BEGIN(LoopRotate, "loop-rotate", "Rotate Loops", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopInfo)
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
INITIALIZE_PASS_DEPENDENCY(LCSSA)
INITIALIZE_PASS_END(LoopRotate, "loop-rotate", "Rotate Loops", false, false)
Pass *llvm::createLoopRotatePass() { return new LoopRotate(); }
bool LoopRotate::runOnLoop(Loop *L, LPPassManager &LPM) {
LI = &getAnalysis<LoopInfo>();
simplifyLoopLatch(L);
bool MadeChange = false;
while (rotateLoop(L))
MadeChange = true;
return MadeChange;
}
static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader,
BasicBlock *OrigPreheader,
ValueToValueMapTy &ValueMap) {
BasicBlock::iterator I, E = OrigHeader->end();
for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I)
PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader));
SSAUpdater SSA;
for (I = OrigHeader->begin(); I != E; ++I) {
Value *OrigHeaderVal = I;
if (OrigHeaderVal->use_empty())
continue;
Value *OrigPreHeaderVal = ValueMap[OrigHeaderVal];
SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName());
SSA.AddAvailableValue(OrigHeader, OrigHeaderVal);
SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal);
for (Value::use_iterator UI = OrigHeaderVal->use_begin(),
UE = OrigHeaderVal->use_end(); UI != UE; ) {
Use &U = UI.getUse();
++UI;
Instruction *UserInst = cast<Instruction>(U.getUser());
if (!isa<PHINode>(UserInst)) {
BasicBlock *UserBB = UserInst->getParent();
if (UserBB == OrigHeader)
continue;
if (UserBB == OrigPreheader) {
U = OrigPreHeaderVal;
continue;
}
}
SSA.RewriteUse(U);
}
}
}
static bool shouldSpeculateInstrs(BasicBlock::iterator Begin,
BasicBlock::iterator End) {
bool seenIncrement = false;
for (BasicBlock::iterator I = Begin; I != End; ++I) {
if (!isSafeToSpeculativelyExecute(I))
return false;
if (isa<DbgInfoIntrinsic>(I))
continue;
switch (I->getOpcode()) {
default:
return false;
case Instruction::GetElementPtr:
if (!cast<GEPOperator>(I)->hasAllConstantIndices())
return false;
case Instruction::Add:
case Instruction::Sub:
case Instruction::And:
case Instruction::Or:
case Instruction::Xor:
case Instruction::Shl:
case Instruction::LShr:
case Instruction::AShr:
if (seenIncrement)
return false;
seenIncrement = true;
break;
case Instruction::Trunc:
case Instruction::ZExt:
case Instruction::SExt:
break;
}
}
return true;
}
void LoopRotate::simplifyLoopLatch(Loop *L) {
BasicBlock *Latch = L->getLoopLatch();
if (!Latch || Latch->hasAddressTaken())
return;
BranchInst *Jmp = dyn_cast<BranchInst>(Latch->getTerminator());
if (!Jmp || !Jmp->isUnconditional())
return;
BasicBlock *LastExit = Latch->getSinglePredecessor();
if (!LastExit || !L->isLoopExiting(LastExit))
return;
BranchInst *BI = dyn_cast<BranchInst>(LastExit->getTerminator());
if (!BI)
return;
if (!shouldSpeculateInstrs(Latch->begin(), Jmp))
return;
DEBUG(dbgs() << "Folding loop latch " << Latch->getName() << " into "
<< LastExit->getName() << "\n");
LastExit->getInstList().splice(BI, Latch->getInstList(), Latch->begin(), Jmp);
unsigned FallThruPath = BI->getSuccessor(0) == Latch ? 0 : 1;
BasicBlock *Header = Jmp->getSuccessor(0);
assert(Header == L->getHeader() && "expected a backward branch");
BI->setSuccessor(FallThruPath, Header);
Latch->replaceSuccessorsPhiUsesWith(LastExit);
Jmp->eraseFromParent();
assert(Latch->empty() && "unable to evacuate Latch");
LI->removeBlock(Latch);
if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>())
DT->eraseNode(Latch);
Latch->eraseFromParent();
}
bool LoopRotate::rotateLoop(Loop *L) {
if (L->getBlocks().size() == 1)
return false;
BasicBlock *OrigHeader = L->getHeader();
BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator());
if (BI == 0 || BI->isUnconditional())
return false;
if (!L->isLoopExiting(OrigHeader))
return false;
SmallVector<BasicBlock*, 8> ExitBlocks;
L->getExitBlocks(ExitBlocks);
if (ExitBlocks.size() > 1)
return false;
{
CodeMetrics Metrics;
Metrics.analyzeBasicBlock(OrigHeader);
if (Metrics.NumInsts > MAX_HEADER_SIZE)
return false;
}
BasicBlock *OrigPreheader = L->getLoopPreheader();
BasicBlock *OrigLatch = L->getLoopLatch();
if (OrigPreheader == 0 || OrigLatch == 0)
return false;
if (ScalarEvolution *SE = getAnalysisIfAvailable<ScalarEvolution>())
SE->forgetLoop(L);
BasicBlock *Exit = BI->getSuccessor(0);
BasicBlock *NewHeader = BI->getSuccessor(1);
if (L->contains(Exit))
std::swap(Exit, NewHeader);
assert(NewHeader && "Unable to determine new loop header");
assert(L->contains(NewHeader) && !L->contains(Exit) &&
"Unable to determine loop header and exit blocks");
assert(NewHeader->getSinglePredecessor() &&
"New header doesn't have one pred!");
FoldSingleEntryPHINodes(NewHeader);
BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end();
ValueToValueMapTy ValueMap;
for (; PHINode *PN = dyn_cast<PHINode>(I); ++I)
ValueMap[PN] = PN->getIncomingValueForBlock(OrigPreheader);
TerminatorInst *LoopEntryBranch = OrigPreheader->getTerminator();
while (I != E) {
Instruction *Inst = I++;
if (L->hasLoopInvariantOperands(Inst) &&
!Inst->mayReadFromMemory() && !Inst->mayWriteToMemory() &&
!isa<TerminatorInst>(Inst) && !isa<DbgInfoIntrinsic>(Inst) &&
!isa<AllocaInst>(Inst)) {
Inst->moveBefore(LoopEntryBranch);
continue;
}
Instruction *C = Inst->clone();
RemapInstruction(C, ValueMap,
RF_NoModuleLevelChanges|RF_IgnoreMissingEntries);
Value *V = SimplifyInstruction(C);
if (V && LI->replacementPreservesLCSSAForm(C, V)) {
delete C;
ValueMap[Inst] = V;
} else {
C->setName(Inst->getName());
C->insertBefore(LoopEntryBranch);
ValueMap[Inst] = C;
}
}
TerminatorInst *TI = OrigHeader->getTerminator();
for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
for (BasicBlock::iterator BI = TI->getSuccessor(i)->begin();
PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreheader);
LoopEntryBranch->eraseFromParent();
RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap);
L->moveToHeader(NewHeader);
assert(L->getHeader() == NewHeader && "Latch block is our new header");
BranchInst *PHBI = cast<BranchInst>(OrigPreheader->getTerminator());
assert(PHBI->isConditional() && "Should be clone of BI condbr!");
if (!isa<ConstantInt>(PHBI->getCondition()) ||
PHBI->getSuccessor(cast<ConstantInt>(PHBI->getCondition())->isZero())
!= NewHeader) {
if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>()) {
DT->changeImmediateDominator(Exit, OrigPreheader);
DT->changeImmediateDominator(NewHeader, OrigPreheader);
DT->changeImmediateDominator(OrigHeader, OrigLatch);
}
BasicBlock *NewPH = SplitCriticalEdge(OrigPreheader, NewHeader, this);
NewPH->setName(NewHeader->getName() + ".lr.ph");
BasicBlock *ExitSplit = SplitCriticalEdge(L->getLoopLatch(), Exit, this);
ExitSplit->moveBefore(Exit);
} else {
Exit->removePredecessor(OrigPreheader, true );
BranchInst *NewBI = BranchInst::Create(NewHeader, PHBI);
NewBI->setDebugLoc(PHBI->getDebugLoc());
PHBI->eraseFromParent();
if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>()) {
DT->changeImmediateDominator(NewHeader, OrigPreheader);
DT->changeImmediateDominator(OrigHeader, OrigLatch);
}
}
assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");
assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");
MergeBlockIntoPredecessor(OrigHeader, this);
++NumRotated;
return true;
}