LLVM  14.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 
20 #include "llvm/IR/InstVisitor.h"
21 
22 // This class is used to get an estimate of the optimization effects that we
23 // could get from complete loop unrolling. It comes from the fact that some
24 // loads might be replaced with concrete constant values and that could trigger
25 // a chain of instruction simplifications.
26 //
27 // E.g. we might have:
28 // int a[] = {0, 1, 0};
29 // v = 0;
30 // for (i = 0; i < 3; i ++)
31 // v += b[i]*a[i];
32 // If we completely unroll the loop, we would get:
33 // v = b[0]*a[0] + b[1]*a[1] + b[2]*a[2]
34 // Which then will be simplified to:
35 // v = b[0]* 0 + b[1]* 1 + b[2]* 0
36 // And finally:
37 // v = b[1]
38 namespace llvm {
39 class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> {
41  friend class InstVisitor<UnrolledInstAnalyzer, bool>;
42  struct SimplifiedAddress {
43  Value *Base = nullptr;
44  ConstantInt *Offset = nullptr;
45  };
46 
47 public:
48  UnrolledInstAnalyzer(unsigned Iteration,
49  DenseMap<Value *, Value *> &SimplifiedValues,
50  ScalarEvolution &SE, const Loop *L)
51  : SimplifiedValues(SimplifiedValues), SE(SE), L(L) {
52  IterationNumber = SE.getConstant(APInt(64, Iteration));
53  }
54 
55  // Allow access to the initial visit method.
56  using Base::visit;
57 
58 private:
59  /// A cache of pointer bases and constant-folded offsets corresponding
60  /// to GEP (or derived from GEP) instructions.
61  ///
62  /// In order to find the base pointer one needs to perform non-trivial
63  /// traversal of the corresponding SCEV expression, so it's good to have the
64  /// results saved.
65  DenseMap<Value *, SimplifiedAddress> SimplifiedAddresses;
66 
67  /// SCEV expression corresponding to number of currently simulated
68  /// iteration.
69  const SCEV *IterationNumber;
70 
71  /// While we walk the loop instructions, we build up and maintain a mapping
72  /// of simplified values specific to this iteration. The idea is to propagate
73  /// any special information we have about loads that can be replaced with
74  /// constants after complete unrolling, and account for likely simplifications
75  /// post-unrolling.
76  DenseMap<Value *, Value *> &SimplifiedValues;
77 
78  ScalarEvolution &SE;
79  const Loop *L;
80 
81  bool simplifyInstWithSCEV(Instruction *I);
82 
83  bool visitInstruction(Instruction &I);
84  bool visitBinaryOperator(BinaryOperator &I);
85  bool visitLoad(LoadInst &I);
86  bool visitCastInst(CastInst &I);
87  bool visitCmpInst(CmpInst &I);
88  bool visitPHINode(PHINode &PN);
89 };
90 }
91 #endif
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::UnrolledInstAnalyzer
Definition: LoopUnrollAnalyzer.h:39
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:460
Offset
uint64_t Offset
Definition: ELFObjHandler.cpp:81
llvm::UnrolledInstAnalyzer::UnrolledInstAnalyzer
UnrolledInstAnalyzer(unsigned Iteration, DenseMap< Value *, Value * > &SimplifiedValues, ScalarEvolution &SE, const Loop *L)
Definition: LoopUnrollAnalyzer.h:48
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::Instruction
Definition: Instruction.h:45
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:711
llvm::SCEV
This class represents an analyzed expression in the program.
Definition: ScalarEvolution.h:77
llvm::DenseMap
Definition: DenseMap.h:714
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::InstVisitor< UnrolledInstAnalyzer, bool >::visit
void visit(Iterator Start, Iterator End)
Definition: InstVisitor.h:88
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::BinaryOperator
Definition: InstrTypes.h:190
InstVisitor.h
llvm::ScalarEvolution::getConstant
const SCEV * getConstant(ConstantInt *V)
Definition: ScalarEvolution.cpp:444
llvm::InstVisitor
Base class for instruction visitors.
Definition: InstVisitor.h:79
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:431
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
ScalarEvolutionExpressions.h
InstructionSimplify.h
llvm::PHINode
Definition: Instructions.h:2648
llvm::Value
LLVM Value Representation.
Definition: Value.h:74