1/*
2 * Copyright © 2010 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
21 * DEALINGS IN THE SOFTWARE.
22 */
23
24/**
25 * \file lower_if_to_cond_assign.cpp
26 *
27 * This attempts to flatten if-statements to conditional assignments for
28 * GPUs with limited or no flow control support.
29 *
30 * It can't handle other control flow being inside of its block, such
31 * as calls or loops.  Hopefully loop unrolling and inlining will take
32 * care of those.
33 *
34 * Drivers for GPUs with no control flow support should simply call
35 *
36 *    lower_if_to_cond_assign(instructions)
37 *
38 * to attempt to flatten all if-statements.
39 *
40 * Some GPUs (such as i965 prior to gen6) do support control flow, but have a
41 * maximum nesting depth N.  Drivers for such hardware can call
42 *
43 *    lower_if_to_cond_assign(instructions, N)
44 *
45 * to attempt to flatten any if-statements appearing at depth > N.
46 */
47
48#include "glsl_types.h"
49#include "ir.h"
50#include "program/hash_table.h"
51
52class ir_if_to_cond_assign_visitor : public ir_hierarchical_visitor {
53public:
54   ir_if_to_cond_assign_visitor(unsigned max_depth)
55   {
56      this->progress = false;
57      this->max_depth = max_depth;
58      this->depth = 0;
59
60      this->condition_variables = hash_table_ctor(0, hash_table_pointer_hash,
61						  hash_table_pointer_compare);
62   }
63
64   ~ir_if_to_cond_assign_visitor()
65   {
66      hash_table_dtor(this->condition_variables);
67   }
68
69   ir_visitor_status visit_enter(ir_if *);
70   ir_visitor_status visit_leave(ir_if *);
71
72   bool progress;
73   unsigned max_depth;
74   unsigned depth;
75
76   struct hash_table *condition_variables;
77};
78
79bool
80lower_if_to_cond_assign(exec_list *instructions, unsigned max_depth)
81{
82   if (max_depth == UINT_MAX)
83      return false;
84
85   ir_if_to_cond_assign_visitor v(max_depth);
86
87   visit_list_elements(&v, instructions);
88
89   return v.progress;
90}
91
92void
93check_control_flow(ir_instruction *ir, void *data)
94{
95   bool *found_control_flow = (bool *)data;
96   switch (ir->ir_type) {
97   case ir_type_call:
98   case ir_type_discard:
99   case ir_type_loop:
100   case ir_type_loop_jump:
101   case ir_type_return:
102      *found_control_flow = true;
103      break;
104   default:
105      break;
106   }
107}
108
109void
110move_block_to_cond_assign(void *mem_ctx,
111			  ir_if *if_ir, ir_rvalue *cond_expr,
112			  exec_list *instructions,
113			  struct hash_table *ht)
114{
115   foreach_list_safe(node, instructions) {
116      ir_instruction *ir = (ir_instruction *) node;
117
118      if (ir->ir_type == ir_type_assignment) {
119	 ir_assignment *assign = (ir_assignment *)ir;
120
121	 if (hash_table_find(ht, assign) == NULL) {
122	    hash_table_insert(ht, assign, assign);
123
124	    /* If the LHS of the assignment is a condition variable that was
125	     * previously added, insert an additional assignment of false to
126	     * the variable.
127	     */
128	    const bool assign_to_cv =
129	       hash_table_find(ht, assign->lhs->variable_referenced()) != NULL;
130
131	    if (!assign->condition) {
132	       if (assign_to_cv) {
133		  assign->rhs =
134		     new(mem_ctx) ir_expression(ir_binop_logic_and,
135						glsl_type::bool_type,
136						cond_expr->clone(mem_ctx, NULL),
137						assign->rhs);
138	       } else {
139		  assign->condition = cond_expr->clone(mem_ctx, NULL);
140	       }
141	    } else {
142	       assign->condition =
143		  new(mem_ctx) ir_expression(ir_binop_logic_and,
144					     glsl_type::bool_type,
145					     cond_expr->clone(mem_ctx, NULL),
146					     assign->condition);
147	    }
148	 }
149      }
150
151      /* Now, move from the if block to the block surrounding it. */
152      ir->remove();
153      if_ir->insert_before(ir);
154   }
155}
156
157ir_visitor_status
158ir_if_to_cond_assign_visitor::visit_enter(ir_if *ir)
159{
160   (void) ir;
161   this->depth++;
162
163   return visit_continue;
164}
165
166ir_visitor_status
167ir_if_to_cond_assign_visitor::visit_leave(ir_if *ir)
168{
169   /* Only flatten when beyond the GPU's maximum supported nesting depth. */
170   if (this->depth-- <= this->max_depth)
171      return visit_continue;
172
173   bool found_control_flow = false;
174   ir_assignment *assign;
175
176   /* Check that both blocks don't contain anything we can't support. */
177   foreach_iter(exec_list_iterator, then_iter, ir->then_instructions) {
178      ir_instruction *then_ir = (ir_instruction *)then_iter.get();
179      visit_tree(then_ir, check_control_flow, &found_control_flow);
180   }
181   foreach_iter(exec_list_iterator, else_iter, ir->else_instructions) {
182      ir_instruction *else_ir = (ir_instruction *)else_iter.get();
183      visit_tree(else_ir, check_control_flow, &found_control_flow);
184   }
185   if (found_control_flow)
186      return visit_continue;
187
188   void *mem_ctx = ralloc_parent(ir);
189
190   /* Store the condition to a variable.  Move all of the instructions from
191    * the then-clause of the if-statement.  Use the condition variable as a
192    * condition for all assignments.
193    */
194   ir_variable *const then_var =
195      new(mem_ctx) ir_variable(glsl_type::bool_type,
196			       "if_to_cond_assign_then",
197			       ir_var_temporary);
198   ir->insert_before(then_var);
199
200   ir_dereference_variable *then_cond =
201      new(mem_ctx) ir_dereference_variable(then_var);
202
203   assign = new(mem_ctx) ir_assignment(then_cond, ir->condition);
204   ir->insert_before(assign);
205
206   move_block_to_cond_assign(mem_ctx, ir, then_cond,
207			     &ir->then_instructions,
208			     this->condition_variables);
209
210   /* Add the new condition variable to the hash table.  This allows us to
211    * find this variable when lowering other (enclosing) if-statements.
212    */
213   hash_table_insert(this->condition_variables, then_var, then_var);
214
215   /* If there are instructions in the else-clause, store the inverse of the
216    * condition to a variable.  Move all of the instructions from the
217    * else-clause if the if-statement.  Use the (inverse) condition variable
218    * as a condition for all assignments.
219    */
220   if (!ir->else_instructions.is_empty()) {
221      ir_variable *const else_var =
222	 new(mem_ctx) ir_variable(glsl_type::bool_type,
223				  "if_to_cond_assign_else",
224				  ir_var_temporary);
225      ir->insert_before(else_var);
226
227      ir_dereference_variable *else_cond =
228	 new(mem_ctx) ir_dereference_variable(else_var);
229
230      ir_rvalue *inverse =
231	 new(mem_ctx) ir_expression(ir_unop_logic_not,
232				    then_cond->clone(mem_ctx, NULL));
233
234      assign = new(mem_ctx) ir_assignment(else_cond, inverse);
235      ir->insert_before(assign);
236
237      move_block_to_cond_assign(mem_ctx, ir, else_cond,
238				&ir->else_instructions,
239				this->condition_variables);
240
241      /* Add the new condition variable to the hash table.  This allows us to
242       * find this variable when lowering other (enclosing) if-statements.
243       */
244      hash_table_insert(this->condition_variables, else_var, else_var);
245   }
246
247   ir->remove();
248
249   this->progress = true;
250
251   return visit_continue;
252}
253