1 //===- llvm/Analysis/LoopUnrollAnalyzer.h - Loop Unroll Analyzer-*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements UnrolledInstAnalyzer class. It's used for predicting 10 // potential effects that loop unrolling might have, such as enabling constant 11 // propagation and other optimizations. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_ANALYSIS_LOOPUNROLLANALYZER_H 16 #define LLVM_ANALYSIS_LOOPUNROLLANALYZER_H 17 18 #include "llvm/ADT/APInt.h" 19 #include "llvm/ADT/DenseMap.h" 20 #include "llvm/Analysis/ScalarEvolution.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 Instruction; 41 42 class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> { 43 typedef InstVisitor<UnrolledInstAnalyzer, bool> Base; 44 friend class InstVisitor<UnrolledInstAnalyzer, bool>; 45 struct SimplifiedAddress { 46 Value *Base = nullptr; 47 ConstantInt *Offset = nullptr; 48 }; 49 50 public: UnrolledInstAnalyzer(unsigned Iteration,DenseMap<Value *,Value * > & SimplifiedValues,ScalarEvolution & SE,const Loop * L)51 UnrolledInstAnalyzer(unsigned Iteration, 52 DenseMap<Value *, Value *> &SimplifiedValues, 53 ScalarEvolution &SE, const Loop *L) 54 : SimplifiedValues(SimplifiedValues), SE(SE), L(L) { 55 IterationNumber = SE.getConstant(APInt(64, Iteration)); 56 } 57 58 // Allow access to the initial visit method. 59 using Base::visit; 60 61 private: 62 /// A cache of pointer bases and constant-folded offsets corresponding 63 /// to GEP (or derived from GEP) instructions. 64 /// 65 /// In order to find the base pointer one needs to perform non-trivial 66 /// traversal of the corresponding SCEV expression, so it's good to have the 67 /// results saved. 68 DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses; 69 70 /// SCEV expression corresponding to number of currently simulated 71 /// iteration. 72 const SCEV *IterationNumber; 73 74 /// While we walk the loop instructions, we build up and maintain a mapping 75 /// of simplified values specific to this iteration. The idea is to propagate 76 /// any special information we have about loads that can be replaced with 77 /// constants after complete unrolling, and account for likely simplifications 78 /// post-unrolling. 79 DenseMap<Value *, Value *> &SimplifiedValues; 80 81 ScalarEvolution &SE; 82 const Loop *L; 83 84 bool simplifyInstWithSCEV(Instruction *I); 85 86 bool visitInstruction(Instruction &I); 87 bool visitBinaryOperator(BinaryOperator &I); 88 bool visitLoad(LoadInst &I); 89 bool visitCastInst(CastInst &I); 90 bool visitCmpInst(CmpInst &I); 91 bool visitPHINode(PHINode &PN); 92 }; 93 } 94 #endif 95