Movatterモバイル変換


[0]ホーム

URL:


LLVM 20.0.0git
LoopConstrainer.h
Go to the documentation of this file.
1//===- LoopConstrainer.h ----------------------------------------*- 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#ifndef LLVM_TRANSFORMS_UTILS_LOOP_CONSTRAINER_H
10#define LLVM_TRANSFORMS_UTILS_LOOP_CONSTRAINER_H
11
12#include "llvm/Support/Casting.h"
13#include "llvm/Transforms/Utils/ValueMapper.h"
14#include <optional>
15
16namespacellvm {
17
18classBasicBlock;
19classBranchInst;
20classDominatorTree;
21classIntegerType;
22classLoop;
23classLoopInfo;
24classPHINode;
25classScalarEvolution;
26classSCEV;
27classValue;
28
29// Keeps track of the structure of a loop. This is similar to llvm::Loop,
30// except that it is more lightweight and can track the state of a loop through
31// changing and potentially invalid IR. This structure also formalizes the
32// kinds of loops we can deal with -- ones that have a single latch that is also
33// an exiting block *and* have a canonical induction variable.
34structLoopStructure {
35constchar *Tag ="";
36
37BasicBlock *Header =nullptr;
38BasicBlock *Latch =nullptr;
39
40// `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th
41// successor is `LatchExit', the exit block of the loop.
42BranchInst *LatchBr =nullptr;
43BasicBlock *LatchExit =nullptr;
44unsignedLatchBrExitIdx = std::numeric_limits<unsigned>::max();
45
46// The loop represented by this instance of LoopStructure is semantically
47// equivalent to:
48//
49// intN_ty inc = IndVarIncreasing ? 1 : -1;
50// pred_ty predicate = IndVarIncreasing ? ICMP_SLT : ICMP_SGT;
51//
52// for (intN_ty iv = IndVarStart; predicate(iv, LoopExitAt); iv = IndVarBase)
53// ... body ...
54
55Value *IndVarBase =nullptr;
56Value *IndVarStart =nullptr;
57Value *IndVarStep =nullptr;
58Value *LoopExitAt =nullptr;
59boolIndVarIncreasing =false;
60boolIsSignedPredicate =true;
61IntegerType *ExitCountTy =nullptr;
62
63LoopStructure() =default;
64
65template <typename M>LoopStructuremap(M Map) const{
66LoopStructure Result;
67 Result.Tag =Tag;
68 Result.Header = cast<BasicBlock>(Map(Header));
69 Result.Latch = cast<BasicBlock>(Map(Latch));
70 Result.LatchBr = cast<BranchInst>(Map(LatchBr));
71 Result.LatchExit = cast<BasicBlock>(Map(LatchExit));
72 Result.LatchBrExitIdx =LatchBrExitIdx;
73 Result.IndVarBase = Map(IndVarBase);
74 Result.IndVarStart = Map(IndVarStart);
75 Result.IndVarStep = Map(IndVarStep);
76 Result.LoopExitAt = Map(LoopExitAt);
77 Result.IndVarIncreasing =IndVarIncreasing;
78 Result.IsSignedPredicate =IsSignedPredicate;
79 Result.ExitCountTy =ExitCountTy;
80return Result;
81 }
82
83static std::optional<LoopStructure>
84parseLoopStructure(ScalarEvolution &,Loop &,bool,constchar *&);
85};
86
87/// This class is used to constrain loops to run within a given iteration space.
88/// The algorithm this class implements is given a Loop and a range [Begin,
89/// End). The algorithm then tries to break out a "main loop" out of the loop
90/// it is given in a way that the "main loop" runs with the induction variable
91/// in a subset of [Begin, End). The algorithm emits appropriate pre and post
92/// loops to run any remaining iterations. The pre loop runs any iterations in
93/// which the induction variable is < Begin, and the post loop runs any
94/// iterations in which the induction variable is >= End.
95classLoopConstrainer {
96public:
97// Calculated subranges we restrict the iteration space of the main loop to.
98// See the implementation of `calculateSubRanges' for more details on how
99// these fields are computed. `LowLimit` is std::nullopt if there is no
100// restriction on low end of the restricted iteration space of the main loop.
101// `HighLimit` is std::nullopt if there is no restriction on high end of the
102// restricted iteration space of the main loop.
103
104structSubRanges {
105 std::optional<const SCEV *>LowLimit;
106 std::optional<const SCEV *>HighLimit;
107 };
108
109private:
110// The representation of a clone of the original loop we started out with.
111structClonedLoop {
112// The cloned blocks
113 std::vector<BasicBlock *>Blocks;
114
115// `Map` maps values in the clonee into values in the cloned version
116ValueToValueMapTy Map;
117
118// An instance of `LoopStructure` for the cloned loop
119LoopStructure Structure;
120 };
121
122// Result of rewriting the range of a loop. See changeIterationSpaceEnd for
123// more details on what these fields mean.
124structRewrittenRangeInfo {
125BasicBlock *PseudoExit =nullptr;
126BasicBlock *ExitSelector =nullptr;
127 std::vector<PHINode *> PHIValuesAtPseudoExit;
128PHINode *IndVarEnd =nullptr;
129
130 RewrittenRangeInfo() =default;
131 };
132
133// Clone `OriginalLoop' and return the result in CLResult. The IR after
134// running `cloneLoop' is well formed except for the PHI nodes in CLResult --
135// the PHI nodes say that there is an incoming edge from `OriginalPreheader`
136// but there is no such edge.
137void cloneLoop(ClonedLoop &CLResult,constchar *Tag)const;
138
139// Create the appropriate loop structure needed to describe a cloned copy of
140// `Original`. The clone is described by `VM`.
141 Loop *createClonedLoopStructure(Loop *Original, Loop *Parent,
142ValueToValueMapTy &VM,bool IsSubloop);
143
144// Rewrite the iteration space of the loop denoted by (LS, Preheader). The
145// iteration space of the rewritten loop ends at ExitLoopAt. The start of the
146// iteration space is not changed. `ExitLoopAt' is assumed to be slt
147// `OriginalHeaderCount'.
148//
149// If there are iterations left to execute, control is made to jump to
150// `ContinuationBlock', otherwise they take the normal loop exit. The
151// returned `RewrittenRangeInfo' object is populated as follows:
152//
153// .PseudoExit is a basic block that unconditionally branches to
154// `ContinuationBlock'.
155//
156// .ExitSelector is a basic block that decides, on exit from the loop,
157// whether to branch to the "true" exit or to `PseudoExit'.
158//
159// .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value
160// for each PHINode in the loop header on taking the pseudo exit.
161//
162// After changeIterationSpaceEnd, `Preheader' is no longer a legitimate
163// preheader because it is made to branch to the loop header only
164// conditionally.
165 RewrittenRangeInfo
166 changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader,
167 Value *ExitLoopAt,
168 BasicBlock *ContinuationBlock)const;
169
170// The loop denoted by `LS' has `OldPreheader' as its preheader. This
171// function creates a new preheader for `LS' and returns it.
172 BasicBlock *createPreheader(const LoopStructure &LS, BasicBlock *OldPreheader,
173constchar *Tag)const;
174
175// `ContinuationBlockAndPreheader' was the continuation block for some call to
176// `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'.
177// This function rewrites the PHI nodes in `LS.Header' to start with the
178// correct value.
179void rewriteIncomingValuesForPHIs(
180 LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader,
181const LoopConstrainer::RewrittenRangeInfo &RRI)const;
182
183// Even though we do not preserve any passes at this time, we at least need to
184// keep the parent loop structure consistent. The `LPPassManager' seems to
185// verify this after running a loop pass. This function adds the list of
186// blocks denoted by BBs to this loops parent loop if required.
187void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs);
188
189// Some global state.
190 Function &F;
191 LLVMContext &Ctx;
192 ScalarEvolution &SE;
193 DominatorTree &DT;
194 LoopInfo &LI;
195 function_ref<void(Loop *,bool)> LPMAddNewLoop;
196
197// Information about the original loop we started out with.
198 Loop &OriginalLoop;
199
200 BasicBlock *OriginalPreheader =nullptr;
201
202// The preheader of the main loop. This may or may not be different from
203// `OriginalPreheader'.
204 BasicBlock *MainLoopPreheader =nullptr;
205
206// Type of the range we need to run the main loop in.
207 Type *RangeTy;
208
209// The structure of the main loop (see comment at the beginning of this class
210// for a definition)
211 LoopStructure MainLoopStructure;
212
213 SubRanges SR;
214
215public:
216 LoopConstrainer(Loop &L, LoopInfo &LI,
217 function_ref<void(Loop *,bool)> LPMAddNewLoop,
218const LoopStructure &LS, ScalarEvolution &SE,
219 DominatorTree &DT, Type *T, SubRanges SR);
220
221// Entry point for the algorithm. Returns true on success.
222boolrun();
223};
224}// namespace llvm
225
226#endif// LLVM_TRANSFORMS_UTILS_LOOP_CONSTRAINER_H
Casting.h
Blocks
DenseMap< Block *, BlockRelaxAux > Blocks
Definition:ELF_riscv.cpp:507
ValueMapper.h
T
llvm::BasicBlock
LLVM Basic Block Representation.
Definition:BasicBlock.h:61
llvm::BranchInst
Conditional or Unconditional Branch instruction.
Definition:Instructions.h:3016
llvm::IntegerType
Class to represent integer types.
Definition:DerivedTypes.h:42
llvm::LoopConstrainer
This class is used to constrain loops to run within a given iteration space.
Definition:LoopConstrainer.h:95
llvm::LoopConstrainer::run
bool run()
Definition:LoopConstrainer.cpp:726
llvm::Loop
Represents a single loop in the control flow graph.
Definition:LoopInfo.h:39
llvm::PHINode
Definition:Instructions.h:2600
llvm::ScalarEvolution
The main scalar evolution driver.
Definition:ScalarEvolution.h:447
llvm::ValueMap< const Value *, WeakTrackingVH >
llvm::Value
LLVM Value Representation.
Definition:Value.h:74
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition:ISDOpcodes.h:71
llvm::TargetStackID::Value
Value
Definition:TargetFrameLowering.h:29
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition:AddressRanges.h:18
llvm::ValueToValueMapTy
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
Definition:MemorySSAUpdater.h:50
llvm::HighlightColor::Tag
@ Tag
llvm::LoopConstrainer::SubRanges
Definition:LoopConstrainer.h:104
llvm::LoopConstrainer::SubRanges::LowLimit
std::optional< const SCEV * > LowLimit
Definition:LoopConstrainer.h:105
llvm::LoopConstrainer::SubRanges::HighLimit
std::optional< const SCEV * > HighLimit
Definition:LoopConstrainer.h:106
llvm::LoopStructure
Definition:LoopConstrainer.h:34
llvm::LoopStructure::LatchExit
BasicBlock * LatchExit
Definition:LoopConstrainer.h:43
llvm::LoopStructure::IndVarBase
Value * IndVarBase
Definition:LoopConstrainer.h:55
llvm::LoopStructure::map
LoopStructure map(M Map) const
Definition:LoopConstrainer.h:65
llvm::LoopStructure::LatchBr
BranchInst * LatchBr
Definition:LoopConstrainer.h:42
llvm::LoopStructure::IndVarStart
Value * IndVarStart
Definition:LoopConstrainer.h:56
llvm::LoopStructure::Tag
const char * Tag
Definition:LoopConstrainer.h:35
llvm::LoopStructure::IndVarIncreasing
bool IndVarIncreasing
Definition:LoopConstrainer.h:59
llvm::LoopStructure::ExitCountTy
IntegerType * ExitCountTy
Definition:LoopConstrainer.h:61
llvm::LoopStructure::Header
BasicBlock * Header
Definition:LoopConstrainer.h:37
llvm::LoopStructure::IsSignedPredicate
bool IsSignedPredicate
Definition:LoopConstrainer.h:60
llvm::LoopStructure::Latch
BasicBlock * Latch
Definition:LoopConstrainer.h:38
llvm::LoopStructure::LoopStructure
LoopStructure()=default
llvm::LoopStructure::LoopExitAt
Value * LoopExitAt
Definition:LoopConstrainer.h:58
llvm::LoopStructure::IndVarStep
Value * IndVarStep
Definition:LoopConstrainer.h:57
llvm::LoopStructure::parseLoopStructure
static std::optional< LoopStructure > parseLoopStructure(ScalarEvolution &, Loop &, bool, const char *&)
Definition:LoopConstrainer.cpp:125
llvm::LoopStructure::LatchBrExitIdx
unsigned LatchBrExitIdx
Definition:LoopConstrainer.h:44

Generated on Thu Jul 17 2025 10:37:53 for LLVM by doxygen 1.9.6
[8]ページ先頭

©2009-2025 Movatter.jp