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] 39namespace llvm { 40class 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 48public: 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 59private: 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