src/panfrost/midgard/midgard_helper_invocations.c - third_party/mesa - Git at Google

 /*
  * Copyright (C) 2019 Collabora, Ltd.
  *
  * 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.
  *
  * Authors (Collabora):
  *    Alyssa Rosenzweig <alyssa.rosenzweig@collabora.com>
  */

 #include "compiler.h"

 /* Midgard texture/derivative operations have a pair of bits controlling the
  * behaviour of helper invocations:
  *
  *  - Should a helper invocation terminate after executing this instruction?
  *  - Should a helper invocation actually execute this instruction?
  *
  * The terminate bit should be set on the last instruction requiring helper
  * invocations. Without control flow, that's literally the last instruction;
  * with control flow, there may be multiple such instructions (with ifs) or no
  * such instruction (with loops).
  *
  * The execute bit should be set if the value of this instruction is required
  * by a future instruction requiring helper invocations. Consider:
  *
  *      0 = texture ...
  *      1 = fmul 0, #10
  *      2 = dfdx 1
  *      store 2
  *
  * Since the derivative calculation 2 requires helper invocations, the value 1
  * must be calculated by helper invocations, and since it depends on 0, 0 must
  * be calculated by helpers. Hence the texture op has the execute bit set, and
  * the derivative op has the terminate bit set.
  *
  * Calculating the terminate bit occurs by forward dataflow analysis to
  * determine which blocks require helper invocations. A block requires
  * invocations in if any of its instructions use helper invocations, or if it
  * depends on a block that requires invocation. With that analysis, the
  * terminate bit is set on the last instruction using invocations within any
  * block that does *not* require invocations out.
  *
  * Likewise, calculating the execute bit requires backward dataflow analysis
  * with union as the join operation and the generating set being the union of
  * sources of instructions writing executed values.
  */

 /* Does a block use helpers directly */
 static bool
 mir_block_uses_helpers(gl_shader_stage stage, midgard_block *block)
 {
         mir_foreach_instr_in_block(block, ins) {
                 if (ins->type != TAG_TEXTURE_4) continue;
                 if (mir_op_computes_derivatives(stage, ins->op))
                         return true;
         }

         return false;
 }

 static bool
 mir_block_terminates_helpers(midgard_block *block)
 {
         /* Can't terminate if there are no helpers */
         if (!block->helpers_in)
                 return false;

         /* Can't terminate if a successor needs helpers */
         pan_foreach_successor((&block->base), succ) {
                 if (((midgard_block *) succ)->helpers_in)
                         return false;
         }

         /* Otherwise we terminate */
         return true;
 }

 void
 mir_analyze_helper_terminate(compiler_context *ctx)
 {
         /* Set blocks as directly requiring helpers, and if they do add them to
          * the worklist to propagate to their predecessors */

         struct set *worklist = _mesa_set_create(NULL,
                         _mesa_hash_pointer,
                         _mesa_key_pointer_equal);

         struct set *visited = _mesa_set_create(NULL,
                         _mesa_hash_pointer,
                         _mesa_key_pointer_equal);

         mir_foreach_block(ctx, _block) {
                 midgard_block *block = (midgard_block *) _block;
                 block->helpers_in |= mir_block_uses_helpers(ctx->stage, block);

                 if (block->helpers_in)
                         _mesa_set_add(worklist, _block);
         }

         /* Next, propagate back. Since there are a finite number of blocks, the
          * worklist (a subset of all the blocks) is finite. Since a block can
          * only be added to the worklist if it is not on the visited list and
          * the visited list - also a subset of the blocks - grows every
          * iteration, the algorithm must terminate. */

         struct set_entry *cur;

         while((cur = _mesa_set_next_entry(worklist, NULL)) != NULL) {
                 /* Pop off a block requiring helpers */
                 pan_block *blk = (struct pan_block *) cur->key;
                 _mesa_set_remove(worklist, cur);

                 /* Its predecessors also require helpers */
                 pan_foreach_predecessor(blk, pred) {
                         if (!_mesa_set_search(visited, pred)) {
                                 ((midgard_block *) pred)->helpers_in = true;
                                 _mesa_set_add(worklist, pred);
                         }
                 }

                 _mesa_set_add(visited, blk);
         }

         _mesa_set_destroy(visited, NULL);
         _mesa_set_destroy(worklist, NULL);

         /* Finally, set helper_terminate on the last derivative-calculating
          * instruction in a block that terminates helpers */
         mir_foreach_block(ctx, _block) {
                 midgard_block *block = (midgard_block *) _block;

                 if (!mir_block_terminates_helpers(block))
                         continue;

                 mir_foreach_instr_in_block_rev(block, ins) {
                         if (ins->type != TAG_TEXTURE_4) continue;
                         if (!mir_op_computes_derivatives(ctx->stage, ins->op)) continue;

                         ins->helper_terminate = true;
                         break;
                 }
         }
 }

 static bool
 mir_helper_block_update(BITSET_WORD *deps, pan_block *_block, unsigned temp_count)
 {
         bool progress = false;
         midgard_block *block = (midgard_block *) _block;

         mir_foreach_instr_in_block_rev(block, ins) {
                 /* Ensure we write to a helper dependency */
                 if (ins->dest >= temp_count || !BITSET_TEST(deps, ins->dest))
                         continue;

                 /* Then add all of our dependencies */
                 mir_foreach_src(ins, s) {
                         if (ins->src[s] >= temp_count)
                                 continue;

                         /* Progress if the dependency set changes */
                         progress |= !BITSET_TEST(deps, ins->src[s]);
                         BITSET_SET(deps, ins->src[s]);
                 }
         }

         return progress;
 }

 void
 mir_analyze_helper_requirements(compiler_context *ctx)
 {
         mir_compute_temp_count(ctx);
         unsigned temp_count = ctx->temp_count;
         BITSET_WORD *deps = calloc(sizeof(BITSET_WORD), BITSET_WORDS(temp_count));

         /* Initialize with the sources of instructions consuming
          * derivatives */

         mir_foreach_instr_global(ctx, ins) {
                 if (ins->type != TAG_TEXTURE_4) continue;
                 if (ins->dest >= ctx->temp_count) continue;
                 if (!mir_op_computes_derivatives(ctx->stage, ins->op)) continue;

                 mir_foreach_src(ins, s) {
                         if (ins->src[s] < temp_count)
                                 BITSET_SET(deps, ins->src[s]);
                 }
         }

         /* Propagate that up */

         struct set *work_list = _mesa_set_create(NULL,
                         _mesa_hash_pointer,
                         _mesa_key_pointer_equal);

         struct set *visited = _mesa_set_create(NULL,
                         _mesa_hash_pointer,
                         _mesa_key_pointer_equal);

         struct set_entry *cur = _mesa_set_add(work_list, pan_exit_block(&ctx->blocks));

         do {
                 pan_block *blk = (struct pan_block *) cur->key;
                 _mesa_set_remove(work_list, cur);

                 bool progress = mir_helper_block_update(deps, blk, temp_count);

                 if (progress || !_mesa_set_search(visited, blk)) {
                         pan_foreach_predecessor(blk, pred)
                                 _mesa_set_add(work_list, pred);
                 }

                 _mesa_set_add(visited, blk);
         } while((cur = _mesa_set_next_entry(work_list, NULL)) != NULL);

         _mesa_set_destroy(visited, NULL);
         _mesa_set_destroy(work_list, NULL);

         /* Set the execute bits */

         mir_foreach_instr_global(ctx, ins) {
                 if (ins->type != TAG_TEXTURE_4) continue;
                 if (ins->dest >= ctx->temp_count) continue;

                 ins->helper_execute = BITSET_TEST(deps, ins->dest);
         }

         free(deps);
 }
	/*
	* Copyright (C) 2019 Collabora, Ltd.
	*
	* 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.
	*
	* Authors (Collabora):
	* Alyssa Rosenzweig <alyssa.rosenzweig@collabora.com>
	*/

	#include "compiler.h"

	/* Midgard texture/derivative operations have a pair of bits controlling the
	* behaviour of helper invocations:
	*
	* - Should a helper invocation terminate after executing this instruction?
	* - Should a helper invocation actually execute this instruction?
	*
	* The terminate bit should be set on the last instruction requiring helper
	* invocations. Without control flow, that's literally the last instruction;
	* with control flow, there may be multiple such instructions (with ifs) or no
	* such instruction (with loops).
	*
	* The execute bit should be set if the value of this instruction is required
	* by a future instruction requiring helper invocations. Consider:
	*
	* 0 = texture ...
	* 1 = fmul 0, #10
	* 2 = dfdx 1
	* store 2
	*
	* Since the derivative calculation 2 requires helper invocations, the value 1
	* must be calculated by helper invocations, and since it depends on 0, 0 must
	* be calculated by helpers. Hence the texture op has the execute bit set, and
	* the derivative op has the terminate bit set.
	*
	* Calculating the terminate bit occurs by forward dataflow analysis to
	* determine which blocks require helper invocations. A block requires
	* invocations in if any of its instructions use helper invocations, or if it
	* depends on a block that requires invocation. With that analysis, the
	* terminate bit is set on the last instruction using invocations within any
	* block that does not require invocations out.
	*
	* Likewise, calculating the execute bit requires backward dataflow analysis
	* with union as the join operation and the generating set being the union of
	* sources of instructions writing executed values.
	*/

	/* Does a block use helpers directly */
	static bool
	mir_block_uses_helpers(gl_shader_stage stage, midgard_block *block)
	{
	mir_foreach_instr_in_block(block, ins) {
	if (ins->type != TAG_TEXTURE_4) continue;
	if (mir_op_computes_derivatives(stage, ins->op))
	return true;
	}

	return false;
	}

	static bool
	mir_block_terminates_helpers(midgard_block *block)
	{
	/* Can't terminate if there are no helpers */
	if (!block->helpers_in)
	return false;

	/* Can't terminate if a successor needs helpers */
	pan_foreach_successor((&block->base), succ) {
	if (((midgard_block *) succ)->helpers_in)
	return false;
	}

	/* Otherwise we terminate */
	return true;
	}

	void
	mir_analyze_helper_terminate(compiler_context *ctx)
	{
	/* Set blocks as directly requiring helpers, and if they do add them to
	* the worklist to propagate to their predecessors */

	struct set *worklist = _mesa_set_create(NULL,
	_mesa_hash_pointer,
	_mesa_key_pointer_equal);

	struct set *visited = _mesa_set_create(NULL,
	_mesa_hash_pointer,
	_mesa_key_pointer_equal);

	mir_foreach_block(ctx, _block) {
	midgard_block block = (midgard_block ) _block;
	block->helpers_in \|= mir_block_uses_helpers(ctx->stage, block);

	if (block->helpers_in)
	_mesa_set_add(worklist, _block);
	}

	/* Next, propagate back. Since there are a finite number of blocks, the
	* worklist (a subset of all the blocks) is finite. Since a block can
	* only be added to the worklist if it is not on the visited list and
	* the visited list - also a subset of the blocks - grows every
	* iteration, the algorithm must terminate. */

	struct set_entry *cur;

	while((cur = _mesa_set_next_entry(worklist, NULL)) != NULL) {
	/* Pop off a block requiring helpers */
	pan_block blk = (struct pan_block ) cur->key;
	_mesa_set_remove(worklist, cur);

	/* Its predecessors also require helpers */
	pan_foreach_predecessor(blk, pred) {
	if (!_mesa_set_search(visited, pred)) {
	((midgard_block *) pred)->helpers_in = true;
	_mesa_set_add(worklist, pred);
	}
	}

	_mesa_set_add(visited, blk);
	}

	_mesa_set_destroy(visited, NULL);
	_mesa_set_destroy(worklist, NULL);

	/* Finally, set helper_terminate on the last derivative-calculating
	* instruction in a block that terminates helpers */
	mir_foreach_block(ctx, _block) {
	midgard_block block = (midgard_block ) _block;

	if (!mir_block_terminates_helpers(block))
	continue;

	mir_foreach_instr_in_block_rev(block, ins) {
	if (ins->type != TAG_TEXTURE_4) continue;
	if (!mir_op_computes_derivatives(ctx->stage, ins->op)) continue;

	ins->helper_terminate = true;
	break;
	}
	}
	}

	static bool
	mir_helper_block_update(BITSET_WORD deps, pan_block _block, unsigned temp_count)
	{
	bool progress = false;
	midgard_block block = (midgard_block ) _block;

	mir_foreach_instr_in_block_rev(block, ins) {
	/* Ensure we write to a helper dependency */
	if (ins->dest >= temp_count \|\| !BITSET_TEST(deps, ins->dest))
	continue;

	/* Then add all of our dependencies */
	mir_foreach_src(ins, s) {
	if (ins->src[s] >= temp_count)
	continue;

	/* Progress if the dependency set changes */
	progress \|= !BITSET_TEST(deps, ins->src[s]);
	BITSET_SET(deps, ins->src[s]);
	}
	}

	return progress;
	}

	void
	mir_analyze_helper_requirements(compiler_context *ctx)
	{
	mir_compute_temp_count(ctx);
	unsigned temp_count = ctx->temp_count;
	BITSET_WORD *deps = calloc(sizeof(BITSET_WORD), BITSET_WORDS(temp_count));

	/* Initialize with the sources of instructions consuming
	* derivatives */

	mir_foreach_instr_global(ctx, ins) {
	if (ins->type != TAG_TEXTURE_4) continue;
	if (ins->dest >= ctx->temp_count) continue;
	if (!mir_op_computes_derivatives(ctx->stage, ins->op)) continue;

	mir_foreach_src(ins, s) {
	if (ins->src[s] < temp_count)
	BITSET_SET(deps, ins->src[s]);
	}
	}

	/* Propagate that up */

	struct set *work_list = _mesa_set_create(NULL,
	_mesa_hash_pointer,
	_mesa_key_pointer_equal);

	struct set *visited = _mesa_set_create(NULL,
	_mesa_hash_pointer,
	_mesa_key_pointer_equal);

	struct set_entry *cur = _mesa_set_add(work_list, pan_exit_block(&ctx->blocks));

	do {
	pan_block blk = (struct pan_block ) cur->key;
	_mesa_set_remove(work_list, cur);

	bool progress = mir_helper_block_update(deps, blk, temp_count);

	if (progress \|\| !_mesa_set_search(visited, blk)) {
	pan_foreach_predecessor(blk, pred)
	_mesa_set_add(work_list, pred);
	}

	_mesa_set_add(visited, blk);
	} while((cur = _mesa_set_next_entry(work_list, NULL)) != NULL);

	_mesa_set_destroy(visited, NULL);
	_mesa_set_destroy(work_list, NULL);

	/* Set the execute bits */

	mir_foreach_instr_global(ctx, ins) {
	if (ins->type != TAG_TEXTURE_4) continue;
	if (ins->dest >= ctx->temp_count) continue;

	ins->helper_execute = BITSET_TEST(deps, ins->dest);
	}

	free(deps);
	}