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_ir.h"
  32 #ifdef __cplusplus
  33 #include "brw_ir_analysis.h"
  34 #endif
  35
  36 struct bblock_t;
  37
  38 /**
  39  * CFG edge types.
  40  *
  41  * A logical edge represents a potential control flow path of the original
  42  * scalar program, while a physical edge represents a control flow path that
  43  * may not have existed in the original program but was introduced during
  44  * vectorization in order to implement divergent control flow of different
  45  * shader invocations within the same SIMD thread.
  46  *
  47  * All logical edges in the CFG are considered to be physical edges but not
  48  * the other way around -- I.e. the logical CFG is a subset of the physical
  49  * one.
  50  */
  51 enum bblock_link_kind {
  52    bblock_link_logical = 0,
  53    bblock_link_physical
  54 };
  55
  56 struct bblock_link {
  57 #ifdef __cplusplus
  58    DECLARE_RALLOC_CXX_OPERATORS(bblock_link)
  59
  60    bblock_link(bblock_t *block, enum bblock_link_kind kind)
  61       : block(block), kind(kind)
  62    {
  63    }
  64 #endif
  65
  66    struct exec_node link;
  67    struct bblock_t *block;
  68
  69    /* Type of this CFG edge.  Because bblock_link_logical also implies
  70     * bblock_link_physical, the proper way to test for membership of edge 'l'
  71     * in CFG kind 'k' is 'l.kind <= k'.
  72     */
  73    enum bblock_link_kind kind;
  74 };
  75
  76 struct backend_shader;
  77 struct cfg_t;
  78
  79 struct bblock_t {
  80 #ifdef __cplusplus
  81    DECLARE_RALLOC_CXX_OPERATORS(bblock_t)
  82
  83    explicit bblock_t(cfg_t *cfg);
  84
  85    void add_successor(void *mem_ctx, bblock_t *successor,
  86                       enum bblock_link_kind kind);
  87    bool is_predecessor_of(const bblock_t *block,
  88                           enum bblock_link_kind kind) const;
  89    bool is_successor_of(const bblock_t *block,
  90                         enum bblock_link_kind kind) const;
  91    bool can_combine_with(const bblock_t *that) const;
  92    void combine_with(bblock_t *that);
  93    void dump() const;
  94
  95    backend_instruction *start();
  96    const backend_instruction *start() const;
  97    backend_instruction *end();
  98    const backend_instruction *end() const;
  99
 100    bblock_t *next();
 101    const bblock_t *next() const;
 102    bblock_t *prev();
 103    const bblock_t *prev() const;
 104
 105    bool starts_with_control_flow() const;
 106    bool ends_with_control_flow() const;
 107
 108    backend_instruction *first_non_control_flow_inst();
 109    backend_instruction *last_non_control_flow_inst();
 110 #endif
 111
 112    struct exec_node link;
 113    struct cfg_t *cfg;
 114
 115    int start_ip;
 116    int end_ip;
 117
 118    struct exec_list instructions;
 119    struct exec_list parents;
 120    struct exec_list children;
 121    int num;
 122
 123    unsigned cycle_count;
 124 };
 125
 126 static inline struct backend_instruction *
 127 bblock_start(struct bblock_t *block)
 128 {
 129    return (struct backend_instruction *)exec_list_get_head(&block->instructions);
 130 }
 131
 132 static inline const struct backend_instruction *
 133 bblock_start_const(const struct bblock_t *block)
 134 {
 135    return (const struct backend_instruction *)exec_list_get_head_const(&block->instructions);
 136 }
 137
 138 static inline struct backend_instruction *
 139 bblock_end(struct bblock_t *block)
 140 {
 141    return (struct backend_instruction *)exec_list_get_tail(&block->instructions);
 142 }
 143
 144 static inline const struct backend_instruction *
 145 bblock_end_const(const struct bblock_t *block)
 146 {
 147    return (const struct backend_instruction *)exec_list_get_tail_const(&block->instructions);
 148 }
 149
 150 static inline struct bblock_t *
 151 bblock_next(struct bblock_t *block)
 152 {
 153    if (exec_node_is_tail_sentinel(block->link.next))
 154       return NULL;
 155
 156    return (struct bblock_t *)block->link.next;
 157 }
 158
 159 static inline const struct bblock_t *
 160 bblock_next_const(const struct bblock_t *block)
 161 {
 162    if (exec_node_is_tail_sentinel(block->link.next))
 163       return NULL;
 164
 165    return (const struct bblock_t *)block->link.next;
 166 }
 167
 168 static inline struct bblock_t *
 169 bblock_prev(struct bblock_t *block)
 170 {
 171    if (exec_node_is_head_sentinel(block->link.prev))
 172       return NULL;
 173
 174    return (struct bblock_t *)block->link.prev;
 175 }
 176
 177 static inline const struct bblock_t *
 178 bblock_prev_const(const struct bblock_t *block)
 179 {
 180    if (exec_node_is_head_sentinel(block->link.prev))
 181       return NULL;
 182
 183    return (const struct bblock_t *)block->link.prev;
 184 }
 185
 186 static inline bool
 187 bblock_starts_with_control_flow(const struct bblock_t *block)
 188 {
 189    enum opcode op = bblock_start_const(block)->opcode;
 190    return op == BRW_OPCODE_DO || op == BRW_OPCODE_ENDIF;
 191 }
 192
 193 static inline bool
 194 bblock_ends_with_control_flow(const struct bblock_t *block)
 195 {
 196    enum opcode op = bblock_end_const(block)->opcode;
 197    return op == BRW_OPCODE_IF ||
 198           op == BRW_OPCODE_ELSE ||
 199           op == BRW_OPCODE_WHILE ||
 200           op == BRW_OPCODE_BREAK ||
 201           op == BRW_OPCODE_CONTINUE;
 202 }
 203
 204 static inline struct backend_instruction *
 205 bblock_first_non_control_flow_inst(struct bblock_t *block)
 206 {
 207    struct backend_instruction *inst = bblock_start(block);
 208    if (bblock_starts_with_control_flow(block))
 209 #ifdef __cplusplus
 210       inst = (struct backend_instruction *)inst->next;
 211 #else
 212       inst = (struct backend_instruction *)inst->link.next;
 213 #endif
 214    return inst;
 215 }
 216
 217 static inline struct backend_instruction *
 218 bblock_last_non_control_flow_inst(struct bblock_t *block)
 219 {
 220    struct backend_instruction *inst = bblock_end(block);
 221    if (bblock_ends_with_control_flow(block))
 222 #ifdef __cplusplus
 223       inst = (struct backend_instruction *)inst->prev;
 224 #else
 225       inst = (struct backend_instruction *)inst->link.prev;
 226 #endif
 227    return inst;
 228 }
 229
 230 #ifdef __cplusplus
 231 inline backend_instruction *
 232 bblock_t::start()
 233 {
 234    return bblock_start(this);
 235 }
 236
 237 inline const backend_instruction *
 238 bblock_t::start() const
 239 {
 240    return bblock_start_const(this);
 241 }
 242
 243 inline backend_instruction *
 244 bblock_t::end()
 245 {
 246    return bblock_end(this);
 247 }
 248
 249 inline const backend_instruction *
 250 bblock_t::end() const
 251 {
 252    return bblock_end_const(this);
 253 }
 254
 255 inline bblock_t *
 256 bblock_t::next()
 257 {
 258    return bblock_next(this);
 259 }
 260
 261 inline const bblock_t *
 262 bblock_t::next() const
 263 {
 264    return bblock_next_const(this);
 265 }
 266
 267 inline bblock_t *
 268 bblock_t::prev()
 269 {
 270    return bblock_prev(this);
 271 }
 272
 273 inline const bblock_t *
 274 bblock_t::prev() const
 275 {
 276    return bblock_prev_const(this);
 277 }
 278
 279 inline bool
 280 bblock_t::starts_with_control_flow() const
 281 {
 282    return bblock_starts_with_control_flow(this);
 283 }
 284
 285 inline bool
 286 bblock_t::ends_with_control_flow() const
 287 {
 288    return bblock_ends_with_control_flow(this);
 289 }
 290
 291 inline backend_instruction *
 292 bblock_t::first_non_control_flow_inst()
 293 {
 294    return bblock_first_non_control_flow_inst(this);
 295 }
 296
 297 inline backend_instruction *
 298 bblock_t::last_non_control_flow_inst()
 299 {
 300    return bblock_last_non_control_flow_inst(this);
 301 }
 302 #endif
 303
 304 struct cfg_t {
 305 #ifdef __cplusplus
 306    DECLARE_RALLOC_CXX_OPERATORS(cfg_t)
 307
 308    cfg_t(const backend_shader *s, exec_list *instructions);
 309    ~cfg_t();
 310
 311    void remove_block(bblock_t *block);
 312
 313    bblock_t *first_block();
 314    const bblock_t *first_block() const;
 315    bblock_t *last_block();
 316    const bblock_t *last_block() const;
 317
 318    bblock_t *new_block();
 319    void set_next_block(bblock_t **cur, bblock_t *block, int ip);
 320    void make_block_array();
 321
 322    void dump();
 323    void dump_cfg();
 324 #endif
 325    const struct backend_shader *s;
 326    void *mem_ctx;
 327
 328    /** Ordered list (by ip) of basic blocks */
 329    struct exec_list block_list;
 330    struct bblock_t **blocks;
 331    int num_blocks;
 332
 333    unsigned cycle_count;
 334 };
 335
 336 static inline struct bblock_t *
 337 cfg_first_block(struct cfg_t *cfg)
 338 {
 339    return (struct bblock_t *)exec_list_get_head(&cfg->block_list);
 340 }
 341
 342 static inline const struct bblock_t *
 343 cfg_first_block_const(const struct cfg_t *cfg)
 344 {
 345    return (const struct bblock_t *)exec_list_get_head_const(&cfg->block_list);
 346 }
 347
 348 static inline struct bblock_t *
 349 cfg_last_block(struct cfg_t *cfg)
 350 {
 351    return (struct bblock_t *)exec_list_get_tail(&cfg->block_list);
 352 }
 353
 354 static inline const struct bblock_t *
 355 cfg_last_block_const(const struct cfg_t *cfg)
 356 {
 357    return (const struct bblock_t *)exec_list_get_tail_const(&cfg->block_list);
 358 }
 359
 360 #ifdef __cplusplus
 361 inline bblock_t *
 362 cfg_t::first_block()
 363 {
 364    return cfg_first_block(this);
 365 }
 366
 367 const inline bblock_t *
 368 cfg_t::first_block() const
 369 {
 370    return cfg_first_block_const(this);
 371 }
 372
 373 inline bblock_t *
 374 cfg_t::last_block()
 375 {
 376    return cfg_last_block(this);
 377 }
 378
 379 const inline bblock_t *
 380 cfg_t::last_block() const
 381 {
 382    return cfg_last_block_const(this);
 383 }
 384 #endif
 385
 386 /* Note that this is implemented with a double for loop -- break will
 387  * break from the inner loop only!
 388  */
 389 #define foreach_block_and_inst(__block, __type, __inst, __cfg) \
 390    foreach_block (__block, __cfg)                              \
 391       foreach_inst_in_block (__type, __inst, __block)
 392
 393 /* Note that this is implemented with a double for loop -- break will
 394  * break from the inner loop only!
 395  */
 396 #define foreach_block_and_inst_safe(__block, __type, __inst, __cfg) \
 397    foreach_block_safe (__block, __cfg)                              \
 398       foreach_inst_in_block_safe (__type, __inst, __block)
 399
 400 #define foreach_block(__block, __cfg)                          \
 401    foreach_list_typed (bblock_t, __block, link, &(__cfg)->block_list)
 402
 403 #define foreach_block_reverse(__block, __cfg)                  \
 404    foreach_list_typed_reverse (bblock_t, __block, link, &(__cfg)->block_list)
 405
 406 #define foreach_block_safe(__block, __cfg)                     \
 407    foreach_list_typed_safe (bblock_t, __block, link, &(__cfg)->block_list)
 408
 409 #define foreach_block_reverse_safe(__block, __cfg)             \
 410    foreach_list_typed_reverse_safe (bblock_t, __block, link, &(__cfg)->block_list)
 411
 412 #define foreach_inst_in_block(__type, __inst, __block)         \
 413    foreach_in_list(__type, __inst, &(__block)->instructions)
 414
 415 #define foreach_inst_in_block_safe(__type, __inst, __block)    \
 416    for (__type *__inst = (__type *)__block->instructions.head_sentinel.next, \
 417                *__next = (__type *)__inst->next;               \
 418         __next != NULL;                                        \
 419         __inst = __next,                                       \
 420         __next = (__type *)__next->next)
 421
 422 #define foreach_inst_in_block_reverse(__type, __inst, __block) \
 423    foreach_in_list_reverse(__type, __inst, &(__block)->instructions)
 424
 425 #define foreach_inst_in_block_reverse_safe(__type, __inst, __block) \
 426    foreach_in_list_reverse_safe(__type, __inst, &(__block)->instructions)
 427
 428 #define foreach_inst_in_block_starting_from(__type, __scan_inst, __inst) \
 429    for (__type *__scan_inst = (__type *)__inst->next;          \
 430         !__scan_inst->is_tail_sentinel();                      \
 431         __scan_inst = (__type *)__scan_inst->next)
 432
 433 #define foreach_inst_in_block_reverse_starting_from(__type, __scan_inst, __inst) \
 434    for (__type *__scan_inst = (__type *)__inst->prev;          \
 435         !__scan_inst->is_head_sentinel();                      \
 436         __scan_inst = (__type *)__scan_inst->prev)
 437
 438 #ifdef __cplusplus
 439 namespace brw {
 440    /**
 441     * Immediate dominator tree analysis of a shader.
 442     */
 443    struct idom_tree {
 444       idom_tree(const backend_shader *s);
 445       ~idom_tree();
 446
 447       bool
 448       validate(const backend_shader *) const
 449       {
 450          /* FINISHME */
 451          return true;
 452       }
 453
 454       analysis_dependency_class
 455       dependency_class() const
 456       {
 457          return DEPENDENCY_BLOCKS;
 458       }
 459
 460       const bblock_t *
 461       parent(const bblock_t *b) const
 462       {
 463          assert(unsigned(b->num) < num_parents);
 464          return parents[b->num];
 465       }
 466
 467       bblock_t *
 468       parent(bblock_t *b) const
 469       {
 470          assert(unsigned(b->num) < num_parents);
 471          return parents[b->num];
 472       }
 473
 474       bblock_t *
 475       intersect(bblock_t *b1, bblock_t *b2) const;
 476
 477       void
 478       dump() const;
 479
 480    private:
 481       unsigned num_parents;
 482       bblock_t **parents;
 483    };
 484 }
 485 #endif
 486
 487 #endif /* BRW_CFG_H */