Mercurial > hg > Members > tobaru > cbc > CbC_llvm
diff lib/Analysis/IVUsers.cpp @ 77:54457678186b
LLVM 3.6
author | Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 08 Sep 2014 22:06:00 +0900 |
parents | 95c75e76d11b |
children | 60c9769439b8 |
line wrap: on
line diff
--- a/lib/Analysis/IVUsers.cpp Thu Dec 12 15:22:36 2013 +0900 +++ b/lib/Analysis/IVUsers.cpp Mon Sep 08 22:06:00 2014 +0900 @@ -12,17 +12,15 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "iv-users" #include "llvm/Analysis/IVUsers.h" #include "llvm/ADT/STLExtras.h" -#include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/ValueTracking.h" -#include "llvm/Assembly/Writer.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/Type.h" #include "llvm/Support/Debug.h" @@ -30,11 +28,13 @@ #include <algorithm> using namespace llvm; +#define DEBUG_TYPE "iv-users" + char IVUsers::ID = 0; INITIALIZE_PASS_BEGIN(IVUsers, "iv-users", "Induction Variable Users", false, true) INITIALIZE_PASS_DEPENDENCY(LoopInfo) -INITIALIZE_PASS_DEPENDENCY(DominatorTree) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) INITIALIZE_PASS_END(IVUsers, "iv-users", "Induction Variable Users", false, true) @@ -84,8 +84,8 @@ /// form. static bool isSimplifiedLoopNest(BasicBlock *BB, const DominatorTree *DT, const LoopInfo *LI, - SmallPtrSet<Loop*,16> &SimpleLoopNests) { - Loop *NearestLoop = 0; + SmallPtrSetImpl<Loop*> &SimpleLoopNests) { + Loop *NearestLoop = nullptr; for (DomTreeNode *Rung = DT->getNode(BB); Rung; Rung = Rung->getIDom()) { BasicBlock *DomBB = Rung->getBlock(); @@ -112,7 +112,7 @@ /// reducible SCEV, recursively add its users to the IVUsesByStride set and /// return true. Otherwise, return false. bool IVUsers::AddUsersImpl(Instruction *I, - SmallPtrSet<Loop*,16> &SimpleLoopNests) { + SmallPtrSetImpl<Loop*> &SimpleLoopNests) { // Add this IV user to the Processed set before returning false to ensure that // all IV users are members of the set. See IVUsers::isIVUserOrOperand. if (!Processed.insert(I)) @@ -124,14 +124,14 @@ // IVUsers is used by LSR which assumes that all SCEV expressions are safe to // pass to SCEVExpander. Expressions are not safe to expand if they represent // operations that are not safe to speculate, namely integer division. - if (!isa<PHINode>(I) && !isSafeToSpeculativelyExecute(I, TD)) + if (!isa<PHINode>(I) && !isSafeToSpeculativelyExecute(I, DL)) return false; // LSR is not APInt clean, do not touch integers bigger than 64-bits. // Also avoid creating IVs of non-native types. For example, we don't want a // 64-bit IV in 32-bit code just because the loop has one 64-bit cast. uint64_t Width = SE->getTypeSizeInBits(I->getType()); - if (Width > 64 || (TD && !TD->isLegalInteger(Width))) + if (Width > 64 || (DL && !DL->isLegalInteger(Width))) return false; // Get the symbolic expression for this instruction. @@ -143,9 +143,8 @@ return false; SmallPtrSet<Instruction *, 4> UniqueUsers; - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); - UI != E; ++UI) { - Instruction *User = cast<Instruction>(*UI); + for (Use &U : I->uses()) { + Instruction *User = cast<Instruction>(U.getUser()); if (!UniqueUsers.insert(User)) continue; @@ -158,7 +157,7 @@ BasicBlock *UseBB = User->getParent(); // A phi's use is live out of its predecessor block. if (PHINode *PHI = dyn_cast<PHINode>(User)) { - unsigned OperandNo = UI.getOperandNo(); + unsigned OperandNo = U.getOperandNo(); unsigned ValNo = PHINode::getIncomingValueNumForOperand(OperandNo); UseBB = PHI->getIncomingBlock(ValNo); } @@ -187,15 +186,34 @@ if (AddUserToIVUsers) { // Okay, we found a user that we cannot reduce. - IVUses.push_back(new IVStrideUse(this, User, I)); - IVStrideUse &NewUse = IVUses.back(); + IVStrideUse &NewUse = AddUser(User, I); // Autodetect the post-inc loop set, populating NewUse.PostIncLoops. // The regular return value here is discarded; instead of recording // it, we just recompute it when we need it. + const SCEV *OriginalISE = ISE; ISE = TransformForPostIncUse(NormalizeAutodetect, ISE, User, I, NewUse.PostIncLoops, *SE, *DT); + + // PostIncNormalization effectively simplifies the expression under + // pre-increment assumptions. Those assumptions (no wrapping) might not + // hold for the post-inc value. Catch such cases by making sure the + // transformation is invertible. + if (OriginalISE != ISE) { + const SCEV *DenormalizedISE = + TransformForPostIncUse(Denormalize, ISE, User, I, + NewUse.PostIncLoops, *SE, *DT); + + // If we normalized the expression, but denormalization doesn't give the + // original one, discard this user. + if (OriginalISE != DenormalizedISE) { + DEBUG(dbgs() << " DISCARDING (NORMALIZATION ISN'T INVERTIBLE): " + << *ISE << '\n'); + IVUses.pop_back(); + return false; + } + } DEBUG(if (SE->getSCEV(I) != ISE) dbgs() << " NORMALIZED TO: " << *ISE << '\n'); } @@ -224,7 +242,7 @@ void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired<LoopInfo>(); - AU.addRequired<DominatorTree>(); + AU.addRequired<DominatorTreeWrapperPass>(); AU.addRequired<ScalarEvolution>(); AU.setPreservesAll(); } @@ -233,9 +251,10 @@ L = l; LI = &getAnalysis<LoopInfo>(); - DT = &getAnalysis<DominatorTree>(); + DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); SE = &getAnalysis<ScalarEvolution>(); - TD = getAnalysisIfAvailable<DataLayout>(); + DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); + DL = DLP ? &DLP->getDataLayout() : nullptr; // Find all uses of induction variables in this loop, and categorize // them by stride. Start by finding all of the PHI nodes in the header for @@ -248,7 +267,7 @@ void IVUsers::print(raw_ostream &OS, const Module *M) const { OS << "IV Users for loop "; - WriteAsOperand(OS, L->getHeader(), false); + L->getHeader()->printAsOperand(OS, false); if (SE->hasLoopInvariantBackedgeTakenCount(L)) { OS << " with backedge-taken count " << *SE->getBackedgeTakenCount(L); @@ -258,17 +277,20 @@ for (ilist<IVStrideUse>::const_iterator UI = IVUses.begin(), E = IVUses.end(); UI != E; ++UI) { OS << " "; - WriteAsOperand(OS, UI->getOperandValToReplace(), false); + UI->getOperandValToReplace()->printAsOperand(OS, false); OS << " = " << *getReplacementExpr(*UI); for (PostIncLoopSet::const_iterator I = UI->PostIncLoops.begin(), E = UI->PostIncLoops.end(); I != E; ++I) { OS << " (post-inc with loop "; - WriteAsOperand(OS, (*I)->getHeader(), false); + (*I)->getHeader()->printAsOperand(OS, false); OS << ")"; } OS << " in "; - UI->getUser()->print(OS); + if (UI->getUser()) + UI->getUser()->print(OS); + else + OS << "Printing <null> User"; OS << '\n'; } } @@ -311,16 +333,16 @@ I != E; ++I) if (const SCEVAddRecExpr *AR = findAddRecForLoop(*I, L)) return AR; - return 0; + return nullptr; } - return 0; + return nullptr; } const SCEV *IVUsers::getStride(const IVStrideUse &IU, const Loop *L) const { if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(IU), L)) return AR->getStepRecurrence(*SE); - return 0; + return nullptr; } void IVStrideUse::transformToPostInc(const Loop *L) {