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/Transforms/Utils/ValueMapper.h"
  20
  21 namespace llvm {
  22
  23 class Loop;
  24 class LoopAccessInfo;
  25 class LoopInfo;
  26
  27 /// \brief This class emits a version of the loop where run-time checks ensure
  28 /// that may-alias pointers can't overlap.
  29 ///
  30 /// It currently only supports single-exit loops and assumes that the loop
  31 /// already has a preheader.
  32 class LoopVersioning {
  33 public:
  34   LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
  35                  DominatorTree *DT,
  36                  const SmallVector<int, 8> *PtrToPartition = nullptr);
  37
  38   /// \brief Returns true if we need memchecks to disambiguate may-aliasing
  39   /// accesses.
  40   bool needsRuntimeChecks() const;
  41
  42   /// \brief Performs the CFG manipulation part of versioning the loop including
  43   /// the DominatorTree and LoopInfo updates.
  44   ///
  45   /// The loop that was used to construct the class will be the "versioned" loop
  46   /// i.e. the loop that will receive control if all the memchecks pass.
  47   ///
  48   /// This allows the loop transform pass to operate on the same loop regardless
  49   /// of whether versioning was necessary or not:
  50   ///
  51   ///    for each loop L:
  52   ///        analyze L
  53   ///        if versioning is necessary version L
  54   ///        transform L
  55   void versionLoop(Pass *P);
  56
  57   /// \brief Adds the necessary PHI nodes for the versioned loops based on the
  58   /// loop-defined values used outside of the loop.
  59   ///
  60   /// This needs to be called after versionLoop if there are defs in the loop
  61   /// that are used outside the loop.  FIXME: this should be invoked internally
  62   /// by versionLoop and made private.
  63   void addPHINodes(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 private:
  75   /// \brief The original loop.  This becomes the "versioned" one.  I.e.,
  76   /// control flows here if pointers in the loop don't alias.
  77   Loop *VersionedLoop;
  78   /// \brief The fall-back loop.  I.e. control flows here if pointers in the
  79   /// loop may alias (memchecks failed).
  80   Loop *NonVersionedLoop;
  81
  82   /// \brief For each memory pointer it contains the partitionId it is used in.
  83   /// If nullptr, no partitioning is used.
  84   ///
  85   /// The I-th entry corresponds to I-th entry in LAI.getRuntimePointerCheck().
  86   /// If the pointer is used in multiple partitions the entry is set to -1.
  87   const SmallVector<int, 8> *PtrToPartition;
  88
  89   /// \brief This maps the instructions from VersionedLoop to their counterpart
  90   /// in NonVersionedLoop.
  91   ValueToValueMapTy VMap;
  92
  93   /// \brief Analyses used.
  94   const LoopAccessInfo &LAI;
  95   LoopInfo *LI;
  96   DominatorTree *DT;
  97 };
  98 }
  99
 100 #endif