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/ScalarEvolution.h"
19#include "llvm/IR/PassManager.h"
20#include "llvm/Transforms/Utils/LoopUtils.h"
21#include "llvm/Transforms/Utils/ValueMapper.h"
22
23namespace llvm {
24
25class Loop;
26class LoopAccessInfo;
27class LoopInfo;
28struct RuntimeCheckingPtrGroup;
29typedef std::pair<const RuntimeCheckingPtrGroup *,
30 const RuntimeCheckingPtrGroup *>
31 RuntimePointerCheck;
32
33template <typename T> class ArrayRef;
34
35/// This class emits a version of the loop where run-time checks ensure
36/// that may-alias pointers can't overlap.
37///
38/// It currently only supports single-exit loops and assumes that the loop
39/// already has a preheader.
40class LoopVersioning {
41public:
42 /// Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
43 /// It uses runtime check provided by the user. If \p UseLAIChecks is true,
44 /// we will retain the default checks made by LAI. Otherwise, construct an
45 /// object having no checks and we expect the user to add them.
46 LoopVersioning(const LoopAccessInfo &LAI,
47 ArrayRef<RuntimePointerCheck> Checks, Loop *L, LoopInfo *LI,
48 DominatorTree *DT, ScalarEvolution *SE);
49
50 /// Performs the CFG manipulation part of versioning the loop including
51 /// the DominatorTree and LoopInfo updates.
52 ///
53 /// The loop that was used to construct the class will be the "versioned" loop
54 /// i.e. the loop that will receive control if all the memchecks pass.
55 ///
56 /// This allows the loop transform pass to operate on the same loop regardless
57 /// of whether versioning was necessary or not:
58 ///
59 /// for each loop L:
60 /// analyze L
61 /// if versioning is necessary version L
62 /// transform L
63 void versionLoop() { versionLoop(findDefsUsedOutsideOfLoop(VersionedLoop)); }
64
65 /// Same but if the client has already precomputed the set of values
66 /// used outside the loop, this API will allows passing that.
67 void versionLoop(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
68
69 /// Returns the versioned loop. Control flows here if pointers in the
70 /// loop don't alias (i.e. all memchecks passed). (This loop is actually the
71 /// same as the original loop that we got constructed with.)
72 Loop *getVersionedLoop() { return VersionedLoop; }
73
74 /// Returns the fall-back loop. Control flows here if pointers in the
75 /// loop may alias (i.e. one of the memchecks failed).
76 Loop *getNonVersionedLoop() { return NonVersionedLoop; }
77
78 /// Annotate memory instructions in the versioned loop with no-alias
79 /// metadata based on the memchecks issued.
80 ///
81 /// This is just wrapper that calls prepareNoAliasMetadata and
82 /// annotateInstWithNoAlias on the instructions of the versioned loop.
83 void annotateLoopWithNoAlias();
84
85 /// Set up the aliasing scopes based on the memchecks. This needs to
86 /// be called before the first call to annotateInstWithNoAlias.
87 void prepareNoAliasMetadata();
88
89 /// Add the noalias annotations to \p VersionedInst.
90 ///
91 /// \p OrigInst is the instruction corresponding to \p VersionedInst in the
92 /// original loop. Initialize the aliasing scopes with
93 /// prepareNoAliasMetadata once before this can be called.
94 void annotateInstWithNoAlias(Instruction *VersionedInst,
95 const Instruction *OrigInst);
96
97private:
98 /// Adds the necessary PHI nodes for the versioned loops based on the
99 /// loop-defined values used outside of the loop.
100 ///
101 /// This needs to be called after versionLoop if there are defs in the loop
102 /// that are used outside the loop.
103 void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
104
105 /// Add the noalias annotations to \p I. Initialize the aliasing
106 /// scopes with prepareNoAliasMetadata once before this can be called.
107 void annotateInstWithNoAlias(Instruction *I) {
108 annotateInstWithNoAlias(I, I);
109 }
110
111 /// The original loop. This becomes the "versioned" one. I.e.,
112 /// control flows here if pointers in the loop don't alias.
113 Loop *VersionedLoop;
114 /// The fall-back loop. I.e. control flows here if pointers in the
115 /// loop may alias (memchecks failed).
116 Loop *NonVersionedLoop;
117
118 /// This maps the instructions from VersionedLoop to their counterpart
119 /// in NonVersionedLoop.
120 ValueToValueMapTy VMap;
121
122 /// The set of alias checks that we are versioning for.
123 SmallVector<RuntimePointerCheck, 4> AliasChecks;
124
125 /// The set of SCEV checks that we are versioning for.
126 const SCEVUnionPredicate &Preds;
127
128 /// Maps a pointer to the pointer checking group that the pointer
129 /// belongs to.
130 DenseMap<const Value *, const RuntimeCheckingPtrGroup *> PtrToGroup;
131
132 /// The alias scope corresponding to a pointer checking group.
133 DenseMap<const RuntimeCheckingPtrGroup *, MDNode *> GroupToScope;
134
135 /// The list of alias scopes that a pointer checking group can't alias.
136 DenseMap<const RuntimeCheckingPtrGroup *, MDNode *>
137 GroupToNonAliasingScopeList;
138
139 /// Analyses used.
140 const LoopAccessInfo &LAI;
141 LoopInfo *LI;
142 DominatorTree *DT;
143 ScalarEvolution *SE;
144};
145
146/// Expose LoopVersioning as a pass. Currently this is only used for
147/// unit-testing. It adds all memchecks necessary to remove all may-aliasing
148/// array accesses from the loop.
149class LoopVersioningPass : public PassInfoMixin<LoopVersioningPass> {
150public:
151 PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);
152};
153}
154
155#endif
156