src/intel/compiler/brw_cfg.h

   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@anholt.net>
  25  *
  26  */
  27
  28 #ifndef BRW_CFG_H
  29 #define BRW_CFG_H
  30
  31 #include "brw_shader.h"
  32
  33 struct bblock_t;
  34
  35 struct bblock_link {
  36 #ifdef __cplusplus
  37    DECLARE_RALLOC_CXX_OPERATORS(bblock_link)
  38
  39    bblock_link(bblock_t *block)
  40       : block(block)
  41    {
  42    }
  43 #endif
  44
  45    struct exec_node link;
  46    struct bblock_t *block;
  47 };
  48
  49 struct backend_instruction;
  50
  51 struct bblock_t {
  52 #ifdef __cplusplus
  53    DECLARE_RALLOC_CXX_OPERATORS(bblock_t)
  54
  55    explicit bblock_t(cfg_t *cfg);
  56
  57    void add_successor(void *mem_ctx, bblock_t *successor);
  58    bool is_predecessor_of(const bblock_t *block) const;
  59    bool is_successor_of(const bblock_t *block) const;
  60    bool can_combine_with(const bblock_t *that) const;
  61    void combine_with(bblock_t *that);
  62    void dump(backend_shader *s) const;
  63
  64    backend_instruction *start();
  65    const backend_instruction *start() const;
  66    backend_instruction *end();
  67    const backend_instruction *end() const;
  68
  69    bblock_t *next();
  70    const bblock_t *next() const;
  71    bblock_t *prev();
  72    const bblock_t *prev() const;
  73
  74    bool starts_with_control_flow() const;
  75    bool ends_with_control_flow() const;
  76
  77    backend_instruction *first_non_control_flow_inst();
  78    backend_instruction *last_non_control_flow_inst();
  79 #endif
  80
  81    struct exec_node link;
  82    struct cfg_t *cfg;
  83    struct bblock_t *idom;
  84
  85    int start_ip;
  86    int end_ip;
  87
  88    struct exec_list instructions;
  89    struct exec_list parents;
  90    struct exec_list children;
  91    int num;
  92
  93    unsigned cycle_count;
  94 };
  95
  96 static inline struct backend_instruction *
  97 bblock_start(struct bblock_t *block)
  98 {
  99    return (struct backend_instruction *)exec_list_get_head(&block->instructions);
 100 }
 101
 102 static inline const struct backend_instruction *
 103 bblock_start_const(const struct bblock_t *block)
 104 {
 105    return (const struct backend_instruction *)exec_list_get_head_const(&block->instructions);
 106 }
 107
 108 static inline struct backend_instruction *
 109 bblock_end(struct bblock_t *block)
 110 {
 111    return (struct backend_instruction *)exec_list_get_tail(&block->instructions);
 112 }
 113
 114 static inline const struct backend_instruction *
 115 bblock_end_const(const struct bblock_t *block)
 116 {
 117    return (const struct backend_instruction *)exec_list_get_tail_const(&block->instructions);
 118 }
 119
 120 static inline struct bblock_t *
 121 bblock_next(struct bblock_t *block)
 122 {
 123    if (exec_node_is_tail_sentinel(block->link.next))
 124       return NULL;
 125
 126    return (struct bblock_t *)block->link.next;
 127 }
 128
 129 static inline const struct bblock_t *
 130 bblock_next_const(const struct bblock_t *block)
 131 {
 132    if (exec_node_is_tail_sentinel(block->link.next))
 133       return NULL;
 134
 135    return (const struct bblock_t *)block->link.next;
 136 }
 137
 138 static inline struct bblock_t *
 139 bblock_prev(struct bblock_t *block)
 140 {
 141    if (exec_node_is_head_sentinel(block->link.prev))
 142       return NULL;
 143
 144    return (struct bblock_t *)block->link.prev;
 145 }
 146
 147 static inline const struct bblock_t *
 148 bblock_prev_const(const struct bblock_t *block)
 149 {
 150    if (exec_node_is_head_sentinel(block->link.prev))
 151       return NULL;
 152
 153    return (const struct bblock_t *)block->link.prev;
 154 }
 155
 156 static inline bool
 157 bblock_starts_with_control_flow(const struct bblock_t *block)
 158 {
 159    enum opcode op = bblock_start_const(block)->opcode;
 160    return op == BRW_OPCODE_DO || op == BRW_OPCODE_ENDIF;
 161 }
 162
 163 static inline bool
 164 bblock_ends_with_control_flow(const struct bblock_t *block)
 165 {
 166    enum opcode op = bblock_end_const(block)->opcode;
 167    return op == BRW_OPCODE_IF ||
 168           op == BRW_OPCODE_ELSE ||
 169           op == BRW_OPCODE_WHILE ||
 170           op == BRW_OPCODE_BREAK ||
 171           op == BRW_OPCODE_CONTINUE;
 172 }
 173
 174 static inline struct backend_instruction *
 175 bblock_first_non_control_flow_inst(struct bblock_t *block)
 176 {
 177    struct backend_instruction *inst = bblock_start(block);
 178    if (bblock_starts_with_control_flow(block))
 179 #ifdef __cplusplus
 180       inst = (struct backend_instruction *)inst->next;
 181 #else
 182       inst = (struct backend_instruction *)inst->link.next;
 183 #endif
 184    return inst;
 185 }
 186
 187 static inline struct backend_instruction *
 188 bblock_last_non_control_flow_inst(struct bblock_t *block)
 189 {
 190    struct backend_instruction *inst = bblock_end(block);
 191    if (bblock_ends_with_control_flow(block))
 192 #ifdef __cplusplus
 193       inst = (struct backend_instruction *)inst->prev;
 194 #else
 195       inst = (struct backend_instruction *)inst->link.prev;
 196 #endif
 197    return inst;
 198 }
 199
 200 #ifdef __cplusplus
 201 inline backend_instruction *
 202 bblock_t::start()
 203 {
 204    return bblock_start(this);
 205 }
 206
 207 inline const backend_instruction *
 208 bblock_t::start() const
 209 {
 210    return bblock_start_const(this);
 211 }
 212
 213 inline backend_instruction *
 214 bblock_t::end()
 215 {
 216    return bblock_end(this);
 217 }
 218
 219 inline const backend_instruction *
 220 bblock_t::end() const
 221 {
 222    return bblock_end_const(this);
 223 }
 224
 225 inline bblock_t *
 226 bblock_t::next()
 227 {
 228    return bblock_next(this);
 229 }
 230
 231 inline const bblock_t *
 232 bblock_t::next() const
 233 {
 234    return bblock_next_const(this);
 235 }
 236
 237 inline bblock_t *
 238 bblock_t::prev()
 239 {
 240    return bblock_prev(this);
 241 }
 242
 243 inline const bblock_t *
 244 bblock_t::prev() const
 245 {
 246    return bblock_prev_const(this);
 247 }
 248
 249 inline bool
 250 bblock_t::starts_with_control_flow() const
 251 {
 252    return bblock_starts_with_control_flow(this);
 253 }
 254
 255 inline bool
 256 bblock_t::ends_with_control_flow() const
 257 {
 258    return bblock_ends_with_control_flow(this);
 259 }
 260
 261 inline backend_instruction *
 262 bblock_t::first_non_control_flow_inst()
 263 {
 264    return bblock_first_non_control_flow_inst(this);
 265 }
 266
 267 inline backend_instruction *
 268 bblock_t::last_non_control_flow_inst()
 269 {
 270    return bblock_last_non_control_flow_inst(this);
 271 }
 272 #endif
 273
 274 struct cfg_t {
 275 #ifdef __cplusplus
 276    DECLARE_RALLOC_CXX_OPERATORS(cfg_t)
 277
 278    cfg_t(exec_list *instructions);
 279    ~cfg_t();
 280
 281    void remove_block(bblock_t *block);
 282
 283    bblock_t *new_block();
 284    void set_next_block(bblock_t **cur, bblock_t *block, int ip);
 285    void make_block_array();
 286    void calculate_idom();
 287    static bblock_t *intersect(bblock_t *b1, bblock_t *b2);
 288
 289    void dump(backend_shader *s);
 290    void dump_cfg();
 291    void dump_domtree();
 292 #endif
 293    void *mem_ctx;
 294
 295    /** Ordered list (by ip) of basic blocks */
 296    struct exec_list block_list;
 297    struct bblock_t **blocks;
 298    int num_blocks;
 299
 300    bool idom_dirty;
 301
 302    unsigned cycle_count;
 303 };
 304
 305 /* Note that this is implemented with a double for loop -- break will
 306  * break from the inner loop only!
 307  */
 308 #define foreach_block_and_inst(__block, __type, __inst, __cfg) \
 309    foreach_block (__block, __cfg)                              \
 310       foreach_inst_in_block (__type, __inst, __block)
 311
 312 /* Note that this is implemented with a double for loop -- break will
 313  * break from the inner loop only!
 314  */
 315 #define foreach_block_and_inst_safe(__block, __type, __inst, __cfg) \
 316    foreach_block_safe (__block, __cfg)                              \
 317       foreach_inst_in_block_safe (__type, __inst, __block)
 318
 319 #define foreach_block(__block, __cfg)                          \
 320    foreach_list_typed (bblock_t, __block, link, &(__cfg)->block_list)
 321
 322 #define foreach_block_reverse(__block, __cfg)                  \
 323    foreach_list_typed_reverse (bblock_t, __block, link, &(__cfg)->block_list)
 324
 325 #define foreach_block_safe(__block, __cfg)                     \
 326    foreach_list_typed_safe (bblock_t, __block, link, &(__cfg)->block_list)
 327
 328 #define foreach_block_reverse_safe(__block, __cfg)             \
 329    foreach_list_typed_reverse_safe (bblock_t, __block, link, &(__cfg)->block_list)
 330
 331 #define foreach_inst_in_block(__type, __inst, __block)         \
 332    foreach_in_list(__type, __inst, &(__block)->instructions)
 333
 334 #define foreach_inst_in_block_safe(__type, __inst, __block)    \
 335    for (__type *__inst = (__type *)__block->instructions.head_sentinel.next, \
 336                *__next = (__type *)__inst->next;               \
 337         __next != NULL;                                        \
 338         __inst = __next,                                       \
 339         __next = (__type *)__next->next)
 340
 341 #define foreach_inst_in_block_reverse(__type, __inst, __block) \
 342    foreach_in_list_reverse(__type, __inst, &(__block)->instructions)
 343
 344 #define foreach_inst_in_block_reverse_safe(__type, __inst, __block) \
 345    foreach_in_list_reverse_safe(__type, __inst, &(__block)->instructions)
 346
 347 #define foreach_inst_in_block_starting_from(__type, __scan_inst, __inst) \
 348    for (__type *__scan_inst = (__type *)__inst->next;          \
 349         !__scan_inst->is_tail_sentinel();                      \
 350         __scan_inst = (__type *)__scan_inst->next)
 351
 352 #define foreach_inst_in_block_reverse_starting_from(__type, __scan_inst, __inst) \
 353    for (__type *__scan_inst = (__type *)__inst->prev;          \
 354         !__scan_inst->is_head_sentinel();                      \
 355         __scan_inst = (__type *)__scan_inst->prev)
 356
 357 #endif /* BRW_CFG_H */