1 /* 2 * Copyright 2012 Intel Corporation 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21 * IN THE SOFTWARE. 22 * 23 * Authors: 24 * Eric Anholt <eric (at) anholt.net> 25 * 26 */ 27 28 #pragma once 29 #ifndef BRW_CFG_H 30 #define BRW_CFG_H 31 32 #include "brw_shader.h" 33 34 struct bblock_t; 35 36 struct bblock_link { 37 #ifdef __cplusplus 38 DECLARE_RALLOC_CXX_OPERATORS(bblock_link) 39 40 bblock_link(bblock_t *block) 41 : block(block) 42 { 43 } 44 #endif 45 46 struct exec_node link; 47 struct bblock_t *block; 48 }; 49 50 struct backend_instruction; 51 52 struct bblock_t { 53 #ifdef __cplusplus 54 DECLARE_RALLOC_CXX_OPERATORS(bblock_t) 55 56 explicit bblock_t(cfg_t *cfg); 57 58 void add_successor(void *mem_ctx, bblock_t *successor); 59 bool is_predecessor_of(const bblock_t *block) const; 60 bool is_successor_of(const bblock_t *block) const; 61 bool can_combine_with(const bblock_t *that) const; 62 void combine_with(bblock_t *that); 63 void dump(backend_shader *s) const; 64 65 backend_instruction *start(); 66 const backend_instruction *start() const; 67 backend_instruction *end(); 68 const backend_instruction *end() const; 69 70 bblock_t *next(); 71 const bblock_t *next() const; 72 bblock_t *prev(); 73 const bblock_t *prev() const; 74 75 bool starts_with_control_flow() const; 76 bool ends_with_control_flow() const; 77 78 backend_instruction *first_non_control_flow_inst(); 79 backend_instruction *last_non_control_flow_inst(); 80 #endif 81 82 struct exec_node link; 83 struct cfg_t *cfg; 84 struct bblock_t *idom; 85 86 int start_ip; 87 int end_ip; 88 89 struct exec_list instructions; 90 struct exec_list parents; 91 struct exec_list children; 92 int num; 93 94 unsigned cycle_count; 95 }; 96 97 static inline struct backend_instruction * 98 bblock_start(struct bblock_t *block) 99 { 100 return (struct backend_instruction *)exec_list_get_head(&block->instructions); 101 } 102 103 static inline const struct backend_instruction * 104 bblock_start_const(const struct bblock_t *block) 105 { 106 return (const struct backend_instruction *)exec_list_get_head_const(&block->instructions); 107 } 108 109 static inline struct backend_instruction * 110 bblock_end(struct bblock_t *block) 111 { 112 return (struct backend_instruction *)exec_list_get_tail(&block->instructions); 113 } 114 115 static inline const struct backend_instruction * 116 bblock_end_const(const struct bblock_t *block) 117 { 118 return (const struct backend_instruction *)exec_list_get_tail_const(&block->instructions); 119 } 120 121 static inline struct bblock_t * 122 bblock_next(struct bblock_t *block) 123 { 124 if (exec_node_is_tail_sentinel(block->link.next)) 125 return NULL; 126 127 return (struct bblock_t *)block->link.next; 128 } 129 130 static inline const struct bblock_t * 131 bblock_next_const(const struct bblock_t *block) 132 { 133 if (exec_node_is_tail_sentinel(block->link.next)) 134 return NULL; 135 136 return (const struct bblock_t *)block->link.next; 137 } 138 139 static inline struct bblock_t * 140 bblock_prev(struct bblock_t *block) 141 { 142 if (exec_node_is_head_sentinel(block->link.prev)) 143 return NULL; 144 145 return (struct bblock_t *)block->link.prev; 146 } 147 148 static inline const struct bblock_t * 149 bblock_prev_const(const struct bblock_t *block) 150 { 151 if (exec_node_is_head_sentinel(block->link.prev)) 152 return NULL; 153 154 return (const struct bblock_t *)block->link.prev; 155 } 156 157 static inline bool 158 bblock_starts_with_control_flow(const struct bblock_t *block) 159 { 160 enum opcode op = bblock_start_const(block)->opcode; 161 return op == BRW_OPCODE_DO || op == BRW_OPCODE_ENDIF; 162 } 163 164 static inline bool 165 bblock_ends_with_control_flow(const struct bblock_t *block) 166 { 167 enum opcode op = bblock_end_const(block)->opcode; 168 return op == BRW_OPCODE_IF || 169 op == BRW_OPCODE_ELSE || 170 op == BRW_OPCODE_WHILE || 171 op == BRW_OPCODE_BREAK || 172 op == BRW_OPCODE_CONTINUE; 173 } 174 175 static inline struct backend_instruction * 176 bblock_first_non_control_flow_inst(struct bblock_t *block) 177 { 178 struct backend_instruction *inst = bblock_start(block); 179 if (bblock_starts_with_control_flow(block)) 180 #ifdef __cplusplus 181 inst = (struct backend_instruction *)inst->next; 182 #else 183 inst = (struct backend_instruction *)inst->link.next; 184 #endif 185 return inst; 186 } 187 188 static inline struct backend_instruction * 189 bblock_last_non_control_flow_inst(struct bblock_t *block) 190 { 191 struct backend_instruction *inst = bblock_end(block); 192 if (bblock_ends_with_control_flow(block)) 193 #ifdef __cplusplus 194 inst = (struct backend_instruction *)inst->prev; 195 #else 196 inst = (struct backend_instruction *)inst->link.prev; 197 #endif 198 return inst; 199 } 200 201 #ifdef __cplusplus 202 inline backend_instruction * 203 bblock_t::start() 204 { 205 return bblock_start(this); 206 } 207 208 inline const backend_instruction * 209 bblock_t::start() const 210 { 211 return bblock_start_const(this); 212 } 213 214 inline backend_instruction * 215 bblock_t::end() 216 { 217 return bblock_end(this); 218 } 219 220 inline const backend_instruction * 221 bblock_t::end() const 222 { 223 return bblock_end_const(this); 224 } 225 226 inline bblock_t * 227 bblock_t::next() 228 { 229 return bblock_next(this); 230 } 231 232 inline const bblock_t * 233 bblock_t::next() const 234 { 235 return bblock_next_const(this); 236 } 237 238 inline bblock_t * 239 bblock_t::prev() 240 { 241 return bblock_prev(this); 242 } 243 244 inline const bblock_t * 245 bblock_t::prev() const 246 { 247 return bblock_prev_const(this); 248 } 249 250 inline bool 251 bblock_t::starts_with_control_flow() const 252 { 253 return bblock_starts_with_control_flow(this); 254 } 255 256 inline bool 257 bblock_t::ends_with_control_flow() const 258 { 259 return bblock_ends_with_control_flow(this); 260 } 261 262 inline backend_instruction * 263 bblock_t::first_non_control_flow_inst() 264 { 265 return bblock_first_non_control_flow_inst(this); 266 } 267 268 inline backend_instruction * 269 bblock_t::last_non_control_flow_inst() 270 { 271 return bblock_last_non_control_flow_inst(this); 272 } 273 #endif 274 275 struct cfg_t { 276 #ifdef __cplusplus 277 DECLARE_RALLOC_CXX_OPERATORS(cfg_t) 278 279 cfg_t(exec_list *instructions); 280 ~cfg_t(); 281 282 void remove_block(bblock_t *block); 283 284 bblock_t *new_block(); 285 void set_next_block(bblock_t **cur, bblock_t *block, int ip); 286 void make_block_array(); 287 void calculate_idom(); 288 static bblock_t *intersect(bblock_t *b1, bblock_t *b2); 289 290 void dump(backend_shader *s); 291 void dump_cfg(); 292 void dump_domtree(); 293 #endif 294 void *mem_ctx; 295 296 /** Ordered list (by ip) of basic blocks */ 297 struct exec_list block_list; 298 struct bblock_t **blocks; 299 int num_blocks; 300 301 bool idom_dirty; 302 303 unsigned cycle_count; 304 }; 305 306 /* Note that this is implemented with a double for loop -- break will 307 * break from the inner loop only! 308 */ 309 #define foreach_block_and_inst(__block, __type, __inst, __cfg) \ 310 foreach_block (__block, __cfg) \ 311 foreach_inst_in_block (__type, __inst, __block) 312 313 /* Note that this is implemented with a double for loop -- break will 314 * break from the inner loop only! 315 */ 316 #define foreach_block_and_inst_safe(__block, __type, __inst, __cfg) \ 317 foreach_block_safe (__block, __cfg) \ 318 foreach_inst_in_block_safe (__type, __inst, __block) 319 320 #define foreach_block(__block, __cfg) \ 321 foreach_list_typed (bblock_t, __block, link, &(__cfg)->block_list) 322 323 #define foreach_block_reverse(__block, __cfg) \ 324 foreach_list_typed_reverse (bblock_t, __block, link, &(__cfg)->block_list) 325 326 #define foreach_block_safe(__block, __cfg) \ 327 foreach_list_typed_safe (bblock_t, __block, link, &(__cfg)->block_list) 328 329 #define foreach_block_reverse_safe(__block, __cfg) \ 330 foreach_list_typed_reverse_safe (bblock_t, __block, link, &(__cfg)->block_list) 331 332 #define foreach_inst_in_block(__type, __inst, __block) \ 333 foreach_in_list(__type, __inst, &(__block)->instructions) 334 335 #define foreach_inst_in_block_safe(__type, __inst, __block) \ 336 for (__type *__inst = (__type *)__block->instructions.head_sentinel.next, \ 337 *__next = (__type *)__inst->next; \ 338 __next != NULL; \ 339 __inst = __next, \ 340 __next = (__type *)__next->next) 341 342 #define foreach_inst_in_block_reverse(__type, __inst, __block) \ 343 foreach_in_list_reverse(__type, __inst, &(__block)->instructions) 344 345 #define foreach_inst_in_block_reverse_safe(__type, __inst, __block) \ 346 foreach_in_list_reverse_safe(__type, __inst, &(__block)->instructions) 347 348 #define foreach_inst_in_block_starting_from(__type, __scan_inst, __inst) \ 349 for (__type *__scan_inst = (__type *)__inst->next; \ 350 !__scan_inst->is_tail_sentinel(); \ 351 __scan_inst = (__type *)__scan_inst->next) 352 353 #define foreach_inst_in_block_reverse_starting_from(__type, __scan_inst, __inst) \ 354 for (__type *__scan_inst = (__type *)__inst->prev; \ 355 !__scan_inst->is_head_sentinel(); \ 356 __scan_inst = (__type *)__scan_inst->prev) 357 358 #endif /* BRW_CFG_H */ 359