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