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       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