[Mesa-dev] [PATCH 3/4] i965: Add code to verify the CFG is sane.
Matt Turner
mattst88 at gmail.com
Thu Nov 6 10:37:44 PST 2014
On Thu, Nov 6, 2014 at 9:41 AM, Jason Ekstrand <jason at jlekstrand.net> wrote:
> 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.
I'm not sure what you mean. That we don't validate that if A -> B then
B has an incoming edge from A? That's true.
I think that would be a good addition. I'm not sure I want to do that
in this patch. It was pretty big as is.
>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?
I don't think it will pass because of the things you pointed out about
unconditional jumps.
> 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.
I think you're right. For purposes of testing the predicated break
pass I didn't really care about unconditional jumps (since they would
be removed by the pass!). I added the unconditional jump cases as an
after thought.
So the question is whether I can actually test the cases you mention
in the current model? I'm not super excited expending a bunch more
effort to rewrite some testing code that already tests the thing I
want.
>>
>> +
>> + 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;
> }
Well, the ELSE instruction jumps, so it'd be in a different block than
the BREAK. There's no case in which an ELSE does not have an ENDIF
successor.
More information about the mesa-dev
mailing list