1// Copyright (c) 2017 Google Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#ifndef SOURCE_OPT_CFG_H_
16#define SOURCE_OPT_CFG_H_
17
18#include <algorithm>
19#include <list>
20#include <unordered_map>
21#include <unordered_set>
22#include <vector>
23
24#include "source/opt/basic_block.h"
25
26namespace spvtools {
27namespace opt {
28
29class CFG {
30 public:
31 explicit CFG(Module* module);
32
33 // Return the list of predecesors for basic block with label |blkid|.
34 // TODO(dnovillo): Move this to BasicBlock.
35 const std::vector<uint32_t>& preds(uint32_t blk_id) const {
36 assert(label2preds_.count(blk_id));
37 return label2preds_.at(blk_id);
38 }
39
40 // Return a pointer to the basic block instance corresponding to the label
41 // |blk_id|.
42 BasicBlock* block(uint32_t blk_id) const { return id2block_.at(blk_id); }
43
44 // Return the pseudo entry and exit blocks.
45 const BasicBlock* pseudo_entry_block() const { return &pseudo_entry_block_; }
46 BasicBlock* pseudo_entry_block() { return &pseudo_entry_block_; }
47
48 const BasicBlock* pseudo_exit_block() const { return &pseudo_exit_block_; }
49 BasicBlock* pseudo_exit_block() { return &pseudo_exit_block_; }
50
51 // Return true if |block_ptr| is the pseudo-entry block.
52 bool IsPseudoEntryBlock(BasicBlock* block_ptr) const {
53 return block_ptr == &pseudo_entry_block_;
54 }
55
56 // Return true if |block_ptr| is the pseudo-exit block.
57 bool IsPseudoExitBlock(BasicBlock* block_ptr) const {
58 return block_ptr == &pseudo_exit_block_;
59 }
60
61 // Compute structured block order into |order| for |func| starting at |root|.
62 // This order has the property that dominators come before all blocks they
63 // dominate, merge blocks come after all blocks that are in the control
64 // constructs of their header, and continue blocks come after all of the
65 // blocks in the body of their loop.
66 void ComputeStructuredOrder(Function* func, BasicBlock* root,
67 std::list<BasicBlock*>* order);
68
69 // Applies |f| to all blocks that can be reach from |bb| in post order.
70 void ForEachBlockInPostOrder(BasicBlock* bb,
71 const std::function<void(BasicBlock*)>& f);
72
73 // Applies |f| to all blocks that can be reach from |bb| in reverse post
74 // order.
75 void ForEachBlockInReversePostOrder(
76 BasicBlock* bb, const std::function<void(BasicBlock*)>& f);
77
78 // Applies |f| to all blocks that can be reach from |bb| in reverse post
79 // order. Return false if |f| return false on any basic block, and stops
80 // processing.
81 bool WhileEachBlockInReversePostOrder(
82 BasicBlock* bb, const std::function<bool(BasicBlock*)>& f);
83
84 // Registers |blk| as a basic block in the cfg, this also updates the
85 // predecessor lists of each successor of |blk|. |blk| must have a terminator
86 // instruction at the end of the block.
87 void RegisterBlock(BasicBlock* blk) {
88 assert(blk->begin() != blk->end() &&
89 "Basic blocks must have a terminator before registering.");
90 assert(blk->tail()->IsBlockTerminator() &&
91 "Basic blocks must have a terminator before registering.");
92 uint32_t blk_id = blk->id();
93 id2block_[blk_id] = blk;
94 AddEdges(blk);
95 }
96
97 // Removes from the CFG any mapping for the basic block id |blk_id|.
98 void ForgetBlock(const BasicBlock* blk) {
99 id2block_.erase(blk->id());
100 label2preds_.erase(blk->id());
101 RemoveSuccessorEdges(blk);
102 }
103
104 void RemoveEdge(uint32_t pred_blk_id, uint32_t succ_blk_id) {
105 auto pred_it = label2preds_.find(succ_blk_id);
106 if (pred_it == label2preds_.end()) return;
107 auto& preds_list = pred_it->second;
108 auto it = std::find(preds_list.begin(), preds_list.end(), pred_blk_id);
109 if (it != preds_list.end()) preds_list.erase(it);
110 }
111
112 // Registers |blk| to all of its successors.
113 void AddEdges(BasicBlock* blk);
114
115 // Registers the basic block id |pred_blk_id| as being a predecessor of the
116 // basic block id |succ_blk_id|.
117 void AddEdge(uint32_t pred_blk_id, uint32_t succ_blk_id) {
118 label2preds_[succ_blk_id].push_back(pred_blk_id);
119 }
120
121 // Removes any edges that no longer exist from the predecessor mapping for
122 // the basic block id |blk_id|.
123 void RemoveNonExistingEdges(uint32_t blk_id);
124
125 // Remove all edges that leave |bb|.
126 void RemoveSuccessorEdges(const BasicBlock* bb) {
127 bb->ForEachSuccessorLabel(
128 [bb, this](uint32_t succ_id) { RemoveEdge(bb->id(), succ_id); });
129 }
130
131 // Divides |block| into two basic blocks. The first block will have the same
132 // id as |block| and will become a preheader for the loop. The other block
133 // is a new block that will be the new loop header.
134 //
135 // Returns a pointer to the new loop header. Returns |nullptr| if the new
136 // loop pointer could not be created.
137 BasicBlock* SplitLoopHeader(BasicBlock* bb);
138
139 private:
140 // Compute structured successors for function |func|. A block's structured
141 // successors are the blocks it branches to together with its declared merge
142 // block and continue block if it has them. When order matters, the merge
143 // block and continue block always appear first. This assures correct depth
144 // first search in the presence of early returns and kills. If the successor
145 // vector contain duplicates of the merge or continue blocks, they are safely
146 // ignored by DFS.
147 void ComputeStructuredSuccessors(Function* func);
148
149 // Computes the post-order traversal of the cfg starting at |bb| skipping
150 // nodes in |seen|. The order of the traversal is appended to |order|, and
151 // all nodes in the traversal are added to |seen|.
152 void ComputePostOrderTraversal(BasicBlock* bb,
153 std::vector<BasicBlock*>* order,
154 std::unordered_set<BasicBlock*>* seen);
155
156 // Module for this CFG.
157 Module* module_;
158
159 // Map from block to its structured successor blocks. See
160 // ComputeStructuredSuccessors() for definition.
161 std::unordered_map<const BasicBlock*, std::vector<BasicBlock*>>
162 block2structured_succs_;
163
164 // Extra block whose successors are all blocks with no predecessors
165 // in function.
166 BasicBlock pseudo_entry_block_;
167
168 // Augmented CFG Exit Block.
169 BasicBlock pseudo_exit_block_;
170
171 // Map from block's label id to its predecessor blocks ids
172 std::unordered_map<uint32_t, std::vector<uint32_t>> label2preds_;
173
174 // Map from block's label id to block.
175 std::unordered_map<uint32_t, BasicBlock*> id2block_;
176};
177
178} // namespace opt
179} // namespace spvtools
180
181#endif // SOURCE_OPT_CFG_H_
182