1//===- LoopConstrainer.h ----------------------------------------*- C++ -*-===// 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 7//===----------------------------------------------------------------------===// 9#ifndef LLVM_TRANSFORMS_UTILS_LOOP_CONSTRAINER_H 10#define LLVM_TRANSFORMS_UTILS_LOOP_CONSTRAINER_H 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. 40// `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th 41// successor is `LatchExit', the exit block of the loop. 46// The loop represented by this instance of LoopStructure is semantically 49// intN_ty inc = IndVarIncreasing ? 1 : -1; 50// pred_ty predicate = IndVarIncreasing ? ICMP_SLT : ICMP_SGT; 52// for (intN_ty iv = IndVarStart; predicate(iv, LoopExitAt); iv = IndVarBase) 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));
83static std::optional<LoopStructure>
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. 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. 110// The representation of a clone of the original loop we started out with. 113 std::vector<BasicBlock *>
Blocks;
115// `Map` maps values in the clonee into values in the cloned version 118// An instance of `LoopStructure` for the cloned loop 122// Result of rewriting the range of a loop. See changeIterationSpaceEnd for 123// more details on what these fields mean. 124structRewrittenRangeInfo {
127 std::vector<PHINode *> PHIValuesAtPseudoExit;
130 RewrittenRangeInfo() =
default;
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;
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,
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'. 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: 153// .PseudoExit is a basic block that unconditionally branches to 154// `ContinuationBlock'. 156// .ExitSelector is a basic block that decides, on exit from the loop, 157// whether to branch to the "true" exit or to `PseudoExit'. 159// .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value 160// for each PHINode in the loop header on taking the pseudo exit. 162// After changeIterationSpaceEnd, `Preheader' is no longer a legitimate 163// preheader because it is made to branch to the loop header only 166 changeIterationSpaceEnd(
const LoopStructure &LS, BasicBlock *Preheader,
168 BasicBlock *ContinuationBlock)
const;
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,
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 179void rewriteIncomingValuesForPHIs(
180 LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader,
181const LoopConstrainer::RewrittenRangeInfo &RRI)
const;
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);
195 function_ref<void(Loop *,
bool)> LPMAddNewLoop;
197// Information about the original loop we started out with. 200 BasicBlock *OriginalPreheader =
nullptr;
202// The preheader of the main loop. This may or may not be different from 203// `OriginalPreheader'. 204 BasicBlock *MainLoopPreheader =
nullptr;
206// Type of the range we need to run the main loop in. 209// The structure of the main loop (see comment at the beginning of this class 211 LoopStructure MainLoopStructure;
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);
221// Entry point for the algorithm. Returns true on success. 226#endif// LLVM_TRANSFORMS_UTILS_LOOP_CONSTRAINER_H DenseMap< Block *, BlockRelaxAux > Blocks
LLVM Basic Block Representation.
Conditional or Unconditional Branch instruction.
Class to represent integer types.
This class is used to constrain loops to run within a given iteration space.
Represents a single loop in the control flow graph.
The main scalar evolution driver.
LLVM Value Representation.
@ BasicBlock
Various leaf nodes.
This is an optimization pass for GlobalISel generic memory operations.
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
std::optional< const SCEV * > LowLimit
std::optional< const SCEV * > HighLimit
LoopStructure map(M Map) const
IntegerType * ExitCountTy
static std::optional< LoopStructure > parseLoopStructure(ScalarEvolution &, Loop &, bool, const char *&)