1// Copyright (c) 2017 The Khronos Group Inc.
2// Copyright (c) 2017 Valve Corporation
3// Copyright (c) 2017 LunarG Inc.
4//
5// Licensed under the Apache License, Version 2.0 (the "License");
6// you may not use this file except in compliance with the License.
7// You may obtain a copy of the License at
8//
9// http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing, software
12// distributed under the License is distributed on an "AS IS" BASIS,
13// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14// See the License for the specific language governing permissions and
15// limitations under the License.
16
17#ifndef SOURCE_OPT_MEM_PASS_H_
18#define SOURCE_OPT_MEM_PASS_H_
19
20#include <algorithm>
21#include <list>
22#include <map>
23#include <queue>
24#include <unordered_map>
25#include <unordered_set>
26#include <utility>
27
28#include "source/opt/basic_block.h"
29#include "source/opt/def_use_manager.h"
30#include "source/opt/dominator_analysis.h"
31#include "source/opt/module.h"
32#include "source/opt/pass.h"
33
34namespace spvtools {
35namespace opt {
36
37// A common base class for mem2reg-type passes. Provides common
38// utility functions and supporting state.
39class MemPass : public Pass {
40 public:
41 virtual ~MemPass() = default;
42
43 // Returns an undef value for the given |var_id|'s type.
44 uint32_t GetUndefVal(uint32_t var_id) {
45 return Type2Undef(GetPointeeTypeId(get_def_use_mgr()->GetDef(var_id)));
46 }
47
48 // Given a load or store |ip|, return the pointer instruction.
49 // Also return the base variable's id in |varId|. If no base variable is
50 // found, |varId| will be 0.
51 Instruction* GetPtr(Instruction* ip, uint32_t* varId);
52
53 // Return true if |varId| is a previously identified target variable.
54 // Return false if |varId| is a previously identified non-target variable.
55 //
56 // Non-target variables are variable of function scope of a target type that
57 // are accessed with constant-index access chains. not accessed with
58 // non-constant-index access chains. Also cache non-target variables.
59 //
60 // If variable is not cached, return true if variable is a function scope
61 // variable of target type, false otherwise. Updates caches of target and
62 // non-target variables.
63 bool IsTargetVar(uint32_t varId);
64
65 // Collect target SSA variables. This traverses all the loads and stores in
66 // function |func| looking for variables that can be replaced with SSA IDs. It
67 // populates the sets |seen_target_vars_| and |seen_non_target_vars_|.
68 void CollectTargetVars(Function* func);
69
70 protected:
71 MemPass();
72
73 // Returns true if |typeInst| is a scalar type
74 // or a vector or matrix
75 bool IsBaseTargetType(const Instruction* typeInst) const;
76
77 // Returns true if |typeInst| is a math type or a struct or array
78 // of a math type.
79 // TODO(): Add more complex types to convert
80 bool IsTargetType(const Instruction* typeInst) const;
81
82 // Returns true if |opcode| is a non-ptr access chain op
83 bool IsNonPtrAccessChain(const SpvOp opcode) const;
84
85 // Given the id |ptrId|, return true if the top-most non-CopyObj is
86 // a variable, a non-ptr access chain or a parameter of pointer type.
87 bool IsPtr(uint32_t ptrId);
88
89 // Given the id of a pointer |ptrId|, return the top-most non-CopyObj.
90 // Also return the base variable's id in |varId|. If no base variable is
91 // found, |varId| will be 0.
92 Instruction* GetPtr(uint32_t ptrId, uint32_t* varId);
93
94 // Return true if all uses of |id| are only name or decorate ops.
95 bool HasOnlyNamesAndDecorates(uint32_t id) const;
96
97 // Kill all instructions in block |bp|. Whether or not to kill the label is
98 // indicated by |killLabel|.
99 void KillAllInsts(BasicBlock* bp, bool killLabel = true);
100
101 // Return true if any instruction loads from |varId|
102 bool HasLoads(uint32_t varId) const;
103
104 // Return true if |varId| is not a function variable or if it has
105 // a load
106 bool IsLiveVar(uint32_t varId) const;
107
108 // Add stores using |ptr_id| to |insts|
109 void AddStores(uint32_t ptr_id, std::queue<Instruction*>* insts);
110
111 // Delete |inst| and iterate DCE on all its operands if they are now
112 // useless. If a load is deleted and its variable has no other loads,
113 // delete all its variable's stores.
114 void DCEInst(Instruction* inst, const std::function<void(Instruction*)>&);
115
116 // Call all the cleanup helper functions on |func|.
117 bool CFGCleanup(Function* func);
118
119 // Return true if |op| is supported decorate.
120 inline bool IsNonTypeDecorate(uint32_t op) const {
121 return (op == SpvOpDecorate || op == SpvOpDecorateId);
122 }
123
124 // Return the id of an undef value with type |type_id|. Create and insert an
125 // undef after the first non-variable in the function if it doesn't already
126 // exist. Add undef to function undef map. Returns 0 of the value does not
127 // exist, and cannot be created.
128 uint32_t Type2Undef(uint32_t type_id);
129
130 // Cache of verified target vars
131 std::unordered_set<uint32_t> seen_target_vars_;
132
133 // Cache of verified non-target vars
134 std::unordered_set<uint32_t> seen_non_target_vars_;
135
136 private:
137 // Return true if all uses of |varId| are only through supported reference
138 // operations ie. loads and store. Also cache in supported_ref_vars_.
139 // TODO(dnovillo): This function is replicated in other passes and it's
140 // slightly different in every pass. Is it possible to make one common
141 // implementation?
142 bool HasOnlySupportedRefs(uint32_t varId);
143
144 // Remove all the unreachable basic blocks in |func|.
145 bool RemoveUnreachableBlocks(Function* func);
146
147 // Remove the block pointed by the iterator |*bi|. This also removes
148 // all the instructions in the pointed-to block.
149 void RemoveBlock(Function::iterator* bi);
150
151 // Remove Phi operands in |phi| that are coming from blocks not in
152 // |reachable_blocks|.
153 void RemovePhiOperands(
154 Instruction* phi,
155 const std::unordered_set<BasicBlock*>& reachable_blocks);
156
157 // Map from type to undef
158 std::unordered_map<uint32_t, uint32_t> type2undefs_;
159};
160
161} // namespace opt
162} // namespace spvtools
163
164#endif // SOURCE_OPT_MEM_PASS_H_
165