1/*
2 * Copyright © 2016 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
24#include "nir.h"
25
26static bool
27instr_is_continue(nir_instr *instr)
28{
29   if (instr->type != nir_instr_type_jump)
30      return false;
31
32   return nir_instr_as_jump(instr)->type == nir_jump_continue;
33}
34
35static bool
36lower_trivial_continues_block(nir_block *block, nir_loop *loop)
37{
38   bool progress = false;
39   nir_instr *first_instr = nir_block_first_instr(block);
40   if (!first_instr || instr_is_continue(first_instr)) {
41      /* The block contains only a continue if anything */
42      nir_cf_node *prev_node = nir_cf_node_prev(&block->cf_node);
43      if (prev_node && prev_node->type == nir_cf_node_if) {
44         nir_if *prev_if = nir_cf_node_as_if(prev_node);
45         progress |= lower_trivial_continues_block(
46            nir_if_last_then_block(prev_if), loop);
47         progress |= lower_trivial_continues_block(
48            nir_if_last_else_block(prev_if), loop);
49      }
50
51      /* The lower_phis_to_regs helper is smart enough to push phi sources as
52       * far up if-ladders as it possibly can.  In other words, the recursive
53       * calls above shouldn't be adding instructions to this block since it
54       * follows an if statement.
55       */
56      first_instr = nir_block_first_instr(block);
57      assert(!first_instr || instr_is_continue(first_instr));
58   }
59
60   nir_instr *last_instr = nir_block_last_instr(block);
61   if (!last_instr || !instr_is_continue(last_instr))
62      return progress;
63
64   /* We're at the end of a block that goes straight through to the end of the
65    * loop and continues to the top.  We can exit normally instead of jump.
66    */
67   nir_lower_phis_to_regs_block(nir_loop_first_block(loop));
68   nir_instr_remove(last_instr);
69   return true;
70}
71
72static bool
73lower_trivial_continues_list(struct exec_list *cf_list,
74                             bool list_ends_at_loop_tail,
75                             nir_loop *loop)
76{
77   bool progress = false;
78   foreach_list_typed(nir_cf_node, cf_node, node, cf_list) {
79      bool at_loop_tail = list_ends_at_loop_tail &&
80                          &cf_node->node == exec_list_get_tail(cf_list);
81      switch (cf_node->type) {
82      case nir_cf_node_block:
83         break;
84
85      case nir_cf_node_if: {
86         nir_if *nif = nir_cf_node_as_if(cf_node);
87         if (lower_trivial_continues_list(&nif->then_list, at_loop_tail, loop))
88            progress = true;
89         if (lower_trivial_continues_list(&nif->else_list, at_loop_tail, loop))
90            progress = true;
91         break;
92      }
93
94      case nir_cf_node_loop: {
95         nir_loop *loop = nir_cf_node_as_loop(cf_node);
96         if (lower_trivial_continues_list(&loop->body, true, loop))
97            progress = true;
98         if (lower_trivial_continues_block(nir_loop_last_block(loop), loop))
99            progress = true;
100         break;
101      }
102
103      case nir_cf_node_function:
104         unreachable("Invalid cf type");
105      }
106   }
107
108   return progress;
109}
110
111/**
112 * This simple pass gets rid of any "trivial" continues, i.e. those that are
113 * at the tail of a loop where we can just delete the continue instruction and
114 * control-flow will naturally and harmlessly take us back to the top of the
115 * loop.
116 */
117bool
118nir_opt_trivial_continues(nir_shader *shader)
119{
120   bool progress = false;
121
122   nir_foreach_function(function, shader) {
123      if (function->impl == NULL)
124         continue;
125
126      /* First we run the simple pass to get rid of pesky continues */
127      if (lower_trivial_continues_list(&function->impl->body, false, NULL)) {
128         nir_metadata_preserve(function->impl, nir_metadata_none);
129
130         /* If that made progress, we're no longer really in SSA form. */
131         nir_lower_regs_to_ssa_impl(function->impl);
132         progress = true;
133      } else {
134         nir_metadata_preserve(function->impl, nir_metadata_all);
135      }
136   }
137
138   return progress;
139}
140