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/Analysis/InstructionSimplify.h" 19 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 20 #include "llvm/IR/InstVisitor.h" 21 22 // This class is used to get an estimate of the optimization effects that we 23 // could get from complete loop unrolling. It comes from the fact that some 24 // loads might be replaced with concrete constant values and that could trigger 25 // a chain of instruction simplifications. 26 // 27 // E.g. we might have: 28 // int a[] = {0, 1, 0}; 29 // v = 0; 30 // for (i = 0; i < 3; i ++) 31 // v += b[i]*a[i]; 32 // If we completely unroll the loop, we would get: 33 // v = b[0]*a[0] + b[1]*a[1] + b[2]*a[2] 34 // Which then will be simplified to: 35 // v = b[0]* 0 + b[1]* 1 + b[2]* 0 36 // And finally: 37 // v = b[1] 38 namespace llvm { 39 class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> { 40 typedef InstVisitor<UnrolledInstAnalyzer, bool> Base; 41 friend class InstVisitor<UnrolledInstAnalyzer, bool>; 42 struct SimplifiedAddress { 43 Value *Base = nullptr; 44 ConstantInt *Offset = nullptr; 45 }; 46 47 public: UnrolledInstAnalyzer(unsigned Iteration,DenseMap<Value *,Constant * > & SimplifiedValues,ScalarEvolution & SE,const Loop * L)48 UnrolledInstAnalyzer(unsigned Iteration, 49 DenseMap<Value *, Constant *> &SimplifiedValues, 50 ScalarEvolution &SE, const Loop *L) 51 : SimplifiedValues(SimplifiedValues), SE(SE), L(L) { 52 IterationNumber = SE.getConstant(APInt(64, Iteration)); 53 } 54 55 // Allow access to the initial visit method. 56 using Base::visit; 57 58 private: 59 /// A cache of pointer bases and constant-folded offsets corresponding 60 /// to GEP (or derived from GEP) instructions. 61 /// 62 /// In order to find the base pointer one needs to perform non-trivial 63 /// traversal of the corresponding SCEV expression, so it's good to have the 64 /// results saved. 65 DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses; 66 67 /// SCEV expression corresponding to number of currently simulated 68 /// iteration. 69 const SCEV *IterationNumber; 70 71 /// A Value->Constant map for keeping values that we managed to 72 /// constant-fold on the given iteration. 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 *, Constant *> &SimplifiedValues; 80 81 ScalarEvolution &SE; 82 const Loop *L; 83 84 bool simplifyInstWithSCEV(Instruction *I); 85 visitInstruction(Instruction & I)86 bool visitInstruction(Instruction &I) { return simplifyInstWithSCEV(&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