contrib/llvm/include/llvm/Transforms/Utils/LoopVersioning.h

   1 //===- LoopVersioning.h - Utility to version a loop -------------*- 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 a utility class to perform loop versioning.  The versioned
  11 // loop speculates that otherwise may-aliasing memory accesses don't overlap and
  12 // emits checks to prove this.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
  17 #define LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
  18
  19 #include "llvm/Analysis/LoopAccessAnalysis.h"
  20 #include "llvm/Analysis/ScalarEvolution.h"
  21 #include "llvm/Transforms/Utils/ValueMapper.h"
  22 #include "llvm/Transforms/Utils/LoopUtils.h"
  23
  24 namespace llvm {
  25
  26 class Loop;
  27 class LoopAccessInfo;
  28 class LoopInfo;
  29 class ScalarEvolution;
  30
  31 /// \brief This class emits a version of the loop where run-time checks ensure
  32 /// that may-alias pointers can't overlap.
  33 ///
  34 /// It currently only supports single-exit loops and assumes that the loop
  35 /// already has a preheader.
  36 class LoopVersioning {
  37 public:
  38   /// \brief Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
  39   /// It uses runtime check provided by the user. If \p UseLAIChecks is true,
  40   /// we will retain the default checks made by LAI. Otherwise, construct an
  41   /// object having no checks and we expect the user to add them.
  42   LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
  43                  DominatorTree *DT, ScalarEvolution *SE,
  44                  bool UseLAIChecks = true);
  45
  46   /// \brief Performs the CFG manipulation part of versioning the loop including
  47   /// the DominatorTree and LoopInfo updates.
  48   ///
  49   /// The loop that was used to construct the class will be the "versioned" loop
  50   /// i.e. the loop that will receive control if all the memchecks pass.
  51   ///
  52   /// This allows the loop transform pass to operate on the same loop regardless
  53   /// of whether versioning was necessary or not:
  54   ///
  55   ///    for each loop L:
  56   ///        analyze L
  57   ///        if versioning is necessary version L
  58   ///        transform L
  59   void versionLoop() { versionLoop(findDefsUsedOutsideOfLoop(VersionedLoop)); }
  60
  61   /// \brief Same but if the client has already precomputed the set of values
  62   /// used outside the loop, this API will allows passing that.
  63   void versionLoop(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
  64
  65   /// \brief Returns the versioned loop.  Control flows here if pointers in the
  66   /// loop don't alias (i.e. all memchecks passed).  (This loop is actually the
  67   /// same as the original loop that we got constructed with.)
  68   Loop *getVersionedLoop() { return VersionedLoop; }
  69
  70   /// \brief Returns the fall-back loop.  Control flows here if pointers in the
  71   /// loop may alias (i.e. one of the memchecks failed).
  72   Loop *getNonVersionedLoop() { return NonVersionedLoop; }
  73
  74   /// \brief Sets the runtime alias checks for versioning the loop.
  75   void setAliasChecks(
  76       SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks);
  77
  78   /// \brief Sets the runtime SCEV checks for versioning the loop.
  79   void setSCEVChecks(SCEVUnionPredicate Check);
  80
  81   /// \brief Annotate memory instructions in the versioned loop with no-alias
  82   /// metadata based on the memchecks issued.
  83   ///
  84   /// This is just wrapper that calls prepareNoAliasMetadata and
  85   /// annotateInstWithNoAlias on the instructions of the versioned loop.
  86   void annotateLoopWithNoAlias();
  87
  88   /// \brief Set up the aliasing scopes based on the memchecks.  This needs to
  89   /// be called before the first call to annotateInstWithNoAlias.
  90   void prepareNoAliasMetadata();
  91
  92   /// \brief Add the noalias annotations to \p VersionedInst.
  93   ///
  94   /// \p OrigInst is the instruction corresponding to \p VersionedInst in the
  95   /// original loop.  Initialize the aliasing scopes with
  96   /// prepareNoAliasMetadata once before this can be called.
  97   void annotateInstWithNoAlias(Instruction *VersionedInst,
  98                                const Instruction *OrigInst);
  99
 100 private:
 101   /// \brief Adds the necessary PHI nodes for the versioned loops based on the
 102   /// loop-defined values used outside of the loop.
 103   ///
 104   /// This needs to be called after versionLoop if there are defs in the loop
 105   /// that are used outside the loop.
 106   void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
 107
 108   /// \brief Add the noalias annotations to \p I.  Initialize the aliasing
 109   /// scopes with prepareNoAliasMetadata once before this can be called.
 110   void annotateInstWithNoAlias(Instruction *I) {
 111     annotateInstWithNoAlias(I, I);
 112   }
 113
 114   /// \brief The original loop.  This becomes the "versioned" one.  I.e.,
 115   /// control flows here if pointers in the loop don't alias.
 116   Loop *VersionedLoop;
 117   /// \brief The fall-back loop.  I.e. control flows here if pointers in the
 118   /// loop may alias (memchecks failed).
 119   Loop *NonVersionedLoop;
 120
 121   /// \brief This maps the instructions from VersionedLoop to their counterpart
 122   /// in NonVersionedLoop.
 123   ValueToValueMapTy VMap;
 124
 125   /// \brief The set of alias checks that we are versioning for.
 126   SmallVector<RuntimePointerChecking::PointerCheck, 4> AliasChecks;
 127
 128   /// \brief The set of SCEV checks that we are versioning for.
 129   SCEVUnionPredicate Preds;
 130
 131   /// \brief Maps a pointer to the pointer checking group that the pointer
 132   /// belongs to.
 133   DenseMap<const Value *, const RuntimePointerChecking::CheckingPtrGroup *>
 134       PtrToGroup;
 135
 136   /// \brief The alias scope corresponding to a pointer checking group.
 137   DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *>
 138       GroupToScope;
 139
 140   /// \brief The list of alias scopes that a pointer checking group can't alias.
 141   DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *>
 142       GroupToNonAliasingScopeList;
 143
 144   /// \brief Analyses used.
 145   const LoopAccessInfo &LAI;
 146   LoopInfo *LI;
 147   DominatorTree *DT;
 148   ScalarEvolution *SE;
 149 };
 150 }
 151
 152 #endif