include/llvm/Transforms/Utils/LoopVersioning.h

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