lib/Analysis/IVUsers.cpp

   1 //===- IVUsers.cpp - Induction Variable Users -------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements bookkeeping for "interesting" users of expressions
  11 // computed from induction variables.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "iv-users"
  16 #include "llvm/Analysis/IVUsers.h"
  17 #include "llvm/Constants.h"
  18 #include "llvm/Instructions.h"
  19 #include "llvm/Type.h"
  20 #include "llvm/DerivedTypes.h"
  21 #include "llvm/Analysis/Dominators.h"
  22 #include "llvm/Analysis/LoopPass.h"
  23 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  24 #include "llvm/Assembly/AsmAnnotationWriter.h"
  25 #include "llvm/ADT/STLExtras.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include <algorithm>
  29 using namespace llvm;
  30
  31 char IVUsers::ID = 0;
  32 static RegisterPass<IVUsers>
  33 X("iv-users", "Induction Variable Users", false, true);
  34
  35 Pass *llvm::createIVUsersPass() {
  36   return new IVUsers();
  37 }
  38
  39 /// CollectSubexprs - Split S into subexpressions which can be pulled out into
  40 /// separate registers.
  41 static void CollectSubexprs(const SCEV *S,
  42                             SmallVectorImpl<const SCEV *> &Ops,
  43                             ScalarEvolution &SE) {
  44   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
  45     // Break out add operands.
  46     for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
  47          I != E; ++I)
  48       CollectSubexprs(*I, Ops, SE);
  49     return;
  50   } else if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
  51     // Split a non-zero base out of an addrec.
  52     if (!AR->getStart()->isZero()) {
  53       CollectSubexprs(AR->getStart(), Ops, SE);
  54       CollectSubexprs(SE.getAddRecExpr(SE.getIntegerSCEV(0, AR->getType()),
  55                                        AR->getStepRecurrence(SE),
  56                                        AR->getLoop()), Ops, SE);
  57       return;
  58     }
  59   }
  60
  61   // Otherwise use the value itself.
  62   Ops.push_back(S);
  63 }
  64
  65 /// isInteresting - Test whether the given expression is "interesting" when
  66 /// used by the given expression, within the context of analyzing the
  67 /// given loop.
  68 static bool isInteresting(const SCEV *S, const Instruction *I, const Loop *L) {
  69   // Anything loop-invariant is interesting.
  70   if (!isa<SCEVUnknown>(S) && S->isLoopInvariant(L))
  71     return true;
  72
  73   // An addrec is interesting if it's affine or if it has an interesting start.
  74   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
  75     // Keep things simple. Don't touch loop-variant strides.
  76     if (AR->getLoop() == L && (AR->isAffine() || !L->contains(I)))
  77         return true;
  78     // Otherwise recurse to see if the start value is interesting.
  79     return isInteresting(AR->getStart(), I, L);
  80   }
  81
  82   // An add is interesting if any of its operands is.
  83   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
  84     for (SCEVAddExpr::op_iterator OI = Add->op_begin(), OE = Add->op_end();
  85          OI != OE; ++OI)
  86       if (isInteresting(*OI, I, L))
  87         return true;
  88     return false;
  89   }
  90
  91   // Nothing else is interesting here.
  92   return false;
  93 }
  94
  95 /// AddUsersIfInteresting - Inspect the specified instruction.  If it is a
  96 /// reducible SCEV, recursively add its users to the IVUsesByStride set and
  97 /// return true.  Otherwise, return false.
  98 bool IVUsers::AddUsersIfInteresting(Instruction *I) {
  99   if (!SE->isSCEVable(I->getType()))
 100     return false;   // Void and FP expressions cannot be reduced.
 101
 102   // LSR is not APInt clean, do not touch integers bigger than 64-bits.
 103   if (SE->getTypeSizeInBits(I->getType()) > 64)
 104     return false;
 105
 106   if (!Processed.insert(I))
 107     return true;    // Instruction already handled.
 108
 109   // Get the symbolic expression for this instruction.
 110   const SCEV *ISE = SE->getSCEV(I);
 111   if (isa<SCEVCouldNotCompute>(ISE)) return false;
 112
 113   // If we've come to an uninteresting expression, stop the traversal and
 114   // call this a user.
 115   if (!isInteresting(ISE, I, L))
 116     return false;
 117
 118   SmallPtrSet<Instruction *, 4> UniqueUsers;
 119   for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
 120        UI != E; ++UI) {
 121     Instruction *User = cast<Instruction>(*UI);
 122     if (!UniqueUsers.insert(User))
 123       continue;
 124
 125     // Do not infinitely recurse on PHI nodes.
 126     if (isa<PHINode>(User) && Processed.count(User))
 127       continue;
 128
 129     // Descend recursively, but not into PHI nodes outside the current loop.
 130     // It's important to see the entire expression outside the loop to get
 131     // choices that depend on addressing mode use right, although we won't
 132     // consider references outside the loop in all cases.
 133     // If User is already in Processed, we don't want to recurse into it again,
 134     // but do want to record a second reference in the same instruction.
 135     bool AddUserToIVUsers = false;
 136     if (LI->getLoopFor(User->getParent()) != L) {
 137       if (isa<PHINode>(User) || Processed.count(User) ||
 138           !AddUsersIfInteresting(User)) {
 139         DEBUG(dbgs() << "FOUND USER in other loop: " << *User << '\n'
 140                      << "   OF SCEV: " << *ISE << '\n');
 141         AddUserToIVUsers = true;
 142       }
 143     } else if (Processed.count(User) ||
 144                !AddUsersIfInteresting(User)) {
 145       DEBUG(dbgs() << "FOUND USER: " << *User << '\n'
 146                    << "   OF SCEV: " << *ISE << '\n');
 147       AddUserToIVUsers = true;
 148     }
 149
 150     if (AddUserToIVUsers) {
 151       // Okay, we found a user that we cannot reduce.
 152       IVUses.push_back(new IVStrideUse(this, ISE, User, I));
 153       IVStrideUse &NewUse = IVUses.back();
 154       // Transform the expression into a normalized form.
 155       NewUse.Expr =
 156         TransformForPostIncUse(NormalizeAutodetect, NewUse.Expr,
 157                                User, I,
 158                                NewUse.PostIncLoops,
 159                                *SE, *DT);
 160       DEBUG(dbgs() << "   NORMALIZED TO: " << *NewUse.Expr << '\n');
 161     }
 162   }
 163   return true;
 164 }
 165
 166 IVStrideUse &IVUsers::AddUser(const SCEV *Expr,
 167                               Instruction *User, Value *Operand) {
 168   IVUses.push_back(new IVStrideUse(this, Expr, User, Operand));
 169   return IVUses.back();
 170 }
 171
 172 IVUsers::IVUsers()
 173  : LoopPass(&ID) {
 174 }
 175
 176 void IVUsers::getAnalysisUsage(AnalysisUsage &AU) const {
 177   AU.addRequired<LoopInfo>();
 178   AU.addRequired<DominatorTree>();
 179   AU.addRequired<ScalarEvolution>();
 180   AU.setPreservesAll();
 181 }
 182
 183 bool IVUsers::runOnLoop(Loop *l, LPPassManager &LPM) {
 184
 185   L = l;
 186   LI = &getAnalysis<LoopInfo>();
 187   DT = &getAnalysis<DominatorTree>();
 188   SE = &getAnalysis<ScalarEvolution>();
 189
 190   // Find all uses of induction variables in this loop, and categorize
 191   // them by stride.  Start by finding all of the PHI nodes in the header for
 192   // this loop.  If they are induction variables, inspect their uses.
 193   for (BasicBlock::iterator I = L->getHeader()->begin(); isa<PHINode>(I); ++I)
 194     AddUsersIfInteresting(I);
 195
 196   return false;
 197 }
 198
 199 /// getReplacementExpr - Return a SCEV expression which computes the
 200 /// value of the OperandValToReplace of the given IVStrideUse.
 201 const SCEV *IVUsers::getReplacementExpr(const IVStrideUse &U) const {
 202   PostIncLoopSet &Loops = const_cast<PostIncLoopSet &>(U.PostIncLoops);
 203   return TransformForPostIncUse(Denormalize, U.getExpr(),
 204                                 U.getUser(), U.getOperandValToReplace(),
 205                                 Loops, *SE, *DT);
 206 }
 207
 208 void IVUsers::print(raw_ostream &OS, const Module *M) const {
 209   OS << "IV Users for loop ";
 210   WriteAsOperand(OS, L->getHeader(), false);
 211   if (SE->hasLoopInvariantBackedgeTakenCount(L)) {
 212     OS << " with backedge-taken count "
 213        << *SE->getBackedgeTakenCount(L);
 214   }
 215   OS << ":\n";
 216
 217   // Use a default AssemblyAnnotationWriter to suppress the default info
 218   // comments, which aren't relevant here.
 219   AssemblyAnnotationWriter Annotator;
 220   for (ilist<IVStrideUse>::const_iterator UI = IVUses.begin(),
 221        E = IVUses.end(); UI != E; ++UI) {
 222     OS << "  ";
 223     WriteAsOperand(OS, UI->getOperandValToReplace(), false);
 224     OS << " = "
 225        << *getReplacementExpr(*UI);
 226     for (PostIncLoopSet::const_iterator
 227          I = UI->PostIncLoops.begin(),
 228          E = UI->PostIncLoops.end(); I != E; ++I) {
 229       OS << " (post-inc with loop ";
 230       WriteAsOperand(OS, (*I)->getHeader(), false);
 231       OS << ")";
 232     }
 233     OS << " in  ";
 234     UI->getUser()->print(OS, &Annotator);
 235     OS << '\n';
 236   }
 237 }
 238
 239 void IVUsers::dump() const {
 240   print(dbgs());
 241 }
 242
 243 void IVUsers::releaseMemory() {
 244   Processed.clear();
 245   IVUses.clear();
 246 }
 247
 248 static const SCEVAddRecExpr *findAddRecForLoop(const SCEV *S, const Loop *L) {
 249   if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(S)) {
 250     if (AR->getLoop() == L)
 251       return AR;
 252     return findAddRecForLoop(AR->getStart(), L);
 253   }
 254
 255   if (const SCEVAddExpr *Add = dyn_cast<SCEVAddExpr>(S)) {
 256     for (SCEVAddExpr::op_iterator I = Add->op_begin(), E = Add->op_end();
 257          I != E; ++I)
 258       if (const SCEVAddRecExpr *AR = findAddRecForLoop(*I, L))
 259         return AR;
 260     return 0;
 261   }
 262
 263   return 0;
 264 }
 265
 266 const SCEV *IVStrideUse::getStride(const Loop *L) const {
 267   if (const SCEVAddRecExpr *AR = findAddRecForLoop(getExpr(), L))
 268     return AR->getStepRecurrence(*Parent->SE);
 269   return 0;
 270 }
 271
 272 void IVStrideUse::transformToPostInc(const Loop *L) {
 273   PostIncLoopSet Loops;
 274   Loops.insert(L);
 275   Expr = TransformForPostIncUse(Normalize, Expr,
 276                                 getUser(), getOperandValToReplace(),
 277                                 Loops, *Parent->SE, *Parent->DT);
 278   PostIncLoops.insert(L);
 279 }
 280
 281 void IVStrideUse::deleted() {
 282   // Remove this user from the list.
 283   Parent->IVUses.erase(this);
 284   // this now dangles!
 285 }