1/**************************************************************************
2 *
3 * Copyright 2009 VMware, Inc.
4 * Copyright 2007-2008 VMware, Inc.
5 * All Rights Reserved.
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a
8 * copy of this software and associated documentation files (the
9 * "Software"), to deal in the Software without restriction, including
10 * without limitation the rights to use, copy, modify, merge, publish,
11 * distribute, sub license, and/or sell copies of the Software, and to
12 * permit persons to whom the Software is furnished to do so, subject to
13 * the following conditions:
14 *
15 * The above copyright notice and this permission notice (including the
16 * next paragraph) shall be included in all copies or substantial portions
17 * of the Software.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
20 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
22 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
23 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
24 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
25 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26 *
27 **************************************************************************/
28
29#include "util/u_memory.h"
30#include "lp_bld_type.h"
31#include "lp_bld_init.h"
32#include "lp_bld_flow.h"
33#include "lp_bld_ir_common.h"
34#include "lp_bld_logic.h"
35
36/*
37 * Return the context for the current function.
38 * (always 'main', if shader doesn't do any function calls)
39 */
40static inline struct function_ctx *
41func_ctx(struct lp_exec_mask *mask)
42{
43   assert(mask->function_stack_size > 0);
44   assert(mask->function_stack_size <= LP_MAX_NUM_FUNCS);
45   return &mask->function_stack[mask->function_stack_size - 1];
46}
47
48/*
49 * Returns true if we're in a loop.
50 * It's global, meaning that it returns true even if there's
51 * no loop inside the current function, but we were inside
52 * a loop inside another function, from which this one was called.
53 */
54static inline boolean
55mask_has_loop(struct lp_exec_mask *mask)
56{
57   int i;
58   for (i = mask->function_stack_size - 1; i >= 0; --i) {
59      const struct function_ctx *ctx = &mask->function_stack[i];
60      if (ctx->loop_stack_size > 0)
61         return TRUE;
62   }
63   return FALSE;
64}
65
66/*
67 * Returns true if we're inside a switch statement.
68 * It's global, meaning that it returns true even if there's
69 * no switch in the current function, but we were inside
70 * a switch inside another function, from which this one was called.
71 */
72static inline boolean
73mask_has_switch(struct lp_exec_mask *mask)
74{
75   int i;
76   for (i = mask->function_stack_size - 1; i >= 0; --i) {
77      const struct function_ctx *ctx = &mask->function_stack[i];
78      if (ctx->switch_stack_size > 0)
79         return TRUE;
80   }
81   return FALSE;
82}
83
84/*
85 * Returns true if we're inside a conditional.
86 * It's global, meaning that it returns true even if there's
87 * no conditional in the current function, but we were inside
88 * a conditional inside another function, from which this one was called.
89 */
90static inline boolean
91mask_has_cond(struct lp_exec_mask *mask)
92{
93   int i;
94   for (i = mask->function_stack_size - 1; i >= 0; --i) {
95      const struct function_ctx *ctx = &mask->function_stack[i];
96      if (ctx->cond_stack_size > 0)
97         return TRUE;
98   }
99   return FALSE;
100}
101
102void lp_exec_mask_update(struct lp_exec_mask *mask)
103{
104   LLVMBuilderRef builder = mask->bld->gallivm->builder;
105   boolean has_loop_mask = mask_has_loop(mask);
106   boolean has_cond_mask = mask_has_cond(mask);
107   boolean has_switch_mask = mask_has_switch(mask);
108   boolean has_ret_mask = mask->function_stack_size > 1 ||
109         mask->ret_in_main;
110
111   if (has_loop_mask) {
112      /*for loops we need to update the entire mask at runtime */
113      LLVMValueRef tmp;
114      assert(mask->break_mask);
115      tmp = LLVMBuildAnd(builder,
116                         mask->cont_mask,
117                         mask->break_mask,
118                         "maskcb");
119      mask->exec_mask = LLVMBuildAnd(builder,
120                                     mask->cond_mask,
121                                     tmp,
122                                     "maskfull");
123   } else
124      mask->exec_mask = mask->cond_mask;
125
126   if (has_switch_mask) {
127      mask->exec_mask = LLVMBuildAnd(builder,
128                                     mask->exec_mask,
129                                     mask->switch_mask,
130                                     "switchmask");
131   }
132
133   if (has_ret_mask) {
134      mask->exec_mask = LLVMBuildAnd(builder,
135                                     mask->exec_mask,
136                                     mask->ret_mask,
137                                     "callmask");
138   }
139
140   mask->has_mask = (has_cond_mask ||
141                     has_loop_mask ||
142                     has_switch_mask ||
143                     has_ret_mask);
144}
145
146/*
147 * Initialize a function context at the specified index.
148 */
149void
150lp_exec_mask_function_init(struct lp_exec_mask *mask, int function_idx)
151{
152   LLVMTypeRef int_type = LLVMInt32TypeInContext(mask->bld->gallivm->context);
153   LLVMBuilderRef builder = mask->bld->gallivm->builder;
154   struct function_ctx *ctx =  &mask->function_stack[function_idx];
155
156   ctx->cond_stack_size = 0;
157   ctx->loop_stack_size = 0;
158   ctx->bgnloop_stack_size = 0;
159   ctx->switch_stack_size = 0;
160
161   if (function_idx == 0) {
162      ctx->ret_mask = mask->ret_mask;
163   }
164
165   ctx->loop_limiter = lp_build_alloca(mask->bld->gallivm,
166                                       int_type, "looplimiter");
167   LLVMBuildStore(
168      builder,
169      LLVMConstInt(int_type, LP_MAX_TGSI_LOOP_ITERATIONS, false),
170      ctx->loop_limiter);
171}
172
173void lp_exec_mask_init(struct lp_exec_mask *mask, struct lp_build_context *bld)
174{
175   mask->bld = bld;
176   mask->has_mask = FALSE;
177   mask->ret_in_main = FALSE;
178   /* For the main function */
179   mask->function_stack_size = 1;
180
181   mask->int_vec_type = lp_build_int_vec_type(bld->gallivm, mask->bld->type);
182   mask->exec_mask = mask->ret_mask = mask->break_mask = mask->cont_mask =
183         mask->cond_mask = mask->switch_mask =
184         LLVMConstAllOnes(mask->int_vec_type);
185
186   mask->function_stack = CALLOC(LP_MAX_NUM_FUNCS,
187                                 sizeof(mask->function_stack[0]));
188   lp_exec_mask_function_init(mask, 0);
189}
190
191void
192lp_exec_mask_fini(struct lp_exec_mask *mask)
193{
194   FREE(mask->function_stack);
195}
196
197/* stores val into an address pointed to by dst_ptr.
198 * mask->exec_mask is used to figure out which bits of val
199 * should be stored into the address
200 * (0 means don't store this bit, 1 means do store).
201 */
202void lp_exec_mask_store(struct lp_exec_mask *mask,
203                        struct lp_build_context *bld_store,
204                        LLVMValueRef val,
205                        LLVMValueRef dst_ptr)
206{
207   LLVMBuilderRef builder = mask->bld->gallivm->builder;
208   LLVMValueRef exec_mask = mask->has_mask ? mask->exec_mask : NULL;
209
210   assert(lp_check_value(bld_store->type, val));
211   assert(LLVMGetTypeKind(LLVMTypeOf(dst_ptr)) == LLVMPointerTypeKind);
212   assert(LLVMGetElementType(LLVMTypeOf(dst_ptr)) == LLVMTypeOf(val) ||
213          LLVMGetTypeKind(LLVMGetElementType(LLVMTypeOf(dst_ptr))) == LLVMArrayTypeKind);
214
215   if (exec_mask) {
216      LLVMValueRef res, dst;
217
218      dst = LLVMBuildLoad(builder, dst_ptr, "");
219      if (bld_store->type.width < 32)
220         exec_mask = LLVMBuildTrunc(builder, exec_mask, bld_store->vec_type, "");
221      res = lp_build_select(bld_store, exec_mask, val, dst);
222      LLVMBuildStore(builder, res, dst_ptr);
223   } else
224      LLVMBuildStore(builder, val, dst_ptr);
225}
226
227void lp_exec_bgnloop_post_phi(struct lp_exec_mask *mask)
228{
229   LLVMBuilderRef builder = mask->bld->gallivm->builder;
230   struct function_ctx *ctx = func_ctx(mask);
231
232   if (ctx->loop_stack_size != ctx->bgnloop_stack_size) {
233      mask->break_mask = LLVMBuildLoad(builder, ctx->break_var, "");
234      lp_exec_mask_update(mask);
235      ctx->bgnloop_stack_size = ctx->loop_stack_size;
236   }
237}
238
239void lp_exec_bgnloop(struct lp_exec_mask *mask, bool load)
240{
241   LLVMBuilderRef builder = mask->bld->gallivm->builder;
242   struct function_ctx *ctx = func_ctx(mask);
243
244   if (ctx->loop_stack_size >= LP_MAX_TGSI_NESTING) {
245      ++ctx->loop_stack_size;
246      return;
247   }
248
249   ctx->break_type_stack[ctx->loop_stack_size + ctx->switch_stack_size] =
250      ctx->break_type;
251   ctx->break_type = LP_EXEC_MASK_BREAK_TYPE_LOOP;
252
253   ctx->loop_stack[ctx->loop_stack_size].loop_block = ctx->loop_block;
254   ctx->loop_stack[ctx->loop_stack_size].cont_mask = mask->cont_mask;
255   ctx->loop_stack[ctx->loop_stack_size].break_mask = mask->break_mask;
256   ctx->loop_stack[ctx->loop_stack_size].break_var = ctx->break_var;
257   ++ctx->loop_stack_size;
258
259   ctx->break_var = lp_build_alloca(mask->bld->gallivm, mask->int_vec_type, "");
260   LLVMBuildStore(builder, mask->break_mask, ctx->break_var);
261
262   ctx->loop_block = lp_build_insert_new_block(mask->bld->gallivm, "bgnloop");
263
264   LLVMBuildBr(builder, ctx->loop_block);
265   LLVMPositionBuilderAtEnd(builder, ctx->loop_block);
266
267   if (load) {
268      lp_exec_bgnloop_post_phi(mask);
269   }
270}
271
272void lp_exec_endloop(struct gallivm_state *gallivm,
273                     struct lp_exec_mask *mask)
274{
275   LLVMBuilderRef builder = mask->bld->gallivm->builder;
276   struct function_ctx *ctx = func_ctx(mask);
277   LLVMBasicBlockRef endloop;
278   LLVMTypeRef int_type = LLVMInt32TypeInContext(mask->bld->gallivm->context);
279   LLVMTypeRef reg_type = LLVMIntTypeInContext(gallivm->context,
280                                               mask->bld->type.width *
281                                               mask->bld->type.length);
282   LLVMValueRef i1cond, i2cond, icond, limiter;
283
284   assert(mask->break_mask);
285
286   assert(ctx->loop_stack_size);
287   if (ctx->loop_stack_size > LP_MAX_TGSI_NESTING) {
288      --ctx->loop_stack_size;
289      --ctx->bgnloop_stack_size;
290      return;
291   }
292
293   /*
294    * Restore the cont_mask, but don't pop
295    */
296   mask->cont_mask = ctx->loop_stack[ctx->loop_stack_size - 1].cont_mask;
297   lp_exec_mask_update(mask);
298
299   /*
300    * Unlike the continue mask, the break_mask must be preserved across loop
301    * iterations
302    */
303   LLVMBuildStore(builder, mask->break_mask, ctx->break_var);
304
305   /* Decrement the loop limiter */
306   limiter = LLVMBuildLoad(builder, ctx->loop_limiter, "");
307
308   limiter = LLVMBuildSub(
309      builder,
310      limiter,
311      LLVMConstInt(int_type, 1, false),
312      "");
313
314   LLVMBuildStore(builder, limiter, ctx->loop_limiter);
315
316   /* i1cond = (mask != 0) */
317   i1cond = LLVMBuildICmp(
318      builder,
319      LLVMIntNE,
320      LLVMBuildBitCast(builder, mask->exec_mask, reg_type, ""),
321      LLVMConstNull(reg_type), "i1cond");
322
323   /* i2cond = (looplimiter > 0) */
324   i2cond = LLVMBuildICmp(
325      builder,
326      LLVMIntSGT,
327      limiter,
328      LLVMConstNull(int_type), "i2cond");
329
330   /* if( i1cond && i2cond ) */
331   icond = LLVMBuildAnd(builder, i1cond, i2cond, "");
332
333   endloop = lp_build_insert_new_block(mask->bld->gallivm, "endloop");
334
335   LLVMBuildCondBr(builder,
336                   icond, ctx->loop_block, endloop);
337
338   LLVMPositionBuilderAtEnd(builder, endloop);
339
340   assert(ctx->loop_stack_size);
341   --ctx->loop_stack_size;
342   --ctx->bgnloop_stack_size;
343   mask->cont_mask = ctx->loop_stack[ctx->loop_stack_size].cont_mask;
344   mask->break_mask = ctx->loop_stack[ctx->loop_stack_size].break_mask;
345   ctx->loop_block = ctx->loop_stack[ctx->loop_stack_size].loop_block;
346   ctx->break_var = ctx->loop_stack[ctx->loop_stack_size].break_var;
347   ctx->break_type = ctx->break_type_stack[ctx->loop_stack_size +
348         ctx->switch_stack_size];
349
350   lp_exec_mask_update(mask);
351}
352
353void lp_exec_mask_cond_push(struct lp_exec_mask *mask,
354                            LLVMValueRef val)
355{
356   LLVMBuilderRef builder = mask->bld->gallivm->builder;
357   struct function_ctx *ctx = func_ctx(mask);
358
359   if (ctx->cond_stack_size >= LP_MAX_TGSI_NESTING) {
360      ctx->cond_stack_size++;
361      return;
362   }
363   if (ctx->cond_stack_size == 0 && mask->function_stack_size == 1) {
364      assert(mask->cond_mask == LLVMConstAllOnes(mask->int_vec_type));
365   }
366   ctx->cond_stack[ctx->cond_stack_size++] = mask->cond_mask;
367   assert(LLVMTypeOf(val) == mask->int_vec_type);
368   mask->cond_mask = LLVMBuildAnd(builder,
369                                  mask->cond_mask,
370                                  val,
371                                  "");
372   lp_exec_mask_update(mask);
373}
374
375void lp_exec_mask_cond_invert(struct lp_exec_mask *mask)
376{
377   LLVMBuilderRef builder = mask->bld->gallivm->builder;
378   struct function_ctx *ctx = func_ctx(mask);
379   LLVMValueRef prev_mask;
380   LLVMValueRef inv_mask;
381
382   assert(ctx->cond_stack_size);
383   if (ctx->cond_stack_size >= LP_MAX_TGSI_NESTING)
384      return;
385   prev_mask = ctx->cond_stack[ctx->cond_stack_size - 1];
386   if (ctx->cond_stack_size == 1 && mask->function_stack_size == 1) {
387      assert(prev_mask == LLVMConstAllOnes(mask->int_vec_type));
388   }
389
390   inv_mask = LLVMBuildNot(builder, mask->cond_mask, "");
391
392   mask->cond_mask = LLVMBuildAnd(builder,
393                                  inv_mask,
394                                  prev_mask, "");
395   lp_exec_mask_update(mask);
396}
397
398void lp_exec_mask_cond_pop(struct lp_exec_mask *mask)
399{
400   struct function_ctx *ctx = func_ctx(mask);
401   assert(ctx->cond_stack_size);
402   --ctx->cond_stack_size;
403   if (ctx->cond_stack_size >= LP_MAX_TGSI_NESTING)
404      return;
405   mask->cond_mask = ctx->cond_stack[ctx->cond_stack_size];
406   lp_exec_mask_update(mask);
407}
408
409
410void lp_exec_continue(struct lp_exec_mask *mask)
411{
412   LLVMBuilderRef builder = mask->bld->gallivm->builder;
413   LLVMValueRef exec_mask = LLVMBuildNot(builder,
414                                         mask->exec_mask,
415                                         "");
416
417   mask->cont_mask = LLVMBuildAnd(builder,
418                                  mask->cont_mask,
419                                  exec_mask, "");
420
421   lp_exec_mask_update(mask);
422}
423
424void lp_exec_break(struct lp_exec_mask *mask, int *pc,
425                   bool break_always)
426{
427   LLVMBuilderRef builder = mask->bld->gallivm->builder;
428   struct function_ctx *ctx = func_ctx(mask);
429
430   if (ctx->break_type == LP_EXEC_MASK_BREAK_TYPE_LOOP) {
431      LLVMValueRef exec_mask = LLVMBuildNot(builder,
432                                            mask->exec_mask,
433                                            "break");
434
435      mask->break_mask = LLVMBuildAnd(builder,
436                                      mask->break_mask,
437                                      exec_mask, "break_full");
438   }
439   else {
440      if (ctx->switch_in_default) {
441         /*
442          * stop default execution but only if this is an unconditional switch.
443          * (The condition here is not perfect since dead code after break is
444          * allowed but should be sufficient since false negatives are just
445          * unoptimized - so we don't have to pre-evaluate that).
446          */
447         if(break_always && ctx->switch_pc) {
448            if (pc)
449               *pc = ctx->switch_pc;
450            return;
451         }
452      }
453
454      if (break_always) {
455         mask->switch_mask = LLVMConstNull(mask->bld->int_vec_type);
456      }
457      else {
458         LLVMValueRef exec_mask = LLVMBuildNot(builder,
459                                               mask->exec_mask,
460                                               "break");
461         mask->switch_mask = LLVMBuildAnd(builder,
462                                          mask->switch_mask,
463                                          exec_mask, "break_switch");
464      }
465   }
466
467   lp_exec_mask_update(mask);
468}
469