Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Transforms/Utils/SSAUpdater.h
Line
Count
Source (jump to first uncovered line)
1
//===- SSAUpdater.h - Unstructured SSA Update Tool --------------*- 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 declares the SSAUpdater class.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H
14
#define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H
15
16
#include "llvm/ADT/ArrayRef.h"
17
#include "llvm/ADT/StringRef.h"
18
#include <string>
19
20
namespace llvm {
21
22
class BasicBlock;
23
class Instruction;
24
class LoadInst;
25
class PHINode;
26
template <typename T> class SmallVectorImpl;
27
template <typename T> class SSAUpdaterTraits;
28
class Type;
29
class Use;
30
class Value;
31
32
/// Helper class for SSA formation on a set of values defined in
33
/// multiple blocks.
34
///
35
/// This is used when code duplication or another unstructured
36
/// transformation wants to rewrite a set of uses of one value with uses of a
37
/// set of values.
38
class SSAUpdater {
39
  friend class SSAUpdaterTraits<SSAUpdater>;
40
41
private:
42
  /// This keeps track of which value to use on a per-block basis. When we
43
  /// insert PHI nodes, we keep track of them here.
44
  void *AV = nullptr;
45
46
  /// ProtoType holds the type of the values being rewritten.
47
  Type *ProtoType = nullptr;
48
49
  /// PHI nodes are given a name based on ProtoName.
50
  std::string ProtoName;
51
52
  /// If this is non-null, the SSAUpdater adds all PHI nodes that it creates to
53
  /// the vector.
54
  SmallVectorImpl<PHINode *> *InsertedPHIs;
55
56
public:
57
  /// If InsertedPHIs is specified, it will be filled
58
  /// in with all PHI Nodes created by rewriting.
59
  explicit SSAUpdater(SmallVectorImpl<PHINode *> *InsertedPHIs = nullptr);
60
  SSAUpdater(const SSAUpdater &) = delete;
61
  SSAUpdater &operator=(const SSAUpdater &) = delete;
62
  ~SSAUpdater();
63
64
  /// Reset this object to get ready for a new set of SSA updates with
65
  /// type 'Ty'.
66
  ///
67
  /// PHI nodes get a name based on 'Name'.
68
  void Initialize(Type *Ty, StringRef Name);
69
70
  /// Indicate that a rewritten value is available in the specified block
71
  /// with the specified value.
72
  void AddAvailableValue(BasicBlock *BB, Value *V);
73
74
  /// Return true if the SSAUpdater already has a value for the specified
75
  /// block.
76
  bool HasValueForBlock(BasicBlock *BB) const;
77
78
  /// Return the value for the specified block if the SSAUpdater has one,
79
  /// otherwise return nullptr.
80
  Value *FindValueForBlock(BasicBlock *BB) const;
81
82
  /// Construct SSA form, materializing a value that is live at the end
83
  /// of the specified block.
84
  Value *GetValueAtEndOfBlock(BasicBlock *BB);
85
86
  /// Construct SSA form, materializing a value that is live in the
87
  /// middle of the specified block.
88
  ///
89
  /// \c GetValueInMiddleOfBlock is the same as \c GetValueAtEndOfBlock except
90
  /// in one important case: if there is a definition of the rewritten value
91
  /// after the 'use' in BB.  Consider code like this:
92
  ///
93
  /// \code
94
  ///      X1 = ...
95
  ///   SomeBB:
96
  ///      use(X)
97
  ///      X2 = ...
98
  ///      br Cond, SomeBB, OutBB
99
  /// \endcode
100
  ///
101
  /// In this case, there are two values (X1 and X2) added to the AvailableVals
102
  /// set by the client of the rewriter, and those values are both live out of
103
  /// their respective blocks.  However, the use of X happens in the *middle* of
104
  /// a block.  Because of this, we need to insert a new PHI node in SomeBB to
105
  /// merge the appropriate values, and this value isn't live out of the block.
106
  Value *GetValueInMiddleOfBlock(BasicBlock *BB);
107
108
  /// Rewrite a use of the symbolic value.
109
  ///
110
  /// This handles PHI nodes, which use their value in the corresponding
111
  /// predecessor. Note that this will not work if the use is supposed to be
112
  /// rewritten to a value defined in the same block as the use, but above it.
113
  /// Any 'AddAvailableValue's added for the use's block will be considered to
114
  /// be below it.
115
  void RewriteUse(Use &U);
116
117
  /// Rewrite a use like \c RewriteUse but handling in-block definitions.
118
  ///
119
  /// This version of the method can rewrite uses in the same block as
120
  /// a definition, because it assumes that all uses of a value are below any
121
  /// inserted values.
122
  void RewriteUseAfterInsertions(Use &U);
123
124
private:
125
  Value *GetValueAtEndOfBlockInternal(BasicBlock *BB);
126
};
127
128
/// Helper class for promoting a collection of loads and stores into SSA
129
/// Form using the SSAUpdater.
130
///
131
/// This handles complexities that SSAUpdater doesn't, such as multiple loads
132
/// and stores in one block.
133
///
134
/// Clients of this class are expected to subclass this and implement the
135
/// virtual methods.
136
class LoadAndStorePromoter {
137
protected:
138
  SSAUpdater &SSA;
139
140
public:
141
  LoadAndStorePromoter(ArrayRef<const Instruction *> Insts,
142
                       SSAUpdater &S, StringRef Name = StringRef());
143
2.51k
  virtual ~LoadAndStorePromoter() = default;
144
145
  /// This does the promotion.
146
  ///
147
  /// Insts is a list of loads and stores to promote, and Name is the basename
148
  /// for the PHIs to insert. After this is complete, the loads and stores are
149
  /// removed from the code.
150
  void run(const SmallVectorImpl<Instruction *> &Insts);
151
152
  /// Return true if the specified instruction is in the Inst list.
153
  ///
154
  /// The Insts list is the one passed into the constructor. Clients should
155
  /// implement this with a more efficient version if possible.
156
  virtual bool isInstInList(Instruction *I,
157
                            const SmallVectorImpl<Instruction *> &Insts) const;
158
159
  /// This hook is invoked after all the stores are found and inserted as
160
  /// available values.
161
0
  virtual void doExtraRewritesBeforeFinalDeletion() {}
162
163
  /// Clients can choose to implement this to get notified right before
164
  /// a load is RAUW'd another value.
165
47
  virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const {}
166
167
  /// Called before each instruction is deleted.
168
94
  virtual void instructionDeleted(Instruction *I) const {}
169
170
  /// Called to update debug info associated with the instruction.
171
2.95k
  virtual void updateDebugInfo(Instruction *I) const {}
172
};
173
174
} // end namespace llvm
175
176
#endif // LLVM_TRANSFORMS_UTILS_SSAUPDATER_H