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
24namespace llvm {
25
26class Loop;
27class LoopAccessInfo;
28class LoopInfo;
29class 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.
36class LoopVersioning {
37public:
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      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
100private:
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.
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