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]
39namespace llvm {
40class Instruction;
41
42class 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
50public:
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(Val: APInt(64, Iteration));
56 }
57
58 // Allow access to the initial visit method.
59 using Base::visit;
60
61private:
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

source code of llvm/include/llvm/Analysis/LoopUnrollAnalyzer.h