<div dir="ltr"><div>In general, it seems as if this can miss several things. For instance, it checks that all the predicessors are valid but never that we have all the predecessors. Same for successors. If we really want to be able to validate a CFG, maybe a stack-based approach like calculate_cfg would work better? Also, did you run this on piglit/shader-db to ensure that everything coming out of calculate_cfg actually passes? </div>More comments inline <div><div><div class="gmail_extra"> <div class="gmail_quote">On Wed, Nov 5, 2014 at 4:13 PM, Matt Turner <<a href="mailto:mattst88@gmail.com" target="_blank">mattst88@gmail.com</a>> wrote: <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">--- src/mesa/drivers/dri/i965/test_verify_cfg.cpp | 273 ++++++++++++++++++++++++++ src/mesa/drivers/dri/i965/test_verify_cfg.h | 26 +++ 2 files changed, 299 insertions(+) create mode 100644 src/mesa/drivers/dri/i965/test_verify_cfg.cpp create mode 100644 src/mesa/drivers/dri/i965/test_verify_cfg.h diff --git a/src/mesa/drivers/dri/i965/test_verify_cfg.cpp b/src/mesa/drivers/dri/i965/test_verify_cfg.cpp new file mode 100644 index 0000000..0aa74c5 --- /dev/null +++ b/src/mesa/drivers/dri/i965/test_verify_cfg.cpp @@ -0,0 +1,273 @@ +/* + * Copyright © 2014 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + +#include <gtest/gtest.h> +#include "test_verify_cfg.h" +#include "brw_cfg.h" + +static bool +is_unconditional_jump(const backend_instruction *inst) +{ + return (inst->opcode == BRW_OPCODE_BREAK || + inst->opcode == BRW_OPCODE_CONTINUE || + inst->opcode == BRW_OPCODE_WHILE) && + inst->predicate == BRW_PREDICATE_NONE; +} + +void +verify_cfg(backend_visitor *v) +{ + foreach_block(block, v->cfg) { + switch (block->start()->opcode) { + case BRW_OPCODE_ENDIF: { + /* Has two predecessors: + * - the previous block is always a predecessor + * - always a predecessor ending in an IF or an ELSE + * + * Note that if the body of the if block is empty, then the + * previous block *is* the block that ends with IF, so the ENDIF + * block will have the same predecessor twice. + */ + if (is_unconditional_jump(block->prev()->end())) { + EXPECT_EQ(block->parents.length(), 1u); + } else { + EXPECT_EQ(block->parents.length(), 2u); + } </blockquote><div> </div><div>This obviously catches </div><div>if (foo) { </div><div> /* Do stuff */ </div><div>} else { </div><div> break; } </div><div>but what about </div><div>if (foo) { </div><div> break; </div><div>} else { /* Do stuff */ } </div><div>Or worse, what about </div><div>if (foo) { </div><div> break; </div><div>} else { </div><div> continue; } </div><div>Maybe there's something I'm missing here. </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> + + bool found_prev = false, found_if = false, found_else = false, + found_other = false; + foreach_list_typed(bblock_link, parent, link, &block->parents) { + if (parent->block == block->prev() && !found_prev) + found_prev = true; + else if (parent->block->end()->opcode == BRW_OPCODE_IF) + found_if = true; + else if (parent->block->end()->opcode == BRW_OPCODE_ELSE) + found_else = true; + else + found_other = true; + } </blockquote><div> </div><div>how do we detect if a parent is simply missing? Or are we trusting in the check above? </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> + EXPECT_NE(found_prev, is_unconditional_jump(block->prev()->end())); + EXPECT_NE(found_if, found_else); + EXPECT_FALSE(found_other); + break; + } + case BRW_OPCODE_DO: { + /* Has two or more predecessors + * - the previous block is always a predecessor + * - always a predecessor ending in a WHILE + * - some number of predecessors ending in continue + */ + if (is_unconditional_jump(block->prev()->end())) { + EXPECT_GE(block->parents.length(), 1u); + } else { + EXPECT_GE(block->parents.length(), 2u); + } + + bool found_prev = false, found_while = false, found_other = false; + foreach_list_typed(bblock_link, parent, link, &block->parents) { + if (parent->block == block->prev()) + found_prev = true; + else if (parent->block->end()->opcode == BRW_OPCODE_WHILE) + found_while = true; + else if (parent->block->end()->opcode != BRW_OPCODE_CONTINUE) + found_other = true; + } + + EXPECT_NE(found_prev, is_unconditional_jump(block->prev()->end())); + EXPECT_TRUE(found_while); + EXPECT_FALSE(found_other); + break; + } + default: { + if (block->num == 0) { + EXPECT_EQ(0u, block->parents.length()); + break; + } + /* Has one or more predecessors + * - the previous block is always a predecessor + * - some number of predecessors ending with break + */ + if (!is_unconditional_jump(block->prev()->end())) { + EXPECT_GE(block->parents.length(), 1u); + } + + bool found_prev = false, found_other = false; + foreach_list_typed(bblock_link, parent, link, &block->parents) { + if (parent->block == block->prev()) + found_prev = true; + else if (parent->block->end()->opcode != BRW_OPCODE_BREAK) + found_other = true; + } + + EXPECT_NE(found_prev, is_unconditional_jump(block->prev()->end())); + EXPECT_FALSE(found_other); + break; + } + } + + switch (block->end()->opcode) { + case BRW_OPCODE_IF: { + /* Has two successors: + * - the next block is always a successor + * - always a successor starting with ENDIF + * + * Note that if the body of the if block is empty, then the next block + * *is* the block that starts with ENDIF, so the IF block will have + * the same successor twice. + */ + EXPECT_EQ(block->children.length(), 2u); + + bool found_next = false, found_endif = false, found_other = false; + foreach_list_typed(bblock_link, child, link, &block->children) { + if (child->block == block->next() && !found_next) + found_next = true; + else if (child->block->start()->opcode == BRW_OPCODE_ENDIF) + found_endif = true; + else + found_other = true; + } + + EXPECT_TRUE(found_next); + EXPECT_TRUE(found_endif); + EXPECT_FALSE(found_other); + break; + } + case BRW_OPCODE_ELSE: { + /* Always a successor starting with ENDIF */ + EXPECT_EQ(1u, block->children.length()); </blockquote><div> </div><div>What about ... </div><div>} else { </div><div> break; } </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> + bool found_endif = false, found_other = false; + foreach_list_typed(bblock_link, child, link, &block->children) { + if (child->block->start()->opcode == BRW_OPCODE_ENDIF) + found_endif = true; + else + found_other = true; + } + + EXPECT_TRUE(found_endif); + EXPECT_FALSE(found_other); + break; + } + case BRW_OPCODE_WHILE: { + /* Has one or two successors: + * - always a successor starting with DO + * - if predicated, the next block is a successor + */ + backend_instruction *while_inst = block->end(); + if (while_inst->predicate == BRW_PREDICATE_NONE) { + EXPECT_EQ(1u, block->children.length()); + } else { + EXPECT_EQ(2u, block->children.length()); + } + + bool found_next = false, found_do = false, found_other = false; + foreach_list_typed(bblock_link, child, link, &block->children) { + if (child->block == block->next()) + found_next = true; + if (child->block->start()->opcode == BRW_OPCODE_DO) + found_do = true; + else + found_other = true; + } + + EXPECT_EQ(while_inst->predicate != BRW_PREDICATE_NONE, found_next); + EXPECT_TRUE(found_do); + EXPECT_FALSE(found_other); + break; + } + case BRW_OPCODE_BREAK: { + /* Has one or two successors: + * - always a successor following a WHILE + * - if predicated, the next block is a successor + */ + backend_instruction *break_inst = block->end(); + if (break_inst->predicate == BRW_PREDICATE_NONE) { + EXPECT_EQ(1u, block->children.length()); + } else { + EXPECT_EQ(2u, block->children.length()); + } + + bool found_next = false, found_while = false, found_other = false; + foreach_list_typed(bblock_link, child, link, &block->children) { + if (child->block == block->next()) + found_next = true; + else if (child->block->prev()->end()->opcode == BRW_OPCODE_WHILE) + found_while = true; + else + found_other = true; + } + + EXPECT_EQ(break_inst->predicate != BRW_PREDICATE_NONE, found_next); + EXPECT_TRUE(found_while); + EXPECT_FALSE(found_other); + break; + } + case BRW_OPCODE_CONTINUE: { + /* Has one or two successors: + * - always a successor starting with DO + * - if predicated, the next block is a successor + */ + backend_instruction *cont_inst = block->end(); + if (cont_inst->predicate == BRW_PREDICATE_NONE) { + EXPECT_EQ(1u, block->children.length()); + } else { + EXPECT_EQ(2u, block->children.length()); + } + + bool found_next = false, found_do = false, found_other = false; + foreach_list_typed(bblock_link, child, link, &block->children) { + if (child->block == block->next()) + found_next = true; + if (child->block->start()->opcode == BRW_OPCODE_DO) + found_do = true; + else + found_other = true; + } + + EXPECT_EQ(cont_inst->predicate != BRW_PREDICATE_NONE, found_next); + EXPECT_TRUE(found_do); + EXPECT_FALSE(found_other); + break; + } + default: + if (block->num == v->cfg->num_blocks - 1) { + EXPECT_EQ(0u, block->children.length()); + break; + } + /* The next block is always a successor */ + EXPECT_EQ(1u, block->children.length()); + bool found_next = false, found_other = false; + foreach_list_typed(bblock_link, child, link, &block->children) { + if (child->block == block->next()) + found_next = true; + else + found_other = true; + } + + EXPECT_TRUE(found_next); + EXPECT_FALSE(found_other); + break; + } + } +} diff --git a/src/mesa/drivers/dri/i965/test_verify_cfg.h b/src/mesa/drivers/dri/i965/test_verify_cfg.h new file mode 100644 index 0000000..16c9a24 --- /dev/null +++ b/src/mesa/drivers/dri/i965/test_verify_cfg.h @@ -0,0 +1,26 @@ +/* + * Copyright © 2014 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + +#include "brw_shader.h" + +void verify_cfg(backend_visitor *v); -- 2.0.4 _______________________________________________ mesa-dev mailing list <a href="mailto:mesa-dev@lists.freedesktop.org" target="_blank">mesa-dev@lists.freedesktop.org</a> <a href="http://lists.freedesktop.org/mailman/listinfo/mesa-dev" target="_blank">http://lists.freedesktop.org/mailman/listinfo/mesa-dev</a> </blockquote></div> </div></div></div></div>