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