gallivm: Comment lp_build_insert_new_block().
[mesa.git] / 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_type.h"
38 #include "lp_bld_flow.h"
39
40
41 /**
42 * Insert a new block, right where builder is pointing to.
43 *
44 * This is useful important not only for aesthetic reasons, but also for
45 * performance reasons, as frequently run blocks should be laid out next to
46 * each other and fall-throughs maximized.
47 *
48 * See also llvm/lib/Transforms/Scalar/BasicBlockPlacement.cpp.
49 *
50 * Note: this function has no dependencies on the flow code and could
51 * be used elsewhere.
52 */
53 LLVMBasicBlockRef
54 lp_build_insert_new_block(LLVMBuilderRef builder, const char *name)
55 {
56 LLVMBasicBlockRef current_block;
57 LLVMBasicBlockRef next_block;
58 LLVMBasicBlockRef new_block;
59
60 /* get current basic block */
61 current_block = LLVMGetInsertBlock(builder);
62
63 /* check if there's another block after this one */
64 next_block = LLVMGetNextBasicBlock(current_block);
65 if (next_block) {
66 /* insert the new block before the next block */
67 new_block = LLVMInsertBasicBlock(next_block, name);
68 }
69 else {
70 /* append new block after current block */
71 LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
72 new_block = LLVMAppendBasicBlock(function, name);
73 }
74
75 return new_block;
76 }
77
78
79 /**
80 * Begin a "skip" block. Inside this block we can test a condition and
81 * skip to the end of the block if the condition is false.
82 */
83 void
84 lp_build_flow_skip_begin(struct lp_build_skip_context *skip,
85 LLVMBuilderRef builder)
86 {
87 skip->builder = builder;
88
89 /* create new basic block */
90 skip->block = lp_build_insert_new_block(skip->builder, "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->builder, "");
105
106 /* if cond is true, goto skip->block, else goto new_block */
107 LLVMBuildCondBr(skip->builder, cond, skip->block, new_block);
108
109 LLVMPositionBuilderAtEnd(skip->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->builder, skip->block);
118 LLVMPositionBuilderAtEnd(skip->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.builder;
129 LLVMValueRef value;
130 LLVMValueRef cond;
131
132 value = lp_build_mask_value(mask);
133
134 /* cond = (mask == 0) */
135 cond = LLVMBuildICmp(builder,
136 LLVMIntEQ,
137 LLVMBuildBitCast(builder, value, mask->reg_type, ""),
138 LLVMConstNull(mask->reg_type),
139 "");
140
141 /* if cond, goto end of block */
142 lp_build_flow_skip_cond_break(&mask->skip, cond);
143 }
144
145
146 /**
147 * Begin a section of code which is predicated on a mask.
148 * \param mask the mask context, initialized here
149 * \param flow the flow context
150 * \param type the type of the mask
151 * \param value storage for the mask
152 */
153 void
154 lp_build_mask_begin(struct lp_build_mask_context *mask,
155 LLVMBuilderRef builder,
156 struct lp_type type,
157 LLVMValueRef value)
158 {
159 memset(mask, 0, sizeof *mask);
160
161 mask->reg_type = LLVMIntType(type.width * type.length);
162 mask->var = lp_build_alloca(builder,
163 lp_build_int_vec_type(type),
164 "execution_mask");
165
166 LLVMBuildStore(builder, value, mask->var);
167
168 lp_build_flow_skip_begin(&mask->skip, builder);
169 }
170
171
172 LLVMValueRef
173 lp_build_mask_value(struct lp_build_mask_context *mask)
174 {
175 return LLVMBuildLoad(mask->skip.builder, mask->var, "");
176 }
177
178
179 /**
180 * Update boolean mask with given value (bitwise AND).
181 * Typically used to update the quad's pixel alive/killed mask
182 * after depth testing, alpha testing, TGSI_OPCODE_KIL, etc.
183 */
184 void
185 lp_build_mask_update(struct lp_build_mask_context *mask,
186 LLVMValueRef value)
187 {
188 value = LLVMBuildAnd(mask->skip.builder,
189 lp_build_mask_value(mask),
190 value, "");
191 LLVMBuildStore(mask->skip.builder, value, mask->var);
192 }
193
194
195 /**
196 * End section of code which is predicated on a mask.
197 */
198 LLVMValueRef
199 lp_build_mask_end(struct lp_build_mask_context *mask)
200 {
201 lp_build_flow_skip_end(&mask->skip);
202 return lp_build_mask_value(mask);
203 }
204
205
206
207 void
208 lp_build_loop_begin(LLVMBuilderRef builder,
209 LLVMValueRef start,
210 struct lp_build_loop_state *state)
211 {
212 state->block = lp_build_insert_new_block(builder, "loop_begin");
213
214 state->counter_var = lp_build_alloca(builder, LLVMTypeOf(start), "loop_counter");
215
216 LLVMBuildStore(builder, start, state->counter_var);
217
218 LLVMBuildBr(builder, state->block);
219
220 LLVMPositionBuilderAtEnd(builder, state->block);
221
222 state->counter = LLVMBuildLoad(builder, state->counter_var, "");
223 }
224
225
226 void
227 lp_build_loop_end_cond(LLVMBuilderRef builder,
228 LLVMValueRef end,
229 LLVMValueRef step,
230 LLVMIntPredicate llvm_cond,
231 struct lp_build_loop_state *state)
232 {
233 LLVMValueRef next;
234 LLVMValueRef cond;
235 LLVMBasicBlockRef after_block;
236
237 if (!step)
238 step = LLVMConstInt(LLVMTypeOf(end), 1, 0);
239
240 next = LLVMBuildAdd(builder, state->counter, step, "");
241
242 LLVMBuildStore(builder, next, state->counter_var);
243
244 cond = LLVMBuildICmp(builder, llvm_cond, next, end, "");
245
246 after_block = lp_build_insert_new_block(builder, "loop_end");
247
248 LLVMBuildCondBr(builder, cond, after_block, state->block);
249
250 LLVMPositionBuilderAtEnd(builder, after_block);
251
252 state->counter = LLVMBuildLoad(builder, state->counter_var, "");
253 }
254
255
256 void
257 lp_build_loop_end(LLVMBuilderRef builder,
258 LLVMValueRef end,
259 LLVMValueRef step,
260 struct lp_build_loop_state *state)
261 {
262 lp_build_loop_end_cond(builder, end, step, LLVMIntNE, state);
263 }
264
265
266
267 /*
268 Example of if/then/else building:
269
270 int x;
271 if (cond) {
272 x = 1 + 2;
273 }
274 else {
275 x = 2 + 3;
276 }
277
278 Is built with:
279
280 // x needs an alloca variable
281 x = lp_build_alloca(builder, type, "x");
282
283
284 lp_build_if(ctx, builder, cond);
285 LLVMBuildStore(LLVMBuildAdd(1, 2), x);
286 lp_build_else(ctx);
287 LLVMBuildStore(LLVMBuildAdd(2, 3). x);
288 lp_build_endif(ctx);
289
290 */
291
292
293
294 /**
295 * Begin an if/else/endif construct.
296 */
297 void
298 lp_build_if(struct lp_build_if_state *ifthen,
299 LLVMBuilderRef builder,
300 LLVMValueRef condition)
301 {
302 LLVMBasicBlockRef block = LLVMGetInsertBlock(builder);
303
304 memset(ifthen, 0, sizeof *ifthen);
305 ifthen->builder = builder;
306 ifthen->condition = condition;
307 ifthen->entry_block = block;
308
309 /* create endif/merge basic block for the phi functions */
310 ifthen->merge_block = lp_build_insert_new_block(builder, "endif-block");
311
312 /* create/insert true_block before merge_block */
313 ifthen->true_block = LLVMInsertBasicBlock(ifthen->merge_block, "if-true-block");
314
315 /* successive code goes into the true block */
316 LLVMPositionBuilderAtEnd(builder, ifthen->true_block);
317 }
318
319
320 /**
321 * Begin else-part of a conditional
322 */
323 void
324 lp_build_else(struct lp_build_if_state *ifthen)
325 {
326 /* Append an unconditional Br(anch) instruction on the true_block */
327 LLVMBuildBr(ifthen->builder, ifthen->merge_block);
328
329 /* create/insert false_block before the merge block */
330 ifthen->false_block = LLVMInsertBasicBlock(ifthen->merge_block, "if-false-block");
331
332 /* successive code goes into the else block */
333 LLVMPositionBuilderAtEnd(ifthen->builder, ifthen->false_block);
334 }
335
336
337 /**
338 * End a conditional.
339 */
340 void
341 lp_build_endif(struct lp_build_if_state *ifthen)
342 {
343 /* Insert branch to the merge block from current block */
344 LLVMBuildBr(ifthen->builder, ifthen->merge_block);
345
346 /*
347 * Now patch in the various branch instructions.
348 */
349
350 /* Insert the conditional branch instruction at the end of entry_block */
351 LLVMPositionBuilderAtEnd(ifthen->builder, ifthen->entry_block);
352 if (ifthen->false_block) {
353 /* we have an else clause */
354 LLVMBuildCondBr(ifthen->builder, ifthen->condition,
355 ifthen->true_block, ifthen->false_block);
356 }
357 else {
358 /* no else clause */
359 LLVMBuildCondBr(ifthen->builder, ifthen->condition,
360 ifthen->true_block, ifthen->merge_block);
361 }
362
363 /* Resume building code at end of the ifthen->merge_block */
364 LLVMPositionBuilderAtEnd(ifthen->builder, ifthen->merge_block);
365 }
366
367
368 /**
369 * Allocate a scalar (or vector) variable.
370 *
371 * Although not strictly part of control flow, control flow has deep impact in
372 * how variables should be allocated.
373 *
374 * The mem2reg optimization pass is the recommended way to dealing with mutable
375 * variables, and SSA. It looks for allocas and if it can handle them, it
376 * promotes them, but only looks for alloca instructions in the entry block of
377 * the function. Being in the entry block guarantees that the alloca is only
378 * executed once, which makes analysis simpler.
379 *
380 * See also:
381 * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory
382 */
383 LLVMValueRef
384 lp_build_alloca(LLVMBuilderRef builder,
385 LLVMTypeRef type,
386 const char *name)
387 {
388 LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder);
389 LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
390 LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function);
391 LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block);
392 LLVMBuilderRef first_builder = LLVMCreateBuilder();
393 LLVMValueRef res;
394
395 if (first_instr) {
396 LLVMPositionBuilderBefore(first_builder, first_instr);
397 } else {
398 LLVMPositionBuilderAtEnd(first_builder, first_block);
399 }
400
401 res = LLVMBuildAlloca(first_builder, type, name);
402 LLVMBuildStore(builder, LLVMConstNull(type), res);
403
404 LLVMDisposeBuilder(first_builder);
405
406 return res;
407 }
408
409
410 /**
411 * Allocate an array of scalars/vectors.
412 *
413 * mem2reg pass is not capable of promoting structs or arrays to registers, but
414 * we still put it in the first block anyway as failure to put allocas in the
415 * first block may prevent the X86 backend from successfully align the stack as
416 * required.
417 *
418 * Also the scalarrepl pass is supposedly more powerful and can promote
419 * arrays in many cases.
420 *
421 * See also:
422 * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory
423 */
424 LLVMValueRef
425 lp_build_array_alloca(LLVMBuilderRef builder,
426 LLVMTypeRef type,
427 LLVMValueRef count,
428 const char *name)
429 {
430 LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder);
431 LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
432 LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function);
433 LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block);
434 LLVMBuilderRef first_builder = LLVMCreateBuilder();
435 LLVMValueRef res;
436
437 if (first_instr) {
438 LLVMPositionBuilderBefore(first_builder, first_instr);
439 } else {
440 LLVMPositionBuilderAtEnd(first_builder, first_block);
441 }
442
443 res = LLVMBuildArrayAlloca(first_builder, type, count, name);
444
445 LLVMDisposeBuilder(first_builder);
446
447 return res;
448 }