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 #define LP_BUILD_FLOW_MAX_VARIABLES 64
  42 #define LP_BUILD_FLOW_MAX_DEPTH 32
  43
  44 /**
  45  * Enumeration of all possible flow constructs.
  46  */
  47 enum lp_build_flow_construct_kind {
  48    LP_BUILD_FLOW_SKIP,
  49    LP_BUILD_FLOW_IF
  50 };
  51
  52
  53 /**
  54  * Early exit. Useful to skip to the end of a function or block when
  55  * the execution mask becomes zero or when there is an error condition.
  56  */
  57 struct lp_build_flow_skip
  58 {
  59    /** Block to skip to */
  60    LLVMBasicBlockRef block;
  61 };
  62
  63
  64 /**
  65  * if/else/endif.
  66  */
  67 struct lp_build_flow_if
  68 {
  69    LLVMValueRef condition;
  70    LLVMBasicBlockRef entry_block, true_block, false_block, merge_block;
  71 };
  72
  73
  74 /**
  75  * Union of all possible flow constructs' data
  76  */
  77 union lp_build_flow_construct_data
  78 {
  79    struct lp_build_flow_skip skip;
  80    struct lp_build_flow_if ifthen;
  81 };
  82
  83
  84 /**
  85  * Element of the flow construct stack.
  86  */
  87 struct lp_build_flow_construct
  88 {
  89    enum lp_build_flow_construct_kind kind;
  90    union lp_build_flow_construct_data data;
  91 };
  92
  93
  94 /**
  95  * All necessary data to generate LLVM control flow constructs.
  96  *
  97  * Besides keeping track of the control flow construct themselves we also
  98  * need to keep track of variables in order to generate SSA Phi values.
  99  */
 100 struct lp_build_flow_context
 101 {
 102    LLVMBuilderRef builder;
 103
 104    /**
 105     * Control flow stack.
 106     */
 107    struct lp_build_flow_construct constructs[LP_BUILD_FLOW_MAX_DEPTH];
 108    unsigned num_constructs;
 109 };
 110
 111
 112 struct lp_build_flow_context *
 113 lp_build_flow_create(LLVMBuilderRef builder)
 114 {
 115    struct lp_build_flow_context *flow;
 116
 117    flow = CALLOC_STRUCT(lp_build_flow_context);
 118    if(!flow)
 119       return NULL;
 120
 121    flow->builder = builder;
 122
 123    return flow;
 124 }
 125
 126
 127 void
 128 lp_build_flow_destroy(struct lp_build_flow_context *flow)
 129 {
 130    assert(flow->num_constructs == 0);
 131    FREE(flow);
 132 }
 133
 134
 135 /**
 136  * Begin/push a new flow control construct, such as a loop, skip block
 137  * or variable scope.
 138  */
 139 static union lp_build_flow_construct_data *
 140 lp_build_flow_push(struct lp_build_flow_context *flow,
 141                    enum lp_build_flow_construct_kind kind)
 142 {
 143    assert(flow->num_constructs < LP_BUILD_FLOW_MAX_DEPTH);
 144    if(flow->num_constructs >= LP_BUILD_FLOW_MAX_DEPTH)
 145       return NULL;
 146
 147    flow->constructs[flow->num_constructs].kind = kind;
 148    return &flow->constructs[flow->num_constructs++].data;
 149 }
 150
 151
 152 /**
 153  * Return the current/top flow control construct on the stack.
 154  * \param kind  the expected type of the top-most construct
 155  */
 156 static union lp_build_flow_construct_data *
 157 lp_build_flow_peek(struct lp_build_flow_context *flow,
 158                    enum lp_build_flow_construct_kind kind)
 159 {
 160    assert(flow->num_constructs);
 161    if(!flow->num_constructs)
 162       return NULL;
 163
 164    assert(flow->constructs[flow->num_constructs - 1].kind == kind);
 165    if(flow->constructs[flow->num_constructs - 1].kind != kind)
 166       return NULL;
 167
 168    return &flow->constructs[flow->num_constructs - 1].data;
 169 }
 170
 171
 172 /**
 173  * End/pop the current/top flow control construct on the stack.
 174  * \param kind  the expected type of the top-most construct
 175  */
 176 static union lp_build_flow_construct_data *
 177 lp_build_flow_pop(struct lp_build_flow_context *flow,
 178                   enum lp_build_flow_construct_kind kind)
 179 {
 180    assert(flow->num_constructs);
 181    if(!flow->num_constructs)
 182       return NULL;
 183
 184    assert(flow->constructs[flow->num_constructs - 1].kind == kind);
 185    if(flow->constructs[flow->num_constructs - 1].kind != kind)
 186       return NULL;
 187
 188    return &flow->constructs[--flow->num_constructs].data;
 189 }
 190
 191
 192 /**
 193  * Note: this function has no dependencies on the flow code and could
 194  * be used elsewhere.
 195  */
 196 LLVMBasicBlockRef
 197 lp_build_insert_new_block(LLVMBuilderRef builder, const char *name)
 198 {
 199    LLVMBasicBlockRef current_block;
 200    LLVMBasicBlockRef next_block;
 201    LLVMBasicBlockRef new_block;
 202
 203    /* get current basic block */
 204    current_block = LLVMGetInsertBlock(builder);
 205
 206    /* check if there's another block after this one */
 207    next_block = LLVMGetNextBasicBlock(current_block);
 208    if (next_block) {
 209       /* insert the new block before the next block */
 210       new_block = LLVMInsertBasicBlock(next_block, name);
 211    }
 212    else {
 213       /* append new block after current block */
 214       LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
 215       new_block = LLVMAppendBasicBlock(function, name);
 216    }
 217
 218    return new_block;
 219 }
 220
 221
 222 static LLVMBasicBlockRef
 223 lp_build_flow_insert_block(struct lp_build_flow_context *flow)
 224 {
 225    return lp_build_insert_new_block(flow->builder, "");
 226 }
 227
 228
 229 /**
 230  * Begin a "skip" block.  Inside this block we can test a condition and
 231  * skip to the end of the block if the condition is false.
 232  */
 233 void
 234 lp_build_flow_skip_begin(struct lp_build_flow_context *flow)
 235 {
 236    struct lp_build_flow_skip *skip;
 237    LLVMBuilderRef builder;
 238
 239    skip = &lp_build_flow_push(flow, LP_BUILD_FLOW_SKIP)->skip;
 240    if(!skip)
 241       return;
 242
 243    /* create new basic block */
 244    skip->block = lp_build_flow_insert_block(flow);
 245
 246    builder = LLVMCreateBuilder();
 247    LLVMPositionBuilderAtEnd(builder, skip->block);
 248
 249    LLVMDisposeBuilder(builder);
 250 }
 251
 252
 253 /**
 254  * Insert code to test a condition and branch to the end of the current
 255  * skip block if the condition is true.
 256  */
 257 void
 258 lp_build_flow_skip_cond_break(struct lp_build_flow_context *flow,
 259                               LLVMValueRef cond)
 260 {
 261    struct lp_build_flow_skip *skip;
 262    LLVMBasicBlockRef new_block;
 263
 264    skip = &lp_build_flow_peek(flow, LP_BUILD_FLOW_SKIP)->skip;
 265    if(!skip)
 266       return;
 267
 268    new_block = lp_build_flow_insert_block(flow);
 269
 270    /* if cond is true, goto skip->block, else goto new_block */
 271    LLVMBuildCondBr(flow->builder, cond, skip->block, new_block);
 272
 273    LLVMPositionBuilderAtEnd(flow->builder, new_block);
 274 }
 275
 276
 277 void
 278 lp_build_flow_skip_end(struct lp_build_flow_context *flow)
 279 {
 280    struct lp_build_flow_skip *skip;
 281
 282    skip = &lp_build_flow_pop(flow, LP_BUILD_FLOW_SKIP)->skip;
 283    if(!skip)
 284       return;
 285
 286    /* goto block */
 287    LLVMBuildBr(flow->builder, skip->block);
 288    LLVMPositionBuilderAtEnd(flow->builder, skip->block);
 289 }
 290
 291
 292 /**
 293  * Check if the mask predicate is zero.  If so, jump to the end of the block.
 294  */
 295 void
 296 lp_build_mask_check(struct lp_build_mask_context *mask)
 297 {
 298    LLVMBuilderRef builder = mask->flow->builder;
 299    LLVMValueRef value;
 300    LLVMValueRef cond;
 301
 302    value = lp_build_mask_value(mask);
 303
 304    /* cond = (mask == 0) */
 305    cond = LLVMBuildICmp(builder,
 306                         LLVMIntEQ,
 307                         LLVMBuildBitCast(builder, value, mask->reg_type, ""),
 308                         LLVMConstNull(mask->reg_type),
 309                         "");
 310
 311    /* if cond, goto end of block */
 312    lp_build_flow_skip_cond_break(mask->flow, cond);
 313 }
 314
 315
 316 /**
 317  * Begin a section of code which is predicated on a mask.
 318  * \param mask  the mask context, initialized here
 319  * \param flow  the flow context
 320  * \param type  the type of the mask
 321  * \param value  storage for the mask
 322  */
 323 void
 324 lp_build_mask_begin(struct lp_build_mask_context *mask,
 325                     struct lp_build_flow_context *flow,
 326                     struct lp_type type,
 327                     LLVMValueRef value)
 328 {
 329    memset(mask, 0, sizeof *mask);
 330
 331    mask->flow = flow;
 332    mask->reg_type = LLVMIntType(type.width * type.length);
 333    mask->var = lp_build_alloca(flow->builder,
 334                                lp_build_int_vec_type(type),
 335                                "execution_mask");
 336
 337    LLVMBuildStore(flow->builder, value, mask->var);
 338
 339    lp_build_flow_skip_begin(flow);
 340 }
 341
 342
 343 LLVMValueRef
 344 lp_build_mask_value(struct lp_build_mask_context *mask)
 345 {
 346    return LLVMBuildLoad(mask->flow->builder, mask->var, "");
 347 }
 348
 349
 350 /**
 351  * Update boolean mask with given value (bitwise AND).
 352  * Typically used to update the quad's pixel alive/killed mask
 353  * after depth testing, alpha testing, TGSI_OPCODE_KIL, etc.
 354  */
 355 void
 356 lp_build_mask_update(struct lp_build_mask_context *mask,
 357                      LLVMValueRef value)
 358 {
 359    value = LLVMBuildAnd(mask->flow->builder,
 360                         lp_build_mask_value(mask),
 361                         value, "");
 362    LLVMBuildStore(mask->flow->builder, value, mask->var);
 363 }
 364
 365
 366 /**
 367  * End section of code which is predicated on a mask.
 368  */
 369 LLVMValueRef
 370 lp_build_mask_end(struct lp_build_mask_context *mask)
 371 {
 372    lp_build_flow_skip_end(mask->flow);
 373    return lp_build_mask_value(mask);
 374 }
 375
 376
 377
 378 void
 379 lp_build_loop_begin(LLVMBuilderRef builder,
 380                     LLVMValueRef start,
 381                     struct lp_build_loop_state *state)
 382 {
 383    LLVMBasicBlockRef block = LLVMGetInsertBlock(builder);
 384    LLVMValueRef function = LLVMGetBasicBlockParent(block);
 385
 386    state->block = LLVMAppendBasicBlock(function, "loop");
 387
 388    LLVMBuildBr(builder, state->block);
 389
 390    LLVMPositionBuilderAtEnd(builder, state->block);
 391
 392    state->counter = LLVMBuildPhi(builder, LLVMTypeOf(start), "");
 393
 394    LLVMAddIncoming(state->counter, &start, &block, 1);
 395
 396 }
 397
 398
 399 void
 400 lp_build_loop_end(LLVMBuilderRef builder,
 401                   LLVMValueRef end,
 402                   LLVMValueRef step,
 403                   struct lp_build_loop_state *state)
 404 {
 405    LLVMBasicBlockRef block = LLVMGetInsertBlock(builder);
 406    LLVMValueRef function = LLVMGetBasicBlockParent(block);
 407    LLVMValueRef next;
 408    LLVMValueRef cond;
 409    LLVMBasicBlockRef after_block;
 410
 411    if (!step)
 412       step = LLVMConstInt(LLVMTypeOf(end), 1, 0);
 413
 414    next = LLVMBuildAdd(builder, state->counter, step, "");
 415
 416    cond = LLVMBuildICmp(builder, LLVMIntNE, next, end, "");
 417
 418    after_block = LLVMAppendBasicBlock(function, "");
 419
 420    LLVMBuildCondBr(builder, cond, after_block, state->block);
 421
 422    LLVMAddIncoming(state->counter, &next, &block, 1);
 423
 424    LLVMPositionBuilderAtEnd(builder, after_block);
 425 }
 426
 427 void
 428 lp_build_loop_end_cond(LLVMBuilderRef builder,
 429                        LLVMValueRef end,
 430                        LLVMValueRef step,
 431                        int llvm_cond,
 432                        struct lp_build_loop_state *state)
 433 {
 434    LLVMBasicBlockRef block = LLVMGetInsertBlock(builder);
 435    LLVMValueRef function = LLVMGetBasicBlockParent(block);
 436    LLVMValueRef next;
 437    LLVMValueRef cond;
 438    LLVMBasicBlockRef after_block;
 439
 440    if (!step)
 441       step = LLVMConstInt(LLVMTypeOf(end), 1, 0);
 442
 443    next = LLVMBuildAdd(builder, state->counter, step, "");
 444
 445    cond = LLVMBuildICmp(builder, llvm_cond, next, end, "");
 446
 447    after_block = LLVMAppendBasicBlock(function, "");
 448
 449    LLVMBuildCondBr(builder, cond, after_block, state->block);
 450
 451    LLVMAddIncoming(state->counter, &next, &block, 1);
 452
 453    LLVMPositionBuilderAtEnd(builder, after_block);
 454 }
 455
 456
 457
 458 /*
 459   Example of if/then/else building:
 460
 461      int x;
 462      if (cond) {
 463         x = 1 + 2;
 464      }
 465      else {
 466         x = 2 + 3;
 467      }
 468
 469   Is built with:
 470
 471      LLVMValueRef x = LLVMGetUndef();  // or something else
 472
 473      flow = lp_build_flow_create(builder);
 474
 475         lp_build_flow_scope_begin(flow);
 476
 477            // x needs a phi node
 478            lp_build_flow_scope_declare(flow, &x);
 479
 480            lp_build_if(ctx, flow, builder, cond);
 481               x = LLVMAdd(1, 2);
 482            lp_build_else(ctx);
 483               x = LLVMAdd(2, 3);
 484            lp_build_endif(ctx);
 485
 486         lp_build_flow_scope_end(flow);
 487
 488      lp_build_flow_destroy(flow);
 489  */
 490
 491
 492
 493 /**
 494  * Begin an if/else/endif construct.
 495  */
 496 void
 497 lp_build_if(struct lp_build_if_state *ctx,
 498             struct lp_build_flow_context *flow,
 499             LLVMBuilderRef builder,
 500             LLVMValueRef condition)
 501 {
 502    LLVMBasicBlockRef block = LLVMGetInsertBlock(builder);
 503    struct lp_build_flow_if *ifthen;
 504
 505    memset(ctx, 0, sizeof(*ctx));
 506    ctx->builder = builder;
 507    ctx->flow = flow;
 508
 509    /* push/create new scope */
 510    ifthen = &lp_build_flow_push(flow, LP_BUILD_FLOW_IF)->ifthen;
 511    assert(ifthen);
 512
 513    ifthen->condition = condition;
 514    ifthen->entry_block = block;
 515
 516    /* create endif/merge basic block for the phi functions */
 517    ifthen->merge_block = lp_build_insert_new_block(builder, "endif-block");
 518    LLVMPositionBuilderAtEnd(builder, ifthen->merge_block);
 519
 520    /* create/insert true_block before merge_block */
 521    ifthen->true_block = LLVMInsertBasicBlock(ifthen->merge_block, "if-true-block");
 522
 523    /* successive code goes into the true block */
 524    LLVMPositionBuilderAtEnd(builder, ifthen->true_block);
 525 }
 526
 527
 528 /**
 529  * Begin else-part of a conditional
 530  */
 531 void
 532 lp_build_else(struct lp_build_if_state *ctx)
 533 {
 534    struct lp_build_flow_context *flow = ctx->flow;
 535    struct lp_build_flow_if *ifthen;
 536
 537    ifthen = &lp_build_flow_peek(flow, LP_BUILD_FLOW_IF)->ifthen;
 538    assert(ifthen);
 539
 540    /* create/insert false_block before the merge block */
 541    ifthen->false_block = LLVMInsertBasicBlock(ifthen->merge_block, "if-false-block");
 542
 543    /* successive code goes into the else block */
 544    LLVMPositionBuilderAtEnd(ctx->builder, ifthen->false_block);
 545 }
 546
 547
 548 /**
 549  * End a conditional.
 550  */
 551 void
 552 lp_build_endif(struct lp_build_if_state *ctx)
 553 {
 554    struct lp_build_flow_context *flow = ctx->flow;
 555    struct lp_build_flow_if *ifthen;
 556
 557    ifthen = &lp_build_flow_pop(flow, LP_BUILD_FLOW_IF)->ifthen;
 558    assert(ifthen);
 559
 560    /* Insert branch to the merge block from current block */
 561    LLVMBuildBr(ctx->builder, ifthen->merge_block);
 562
 563    /***
 564     *** Now patch in the various branch instructions.
 565     ***/
 566
 567    /* Insert the conditional branch instruction at the end of entry_block */
 568    LLVMPositionBuilderAtEnd(ctx->builder, ifthen->entry_block);
 569    if (ifthen->false_block) {
 570       /* we have an else clause */
 571       LLVMBuildCondBr(ctx->builder, ifthen->condition,
 572                       ifthen->true_block, ifthen->false_block);
 573    }
 574    else {
 575       /* no else clause */
 576       LLVMBuildCondBr(ctx->builder, ifthen->condition,
 577                       ifthen->true_block, ifthen->merge_block);
 578    }
 579
 580    /* Insert branch from end of true_block to merge_block */
 581    if (ifthen->false_block) {
 582       /* Append an unconditional Br(anch) instruction on the true_block */
 583       LLVMPositionBuilderAtEnd(ctx->builder, ifthen->true_block);
 584       LLVMBuildBr(ctx->builder, ifthen->merge_block);
 585    }
 586    else {
 587       /* No else clause.
 588        * Note that we've already inserted the branch at the end of
 589        * true_block.  See the very first LLVMBuildBr() call in this function.
 590        */
 591    }
 592
 593    /* Resume building code at end of the ifthen->merge_block */
 594    LLVMPositionBuilderAtEnd(ctx->builder, ifthen->merge_block);
 595 }
 596
 597
 598 /**
 599  * Allocate a scalar (or vector) variable.
 600  *
 601  * Although not strictly part of control flow, control flow has deep impact in
 602  * how variables should be allocated.
 603  *
 604  * The mem2reg optimization pass is the recommended way to dealing with mutable
 605  * variables, and SSA. It looks for allocas and if it can handle them, it
 606  * promotes them, but only looks for alloca instructions in the entry block of
 607  * the function. Being in the entry block guarantees that the alloca is only
 608  * executed once, which makes analysis simpler.
 609  *
 610  * See also:
 611  * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory
 612  */
 613 LLVMValueRef
 614 lp_build_alloca(LLVMBuilderRef builder,
 615                 LLVMTypeRef type,
 616                 const char *name)
 617 {
 618    LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder);
 619    LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
 620    LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function);
 621    LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block);
 622    LLVMBuilderRef first_builder = LLVMCreateBuilder();
 623    LLVMValueRef res;
 624
 625    if (first_instr) {
 626       LLVMPositionBuilderBefore(first_builder, first_instr);
 627    } else {
 628       LLVMPositionBuilderAtEnd(first_builder, first_block);
 629    }
 630
 631    res = LLVMBuildAlloca(first_builder, type, name);
 632    LLVMBuildStore(builder, LLVMConstNull(type), res);
 633
 634    LLVMDisposeBuilder(first_builder);
 635
 636    return res;
 637 }
 638
 639
 640 /**
 641  * Allocate an array of scalars/vectors.
 642  *
 643  * mem2reg pass is not capable of promoting structs or arrays to registers, but
 644  * we still put it in the first block anyway as failure to put allocas in the
 645  * first block may prevent the X86 backend from successfully align the stack as
 646  * required.
 647  *
 648  * Also the scalarrepl pass is supposedly more powerful and can promote
 649  * arrays in many cases.
 650  *
 651  * See also:
 652  * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory
 653  */
 654 LLVMValueRef
 655 lp_build_array_alloca(LLVMBuilderRef builder,
 656                       LLVMTypeRef type,
 657                       LLVMValueRef count,
 658                       const char *name)
 659 {
 660    LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder);
 661    LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
 662    LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function);
 663    LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block);
 664    LLVMBuilderRef first_builder = LLVMCreateBuilder();
 665    LLVMValueRef res;
 666
 667    if (first_instr) {
 668       LLVMPositionBuilderBefore(first_builder, first_instr);
 669    } else {
 670       LLVMPositionBuilderAtEnd(first_builder, first_block);
 671    }
 672
 673    res = LLVMBuildArrayAlloca(first_builder, type, count, name);
 674
 675    LLVMDisposeBuilder(first_builder);
 676
 677    return res;
 678 }