include/llvm/Transforms/Utils/LoopUtils.h

   1 //===- llvm/Transforms/Utils/LoopUtils.h - Loop utilities -*- C++ -*-=========//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines some loop transformation utilities.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
  15 #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
  16
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/IR/Dominators.h"
  19
  20 namespace llvm {
  21 class AliasAnalysis;
  22 class AliasSet;
  23 class AliasSetTracker;
  24 class AssumptionCache;
  25 class BasicBlock;
  26 class DataLayout;
  27 class DominatorTree;
  28 class Loop;
  29 class LoopInfo;
  30 class Pass;
  31 class PredIteratorCache;
  32 class ScalarEvolution;
  33 class TargetLibraryInfo;
  34
  35 /// \brief Captures loop safety information.
  36 /// It keep information for loop & its header may throw exception.
  37 struct LICMSafetyInfo {
  38   bool MayThrow;           // The current loop contains an instruction which
  39                            // may throw.
  40   bool HeaderMayThrow;     // Same as previous, but specific to loop header
  41   LICMSafetyInfo() : MayThrow(false), HeaderMayThrow(false)
  42   {}
  43 };
  44
  45 BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P);
  46
  47 /// \brief Simplify each loop in a loop nest recursively.
  48 ///
  49 /// This takes a potentially un-simplified loop L (and its children) and turns
  50 /// it into a simplified loop nest with preheaders and single backedges. It
  51 /// will optionally update \c AliasAnalysis and \c ScalarEvolution analyses if
  52 /// passed into it.
  53 bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, Pass *PP,
  54                   AliasAnalysis *AA = nullptr, ScalarEvolution *SE = nullptr,
  55                   const DataLayout *DL = nullptr,
  56                   AssumptionCache *AC = nullptr);
  57
  58 /// \brief Put loop into LCSSA form.
  59 ///
  60 /// Looks at all instructions in the loop which have uses outside of the
  61 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
  62 /// the loop are rewritten to use this node.
  63 ///
  64 /// LoopInfo and DominatorTree are required and preserved.
  65 ///
  66 /// If ScalarEvolution is passed in, it will be preserved.
  67 ///
  68 /// Returns true if any modifications are made to the loop.
  69 bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
  70                ScalarEvolution *SE = nullptr);
  71
  72 /// \brief Put a loop nest into LCSSA form.
  73 ///
  74 /// This recursively forms LCSSA for a loop nest.
  75 ///
  76 /// LoopInfo and DominatorTree are required and preserved.
  77 ///
  78 /// If ScalarEvolution is passed in, it will be preserved.
  79 ///
  80 /// Returns true if any modifications are made to the loop.
  81 bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
  82                           ScalarEvolution *SE = nullptr);
  83
  84 /// \brief Walk the specified region of the CFG (defined by all blocks
  85 /// dominated by the specified block, and that are in the current loop) in
  86 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
  87 /// uses before definitions, allowing us to sink a loop body in one pass without
  88 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
  89 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
  90 /// instructions of the loop and loop safety information as arguments.
  91 /// It returns changed status.
  92 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
  93                 const DataLayout *, TargetLibraryInfo *, Loop *,
  94                 AliasSetTracker *, LICMSafetyInfo *);
  95
  96 /// \brief Walk the specified region of the CFG (defined by all blocks
  97 /// dominated by the specified block, and that are in the current loop) in depth
  98 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
  99 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 100 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
 101 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 102 /// loop and loop safety information as arguments. It returns changed status.
 103 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
 104                  const DataLayout *, TargetLibraryInfo *, Loop *,
 105                  AliasSetTracker *, LICMSafetyInfo *);
 106
 107 /// \brief Try to promote memory values to scalars by sinking stores out of
 108 /// the loop and moving loads to before the loop.  We do this by looping over
 109 /// the stores in the loop, looking for stores to Must pointers which are
 110 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
 111 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
 112 /// AliasSet information for all instructions of the loop and loop safety
 113 /// information as arguments. It returns changed status.
 114 bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock*> &,
 115                                   SmallVectorImpl<Instruction*> &,
 116                                   PredIteratorCache &, LoopInfo *,
 117                                   DominatorTree *, Loop *, AliasSetTracker *,
 118                                   LICMSafetyInfo *);
 119
 120 /// \brief Computes safety information for a loop
 121 /// checks loop body & header for the possiblity of may throw
 122 /// exception, it takes LICMSafetyInfo and loop as argument.
 123 /// Updates safety information in LICMSafetyInfo argument.
 124 void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *);
 125
 126 }
 127
 128 #endif