lp_bld_flow.c revision 630fa2688634365c03edf2a189cf9225899fbcc5
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 */ 54LLVMBasicBlockRef 55lp_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 */ 84void 85lp_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 */ 98void 99lp_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 113void 114lp_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 */ 125void 126lp_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 /* 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 */ 153void 154lp_build_mask_begin(struct lp_build_mask_context *mask, 155 struct gallivm_state *gallivm, 156 struct lp_type type, 157 LLVMValueRef value) 158{ 159 memset(mask, 0, sizeof *mask); 160 161 mask->reg_type = LLVMIntTypeInContext(gallivm->context, type.width * type.length); 162 mask->var = lp_build_alloca(gallivm, 163 lp_build_int_vec_type(gallivm, type), 164 "execution_mask"); 165 166 LLVMBuildStore(gallivm->builder, value, mask->var); 167 168 lp_build_flow_skip_begin(&mask->skip, gallivm); 169} 170 171 172LLVMValueRef 173lp_build_mask_value(struct lp_build_mask_context *mask) 174{ 175 return LLVMBuildLoad(mask->skip.gallivm->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 */ 184void 185lp_build_mask_update(struct lp_build_mask_context *mask, 186 LLVMValueRef value) 187{ 188 value = LLVMBuildAnd(mask->skip.gallivm->builder, 189 lp_build_mask_value(mask), 190 value, ""); 191 LLVMBuildStore(mask->skip.gallivm->builder, value, mask->var); 192} 193 194 195/** 196 * End section of code which is predicated on a mask. 197 */ 198LLVMValueRef 199lp_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 207void 208lp_build_loop_begin(struct lp_build_loop_state *state, 209 struct gallivm_state *gallivm, 210 LLVMValueRef start) 211 212{ 213 LLVMBuilderRef builder = gallivm->builder; 214 215 state->block = lp_build_insert_new_block(gallivm, "loop_begin"); 216 217 state->counter_var = lp_build_alloca(gallivm, LLVMTypeOf(start), "loop_counter"); 218 state->gallivm = gallivm; 219 220 LLVMBuildStore(builder, start, state->counter_var); 221 222 LLVMBuildBr(builder, state->block); 223 224 LLVMPositionBuilderAtEnd(builder, state->block); 225 226 state->counter = LLVMBuildLoad(builder, state->counter_var, ""); 227} 228 229 230void 231lp_build_loop_end_cond(struct lp_build_loop_state *state, 232 LLVMValueRef end, 233 LLVMValueRef step, 234 LLVMIntPredicate llvm_cond) 235{ 236 LLVMBuilderRef builder = state->gallivm->builder; 237 LLVMValueRef next; 238 LLVMValueRef cond; 239 LLVMBasicBlockRef after_block; 240 241 if (!step) 242 step = LLVMConstInt(LLVMTypeOf(end), 1, 0); 243 244 next = LLVMBuildAdd(builder, state->counter, step, ""); 245 246 LLVMBuildStore(builder, next, state->counter_var); 247 248 cond = LLVMBuildICmp(builder, llvm_cond, next, end, ""); 249 250 after_block = lp_build_insert_new_block(state->gallivm, "loop_end"); 251 252 LLVMBuildCondBr(builder, cond, after_block, state->block); 253 254 LLVMPositionBuilderAtEnd(builder, after_block); 255 256 state->counter = LLVMBuildLoad(builder, state->counter_var, ""); 257} 258 259 260void 261lp_build_loop_end(struct lp_build_loop_state *state, 262 LLVMValueRef end, 263 LLVMValueRef step) 264{ 265 lp_build_loop_end_cond(state, end, step, LLVMIntNE); 266} 267 268/** 269 * Creates a c-style for loop, 270 * contrasts lp_build_loop as this checks condition on entry 271 * e.g. for(i = start; i cmp_op end; i += step) 272 * \param state the for loop state, initialized here 273 * \param gallivm the gallivm state 274 * \param start starting value of iterator 275 * \param cmp_op comparison operator used for comparing current value with end value 276 * \param end value used to compare against iterator 277 * \param step value added to iterator at end of each loop 278 */ 279void 280lp_build_for_loop_begin(struct lp_build_for_loop_state *state, 281 struct gallivm_state *gallivm, 282 LLVMValueRef start, 283 LLVMIntPredicate cmp_op, 284 LLVMValueRef end, 285 LLVMValueRef step) 286{ 287 LLVMBuilderRef builder = gallivm->builder; 288 289 assert(LLVMTypeOf(start) == LLVMTypeOf(end)); 290 assert(LLVMTypeOf(start) == LLVMTypeOf(step)); 291 292 state->begin = lp_build_insert_new_block(gallivm, "loop_begin"); 293 state->step = step; 294 state->counter_var = lp_build_alloca(gallivm, LLVMTypeOf(start), "loop_counter"); 295 state->gallivm = gallivm; 296 state->cond = cmp_op; 297 state->end = end; 298 299 LLVMBuildStore(builder, start, state->counter_var); 300 LLVMBuildBr(builder, state->begin); 301 302 LLVMPositionBuilderAtEnd(builder, state->begin); 303 state->counter = LLVMBuildLoad(builder, state->counter_var, ""); 304 305 state->body = lp_build_insert_new_block(gallivm, "loop_body"); 306 LLVMPositionBuilderAtEnd(builder, state->body); 307} 308 309/** 310 * End the for loop. 311 */ 312void 313lp_build_for_loop_end(struct lp_build_for_loop_state *state) 314{ 315 LLVMValueRef next, cond; 316 LLVMBuilderRef builder = state->gallivm->builder; 317 318 next = LLVMBuildAdd(builder, state->counter, state->step, ""); 319 LLVMBuildStore(builder, next, state->counter_var); 320 LLVMBuildBr(builder, state->begin); 321 322 state->exit = lp_build_insert_new_block(state->gallivm, "loop_exit"); 323 324 /* 325 * We build the comparison for the begin block here, 326 * if we build it earlier the output llvm ir is not human readable 327 * as the code produced is not in the standard begin -> body -> end order. 328 */ 329 LLVMPositionBuilderAtEnd(builder, state->begin); 330 cond = LLVMBuildICmp(builder, state->cond, state->counter, state->end, ""); 331 LLVMBuildCondBr(builder, cond, state->body, state->exit); 332 333 LLVMPositionBuilderAtEnd(builder, state->exit); 334} 335 336 337/* 338 Example of if/then/else building: 339 340 int x; 341 if (cond) { 342 x = 1 + 2; 343 } 344 else { 345 x = 2 + 3; 346 } 347 348 Is built with: 349 350 // x needs an alloca variable 351 x = lp_build_alloca(builder, type, "x"); 352 353 354 lp_build_if(ctx, builder, cond); 355 LLVMBuildStore(LLVMBuildAdd(1, 2), x); 356 lp_build_else(ctx); 357 LLVMBuildStore(LLVMBuildAdd(2, 3). x); 358 lp_build_endif(ctx); 359 360 */ 361 362 363 364/** 365 * Begin an if/else/endif construct. 366 */ 367void 368lp_build_if(struct lp_build_if_state *ifthen, 369 struct gallivm_state *gallivm, 370 LLVMValueRef condition) 371{ 372 LLVMBasicBlockRef block = LLVMGetInsertBlock(gallivm->builder); 373 374 memset(ifthen, 0, sizeof *ifthen); 375 ifthen->gallivm = gallivm; 376 ifthen->condition = condition; 377 ifthen->entry_block = block; 378 379 /* create endif/merge basic block for the phi functions */ 380 ifthen->merge_block = lp_build_insert_new_block(gallivm, "endif-block"); 381 382 /* create/insert true_block before merge_block */ 383 ifthen->true_block = 384 LLVMInsertBasicBlockInContext(gallivm->context, 385 ifthen->merge_block, 386 "if-true-block"); 387 388 /* successive code goes into the true block */ 389 LLVMPositionBuilderAtEnd(gallivm->builder, ifthen->true_block); 390} 391 392 393/** 394 * Begin else-part of a conditional 395 */ 396void 397lp_build_else(struct lp_build_if_state *ifthen) 398{ 399 LLVMBuilderRef builder = ifthen->gallivm->builder; 400 401 /* Append an unconditional Br(anch) instruction on the true_block */ 402 LLVMBuildBr(builder, ifthen->merge_block); 403 404 /* create/insert false_block before the merge block */ 405 ifthen->false_block = 406 LLVMInsertBasicBlockInContext(ifthen->gallivm->context, 407 ifthen->merge_block, 408 "if-false-block"); 409 410 /* successive code goes into the else block */ 411 LLVMPositionBuilderAtEnd(builder, ifthen->false_block); 412} 413 414 415/** 416 * End a conditional. 417 */ 418void 419lp_build_endif(struct lp_build_if_state *ifthen) 420{ 421 LLVMBuilderRef builder = ifthen->gallivm->builder; 422 423 /* Insert branch to the merge block from current block */ 424 LLVMBuildBr(builder, ifthen->merge_block); 425 426 /* 427 * Now patch in the various branch instructions. 428 */ 429 430 /* Insert the conditional branch instruction at the end of entry_block */ 431 LLVMPositionBuilderAtEnd(builder, ifthen->entry_block); 432 if (ifthen->false_block) { 433 /* we have an else clause */ 434 LLVMBuildCondBr(builder, ifthen->condition, 435 ifthen->true_block, ifthen->false_block); 436 } 437 else { 438 /* no else clause */ 439 LLVMBuildCondBr(builder, ifthen->condition, 440 ifthen->true_block, ifthen->merge_block); 441 } 442 443 /* Resume building code at end of the ifthen->merge_block */ 444 LLVMPositionBuilderAtEnd(builder, ifthen->merge_block); 445} 446 447 448/** 449 * Allocate a scalar (or vector) variable. 450 * 451 * Although not strictly part of control flow, control flow has deep impact in 452 * how variables should be allocated. 453 * 454 * The mem2reg optimization pass is the recommended way to dealing with mutable 455 * variables, and SSA. It looks for allocas and if it can handle them, it 456 * promotes them, but only looks for alloca instructions in the entry block of 457 * the function. Being in the entry block guarantees that the alloca is only 458 * executed once, which makes analysis simpler. 459 * 460 * See also: 461 * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory 462 */ 463LLVMValueRef 464lp_build_alloca(struct gallivm_state *gallivm, 465 LLVMTypeRef type, 466 const char *name) 467{ 468 LLVMBuilderRef builder = gallivm->builder; 469 LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder); 470 LLVMValueRef function = LLVMGetBasicBlockParent(current_block); 471 LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function); 472 LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block); 473 LLVMBuilderRef first_builder = LLVMCreateBuilderInContext(gallivm->context); 474 LLVMValueRef res; 475 476 if (first_instr) { 477 LLVMPositionBuilderBefore(first_builder, first_instr); 478 } else { 479 LLVMPositionBuilderAtEnd(first_builder, first_block); 480 } 481 482 res = LLVMBuildAlloca(first_builder, type, name); 483 LLVMBuildStore(builder, LLVMConstNull(type), res); 484 485 LLVMDisposeBuilder(first_builder); 486 487 return res; 488} 489 490 491/** 492 * Allocate an array of scalars/vectors. 493 * 494 * mem2reg pass is not capable of promoting structs or arrays to registers, but 495 * we still put it in the first block anyway as failure to put allocas in the 496 * first block may prevent the X86 backend from successfully align the stack as 497 * required. 498 * 499 * Also the scalarrepl pass is supposedly more powerful and can promote 500 * arrays in many cases. 501 * 502 * See also: 503 * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory 504 */ 505LLVMValueRef 506lp_build_array_alloca(struct gallivm_state *gallivm, 507 LLVMTypeRef type, 508 LLVMValueRef count, 509 const char *name) 510{ 511 LLVMBuilderRef builder = gallivm->builder; 512 LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder); 513 LLVMValueRef function = LLVMGetBasicBlockParent(current_block); 514 LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function); 515 LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block); 516 LLVMBuilderRef first_builder = LLVMCreateBuilderInContext(gallivm->context); 517 LLVMValueRef res; 518 519 if (first_instr) { 520 LLVMPositionBuilderBefore(first_builder, first_instr); 521 } else { 522 LLVMPositionBuilderAtEnd(first_builder, first_block); 523 } 524 525 res = LLVMBuildArrayAlloca(first_builder, type, count, name); 526 527 LLVMDisposeBuilder(first_builder); 528 529 return res; 530} 531