| 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_DEAD_BRANCH_ELIM_PASS_H_ |
| 18 |
#define SOURCE_OPT_DEAD_BRANCH_ELIM_PASS_H_ |
| 19 |
|
| 20 |
#include <algorithm> |
| 21 |
#include <map> |
| 22 |
#include <queue> |
| 23 |
#include <unordered_map> |
| 24 |
#include <unordered_set> |
| 25 |
#include <utility> |
| 26 |
#include <vector> |
| 27 |
|
| 28 |
#include "source/opt/basic_block.h" |
| 29 |
#include "source/opt/def_use_manager.h" |
| 30 |
#include "source/opt/mem_pass.h" |
| 31 |
#include "source/opt/module.h" |
| 32 |
|
| 33 |
namespace spvtools { |
| 34 |
namespace opt { |
| 35 |
|
| 36 |
// See optimizer.hpp for documentation. |
| 37 |
class DeadBranchElimPass : public MemPass { |
| 38 |
using cbb_ptr = const BasicBlock*; |
| 39 |
|
| 40 |
public: |
| 41 |
DeadBranchElimPass() = default; |
| 42 |
|
| 43 |
const char* name() const override { return "eliminate-dead-branches"; } |
| 44 |
Status Process() override; |
| 45 |
|
| 46 |
IRContext::Analysis GetPreservedAnalyses() override { |
| 47 |
return IRContext::kAnalysisDefUse | |
| 48 |
IRContext::kAnalysisInstrToBlockMapping | |
| 49 |
IRContext::kAnalysisConstants | IRContext::kAnalysisTypes; |
| 50 |
} |
| 51 |
|
| 52 |
private: |
| 53 |
// If |condId| is boolean constant, return conditional value in |condVal| and |
| 54 |
// return true, otherwise return false. |
| 55 |
bool GetConstCondition(uint32_t condId, bool* condVal); |
| 56 |
|
| 57 |
// If |valId| is a 32-bit integer constant, return value via |value| and |
| 58 |
// return true, otherwise return false. |
| 59 |
bool GetConstInteger(uint32_t valId, uint32_t* value); |
| 60 |
|
| 61 |
// Add branch to |labelId| to end of block |bp|. |
| 62 |
void AddBranch(uint32_t labelId, BasicBlock* bp); |
| 63 |
|
| 64 |
// For function |func|, look for BranchConditionals with constant condition |
| 65 |
// and convert to a Branch to the indicated label. Delete resulting dead |
| 66 |
// blocks. Note some such branches and blocks may be left to avoid creating |
| 67 |
// invalid control flow. |
| 68 |
// TODO(greg-lunarg): Remove remaining constant conditional branches and dead |
| 69 |
// blocks. |
| 70 |
bool EliminateDeadBranches(Function* func); |
| 71 |
|
| 72 |
// Returns the basic block containing |id|. |
| 73 |
// Note: this pass only requires correct instruction block mappings for the |
| 74 |
// input. This pass does not preserve the block mapping, so it is not kept |
| 75 |
// up-to-date during processing. |
| 76 |
BasicBlock* GetParentBlock(uint32_t id); |
| 77 |
|
| 78 |
// Marks live blocks reachable from the entry of |func|. Simplifies constant |
| 79 |
// branches and switches as it proceeds, to limit the number of live blocks. |
| 80 |
// It is careful not to eliminate backedges even if they are dead, but the |
| 81 |
// header is live. Likewise, unreachable merge blocks named in live merge |
| 82 |
// instruction must be retained (though they may be clobbered). |
| 83 |
bool MarkLiveBlocks(Function* func, |
| 84 |
std::unordered_set<BasicBlock*>* live_blocks); |
| 85 |
|
| 86 |
// Checks for unreachable merge and continue blocks with live headers; those |
| 87 |
// blocks must be retained. Continues are tracked separately so that a live |
| 88 |
// phi can be updated to take an undef value from any of its predecessors |
| 89 |
// that are unreachable continues. |
| 90 |
// |
| 91 |
// |unreachable_continues| maps the id of an unreachable continue target to |
| 92 |
// the header block that declares it. |
| 93 |
void MarkUnreachableStructuredTargets( |
| 94 |
const std::unordered_set<BasicBlock*>& live_blocks, |
| 95 |
std::unordered_set<BasicBlock*>* unreachable_merges, |
| 96 |
std::unordered_map<BasicBlock*, BasicBlock*>* unreachable_continues); |
| 97 |
|
| 98 |
// Fix phis in reachable blocks so that only live (or unremovable) incoming |
| 99 |
// edges are present. If the block now only has a single live incoming edge, |
| 100 |
// remove the phi and replace its uses with its data input. If the single |
| 101 |
// remaining incoming edge is from the phi itself, the the phi is in an |
| 102 |
// unreachable single block loop. Either the block is dead and will be |
| 103 |
// removed, or it's reachable from an unreachable continue target. In the |
| 104 |
// latter case that continue target block will be collapsed into a block that |
| 105 |
// only branches back to its header and we'll eliminate the block with the |
| 106 |
// phi. |
| 107 |
// |
| 108 |
// |unreachable_continues| maps continue targets that cannot be reached to |
| 109 |
// merge instruction that declares them. |
| 110 |
bool FixPhiNodesInLiveBlocks( |
| 111 |
Function* func, const std::unordered_set<BasicBlock*>& live_blocks, |
| 112 |
const std::unordered_map<BasicBlock*, BasicBlock*>& |
| 113 |
unreachable_continues); |
| 114 |
|
| 115 |
// Erases dead blocks. Any block captured in |unreachable_merges| or |
| 116 |
// |unreachable_continues| is a dead block that is required to remain due to |
| 117 |
// a live merge instruction in the corresponding header. These blocks will |
| 118 |
// have their instructions clobbered and will become a label and terminator. |
| 119 |
// Unreachable merge blocks are terminated by OpUnreachable, while |
| 120 |
// unreachable continue blocks are terminated by an unconditional branch to |
| 121 |
// the header. Otherwise, blocks are dead if not explicitly captured in |
| 122 |
// |live_blocks| and are totally removed. |
| 123 |
// |
| 124 |
// |unreachable_continues| maps continue targets that cannot be reached to |
| 125 |
// corresponding header block that declares them. |
| 126 |
bool EraseDeadBlocks( |
| 127 |
Function* func, const std::unordered_set<BasicBlock*>& live_blocks, |
| 128 |
const std::unordered_set<BasicBlock*>& unreachable_merges, |
| 129 |
const std::unordered_map<BasicBlock*, BasicBlock*>& |
| 130 |
unreachable_continues); |
| 131 |
|
| 132 |
// Reorders blocks in reachable functions so that they satisfy dominator |
| 133 |
// block ordering rules. |
| 134 |
void FixBlockOrder(); |
| 135 |
|
| 136 |
// Return the first branch instruction that is a conditional branch to |
| 137 |
// |merge_block_id|. Returns |nullptr| if no such branch exists. If there are |
| 138 |
// multiple such branches, the first one is the one that would be executed |
| 139 |
// first when running the code. That is, the one that dominates all of the |
| 140 |
// others. |
| 141 |
// |
| 142 |
// |start_block_id| must be a block whose innermost containing merge construct |
| 143 |
// has |merge_block_id| as the merge block. |
| 144 |
// |
| 145 |
// |loop_merge_id| and |loop_continue_id| are the merge and continue block ids |
| 146 |
// of the innermost loop containing |start_block_id|. |
| 147 |
Instruction* FindFirstExitFromSelectionMerge(uint32_t start_block_id, |
| 148 |
uint32_t merge_block_id, |
| 149 |
uint32_t loop_merge_id, |
| 150 |
uint32_t loop_continue_id, |
| 151 |
uint32_t switch_merge_id); |
| 152 |
|
| 153 |
// Adds to |blocks_with_back_edges| all of the blocks on the path from the |
| 154 |
// basic block |cont_id| to |header_id| and |merge_id|. The intention is that |
| 155 |
// |cond_id| is a the continue target of a loop, |header_id| is the header of |
| 156 |
// the loop, and |merge_id| is the merge block of the loop. |
| 157 |
void AddBlocksWithBackEdge( |
| 158 |
uint32_t cont_id, uint32_t header_id, uint32_t merge_id, |
| 159 |
std::unordered_set<BasicBlock*>* blocks_with_back_edges); |
| 160 |
|
| 161 |
// Returns true if there is a brach to the merge node of the selection |
| 162 |
// construct |switch_header_id| that is inside a nested selection construct or |
| 163 |
// in the header of the nested selection construct. |
| 164 |
bool SwitchHasNestedBreak(uint32_t switch_header_id); |
| 165 |
|
| 166 |
// Return true of the terminator of |block| is successfully replaced with a |
| 167 |
// branch to |live_lab_id|. The merge instruction is deleted or moved as |
| 168 |
// needed to maintain structured control flow. Assumes that the |
| 169 |
// StructuredCFGAnalysis is valid for the constructs containing |block|. |
| 170 |
bool SimplifyBranch(BasicBlock* block, uint32_t live_lab_id); |
| 171 |
}; |
| 172 |
|
| 173 |
} // namespace opt |
| 174 |
} // namespace spvtools |
| 175 |
|
| 176 |
#endif // SOURCE_OPT_DEAD_BRANCH_ELIM_PASS_H_ |