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/Transforms/Utils/ValueMapper.h"
  21 #include "llvm/Transforms/Utils/LoopUtils.h"
  22
  23 namespace llvm {
  24
  25 class Loop;
  26 class LoopAccessInfo;
  27 class LoopInfo;
  28
  29 /// \brief This class emits a version of the loop where run-time checks ensure
  30 /// that may-alias pointers can't overlap.
  31 ///
  32 /// It currently only supports single-exit loops and assumes that the loop
  33 /// already has a preheader.
  34 class LoopVersioning {
  35 public:
  36   /// \brief Expects MemCheck, LoopAccessInfo, Loop, LoopInfo, DominatorTree
  37   /// as input. It uses runtime check provided by user.
  38   LoopVersioning(SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks,
  39                  const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
  40                  DominatorTree *DT);
  41
  42   /// \brief Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
  43   /// It uses default runtime check provided by LoopAccessInfo.
  44   LoopVersioning(const LoopAccessInfo &LAInfo, Loop *L, LoopInfo *LI,
  45                  DominatorTree *DT);
  46
  47   /// \brief Performs the CFG manipulation part of versioning the loop including
  48   /// the DominatorTree and LoopInfo updates.
  49   ///
  50   /// The loop that was used to construct the class will be the "versioned" loop
  51   /// i.e. the loop that will receive control if all the memchecks pass.
  52   ///
  53   /// This allows the loop transform pass to operate on the same loop regardless
  54   /// of whether versioning was necessary or not:
  55   ///
  56   ///    for each loop L:
  57   ///        analyze L
  58   ///        if versioning is necessary version L
  59   ///        transform L
  60   void versionLoop() { versionLoop(findDefsUsedOutsideOfLoop(VersionedLoop)); }
  61
  62   /// \brief Same but if the client has already precomputed the set of values
  63   /// used outside the loop, this API will allows passing that.
  64   void versionLoop(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
  65
  66   /// \brief Returns the versioned loop.  Control flows here if pointers in the
  67   /// loop don't alias (i.e. all memchecks passed).  (This loop is actually the
  68   /// same as the original loop that we got constructed with.)
  69   Loop *getVersionedLoop() { return VersionedLoop; }
  70
  71   /// \brief Returns the fall-back loop.  Control flows here if pointers in the
  72   /// loop may alias (i.e. one of the memchecks failed).
  73   Loop *getNonVersionedLoop() { return NonVersionedLoop; }
  74
  75 private:
  76   /// \brief Adds the necessary PHI nodes for the versioned loops based on the
  77   /// loop-defined values used outside of the loop.
  78   ///
  79   /// This needs to be called after versionLoop if there are defs in the loop
  80   /// that are used outside the loop.
  81   void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
  82
  83   /// \brief The original loop.  This becomes the "versioned" one.  I.e.,
  84   /// control flows here if pointers in the loop don't alias.
  85   Loop *VersionedLoop;
  86   /// \brief The fall-back loop.  I.e. control flows here if pointers in the
  87   /// loop may alias (memchecks failed).
  88   Loop *NonVersionedLoop;
  89
  90   /// \brief This maps the instructions from VersionedLoop to their counterpart
  91   /// in NonVersionedLoop.
  92   ValueToValueMapTy VMap;
  93
  94   /// \brief The set of checks that we are versioning for.
  95   SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks;
  96
  97   /// \brief Analyses used.
  98   const LoopAccessInfo &LAI;
  99   LoopInfo *LI;
 100   DominatorTree *DT;
 101 };
 102 }
 103
 104 #endif