1 //===- llvm/Analysis/LoopUnrollAnalyzer.h - Loop Unroll Analyzer-*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_ANALYSIS_LOOPUNROLLANALYZER_H
17 #define LLVM_ANALYSIS_LOOPUNROLLANALYZER_H
19 #include "llvm/Analysis/InstructionSimplify.h"
20 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
21 #include "llvm/IR/InstVisitor.h"
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.
28 // E.g. we might have:
29 // int a[] = {0, 1, 0};
31 // for (i = 0; i < 3; 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
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;
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));
56 // Allow access to the initial visit method.
60 /// \brief A cache of pointer bases and constant-folded offsets corresponding
61 /// to GEP (or derived from GEP) instructions.
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
66 DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses;
68 /// \brief SCEV expression corresponding to number of currently simulated
70 const SCEV *IterationNumber;
72 /// \brief A Value->Constant map for keeping values that we managed to
73 /// constant-fold on the given iteration.
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
80 DenseMap<Value *, Constant *> &SimplifiedValues;
85 bool simplifyInstWithSCEV(Instruction *I);
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);