EIC code displayed by LXR master/​include/​llvm/​Transforms/​Utils/​LoopConstrainer.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-05-10 08:44:43

 //===- LoopConstrainer.h ----------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_LOOP_CONSTRAINER_H
 #define LLVM_TRANSFORMS_UTILS_LOOP_CONSTRAINER_H
 
 #include "llvm/Support/Casting.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 #include <optional>
 
 namespace llvm {
 
 class BasicBlock;
 class BranchInst;
 class DominatorTree;
 class IntegerType;
 class Loop;
 class LoopInfo;
 class PHINode;
 class ScalarEvolution;
 class SCEV;
 class Value;
 
 // Keeps track of the structure of a loop.  This is similar to llvm::Loop,
 // except that it is more lightweight and can track the state of a loop through
 // changing and potentially invalid IR.  This structure also formalizes the
 // kinds of loops we can deal with -- ones that have a single latch that is also
 // an exiting block *and* have a canonical induction variable.
 struct LoopStructure {
   const char *Tag = "";
 
   BasicBlock *Header = nullptr;
   BasicBlock *Latch = nullptr;
 
   // `Latch's terminator instruction is `LatchBr', and it's `LatchBrExitIdx'th
   // successor is `LatchExit', the exit block of the loop.
   BranchInst *LatchBr = nullptr;
   BasicBlock *LatchExit = nullptr;
   unsigned LatchBrExitIdx = std::numeric_limits<unsigned>::max();
 
   // The loop represented by this instance of LoopStructure is semantically
   // equivalent to:
   //
   // intN_ty inc = IndVarIncreasing ? 1 : -1;
   // pred_ty predicate = IndVarIncreasing ? ICMP_SLT : ICMP_SGT;
   //
   // for (intN_ty iv = IndVarStart; predicate(iv, LoopExitAt); iv = IndVarBase)
   //   ... body ...
 
   Value *IndVarBase = nullptr;
   Value *IndVarStart = nullptr;
   Value *IndVarStep = nullptr;
   Value *LoopExitAt = nullptr;
   bool IndVarIncreasing = false;
   bool IsSignedPredicate = true;
   IntegerType *ExitCountTy = nullptr;
 
   LoopStructure() = default;
 
   template <typename M> LoopStructure map(M Map) const {
     LoopStructure Result;
     Result.Tag = Tag;
     Result.Header = cast<BasicBlock>(Map(Header));
     Result.Latch = cast<BasicBlock>(Map(Latch));
     Result.LatchBr = cast<BranchInst>(Map(LatchBr));
     Result.LatchExit = cast<BasicBlock>(Map(LatchExit));
     Result.LatchBrExitIdx = LatchBrExitIdx;
     Result.IndVarBase = Map(IndVarBase);
     Result.IndVarStart = Map(IndVarStart);
     Result.IndVarStep = Map(IndVarStep);
     Result.LoopExitAt = Map(LoopExitAt);
     Result.IndVarIncreasing = IndVarIncreasing;
     Result.IsSignedPredicate = IsSignedPredicate;
     Result.ExitCountTy = ExitCountTy;
     return Result;
   }
 
   static std::optional<LoopStructure>
   parseLoopStructure(ScalarEvolution &, Loop &, bool, const char *&);
 };
 
 /// This class is used to constrain loops to run within a given iteration space.
 /// The algorithm this class implements is given a Loop and a range [Begin,
 /// End).  The algorithm then tries to break out a "main loop" out of the loop
 /// it is given in a way that the "main loop" runs with the induction variable
 /// in a subset of [Begin, End).  The algorithm emits appropriate pre and post
 /// loops to run any remaining iterations.  The pre loop runs any iterations in
 /// which the induction variable is < Begin, and the post loop runs any
 /// iterations in which the induction variable is >= End.
 class LoopConstrainer {
 public:
   // Calculated subranges we restrict the iteration space of the main loop to.
   // See the implementation of `calculateSubRanges' for more details on how
   // these fields are computed.  `LowLimit` is std::nullopt if there is no
   // restriction on low end of the restricted iteration space of the main loop.
   // `HighLimit` is std::nullopt if there is no restriction on high end of the
   // restricted iteration space of the main loop.
 
   struct SubRanges {
     std::optional<const SCEV *> LowLimit;
     std::optional<const SCEV *> HighLimit;
   };
 
 private:
   // The representation of a clone of the original loop we started out with.
   struct ClonedLoop {
     // The cloned blocks
     std::vector<BasicBlock *> Blocks;
 
     // `Map` maps values in the clonee into values in the cloned version
     ValueToValueMapTy Map;
 
     // An instance of `LoopStructure` for the cloned loop
     LoopStructure Structure;
   };
 
   // Result of rewriting the range of a loop.  See changeIterationSpaceEnd for
   // more details on what these fields mean.
   struct RewrittenRangeInfo {
     BasicBlock *PseudoExit = nullptr;
     BasicBlock *ExitSelector = nullptr;
     std::vector<PHINode *> PHIValuesAtPseudoExit;
     PHINode *IndVarEnd = nullptr;
 
     RewrittenRangeInfo() = default;
   };
 
   // Clone `OriginalLoop' and return the result in CLResult.  The IR after
   // running `cloneLoop' is well formed except for the PHI nodes in CLResult --
   // the PHI nodes say that there is an incoming edge from `OriginalPreheader`
   // but there is no such edge.
   void cloneLoop(ClonedLoop &CLResult, const char *Tag) const;
 
   // Create the appropriate loop structure needed to describe a cloned copy of
   // `Original`.  The clone is described by `VM`.
   Loop *createClonedLoopStructure(Loop *Original, Loop *Parent,
                                   ValueToValueMapTy &VM, bool IsSubloop);
 
   // Rewrite the iteration space of the loop denoted by (LS, Preheader). The
   // iteration space of the rewritten loop ends at ExitLoopAt.  The start of the
   // iteration space is not changed.  `ExitLoopAt' is assumed to be slt
   // `OriginalHeaderCount'.
   //
   // If there are iterations left to execute, control is made to jump to
   // `ContinuationBlock', otherwise they take the normal loop exit.  The
   // returned `RewrittenRangeInfo' object is populated as follows:
   //
   //  .PseudoExit is a basic block that unconditionally branches to
   //      `ContinuationBlock'.
   //
   //  .ExitSelector is a basic block that decides, on exit from the loop,
   //      whether to branch to the "true" exit or to `PseudoExit'.
   //
   //  .PHIValuesAtPseudoExit are PHINodes in `PseudoExit' that compute the value
   //      for each PHINode in the loop header on taking the pseudo exit.
   //
   // After changeIterationSpaceEnd, `Preheader' is no longer a legitimate
   // preheader because it is made to branch to the loop header only
   // conditionally.
   RewrittenRangeInfo
   changeIterationSpaceEnd(const LoopStructure &LS, BasicBlock *Preheader,
                           Value *ExitLoopAt,
                           BasicBlock *ContinuationBlock) const;
 
   // The loop denoted by `LS' has `OldPreheader' as its preheader.  This
   // function creates a new preheader for `LS' and returns it.
   BasicBlock *createPreheader(const LoopStructure &LS, BasicBlock *OldPreheader,
                               const char *Tag) const;
 
   // `ContinuationBlockAndPreheader' was the continuation block for some call to
   // `changeIterationSpaceEnd' and is the preheader to the loop denoted by `LS'.
   // This function rewrites the PHI nodes in `LS.Header' to start with the
   // correct value.
   void rewriteIncomingValuesForPHIs(
       LoopStructure &LS, BasicBlock *ContinuationBlockAndPreheader,
       const LoopConstrainer::RewrittenRangeInfo &RRI) const;
 
   // Even though we do not preserve any passes at this time, we at least need to
   // keep the parent loop structure consistent.  The `LPPassManager' seems to
   // verify this after running a loop pass.  This function adds the list of
   // blocks denoted by BBs to this loops parent loop if required.
   void addToParentLoopIfNeeded(ArrayRef<BasicBlock *> BBs);
 
   // Some global state.
   Function &F;
   LLVMContext &Ctx;
   ScalarEvolution &SE;
   DominatorTree &DT;
   LoopInfo &LI;
   function_ref<void(Loop *, bool)> LPMAddNewLoop;
 
   // Information about the original loop we started out with.
   Loop &OriginalLoop;
 
   BasicBlock *OriginalPreheader = nullptr;
 
   // The preheader of the main loop.  This may or may not be different from
   // `OriginalPreheader'.
   BasicBlock *MainLoopPreheader = nullptr;
 
   // Type of the range we need to run the main loop in.
   Type *RangeTy;
 
   // The structure of the main loop (see comment at the beginning of this class
   // for a definition)
   LoopStructure MainLoopStructure;
 
   SubRanges SR;
 
 public:
   LoopConstrainer(Loop &L, LoopInfo &LI,
                   function_ref<void(Loop *, bool)> LPMAddNewLoop,
                   const LoopStructure &LS, ScalarEvolution &SE,
                   DominatorTree &DT, Type *T, SubRanges SR);
 
   // Entry point for the algorithm.  Returns true on success.
   bool run();
 };
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_LOOP_CONSTRAINER_H

This page was automatically generated by the 2.3.7 LXR engine. The LXR team