LLVM  14.0.0git
HexagonVectorLoopCarriedReuse.h
Go to the documentation of this file.
1 //===- HexagonVectorLoopCarriedReuse.h ------------------------------------===//
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 pass removes the computation of provably redundant expressions that have
10 // been computed earlier in a previous iteration. It relies on the use of PHIs
11 // to identify loop carried dependences. This is scalar replacement for vector
12 // types.
13 //
14 //-----------------------------------------------------------------------------
15 // Motivation: Consider the case where we have the following loop structure.
16 //
17 // Loop:
18 // t0 = a[i];
19 // t1 = f(t0);
20 // t2 = g(t1);
21 // ...
22 // t3 = a[i+1];
23 // t4 = f(t3);
24 // t5 = g(t4);
25 // t6 = op(t2, t5)
26 // cond_branch <Loop>
27 //
28 // This can be converted to
29 // t00 = a[0];
30 // t10 = f(t00);
31 // t20 = g(t10);
32 // Loop:
33 // t2 = t20;
34 // t3 = a[i+1];
35 // t4 = f(t3);
36 // t5 = g(t4);
37 // t6 = op(t2, t5)
38 // t20 = t5
39 // cond_branch <Loop>
40 //
41 // SROA does a good job of reusing a[i+1] as a[i] in the next iteration.
42 // Such a loop comes to this pass in the following form.
43 //
44 // LoopPreheader:
45 // X0 = a[0];
46 // Loop:
47 // X2 = PHI<(X0, LoopPreheader), (X1, Loop)>
48 // t1 = f(X2) <-- I1
49 // t2 = g(t1)
50 // ...
51 // X1 = a[i+1]
52 // t4 = f(X1) <-- I2
53 // t5 = g(t4)
54 // t6 = op(t2, t5)
55 // cond_branch <Loop>
56 //
57 // In this pass, we look for PHIs such as X2 whose incoming values come only
58 // from the Loop Preheader and over the backedge and additionaly, both these
59 // values are the results of the same operation in terms of opcode. We call such
60 // a PHI node a dependence chain or DepChain. In this case, the dependence of X2
61 // over X1 is carried over only one iteration and so the DepChain is only one
62 // PHI node long.
63 //
64 // Then, we traverse the uses of the PHI (X2) and the uses of the value of the
65 // PHI coming over the backedge (X1). We stop at the first pair of such users
66 // I1 (of X2) and I2 (of X1) that meet the following conditions.
67 // 1. I1 and I2 are the same operation, but with different operands.
68 // 2. X2 and X1 are used at the same operand number in the two instructions.
69 // 3. All other operands Op1 of I1 and Op2 of I2 are also such that there is a
70 // a DepChain from Op1 to Op2 of the same length as that between X2 and X1.
71 //
72 // We then make the following transformation
73 // LoopPreheader:
74 // X0 = a[0];
75 // Y0 = f(X0);
76 // Loop:
77 // X2 = PHI<(X0, LoopPreheader), (X1, Loop)>
78 // Y2 = PHI<(Y0, LoopPreheader), (t4, Loop)>
79 // t1 = f(X2) <-- Will be removed by DCE.
80 // t2 = g(Y2)
81 // ...
82 // X1 = a[i+1]
83 // t4 = f(X1)
84 // t5 = g(t4)
85 // t6 = op(t2, t5)
86 // cond_branch <Loop>
87 //
88 // We proceed until we cannot find any more such instructions I1 and I2.
89 //
90 // --- DepChains & Loop carried dependences ---
91 // Consider a single basic block loop such as
92 //
93 // LoopPreheader:
94 // X0 = ...
95 // Y0 = ...
96 // Loop:
97 // X2 = PHI<(X0, LoopPreheader), (X1, Loop)>
98 // Y2 = PHI<(Y0, LoopPreheader), (X2, Loop)>
99 // ...
100 // X1 = ...
101 // ...
102 // cond_branch <Loop>
103 //
104 // Then there is a dependence between X2 and X1 that goes back one iteration,
105 // i.e. X1 is used as X2 in the very next iteration. We represent this as a
106 // DepChain from X2 to X1 (X2->X1).
107 // Similarly, there is a dependence between Y2 and X1 that goes back two
108 // iterations. X1 is used as Y2 two iterations after it is computed. This is
109 // represented by a DepChain as (Y2->X2->X1).
110 //
111 // A DepChain has the following properties.
112 // 1. Num of edges in DepChain = Number of Instructions in DepChain = Number of
113 // iterations of carried dependence + 1.
114 // 2. All instructions in the DepChain except the last are PHIs.
115 //
116 //===----------------------------------------------------------------------===//
117 
118 #ifndef LLVM_LIB_TARGET_HEXAGON_HEXAGONVLCR_H
119 #define LLVM_LIB_TARGET_HEXAGON_HEXAGONVLCR_H
120 
122 
123 namespace llvm {
124 
125 class Loop;
126 
127 /// Hexagon Vector Loop Carried Reuse Pass
129  : public PassInfoMixin<HexagonVectorLoopCarriedReusePass> {
131 
132  /// Run pass over the Loop.
135 };
136 
137 } // end namespace llvm
138 
139 #endif // LLVM_LIB_TARGET_HEXAGON_HEXAGONVLCR_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
llvm::HexagonVectorLoopCarriedReusePass::HexagonVectorLoopCarriedReusePass
HexagonVectorLoopCarriedReusePass()
Definition: HexagonVectorLoopCarriedReuse.h:130
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:263
llvm::HexagonVectorLoopCarriedReusePass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &LAM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Run pass over the Loop.
Definition: HexagonVectorLoopCarriedReuse.cpp:225
LoopPassManager.h
LAM
LoopAnalysisManager LAM
Definition: PassBuilderBindings.cpp:58
llvm::HexagonVectorLoopCarriedReusePass
Hexagon Vector Loop Carried Reuse Pass.
Definition: HexagonVectorLoopCarriedReuse.h:128
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44