• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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
versionLoop()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.)
getVersionedLoop()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).
getNonVersionedLoop()72   Loop *getNonVersionedLoop() { return NonVersionedLoop; }
73 
74   /// \brief Sets the runtime alias checks for versioning the loop.
75   void setAliasChecks(
76       SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks);
77 
78   /// \brief Sets the runtime SCEV checks for versioning the loop.
79   void setSCEVChecks(SCEVUnionPredicate Check);
80 
81   /// \brief 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   /// \brief 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   /// \brief 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   /// \brief 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   /// \brief Add the noalias annotations to \p I.  Initialize the aliasing
109   /// scopes with prepareNoAliasMetadata once before this can be called.
annotateInstWithNoAlias(Instruction * I)110   void annotateInstWithNoAlias(Instruction *I) {
111     annotateInstWithNoAlias(I, I);
112   }
113 
114   /// \brief 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   /// \brief The fall-back loop.  I.e. control flows here if pointers in the
118   /// loop may alias (memchecks failed).
119   Loop *NonVersionedLoop;
120 
121   /// \brief This maps the instructions from VersionedLoop to their counterpart
122   /// in NonVersionedLoop.
123   ValueToValueMapTy VMap;
124 
125   /// \brief The set of alias checks that we are versioning for.
126   SmallVector<RuntimePointerChecking::PointerCheck, 4> AliasChecks;
127 
128   /// \brief The set of SCEV checks that we are versioning for.
129   SCEVUnionPredicate Preds;
130 
131   /// \brief 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   /// \brief The alias scope corresponding to a pointer checking group.
137   DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *>
138       GroupToScope;
139 
140   /// \brief The list of alias scopes that a pointer checking group can't alias.
141   DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *>
142       GroupToNonAliasingScopeList;
143 
144   /// \brief Analyses used.
145   const LoopAccessInfo &LAI;
146   LoopInfo *LI;
147   DominatorTree *DT;
148   ScalarEvolution *SE;
149 };
150 }
151 
152 #endif
153