1 //===- llvm/Analysis/LoopUnrollAnalyzer.h - Loop Unroll Analyzer-*- 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 UnrolledInstAnalyzer class. It's used for predicting 11 // potential effects that loop unrolling might have, such as enabling constant 12 // propagation and other optimizations. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #ifndef LLVM_ANALYSIS_LOOPUNROLLANALYZER_H 17 #define LLVM_ANALYSIS_LOOPUNROLLANALYZER_H 18 19 #include "llvm/Analysis/InstructionSimplify.h" 20 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 21 #include "llvm/IR/InstVisitor.h" 22 23 // This class is used to get an estimate of the optimization effects that we 24 // could get from complete loop unrolling. It comes from the fact that some 25 // loads might be replaced with concrete constant values and that could trigger 26 // a chain of instruction simplifications. 27 // 28 // E.g. we might have: 29 // int a[] = {0, 1, 0}; 30 // v = 0; 31 // for (i = 0; i < 3; i ++) 32 // v += b[i]*a[i]; 33 // If we completely unroll the loop, we would get: 34 // v = b[0]*a[0] + b[1]*a[1] + b[2]*a[2] 35 // Which then will be simplified to: 36 // v = b[0]* 0 + b[1]* 1 + b[2]* 0 37 // And finally: 38 // v = b[1] 39 namespace llvm { 40 class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> { 41 typedef InstVisitor<UnrolledInstAnalyzer, bool> Base; 42 friend class InstVisitor<UnrolledInstAnalyzer, bool>; 43 struct SimplifiedAddress { 44 Value *Base = nullptr; 45 ConstantInt *Offset = nullptr; 46 }; 47 48 public: 49 UnrolledInstAnalyzer(unsigned Iteration, 50 DenseMap<Value *, Constant *> &SimplifiedValues, 51 ScalarEvolution &SE, const Loop *L) 52 : SimplifiedValues(SimplifiedValues), SE(SE), L(L) { 53 IterationNumber = SE.getConstant(APInt(64, Iteration)); 54 } 55 56 // Allow access to the initial visit method. 57 using Base::visit; 58 59 private: 60 /// \brief A cache of pointer bases and constant-folded offsets corresponding 61 /// to GEP (or derived from GEP) instructions. 62 /// 63 /// In order to find the base pointer one needs to perform non-trivial 64 /// traversal of the corresponding SCEV expression, so it's good to have the 65 /// results saved. 66 DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses; 67 68 /// \brief SCEV expression corresponding to number of currently simulated 69 /// iteration. 70 const SCEV *IterationNumber; 71 72 /// \brief A Value->Constant map for keeping values that we managed to 73 /// constant-fold on the given iteration. 74 /// 75 /// While we walk the loop instructions, we build up and maintain a mapping 76 /// of simplified values specific to this iteration. The idea is to propagate 77 /// any special information we have about loads that can be replaced with 78 /// constants after complete unrolling, and account for likely simplifications 79 /// post-unrolling. 80 DenseMap<Value *, Constant *> &SimplifiedValues; 81 82 ScalarEvolution &SE; 83 const Loop *L; 84 85 bool simplifyInstWithSCEV(Instruction *I); 86 87 bool visitInstruction(Instruction &I) { return simplifyInstWithSCEV(&I); } 88 bool visitBinaryOperator(BinaryOperator &I); 89 bool visitLoad(LoadInst &I); 90 bool visitCastInst(CastInst &I); 91 bool visitCmpInst(CmpInst &I); 92 bool visitPHINode(PHINode &PN); 93 }; 94 } 95 #endif 96
