Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Transforms/Utils/LoopVersioning.h
Line
Count
Source
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
33
  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
3
  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
15
  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
133
  void annotateInstWithNoAlias(Instruction *I) {
110
133
    annotateInstWithNoAlias(I, I);
111
133
  }
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