• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright (c) 2015-2016 The Khronos Group 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_VAL_BASIC_BLOCK_H_
16 #define SOURCE_VAL_BASIC_BLOCK_H_
17 
18 #include <bitset>
19 #include <cstdint>
20 #include <functional>
21 #include <memory>
22 #include <vector>
23 
24 #include "source/latest_version_spirv_header.h"
25 
26 namespace spvtools {
27 namespace val {
28 
29 enum BlockType : uint32_t {
30   kBlockTypeUndefined,
31   kBlockTypeSelection,
32   kBlockTypeLoop,
33   kBlockTypeMerge,
34   kBlockTypeBreak,
35   kBlockTypeContinue,
36   kBlockTypeReturn,
37   kBlockTypeCOUNT  ///< Total number of block types. (must be the last element)
38 };
39 
40 class Instruction;
41 
42 // This class represents a basic block in a SPIR-V module
43 class BasicBlock {
44  public:
45   /// Constructor for a BasicBlock
46   ///
47   /// @param[in] id The ID of the basic block
48   explicit BasicBlock(uint32_t id);
49 
50   /// Returns the id of the BasicBlock
id()51   uint32_t id() const { return id_; }
52 
53   /// Returns the predecessors of the BasicBlock
predecessors()54   const std::vector<BasicBlock*>* predecessors() const {
55     return &predecessors_;
56   }
57 
58   /// Returns the predecessors of the BasicBlock
predecessors()59   std::vector<BasicBlock*>* predecessors() { return &predecessors_; }
60 
61   /// Returns the successors of the BasicBlock
successors()62   const std::vector<BasicBlock*>* successors() const { return &successors_; }
63 
64   /// Returns the successors of the BasicBlock
successors()65   std::vector<BasicBlock*>* successors() { return &successors_; }
66 
67   /// Returns true if the block is reachable in the CFG
reachable()68   bool reachable() const { return reachable_; }
69 
70   /// Returns true if BasicBlock is of the given type
is_type(BlockType type)71   bool is_type(BlockType type) const {
72     if (type == kBlockTypeUndefined) return type_.none();
73     return type_.test(type);
74   }
75 
76   /// Sets the reachability of the basic block in the CFG
set_reachable(bool reachability)77   void set_reachable(bool reachability) { reachable_ = reachability; }
78 
79   /// Sets the type of the BasicBlock
set_type(BlockType type)80   void set_type(BlockType type) {
81     if (type == kBlockTypeUndefined)
82       type_.reset();
83     else
84       type_.set(type);
85   }
86 
87   /// Sets the immedate dominator of this basic block
88   ///
89   /// @param[in] dom_block The dominator block
90   void SetImmediateDominator(BasicBlock* dom_block);
91 
92   /// Sets the immedate post dominator of this basic block
93   ///
94   /// @param[in] pdom_block The post dominator block
95   void SetImmediatePostDominator(BasicBlock* pdom_block);
96 
97   /// Returns the immedate dominator of this basic block
98   BasicBlock* immediate_dominator();
99 
100   /// Returns the immedate dominator of this basic block
101   const BasicBlock* immediate_dominator() const;
102 
103   /// Returns the immedate post dominator of this basic block
104   BasicBlock* immediate_post_dominator();
105 
106   /// Returns the immedate post dominator of this basic block
107   const BasicBlock* immediate_post_dominator() const;
108 
109   /// Ends the block without a successor
110   void RegisterBranchInstruction(SpvOp branch_instruction);
111 
112   /// Returns the label instruction for the block, or nullptr if not set.
label()113   const Instruction* label() const { return label_; }
114 
115   //// Registers the label instruction for the block.
set_label(const Instruction * t)116   void set_label(const Instruction* t) { label_ = t; }
117 
118   /// Registers the terminator instruction for the block.
set_terminator(const Instruction * t)119   void set_terminator(const Instruction* t) { terminator_ = t; }
120 
121   /// Returns the terminator instruction for the block.
terminator()122   const Instruction* terminator() const { return terminator_; }
123 
124   /// Adds @p next BasicBlocks as successors of this BasicBlock
125   void RegisterSuccessors(
126       const std::vector<BasicBlock*>& next = std::vector<BasicBlock*>());
127 
128   /// Returns true if the id of the BasicBlock matches
129   bool operator==(const BasicBlock& other) const { return other.id_ == id_; }
130 
131   /// Returns true if the id of the BasicBlock matches
132   bool operator==(const uint32_t& other_id) const { return other_id == id_; }
133 
134   /// Returns true if this block dominates the other block.
135   /// Assumes dominators have been computed.
136   bool dominates(const BasicBlock& other) const;
137 
138   /// Returns true if this block postdominates the other block.
139   /// Assumes dominators have been computed.
140   bool postdominates(const BasicBlock& other) const;
141 
142   /// @brief A BasicBlock dominator iterator class
143   ///
144   /// This iterator will iterate over the (post)dominators of the block
145   class DominatorIterator
146       : public std::iterator<std::forward_iterator_tag, BasicBlock*> {
147    public:
148     /// @brief Constructs the end of dominator iterator
149     ///
150     /// This will create an iterator which will represent the element
151     /// before the root node of the dominator tree
152     DominatorIterator();
153 
154     /// @brief Constructs an iterator for the given block which points to
155     ///        @p block
156     ///
157     /// @param block          The block which is referenced by the iterator
158     /// @param dominator_func This function will be called to get the immediate
159     ///                       (post)dominator of the current block
160     DominatorIterator(
161         const BasicBlock* block,
162         std::function<const BasicBlock*(const BasicBlock*)> dominator_func);
163 
164     /// @brief Advances the iterator
165     DominatorIterator& operator++();
166 
167     /// @brief Returns the current element
168     const BasicBlock*& operator*();
169 
170     friend bool operator==(const DominatorIterator& lhs,
171                            const DominatorIterator& rhs);
172 
173    private:
174     const BasicBlock* current_;
175     std::function<const BasicBlock*(const BasicBlock*)> dom_func_;
176   };
177 
178   /// Returns a dominator iterator which points to the current block
179   const DominatorIterator dom_begin() const;
180 
181   /// Returns a dominator iterator which points to the current block
182   DominatorIterator dom_begin();
183 
184   /// Returns a dominator iterator which points to one element past the first
185   /// block
186   const DominatorIterator dom_end() const;
187 
188   /// Returns a dominator iterator which points to one element past the first
189   /// block
190   DominatorIterator dom_end();
191 
192   /// Returns a post dominator iterator which points to the current block
193   const DominatorIterator pdom_begin() const;
194   /// Returns a post dominator iterator which points to the current block
195   DominatorIterator pdom_begin();
196 
197   /// Returns a post dominator iterator which points to one element past the
198   /// last block
199   const DominatorIterator pdom_end() const;
200 
201   /// Returns a post dominator iterator which points to one element past the
202   /// last block
203   DominatorIterator pdom_end();
204 
205  private:
206   /// Id of the BasicBlock
207   const uint32_t id_;
208 
209   /// Pointer to the immediate dominator of the BasicBlock
210   BasicBlock* immediate_dominator_;
211 
212   /// Pointer to the immediate dominator of the BasicBlock
213   BasicBlock* immediate_post_dominator_;
214 
215   /// The set of predecessors of the BasicBlock
216   std::vector<BasicBlock*> predecessors_;
217 
218   /// The set of successors of the BasicBlock
219   std::vector<BasicBlock*> successors_;
220 
221   /// The type of the block
222   std::bitset<kBlockTypeCOUNT> type_;
223 
224   /// True if the block is reachable in the CFG
225   bool reachable_;
226 
227   /// label of this block, if any.
228   const Instruction* label_;
229 
230   /// Terminator of this block.
231   const Instruction* terminator_;
232 };
233 
234 /// @brief Returns true if the iterators point to the same element or if both
235 ///        iterators point to the @p dom_end block
236 bool operator==(const BasicBlock::DominatorIterator& lhs,
237                 const BasicBlock::DominatorIterator& rhs);
238 
239 /// @brief Returns true if the iterators point to different elements and they
240 ///        do not both point to the @p dom_end block
241 bool operator!=(const BasicBlock::DominatorIterator& lhs,
242                 const BasicBlock::DominatorIterator& rhs);
243 
244 }  // namespace val
245 }  // namespace spvtools
246 
247 #endif  // SOURCE_VAL_BASIC_BLOCK_H_
248