LLVM 20.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]
39namespace llvm {
40class Instruction;
41
42class UnrolledInstAnalyzer : private InstVisitor<UnrolledInstAnalyzer, bool> {
45 struct SimplifiedAddress {
46 Value *Base = nullptr;
47 APInt Offset;
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(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
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
This file implements a class to represent arbitrary precision integral constant values and operations...
This file defines the DenseMap class.
#define I(x, y, z)
Definition: MD5.cpp:58
Class for arbitrary precision integers.
Definition: APInt.h:78
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:444
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:661
Base class for instruction visitors.
Definition: InstVisitor.h:78
void visit(Iterator Start, Iterator End)
Definition: InstVisitor.h:87
An instruction for reading from memory.
Definition: Instructions.h:176
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:39
This class represents an analyzed expression in the program.
The main scalar evolution driver.
const SCEV * getConstant(ConstantInt *V)
UnrolledInstAnalyzer(unsigned Iteration, DenseMap< Value *, Value * > &SimplifiedValues, ScalarEvolution &SE, const Loop *L)
LLVM Value Representation.
Definition: Value.h:74
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18