← Back to branch summary

~mmach/netext73/mesa-haswell

« back to all changes in this revision

Viewing changes to src/gallium/auxiliary/gallivm/lp_bld_flow.c

  • Committer: mmach
  • Date: 2022-09-22 19:56:13 UTC
  • Revision ID: netbit73@gmail.com-20220922195613-wtik9mmy20tmor0i
2022-09-22 21:17:09

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/gallium/auxiliary/gallivm/lp_bld_flow.c
1
 
/**************************************************************************
2
 
 *
3
 
 * Copyright 2009 VMware, Inc.
4
 
 * All Rights Reserved.
5
 
 *
6
 
 * Permission is hereby granted, free of charge, to any person obtaining a
7
 
 * copy of this software and associated documentation files (the
8
 
 * "Software"), to deal in the Software without restriction, including
9
 
 * without limitation the rights to use, copy, modify, merge, publish,
10
 
 * distribute, sub license, and/or sell copies of the Software, and to
11
 
 * permit persons to whom the Software is furnished to do so, subject to
12
 
 * the following conditions:
13
 
 *
14
 
 * The above copyright notice and this permission notice (including the
15
 
 * next paragraph) shall be included in all copies or substantial portions
16
 
 * of the Software.
17
 
 *
18
 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19
 
 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20
 
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
21
 
 * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
22
 
 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
23
 
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
24
 
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
25
 
 *
26
 
 **************************************************************************/
27
 
 
28
 
/**
29
 
 * LLVM control flow build helpers.
30
 
 *
31
 
 * @author Jose Fonseca <jfonseca@vmware.com>
32
 
 */
33
 
 
34
 
#include "util/u_debug.h"
35
 
#include "util/u_memory.h"
36
 
 
37
 
#include "lp_bld_init.h"
38
 
#include "lp_bld_type.h"
39
 
#include "lp_bld_flow.h"
40
 
 
41
 
 
42
 
/**
43
 
 * Insert a new block, right where builder is pointing to.
44
 
 *
45
 
 * This is useful important not only for aesthetic reasons, but also for
46
 
 * performance reasons, as frequently run blocks should be laid out next to
47
 
 * each other and fall-throughs maximized.
48
 
 *
49
 
 * See also llvm/lib/Transforms/Scalar/BasicBlockPlacement.cpp.
50
 
 *
51
 
 * Note: this function has no dependencies on the flow code and could
52
 
 * be used elsewhere.
53
 
 */
54
 
LLVMBasicBlockRef
55
 
lp_build_insert_new_block(struct gallivm_state *gallivm, const char *name)
56
 
{
57
 
   LLVMBasicBlockRef current_block;
58
 
   LLVMBasicBlockRef next_block;
59
 
   LLVMBasicBlockRef new_block;
60
 
 
61
 
   /* get current basic block */
62
 
   current_block = LLVMGetInsertBlock(gallivm->builder);
63
 
 
64
 
   /* check if there's another block after this one */
65
 
   next_block = LLVMGetNextBasicBlock(current_block);
66
 
   if (next_block) {
67
 
      /* insert the new block before the next block */
68
 
      new_block = LLVMInsertBasicBlockInContext(gallivm->context, next_block, name);
69
 
   }
70
 
   else {
71
 
      /* append new block after current block */
72
 
      LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
73
 
      new_block = LLVMAppendBasicBlockInContext(gallivm->context, function, name);
74
 
   }
75
 
 
76
 
   return new_block;
77
 
}
78
 
 
79
 
 
80
 
/**
81
 
 * Begin a "skip" block.  Inside this block we can test a condition and
82
 
 * skip to the end of the block if the condition is false.
83
 
 */
84
 
void
85
 
lp_build_flow_skip_begin(struct lp_build_skip_context *skip,
86
 
                         struct gallivm_state *gallivm)
87
 
{
88
 
   skip->gallivm = gallivm;
89
 
   /* create new basic block */
90
 
   skip->block = lp_build_insert_new_block(gallivm, "skip");
91
 
}
92
 
 
93
 
 
94
 
/**
95
 
 * Insert code to test a condition and branch to the end of the current
96
 
 * skip block if the condition is true.
97
 
 */
98
 
void
99
 
lp_build_flow_skip_cond_break(struct lp_build_skip_context *skip,
100
 
                              LLVMValueRef cond)
101
 
{
102
 
   LLVMBasicBlockRef new_block;
103
 
 
104
 
   new_block = lp_build_insert_new_block(skip->gallivm, "");
105
 
 
106
 
   /* if cond is true, goto skip->block, else goto new_block */
107
 
   LLVMBuildCondBr(skip->gallivm->builder, cond, skip->block, new_block);
108
 
 
109
 
   LLVMPositionBuilderAtEnd(skip->gallivm->builder, new_block);
110
 
}
111
 
 
112
 
 
113
 
void
114
 
lp_build_flow_skip_end(struct lp_build_skip_context *skip)
115
 
{
116
 
   /* goto block */
117
 
   LLVMBuildBr(skip->gallivm->builder, skip->block);
118
 
   LLVMPositionBuilderAtEnd(skip->gallivm->builder, skip->block);
119
 
}
120
 
 
121
 
 
122
 
/**
123
 
 * Check if the mask predicate is zero.  If so, jump to the end of the block.
124
 
 */
125
 
void
126
 
lp_build_mask_check(struct lp_build_mask_context *mask)
127
 
{
128
 
   LLVMBuilderRef builder = mask->skip.gallivm->builder;
129
 
   LLVMValueRef value;
130
 
   LLVMValueRef cond;
131
 
 
132
 
   value = lp_build_mask_value(mask);
133
 
 
134
 
   /*
135
 
    * XXX this doesn't quite generate the most efficient code possible, if
136
 
    * the masks are vectors which have all bits set to the same value
137
 
    * in each element.
138
 
    * movmskps/pmovmskb would be more efficient to get the required value
139
 
    * into ordinary reg (certainly with 8 floats).
140
 
    * Not sure if llvm could figure that out on its own.
141
 
    */
142
 
 
143
 
   /* cond = (mask == 0) */
144
 
   cond = LLVMBuildICmp(builder,
145
 
                        LLVMIntEQ,
146
 
                        LLVMBuildBitCast(builder, value, mask->reg_type, ""),
147
 
                        LLVMConstNull(mask->reg_type),
148
 
                        "");
149
 
 
150
 
   /* if cond, goto end of block */
151
 
   lp_build_flow_skip_cond_break(&mask->skip, cond);
152
 
}
153
 
 
154
 
 
155
 
/**
156
 
 * Begin a section of code which is predicated on a mask.
157
 
 * \param mask  the mask context, initialized here
158
 
 * \param flow  the flow context
159
 
 * \param type  the type of the mask
160
 
 * \param value  storage for the mask
161
 
 */
162
 
void
163
 
lp_build_mask_begin(struct lp_build_mask_context *mask,
164
 
                    struct gallivm_state *gallivm,
165
 
                    struct lp_type type,
166
 
                    LLVMValueRef value)
167
 
{
168
 
   memset(mask, 0, sizeof *mask);
169
 
 
170
 
   mask->reg_type = LLVMIntTypeInContext(gallivm->context, type.width * type.length);
171
 
   mask->var = lp_build_alloca(gallivm,
172
 
                               lp_build_int_vec_type(gallivm, type),
173
 
                               "execution_mask");
174
 
 
175
 
   LLVMBuildStore(gallivm->builder, value, mask->var);
176
 
 
177
 
   lp_build_flow_skip_begin(&mask->skip, gallivm);
178
 
}
179
 
 
180
 
 
181
 
LLVMValueRef
182
 
lp_build_mask_value(struct lp_build_mask_context *mask)
183
 
{
184
 
   return LLVMBuildLoad(mask->skip.gallivm->builder, mask->var, "");
185
 
}
186
 
 
187
 
 
188
 
/**
189
 
 * Update boolean mask with given value (bitwise AND).
190
 
 * Typically used to update the quad's pixel alive/killed mask
191
 
 * after depth testing, alpha testing, TGSI_OPCODE_KILL_IF, etc.
192
 
 */
193
 
void
194
 
lp_build_mask_update(struct lp_build_mask_context *mask,
195
 
                     LLVMValueRef value)
196
 
{
197
 
   value = LLVMBuildAnd(mask->skip.gallivm->builder,
198
 
                        lp_build_mask_value(mask),
199
 
                        value, "");
200
 
   LLVMBuildStore(mask->skip.gallivm->builder, value, mask->var);
201
 
}
202
 
 
203
 
/*
204
 
 * Update boolean mask with given value.
205
 
 * Used for per-sample shading to force per-sample execution masks.
206
 
 */
207
 
void
208
 
lp_build_mask_force(struct lp_build_mask_context *mask,
209
 
                    LLVMValueRef value)
210
 
{
211
 
   LLVMBuildStore(mask->skip.gallivm->builder, value, mask->var);
212
 
}
213
 
 
214
 
/**
215
 
 * End section of code which is predicated on a mask.
216
 
 */
217
 
LLVMValueRef
218
 
lp_build_mask_end(struct lp_build_mask_context *mask)
219
 
{
220
 
   lp_build_flow_skip_end(&mask->skip);
221
 
   return lp_build_mask_value(mask);
222
 
}
223
 
 
224
 
 
225
 
 
226
 
void
227
 
lp_build_loop_begin(struct lp_build_loop_state *state,
228
 
                    struct gallivm_state *gallivm,
229
 
                    LLVMValueRef start)
230
 
                    
231
 
{
232
 
   LLVMBuilderRef builder = gallivm->builder;
233
 
 
234
 
   state->block = lp_build_insert_new_block(gallivm, "loop_begin");
235
 
 
236
 
   state->counter_var = lp_build_alloca(gallivm, LLVMTypeOf(start), "loop_counter");
237
 
   state->gallivm = gallivm;
238
 
 
239
 
   LLVMBuildStore(builder, start, state->counter_var);
240
 
 
241
 
   LLVMBuildBr(builder, state->block);
242
 
 
243
 
   LLVMPositionBuilderAtEnd(builder, state->block);
244
 
 
245
 
   state->counter = LLVMBuildLoad(builder, state->counter_var, "");
246
 
}
247
 
 
248
 
 
249
 
void
250
 
lp_build_loop_end_cond(struct lp_build_loop_state *state,
251
 
                       LLVMValueRef end,
252
 
                       LLVMValueRef step,
253
 
                       LLVMIntPredicate llvm_cond)
254
 
{
255
 
   LLVMBuilderRef builder = state->gallivm->builder;
256
 
   LLVMValueRef next;
257
 
   LLVMValueRef cond;
258
 
   LLVMBasicBlockRef after_block;
259
 
 
260
 
   if (!step)
261
 
      step = LLVMConstInt(LLVMTypeOf(end), 1, 0);
262
 
 
263
 
   next = LLVMBuildAdd(builder, state->counter, step, "");
264
 
 
265
 
   LLVMBuildStore(builder, next, state->counter_var);
266
 
 
267
 
   cond = LLVMBuildICmp(builder, llvm_cond, next, end, "");
268
 
 
269
 
   after_block = lp_build_insert_new_block(state->gallivm, "loop_end");
270
 
 
271
 
   LLVMBuildCondBr(builder, cond, after_block, state->block);
272
 
 
273
 
   LLVMPositionBuilderAtEnd(builder, after_block);
274
 
 
275
 
   state->counter = LLVMBuildLoad(builder, state->counter_var, "");
276
 
}
277
 
 
278
 
void
279
 
lp_build_loop_force_set_counter(struct lp_build_loop_state *state,
280
 
                          LLVMValueRef end)
281
 
{
282
 
   LLVMBuilderRef builder = state->gallivm->builder;
283
 
   LLVMBuildStore(builder, end, state->counter_var);
284
 
}
285
 
 
286
 
void
287
 
lp_build_loop_force_reload_counter(struct lp_build_loop_state *state)
288
 
{
289
 
   LLVMBuilderRef builder = state->gallivm->builder;
290
 
   state->counter = LLVMBuildLoad(builder, state->counter_var, "");
291
 
}
292
 
 
293
 
void
294
 
lp_build_loop_end(struct lp_build_loop_state *state,
295
 
                  LLVMValueRef end,
296
 
                  LLVMValueRef step)
297
 
{
298
 
   lp_build_loop_end_cond(state, end, step, LLVMIntNE);
299
 
}
300
 
 
301
 
/**
302
 
 * Creates a c-style for loop,
303
 
 * contrasts lp_build_loop as this checks condition on entry
304
 
 * e.g. for(i = start; i cmp_op end; i += step)
305
 
 * \param state      the for loop state, initialized here
306
 
 * \param gallivm    the gallivm state
307
 
 * \param start      starting value of iterator
308
 
 * \param cmp_op     comparison operator used for comparing current value with end value
309
 
 * \param end        value used to compare against iterator
310
 
 * \param step       value added to iterator at end of each loop
311
 
 */
312
 
void
313
 
lp_build_for_loop_begin(struct lp_build_for_loop_state *state,
314
 
                        struct gallivm_state *gallivm,
315
 
                        LLVMValueRef start,
316
 
                        LLVMIntPredicate cmp_op,
317
 
                        LLVMValueRef end,
318
 
                        LLVMValueRef step)
319
 
{
320
 
   LLVMBuilderRef builder = gallivm->builder;
321
 
 
322
 
   assert(LLVMTypeOf(start) == LLVMTypeOf(end));
323
 
   assert(LLVMTypeOf(start) == LLVMTypeOf(step));
324
 
 
325
 
   state->begin = lp_build_insert_new_block(gallivm, "loop_begin");
326
 
   state->step  = step;
327
 
   state->counter_var = lp_build_alloca(gallivm, LLVMTypeOf(start), "loop_counter");
328
 
   state->gallivm = gallivm;
329
 
   state->cond = cmp_op;
330
 
   state->end = end;
331
 
 
332
 
   LLVMBuildStore(builder, start, state->counter_var);
333
 
   LLVMBuildBr(builder, state->begin);
334
 
 
335
 
   LLVMPositionBuilderAtEnd(builder, state->begin);
336
 
   state->counter = LLVMBuildLoad(builder, state->counter_var, "");
337
 
 
338
 
   state->body = lp_build_insert_new_block(gallivm, "loop_body");
339
 
   LLVMPositionBuilderAtEnd(builder, state->body);
340
 
}
341
 
 
342
 
/**
343
 
 * End the for loop.
344
 
 */
345
 
void
346
 
lp_build_for_loop_end(struct lp_build_for_loop_state *state)
347
 
{
348
 
   LLVMValueRef next, cond;
349
 
   LLVMBuilderRef builder = state->gallivm->builder;
350
 
 
351
 
   next = LLVMBuildAdd(builder, state->counter, state->step, "");
352
 
   LLVMBuildStore(builder, next, state->counter_var);
353
 
   LLVMBuildBr(builder, state->begin);
354
 
 
355
 
   state->exit = lp_build_insert_new_block(state->gallivm, "loop_exit");
356
 
 
357
 
   /*
358
 
    * We build the comparison for the begin block here,
359
 
    * if we build it earlier the output llvm ir is not human readable
360
 
    * as the code produced is not in the standard begin -> body -> end order.
361
 
    */
362
 
   LLVMPositionBuilderAtEnd(builder, state->begin);
363
 
   cond = LLVMBuildICmp(builder, state->cond, state->counter, state->end, "");
364
 
   LLVMBuildCondBr(builder, cond, state->body, state->exit);
365
 
 
366
 
   LLVMPositionBuilderAtEnd(builder, state->exit);
367
 
}
368
 
 
369
 
 
370
 
/*
371
 
  Example of if/then/else building:
372
 
 
373
 
     int x;
374
 
     if (cond) {
375
 
        x = 1 + 2;
376
 
     }
377
 
     else {
378
 
        x = 2 + 3;
379
 
     }
380
 
 
381
 
  Is built with:
382
 
 
383
 
     // x needs an alloca variable
384
 
     x = lp_build_alloca(builder, type, "x");
385
 
 
386
 
 
387
 
     lp_build_if(ctx, builder, cond);
388
 
        LLVMBuildStore(LLVMBuildAdd(1, 2), x);
389
 
     lp_build_else(ctx);
390
 
        LLVMBuildStore(LLVMBuildAdd(2, 3). x);
391
 
     lp_build_endif(ctx);
392
 
 
393
 
 */
394
 
 
395
 
 
396
 
 
397
 
/**
398
 
 * Begin an if/else/endif construct.
399
 
 */
400
 
void
401
 
lp_build_if(struct lp_build_if_state *ifthen,
402
 
            struct gallivm_state *gallivm,
403
 
            LLVMValueRef condition)
404
 
{
405
 
   LLVMBasicBlockRef block = LLVMGetInsertBlock(gallivm->builder);
406
 
 
407
 
   memset(ifthen, 0, sizeof *ifthen);
408
 
   ifthen->gallivm = gallivm;
409
 
   ifthen->condition = condition;
410
 
   ifthen->entry_block = block;
411
 
 
412
 
   /* create endif/merge basic block for the phi functions */
413
 
   ifthen->merge_block = lp_build_insert_new_block(gallivm, "endif-block");
414
 
 
415
 
   /* create/insert true_block before merge_block */
416
 
   ifthen->true_block =
417
 
      LLVMInsertBasicBlockInContext(gallivm->context,
418
 
                                    ifthen->merge_block,
419
 
                                    "if-true-block");
420
 
 
421
 
   /* successive code goes into the true block */
422
 
   LLVMPositionBuilderAtEnd(gallivm->builder, ifthen->true_block);
423
 
}
424
 
 
425
 
 
426
 
/**
427
 
 * Begin else-part of a conditional
428
 
 */
429
 
void
430
 
lp_build_else(struct lp_build_if_state *ifthen)
431
 
{
432
 
   LLVMBuilderRef builder = ifthen->gallivm->builder;
433
 
 
434
 
   /* Append an unconditional Br(anch) instruction on the true_block */
435
 
   LLVMBuildBr(builder, ifthen->merge_block);
436
 
 
437
 
   /* create/insert false_block before the merge block */
438
 
   ifthen->false_block =
439
 
      LLVMInsertBasicBlockInContext(ifthen->gallivm->context,
440
 
                                    ifthen->merge_block,
441
 
                                    "if-false-block");
442
 
 
443
 
   /* successive code goes into the else block */
444
 
   LLVMPositionBuilderAtEnd(builder, ifthen->false_block);
445
 
}
446
 
 
447
 
 
448
 
/**
449
 
 * End a conditional.
450
 
 */
451
 
void
452
 
lp_build_endif(struct lp_build_if_state *ifthen)
453
 
{
454
 
   LLVMBuilderRef builder = ifthen->gallivm->builder;
455
 
 
456
 
   /* Insert branch to the merge block from current block */
457
 
   LLVMBuildBr(builder, ifthen->merge_block);
458
 
 
459
 
   /*
460
 
    * Now patch in the various branch instructions.
461
 
    */
462
 
 
463
 
   /* Insert the conditional branch instruction at the end of entry_block */
464
 
   LLVMPositionBuilderAtEnd(builder, ifthen->entry_block);
465
 
   if (ifthen->false_block) {
466
 
      /* we have an else clause */
467
 
      LLVMBuildCondBr(builder, ifthen->condition,
468
 
                      ifthen->true_block, ifthen->false_block);
469
 
   }
470
 
   else {
471
 
      /* no else clause */
472
 
      LLVMBuildCondBr(builder, ifthen->condition,
473
 
                      ifthen->true_block, ifthen->merge_block);
474
 
   }
475
 
 
476
 
   /* Resume building code at end of the ifthen->merge_block */
477
 
   LLVMPositionBuilderAtEnd(builder, ifthen->merge_block);
478
 
}
479
 
 
480
 
 
481
 
static LLVMBuilderRef
482
 
create_builder_at_entry(struct gallivm_state *gallivm)
483
 
{
484
 
   LLVMBuilderRef builder = gallivm->builder;
485
 
   LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder);
486
 
   LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
487
 
   LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function);
488
 
   LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block);
489
 
   LLVMBuilderRef first_builder = LLVMCreateBuilderInContext(gallivm->context);
490
 
 
491
 
   if (first_instr) {
492
 
      LLVMPositionBuilderBefore(first_builder, first_instr);
493
 
   } else {
494
 
      LLVMPositionBuilderAtEnd(first_builder, first_block);
495
 
   }
496
 
 
497
 
   return first_builder;
498
 
}
499
 
 
500
 
 
501
 
/**
502
 
 * Allocate a scalar (or vector) variable.
503
 
 *
504
 
 * Although not strictly part of control flow, control flow has deep impact in
505
 
 * how variables should be allocated.
506
 
 *
507
 
 * The mem2reg optimization pass is the recommended way to dealing with mutable
508
 
 * variables, and SSA. It looks for allocas and if it can handle them, it
509
 
 * promotes them, but only looks for alloca instructions in the entry block of
510
 
 * the function. Being in the entry block guarantees that the alloca is only
511
 
 * executed once, which makes analysis simpler.
512
 
 *
513
 
 * See also:
514
 
 * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory
515
 
 */
516
 
LLVMValueRef
517
 
lp_build_alloca(struct gallivm_state *gallivm,
518
 
                LLVMTypeRef type,
519
 
                const char *name)
520
 
{
521
 
   LLVMBuilderRef builder = gallivm->builder;
522
 
   LLVMBuilderRef first_builder = create_builder_at_entry(gallivm);
523
 
   LLVMValueRef res;
524
 
 
525
 
   res = LLVMBuildAlloca(first_builder, type, name);
526
 
   LLVMBuildStore(builder, LLVMConstNull(type), res);
527
 
 
528
 
   LLVMDisposeBuilder(first_builder);
529
 
 
530
 
   return res;
531
 
}
532
 
 
533
 
 
534
 
/**
535
 
 * Like lp_build_alloca, but do not zero-initialize the variable.
536
 
 */
537
 
LLVMValueRef
538
 
lp_build_alloca_undef(struct gallivm_state *gallivm,
539
 
                      LLVMTypeRef type,
540
 
                      const char *name)
541
 
{
542
 
   LLVMBuilderRef first_builder = create_builder_at_entry(gallivm);
543
 
   LLVMValueRef res;
544
 
 
545
 
   res = LLVMBuildAlloca(first_builder, type, name);
546
 
 
547
 
   LLVMDisposeBuilder(first_builder);
548
 
 
549
 
   return res;
550
 
}
551
 
 
552
 
 
553
 
/**
554
 
 * Allocate an array of scalars/vectors.
555
 
 *
556
 
 * mem2reg pass is not capable of promoting structs or arrays to registers, but
557
 
 * we still put it in the first block anyway as failure to put allocas in the
558
 
 * first block may prevent the X86 backend from successfully align the stack as
559
 
 * required.
560
 
 *
561
 
 * Also the scalarrepl pass is supposedly more powerful and can promote
562
 
 * arrays in many cases.
563
 
 *
564
 
 * See also:
565
 
 * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory
566
 
 */
567
 
LLVMValueRef
568
 
lp_build_array_alloca(struct gallivm_state *gallivm,
569
 
                      LLVMTypeRef type,
570
 
                      LLVMValueRef count,
571
 
                      const char *name)
572
 
{
573
 
   LLVMBuilderRef first_builder = create_builder_at_entry(gallivm);
574
 
   LLVMValueRef res;
575
 
 
576
 
   res = LLVMBuildArrayAlloca(first_builder, type, count, name);
577
 
 
578
 
   LLVMDisposeBuilder(first_builder);
579
 
 
580
 
   return res;
581
 
}