LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Utils - LoopVersioning.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 2 4 50.0 %
Date: 2018-10-20 13:21:21 Functions: 1 3 33.3 %
Legend: Lines: hit not hit

          Line data    Source code
       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/LoopUtils.h"
      22             : #include "llvm/Transforms/Utils/ValueMapper.h"
      23             : 
      24             : namespace llvm {
      25             : 
      26             : class Loop;
      27             : class LoopAccessInfo;
      28             : class LoopInfo;
      29             : class ScalarEvolution;
      30             : 
      31             : /// 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             :   /// 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             :   /// 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          29 :   void versionLoop() { versionLoop(findDefsUsedOutsideOfLoop(VersionedLoop)); }
      60             : 
      61             :   /// 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             :   /// 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           0 :   Loop *getVersionedLoop() { return VersionedLoop; }
      69             : 
      70             :   /// Returns the fall-back loop.  Control flows here if pointers in the
      71             :   /// loop may alias (i.e. one of the memchecks failed).
      72           0 :   Loop *getNonVersionedLoop() { return NonVersionedLoop; }
      73             : 
      74             :   /// Sets the runtime alias checks for versioning the loop.
      75             :   void setAliasChecks(
      76             :       SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks);
      77             : 
      78             :   /// Sets the runtime SCEV checks for versioning the loop.
      79             :   void setSCEVChecks(SCEVUnionPredicate Check);
      80             : 
      81             :   /// 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             :   /// 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             :   /// 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             :   /// 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             :   /// 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         113 :     annotateInstWithNoAlias(I, I);
     112             :   }
     113             : 
     114             :   /// 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             :   /// The fall-back loop.  I.e. control flows here if pointers in the
     118             :   /// loop may alias (memchecks failed).
     119             :   Loop *NonVersionedLoop;
     120             : 
     121             :   /// This maps the instructions from VersionedLoop to their counterpart
     122             :   /// in NonVersionedLoop.
     123             :   ValueToValueMapTy VMap;
     124             : 
     125             :   /// The set of alias checks that we are versioning for.
     126             :   SmallVector<RuntimePointerChecking::PointerCheck, 4> AliasChecks;
     127             : 
     128             :   /// The set of SCEV checks that we are versioning for.
     129             :   SCEVUnionPredicate Preds;
     130             : 
     131             :   /// 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             :   /// The alias scope corresponding to a pointer checking group.
     137             :   DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *>
     138             :       GroupToScope;
     139             : 
     140             :   /// The list of alias scopes that a pointer checking group can't alias.
     141             :   DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *>
     142             :       GroupToNonAliasingScopeList;
     143             : 
     144             :   /// Analyses used.
     145             :   const LoopAccessInfo &LAI;
     146             :   LoopInfo *LI;
     147             :   DominatorTree *DT;
     148             :   ScalarEvolution *SE;
     149             : };
     150             : }
     151             : 
     152             : #endif

Generated by: LCOV version 1.13