Home | History | Annotate | Download | only in Utils 
      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       const SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks);
     77 
     78   /// \brief Sets the runtime SCEV checks for versioning the loop.
     79   void setSCEVChecks(SCEVUnionPredicate Check);
     80 
     81 private:
     82   /// \brief Adds the necessary PHI nodes for the versioned loops based on the
     83   /// loop-defined values used outside of the loop.
     84   ///
     85   /// This needs to be called after versionLoop if there are defs in the loop
     86   /// that are used outside the loop.
     87   void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
     88 
     89   /// \brief The original loop.  This becomes the "versioned" one.  I.e.,
     90   /// control flows here if pointers in the loop don't alias.
     91   Loop *VersionedLoop;
     92   /// \brief The fall-back loop.  I.e. control flows here if pointers in the
     93   /// loop may alias (memchecks failed).
     94   Loop *NonVersionedLoop;
     95 
     96   /// \brief This maps the instructions from VersionedLoop to their counterpart
     97   /// in NonVersionedLoop.
     98   ValueToValueMapTy VMap;
     99 
    100   /// \brief The set of alias checks that we are versioning for.
    101   SmallVector<RuntimePointerChecking::PointerCheck, 4> AliasChecks;
    102 
    103   /// \brief The set of SCEV checks that we are versioning for.
    104   SCEVUnionPredicate Preds;
    105 
    106   /// \brief Analyses used.
    107   const LoopAccessInfo &LAI;
    108   LoopInfo *LI;
    109   DominatorTree *DT;
    110   ScalarEvolution *SE;
    111 };
    112 }
    113 
    114 #endif
    115