1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
// Copyright (c) 2017 The Khronos Group Inc.
// Copyright (c) 2017 Valve Corporation
// Copyright (c) 2017 LunarG Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef LIBSPIRV_OPT_DEAD_BRANCH_ELIM_PASS_H_
#define LIBSPIRV_OPT_DEAD_BRANCH_ELIM_PASS_H_
#include <algorithm>
#include <map>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include "basic_block.h"
#include "def_use_manager.h"
#include "module.h"
#include "pass.h"
namespace spvtools {
namespace opt {
// See optimizer.hpp for documentation.
class DeadBranchElimPass : public Pass {
using cbb_ptr = const ir::BasicBlock*;
public:
using GetBlocksFunction =
std::function<std::vector<ir::BasicBlock*>*(const ir::BasicBlock*)>;
DeadBranchElimPass();
const char* name() const override { return "dead-branch-elim"; }
Status Process(ir::Module*) override;
private:
// Returns the id of the merge block declared by a merge instruction in
// this block |blk|, if any. If none, returns zero. If loop merge, returns
// the continue target id in |cbid|. Otherwise sets to zero.
uint32_t MergeBlockIdIfAny(const ir::BasicBlock& blk, uint32_t* cbid) const;
// Compute structured successors for function |func|.
// A block's structured successors are the blocks it branches to
// together with its declared merge block if it has one.
// When order matters, the merge block always appears first and if
// a loop merge block, the continue target always appears second.
// This assures correct depth first search in the presence of early
// returns and kills. If the successor vector contain duplicates
// of the merge and continue blocks, they are safely ignored by DFS.
void ComputeStructuredSuccessors(ir::Function* func);
// Compute structured block order |order| for function |func|. This order
// has the property that dominators are before all blocks they dominate and
// merge blocks are after all blocks that are in the control constructs of
// their header.
void ComputeStructuredOrder(
ir::Function* func, std::list<ir::BasicBlock*>* order);
// If |condId| is boolean constant, return value in |condVal| and
// |condIsConst| as true, otherwise return |condIsConst| as false.
void GetConstCondition(uint32_t condId, bool* condVal, bool* condIsConst);
// Add branch to |labelId| to end of block |bp|.
void AddBranch(uint32_t labelId, ir::BasicBlock* bp);
// Add selction merge of |labelId| to end of block |bp|.
void AddSelectionMerge(uint32_t labelId, ir::BasicBlock* bp);
// Add conditional branch of |condId|, |trueLabId| and |falseLabId| to end
// of block |bp|.
void AddBranchConditional(uint32_t condId, uint32_t trueLabId,
uint32_t falseLabId, ir::BasicBlock* bp);
// Kill all instructions in block |bp|.
void KillAllInsts(ir::BasicBlock* bp);
// If block |bp| contains constant conditional branch preceeded by an
// OpSelctionMerge, return true and return branch and merge instructions
// in |branchInst| and |mergeInst| and the boolean constant in |condVal|.
bool GetConstConditionalSelectionBranch(ir::BasicBlock* bp,
ir::Instruction** branchInst, ir::Instruction** mergeInst,
uint32_t *condId, bool *condVal);
// Return true if |labelId| has any non-phi references
bool HasNonPhiRef(uint32_t labelId);
// Return true if |op| is supported decorate.
inline bool IsDecorate(uint32_t op) const {
return (op == SpvOpDecorate || op == SpvOpDecorateId);
}
// Kill all name and decorate ops using |inst|
void KillNamesAndDecorates(ir::Instruction* inst);
// Kill all name and decorate ops using |id|
void KillNamesAndDecorates(uint32_t id);
// Collect all named or decorated ids in module
void FindNamedOrDecoratedIds();
// For function |func|, look for BranchConditionals with constant condition
// and convert to a Branch to the indicated label. Delete resulting dead
// blocks. Assumes only structured control flow in shader. Note some such
// branches and blocks may be left to avoid creating invalid control flow.
// TODO(greg-lunarg): Remove remaining constant conditional branches and
// dead blocks.
bool EliminateDeadBranches(ir::Function* func);
// Initialize extensions whitelist
void InitExtensions();
// Return true if all extensions in this module are allowed by this pass.
bool AllExtensionsSupported() const;
void Initialize(ir::Module* module);
Pass::Status ProcessImpl();
// Module this pass is processing
ir::Module* module_;
// Def-Uses for the module we are processing
std::unique_ptr<analysis::DefUseManager> def_use_mgr_;
// Map from function's result id to function
std::unordered_map<uint32_t, ir::Function*> id2function_;
// Map from block's label id to block.
std::unordered_map<uint32_t, ir::BasicBlock*> id2block_;
// Map from block to its structured successor blocks. See
// ComputeStructuredSuccessors() for definition.
std::unordered_map<const ir::BasicBlock*, std::vector<ir::BasicBlock*>>
block2structured_succs_;
// named or decorated ids
std::unordered_set<uint32_t> named_or_decorated_ids_;
// Extensions supported by this pass.
std::unordered_set<std::string> extensions_whitelist_;
};
} // namespace opt
} // namespace spvtools
#endif // LIBSPIRV_OPT_DEAD_BRANCH_ELIM_PASS_H_
|
