[Mesa-dev] [PATCH 3/4] i965: Add code to verify the CFG is sane.
Jason Ekstrand
jason at jlekstrand.net
Thu Nov 6 09:41:02 PST 2014
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?
More comments inline
On Wed, Nov 5, 2014 at 4:13 PM, Matt Turner <mattst88 at gmail.com> wrote:
> ---
> 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);
> + }
>
This obviously catches
if (foo) {
/* Do stuff */
} else {
break;
}
but what about
if (foo) {
break;
} else {
/* Do stuff */
}
Or worse, what about
if (foo) {
break;
} else {
continue;
}
Maybe there's something I'm missing here.
> +
> + 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;
> + }
>
how do we detect if a parent is simply missing? Or are we trusting in the
check above?
> + 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());
>
What about
...
} else {
break;
}
> + 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
> mesa-dev at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/mesa-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/mesa-dev/attachments/20141106/f738c00a/attachment-0001.html>
More information about the mesa-dev
mailing list