LLVM  16.0.0git
LoopUnrollAnalyzer.h
Go to the documentation of this file.
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"
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]
39 namespace llvm {
40 class Instruction;
41 
42 class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> {
44  friend class InstVisitor<UnrolledInstAnalyzer, bool>;
45  struct SimplifiedAddress {
46  Value *Base = nullptr;
47  ConstantInt *Offset = nullptr;
48  };
49 
50 public:
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(APInt(64, Iteration));
56  }
57 
58  // Allow access to the initial visit method.
59  using Base::visit;
60 
61 private:
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
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::UnrolledInstAnalyzer
Definition: LoopUnrollAnalyzer.h:42
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
APInt.h
ScalarEvolution.h
DenseMap.h
llvm::UnrolledInstAnalyzer::UnrolledInstAnalyzer
UnrolledInstAnalyzer(unsigned Iteration, DenseMap< Value *, Value * > &SimplifiedValues, ScalarEvolution &SE, const Loop *L)
Definition: LoopUnrollAnalyzer.h:51
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::Instruction
Definition: Instruction.h:42
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:709
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:75
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::InstVisitor< UnrolledInstAnalyzer, bool >::visit
void visit(Iterator Start, Iterator End)
Definition: InstVisitor.h:87
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::BinaryOperator
Definition: InstrTypes.h:188
InstVisitor.h
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:466
llvm::InstVisitor
Base class for instruction visitors.
Definition: InstVisitor.h:78
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:429
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
llvm::PHINode
Definition: Instructions.h:2664
llvm::Value
LLVM Value Representation.
Definition: Value.h:74