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 32
  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_SCOPE,
  49    LP_BUILD_FLOW_SKIP,
  50    LP_BUILD_FLOW_IF
  51 };
  52
  53
  54 /**
  55  * Variable declaration scope.
  56  */
  57 struct lp_build_flow_scope
  58 {
  59    /** Number of variables declared in this scope */
  60    unsigned num_variables;
  61 };
  62
  63
  64 /**
  65  * Early exit. Useful to skip to the end of a function or block when
  66  * the execution mask becomes zero or when there is an error condition.
  67  */
  68 struct lp_build_flow_skip
  69 {
  70    /** Block to skip to */
  71    LLVMBasicBlockRef block;
  72
  73    /** Number of variables declared at the beginning */
  74    unsigned num_variables;
  75
  76    LLVMValueRef *phi;  /**< array [num_variables] */
  77 };
  78
  79
  80 /**
  81  * if/else/endif.
  82  */
  83 struct lp_build_flow_if
  84 {
  85    unsigned num_variables;
  86
  87    LLVMValueRef *phi;  /**< array [num_variables] */
  88
  89    LLVMValueRef condition;
  90    LLVMBasicBlockRef entry_block, true_block, false_block, merge_block;
  91 };
  92
  93
  94 /**
  95  * Union of all possible flow constructs' data
  96  */
  97 union lp_build_flow_construct_data
  98 {
  99    struct lp_build_flow_scope scope;
 100    struct lp_build_flow_skip skip;
 101    struct lp_build_flow_if ifthen;
 102 };
 103
 104
 105 /**
 106  * Element of the flow construct stack.
 107  */
 108 struct lp_build_flow_construct
 109 {
 110    enum lp_build_flow_construct_kind kind;
 111    union lp_build_flow_construct_data data;
 112 };
 113
 114
 115 /**
 116  * All necessary data to generate LLVM control flow constructs.
 117  *
 118  * Besides keeping track of the control flow construct themselves we also
 119  * need to keep track of variables in order to generate SSA Phi values.
 120  */
 121 struct lp_build_flow_context
 122 {
 123    LLVMBuilderRef builder;
 124
 125    /**
 126     * Control flow stack.
 127     */
 128    struct lp_build_flow_construct constructs[LP_BUILD_FLOW_MAX_DEPTH];
 129    unsigned num_constructs;
 130
 131    /**
 132     * Variable stack
 133     */
 134    LLVMValueRef *variables[LP_BUILD_FLOW_MAX_VARIABLES];
 135    unsigned num_variables;
 136 };
 137
 138
 139 struct lp_build_flow_context *
 140 lp_build_flow_create(LLVMBuilderRef builder)
 141 {
 142    struct lp_build_flow_context *flow;
 143
 144    flow = CALLOC_STRUCT(lp_build_flow_context);
 145    if(!flow)
 146       return NULL;
 147
 148    flow->builder = builder;
 149
 150    return flow;
 151 }
 152
 153
 154 void
 155 lp_build_flow_destroy(struct lp_build_flow_context *flow)
 156 {
 157    assert(flow->num_constructs == 0);
 158    assert(flow->num_variables == 0);
 159    FREE(flow);
 160 }
 161
 162
 163 /**
 164  * Begin/push a new flow control construct, such as a loop, skip block
 165  * or variable scope.
 166  */
 167 static union lp_build_flow_construct_data *
 168 lp_build_flow_push(struct lp_build_flow_context *flow,
 169                    enum lp_build_flow_construct_kind kind)
 170 {
 171    assert(flow->num_constructs < LP_BUILD_FLOW_MAX_DEPTH);
 172    if(flow->num_constructs >= LP_BUILD_FLOW_MAX_DEPTH)
 173       return NULL;
 174
 175    flow->constructs[flow->num_constructs].kind = kind;
 176    return &flow->constructs[flow->num_constructs++].data;
 177 }
 178
 179
 180 /**
 181  * Return the current/top flow control construct on the stack.
 182  * \param kind  the expected type of the top-most construct
 183  */
 184 static union lp_build_flow_construct_data *
 185 lp_build_flow_peek(struct lp_build_flow_context *flow,
 186                    enum lp_build_flow_construct_kind kind)
 187 {
 188    assert(flow->num_constructs);
 189    if(!flow->num_constructs)
 190       return NULL;
 191
 192    assert(flow->constructs[flow->num_constructs - 1].kind == kind);
 193    if(flow->constructs[flow->num_constructs - 1].kind != kind)
 194       return NULL;
 195
 196    return &flow->constructs[flow->num_constructs - 1].data;
 197 }
 198
 199
 200 /**
 201  * End/pop the current/top flow control construct on the stack.
 202  * \param kind  the expected type of the top-most construct
 203  */
 204 static union lp_build_flow_construct_data *
 205 lp_build_flow_pop(struct lp_build_flow_context *flow,
 206                   enum lp_build_flow_construct_kind kind)
 207 {
 208    assert(flow->num_constructs);
 209    if(!flow->num_constructs)
 210       return NULL;
 211
 212    assert(flow->constructs[flow->num_constructs - 1].kind == kind);
 213    if(flow->constructs[flow->num_constructs - 1].kind != kind)
 214       return NULL;
 215
 216    return &flow->constructs[--flow->num_constructs].data;
 217 }
 218
 219
 220 /**
 221  * Begin a variable scope.
 222  *
 223  *
 224  */
 225 void
 226 lp_build_flow_scope_begin(struct lp_build_flow_context *flow)
 227 {
 228    struct lp_build_flow_scope *scope;
 229
 230    scope = &lp_build_flow_push(flow, LP_BUILD_FLOW_SCOPE)->scope;
 231    if(!scope)
 232       return;
 233
 234    scope->num_variables = 0;
 235 }
 236
 237
 238 /**
 239  * Declare a variable.
 240  *
 241  * A variable is a named entity which can have different LLVMValueRef's at
 242  * different points of the program. This is relevant for control flow because
 243  * when there are multiple branches to a same location we need to replace
 244  * the variable's value with a Phi function as explained in
 245  * http://en.wikipedia.org/wiki/Static_single_assignment_form .
 246  *
 247  * We keep track of variables by keeping around a pointer to where they're
 248  * current.
 249  *
 250  * There are a few cautions to observe:
 251  *
 252  * - Variable's value must not be NULL. If there is no initial value then
 253  *   LLVMGetUndef() should be used.
 254  *
 255  * - Variable's value must be kept up-to-date. If the variable is going to be
 256  *   modified by a function then a pointer should be passed so that its value
 257  *   is accurate. Failure to do this will cause some of the variables'
 258  *   transient values to be lost, leading to wrong results.
 259  *
 260  * - A program should be written from top to bottom, by always appending
 261  *   instructions to the bottom with a single LLVMBuilderRef. Inserting and/or
 262  *   modifying existing statements will most likely lead to wrong results.
 263  *
 264  */
 265 void
 266 lp_build_flow_scope_declare(struct lp_build_flow_context *flow,
 267                             LLVMValueRef *variable)
 268 {
 269    struct lp_build_flow_scope *scope;
 270
 271    scope = &lp_build_flow_peek(flow, LP_BUILD_FLOW_SCOPE)->scope;
 272    if(!scope)
 273       return;
 274
 275    assert(*variable);
 276    if(!*variable)
 277       return;
 278
 279    assert(flow->num_variables < LP_BUILD_FLOW_MAX_VARIABLES);
 280    if(flow->num_variables >= LP_BUILD_FLOW_MAX_VARIABLES)
 281       return;
 282
 283    flow->variables[flow->num_variables++] = variable;
 284    ++scope->num_variables;
 285 }
 286
 287
 288 void
 289 lp_build_flow_scope_end(struct lp_build_flow_context *flow)
 290 {
 291    struct lp_build_flow_scope *scope;
 292
 293    scope = &lp_build_flow_pop(flow, LP_BUILD_FLOW_SCOPE)->scope;
 294    if(!scope)
 295       return;
 296
 297    assert(flow->num_variables >= scope->num_variables);
 298    if(flow->num_variables < scope->num_variables) {
 299       flow->num_variables = 0;
 300       return;
 301    }
 302
 303    flow->num_variables -= scope->num_variables;
 304 }
 305
 306
 307 /**
 308  * Note: this function has no dependencies on the flow code and could
 309  * be used elsewhere.
 310  */
 311 LLVMBasicBlockRef
 312 lp_build_insert_new_block(LLVMBuilderRef builder, const char *name)
 313 {
 314    LLVMBasicBlockRef current_block;
 315    LLVMBasicBlockRef next_block;
 316    LLVMBasicBlockRef new_block;
 317
 318    /* get current basic block */
 319    current_block = LLVMGetInsertBlock(builder);
 320
 321    /* check if there's another block after this one */
 322    next_block = LLVMGetNextBasicBlock(current_block);
 323    if (next_block) {
 324       /* insert the new block before the next block */
 325       new_block = LLVMInsertBasicBlock(next_block, name);
 326    }
 327    else {
 328       /* append new block after current block */
 329       LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
 330       new_block = LLVMAppendBasicBlock(function, name);
 331    }
 332
 333    return new_block;
 334 }
 335
 336
 337 static LLVMBasicBlockRef
 338 lp_build_flow_insert_block(struct lp_build_flow_context *flow)
 339 {
 340    return lp_build_insert_new_block(flow->builder, "");
 341 }
 342
 343
 344 /**
 345  * Begin a "skip" block.  Inside this block we can test a condition and
 346  * skip to the end of the block if the condition is false.
 347  */
 348 void
 349 lp_build_flow_skip_begin(struct lp_build_flow_context *flow)
 350 {
 351    struct lp_build_flow_skip *skip;
 352    LLVMBuilderRef builder;
 353    unsigned i;
 354
 355    skip = &lp_build_flow_push(flow, LP_BUILD_FLOW_SKIP)->skip;
 356    if(!skip)
 357       return;
 358
 359    /* create new basic block */
 360    skip->block = lp_build_flow_insert_block(flow);
 361
 362    skip->num_variables = flow->num_variables;
 363    if(!skip->num_variables) {
 364       skip->phi = NULL;
 365       return;
 366    }
 367
 368    /* Allocate a Phi node for each variable in this skip scope */
 369    skip->phi = MALLOC(skip->num_variables * sizeof *skip->phi);
 370    if(!skip->phi) {
 371       skip->num_variables = 0;
 372       return;
 373    }
 374
 375    builder = LLVMCreateBuilder();
 376    LLVMPositionBuilderAtEnd(builder, skip->block);
 377
 378    /* create a Phi node for each variable */
 379    for(i = 0; i < skip->num_variables; ++i)
 380       skip->phi[i] = LLVMBuildPhi(builder, LLVMTypeOf(*flow->variables[i]), "");
 381
 382    LLVMDisposeBuilder(builder);
 383 }
 384
 385
 386 /**
 387  * Insert code to test a condition and branch to the end of the current
 388  * skip block if the condition is true.
 389  */
 390 void
 391 lp_build_flow_skip_cond_break(struct lp_build_flow_context *flow,
 392                               LLVMValueRef cond)
 393 {
 394    struct lp_build_flow_skip *skip;
 395    LLVMBasicBlockRef current_block;
 396    LLVMBasicBlockRef new_block;
 397    unsigned i;
 398
 399    skip = &lp_build_flow_peek(flow, LP_BUILD_FLOW_SKIP)->skip;
 400    if(!skip)
 401       return;
 402
 403    current_block = LLVMGetInsertBlock(flow->builder);
 404
 405    new_block = lp_build_flow_insert_block(flow);
 406
 407    /* for each variable, update the Phi node with a (variable, block) pair */
 408    for(i = 0; i < skip->num_variables; ++i) {
 409       assert(*flow->variables[i]);
 410       LLVMAddIncoming(skip->phi[i], flow->variables[i], &current_block, 1);
 411    }
 412
 413    /* if cond is true, goto skip->block, else goto new_block */
 414    LLVMBuildCondBr(flow->builder, cond, skip->block, new_block);
 415
 416    LLVMPositionBuilderAtEnd(flow->builder, new_block);
 417 }
 418
 419
 420 void
 421 lp_build_flow_skip_end(struct lp_build_flow_context *flow)
 422 {
 423    struct lp_build_flow_skip *skip;
 424    LLVMBasicBlockRef current_block;
 425    unsigned i;
 426
 427    skip = &lp_build_flow_pop(flow, LP_BUILD_FLOW_SKIP)->skip;
 428    if(!skip)
 429       return;
 430
 431    current_block = LLVMGetInsertBlock(flow->builder);
 432
 433    /* add (variable, block) tuples to the phi nodes */
 434    for(i = 0; i < skip->num_variables; ++i) {
 435       assert(*flow->variables[i]);
 436       LLVMAddIncoming(skip->phi[i], flow->variables[i], &current_block, 1);
 437       *flow->variables[i] = skip->phi[i];
 438    }
 439
 440    /* goto block */
 441    LLVMBuildBr(flow->builder, skip->block);
 442    LLVMPositionBuilderAtEnd(flow->builder, skip->block);
 443
 444    FREE(skip->phi);
 445 }
 446
 447
 448 /**
 449  * Check if the mask predicate is zero.  If so, jump to the end of the block.
 450  */
 451 static void
 452 lp_build_mask_check(struct lp_build_mask_context *mask)
 453 {
 454    LLVMBuilderRef builder = mask->flow->builder;
 455    LLVMValueRef cond;
 456
 457    /* cond = (mask == 0) */
 458    cond = LLVMBuildICmp(builder,
 459                         LLVMIntEQ,
 460                         LLVMBuildBitCast(builder, mask->value, mask->reg_type, ""),
 461                         LLVMConstNull(mask->reg_type),
 462                         "");
 463
 464    /* if cond, goto end of block */
 465    lp_build_flow_skip_cond_break(mask->flow, cond);
 466 }
 467
 468
 469 /**
 470  * Begin a section of code which is predicated on a mask.
 471  * \param mask  the mask context, initialized here
 472  * \param flow  the flow context
 473  * \param type  the type of the mask
 474  * \param value  storage for the mask
 475  */
 476 void
 477 lp_build_mask_begin(struct lp_build_mask_context *mask,
 478                     struct lp_build_flow_context *flow,
 479                     struct lp_type type,
 480                     LLVMValueRef value)
 481 {
 482    memset(mask, 0, sizeof *mask);
 483
 484    mask->flow = flow;
 485    mask->reg_type = LLVMIntType(type.width * type.length);
 486    mask->value = value;
 487
 488    lp_build_flow_scope_begin(flow);
 489    lp_build_flow_scope_declare(flow, &mask->value);
 490    lp_build_flow_skip_begin(flow);
 491
 492    lp_build_mask_check(mask);
 493 }
 494
 495
 496 /**
 497  * Update boolean mask with given value (bitwise AND).
 498  * Typically used to update the quad's pixel alive/killed mask
 499  * after depth testing, alpha testing, TGSI_OPCODE_KIL, etc.
 500  */
 501 void
 502 lp_build_mask_update(struct lp_build_mask_context *mask,
 503                      LLVMValueRef value)
 504 {
 505    mask->value = LLVMBuildAnd( mask->flow->builder, mask->value, value, "");
 506
 507    lp_build_mask_check(mask);
 508 }
 509
 510
 511 /**
 512  * End section of code which is predicated on a mask.
 513  */
 514 LLVMValueRef
 515 lp_build_mask_end(struct lp_build_mask_context *mask)
 516 {
 517    lp_build_flow_skip_end(mask->flow);
 518    lp_build_flow_scope_end(mask->flow);
 519    return mask->value;
 520 }
 521
 522
 523
 524 void
 525 lp_build_loop_begin(LLVMBuilderRef builder,
 526                     LLVMValueRef start,
 527                     struct lp_build_loop_state *state)
 528 {
 529    LLVMBasicBlockRef block = LLVMGetInsertBlock(builder);
 530    LLVMValueRef function = LLVMGetBasicBlockParent(block);
 531
 532    state->block = LLVMAppendBasicBlock(function, "loop");
 533
 534    LLVMBuildBr(builder, state->block);
 535
 536    LLVMPositionBuilderAtEnd(builder, state->block);
 537
 538    state->counter = LLVMBuildPhi(builder, LLVMTypeOf(start), "");
 539
 540    LLVMAddIncoming(state->counter, &start, &block, 1);
 541
 542 }
 543
 544
 545 void
 546 lp_build_loop_end(LLVMBuilderRef builder,
 547                   LLVMValueRef end,
 548                   LLVMValueRef step,
 549                   struct lp_build_loop_state *state)
 550 {
 551    LLVMBasicBlockRef block = LLVMGetInsertBlock(builder);
 552    LLVMValueRef function = LLVMGetBasicBlockParent(block);
 553    LLVMValueRef next;
 554    LLVMValueRef cond;
 555    LLVMBasicBlockRef after_block;
 556
 557    if (!step)
 558       step = LLVMConstInt(LLVMTypeOf(end), 1, 0);
 559
 560    next = LLVMBuildAdd(builder, state->counter, step, "");
 561
 562    cond = LLVMBuildICmp(builder, LLVMIntNE, next, end, "");
 563
 564    after_block = LLVMAppendBasicBlock(function, "");
 565
 566    LLVMBuildCondBr(builder, cond, after_block, state->block);
 567
 568    LLVMAddIncoming(state->counter, &next, &block, 1);
 569
 570    LLVMPositionBuilderAtEnd(builder, after_block);
 571 }
 572
 573 void
 574 lp_build_loop_end_cond(LLVMBuilderRef builder,
 575                        LLVMValueRef end,
 576                        LLVMValueRef step,
 577                        int llvm_cond,
 578                        struct lp_build_loop_state *state)
 579 {
 580    LLVMBasicBlockRef block = LLVMGetInsertBlock(builder);
 581    LLVMValueRef function = LLVMGetBasicBlockParent(block);
 582    LLVMValueRef next;
 583    LLVMValueRef cond;
 584    LLVMBasicBlockRef after_block;
 585
 586    if (!step)
 587       step = LLVMConstInt(LLVMTypeOf(end), 1, 0);
 588
 589    next = LLVMBuildAdd(builder, state->counter, step, "");
 590
 591    cond = LLVMBuildICmp(builder, llvm_cond, next, end, "");
 592
 593    after_block = LLVMAppendBasicBlock(function, "");
 594
 595    LLVMBuildCondBr(builder, cond, after_block, state->block);
 596
 597    LLVMAddIncoming(state->counter, &next, &block, 1);
 598
 599    LLVMPositionBuilderAtEnd(builder, after_block);
 600 }
 601
 602
 603
 604 /*
 605   Example of if/then/else building:
 606
 607      int x;
 608      if (cond) {
 609         x = 1 + 2;
 610      }
 611      else {
 612         x = 2 + 3;
 613      }
 614
 615   Is built with:
 616
 617      LLVMValueRef x = LLVMGetUndef();  // or something else
 618
 619      flow = lp_build_flow_create(builder);
 620
 621         lp_build_flow_scope_begin(flow);
 622
 623            // x needs a phi node
 624            lp_build_flow_scope_declare(flow, &x);
 625
 626            lp_build_if(ctx, flow, builder, cond);
 627               x = LLVMAdd(1, 2);
 628            lp_build_else(ctx);
 629               x = LLVMAdd(2, 3);
 630            lp_build_endif(ctx);
 631
 632         lp_build_flow_scope_end(flow);
 633
 634      lp_build_flow_destroy(flow);
 635  */
 636
 637
 638
 639 /**
 640  * Begin an if/else/endif construct.
 641  */
 642 void
 643 lp_build_if(struct lp_build_if_state *ctx,
 644             struct lp_build_flow_context *flow,
 645             LLVMBuilderRef builder,
 646             LLVMValueRef condition)
 647 {
 648    LLVMBasicBlockRef block = LLVMGetInsertBlock(builder);
 649    struct lp_build_flow_if *ifthen;
 650    unsigned i;
 651
 652    memset(ctx, 0, sizeof(*ctx));
 653    ctx->builder = builder;
 654    ctx->flow = flow;
 655
 656    /* push/create new scope */
 657    ifthen = &lp_build_flow_push(flow, LP_BUILD_FLOW_IF)->ifthen;
 658    assert(ifthen);
 659
 660    ifthen->num_variables = flow->num_variables;
 661    ifthen->condition = condition;
 662    ifthen->entry_block = block;
 663
 664    /* create a Phi node for each variable in this flow scope */
 665    ifthen->phi = MALLOC(ifthen->num_variables * sizeof(*ifthen->phi));
 666    if (!ifthen->phi) {
 667       ifthen->num_variables = 0;
 668       return;
 669    }
 670
 671    /* create endif/merge basic block for the phi functions */
 672    ifthen->merge_block = lp_build_insert_new_block(builder, "endif-block");
 673    LLVMPositionBuilderAtEnd(builder, ifthen->merge_block);
 674
 675    /* create a phi node for each variable */
 676    for (i = 0; i < flow->num_variables; i++) {
 677       ifthen->phi[i] = LLVMBuildPhi(builder, LLVMTypeOf(*flow->variables[i]), "");
 678
 679       /* add add the initial value of the var from the entry block */
 680       if (!LLVMIsUndef(*flow->variables[i]))
 681          LLVMAddIncoming(ifthen->phi[i], flow->variables[i],
 682                          &ifthen->entry_block, 1);
 683    }
 684
 685    /* create/insert true_block before merge_block */
 686    ifthen->true_block = LLVMInsertBasicBlock(ifthen->merge_block, "if-true-block");
 687
 688    /* successive code goes into the true block */
 689    LLVMPositionBuilderAtEnd(builder, ifthen->true_block);
 690 }
 691
 692
 693 /**
 694  * Begin else-part of a conditional
 695  */
 696 void
 697 lp_build_else(struct lp_build_if_state *ctx)
 698 {
 699    struct lp_build_flow_context *flow = ctx->flow;
 700    struct lp_build_flow_if *ifthen;
 701    unsigned i;
 702
 703    ifthen = &lp_build_flow_peek(flow, LP_BUILD_FLOW_IF)->ifthen;
 704    assert(ifthen);
 705
 706    /* for each variable, update the Phi node with a (variable, block) pair */
 707    LLVMPositionBuilderAtEnd(ctx->builder, ifthen->merge_block);
 708    for (i = 0; i < flow->num_variables; i++) {
 709       assert(*flow->variables[i]);
 710       LLVMAddIncoming(ifthen->phi[i], flow->variables[i], &ifthen->true_block, 1);
 711    }
 712
 713    /* create/insert false_block before the merge block */
 714    ifthen->false_block = LLVMInsertBasicBlock(ifthen->merge_block, "if-false-block");
 715
 716    /* successive code goes into the else block */
 717    LLVMPositionBuilderAtEnd(ctx->builder, ifthen->false_block);
 718 }
 719
 720
 721 /**
 722  * End a conditional.
 723  */
 724 void
 725 lp_build_endif(struct lp_build_if_state *ctx)
 726 {
 727    struct lp_build_flow_context *flow = ctx->flow;
 728    struct lp_build_flow_if *ifthen;
 729    LLVMBasicBlockRef curBlock = LLVMGetInsertBlock(ctx->builder);
 730    unsigned i;
 731
 732    ifthen = &lp_build_flow_pop(flow, LP_BUILD_FLOW_IF)->ifthen;
 733    assert(ifthen);
 734
 735    /* Insert branch to the merge block from current block */
 736    LLVMBuildBr(ctx->builder, ifthen->merge_block);
 737
 738    if (ifthen->false_block) {
 739       LLVMPositionBuilderAtEnd(ctx->builder, ifthen->merge_block);
 740       /* for each variable, update the Phi node with a (variable, block) pair */
 741       for (i = 0; i < flow->num_variables; i++) {
 742          assert(*flow->variables[i]);
 743          LLVMAddIncoming(ifthen->phi[i], flow->variables[i], &curBlock, 1);
 744          /* replace the variable ref with the phi function */
 745          *flow->variables[i] = ifthen->phi[i];
 746       }
 747    }
 748    else {
 749       /* no else clause */
 750       LLVMPositionBuilderAtEnd(ctx->builder, ifthen->merge_block);
 751       for (i = 0; i < flow->num_variables; i++) {
 752          assert(*flow->variables[i]);
 753          LLVMAddIncoming(ifthen->phi[i], flow->variables[i], &ifthen->true_block, 1);
 754
 755          /* replace the variable ref with the phi function */
 756          *flow->variables[i] = ifthen->phi[i];
 757       }
 758    }
 759
 760    FREE(ifthen->phi);
 761
 762    /***
 763     *** Now patch in the various branch instructions.
 764     ***/
 765
 766    /* Insert the conditional branch instruction at the end of entry_block */
 767    LLVMPositionBuilderAtEnd(ctx->builder, ifthen->entry_block);
 768    if (ifthen->false_block) {
 769       /* we have an else clause */
 770       LLVMBuildCondBr(ctx->builder, ifthen->condition,
 771                       ifthen->true_block, ifthen->false_block);
 772    }
 773    else {
 774       /* no else clause */
 775       LLVMBuildCondBr(ctx->builder, ifthen->condition,
 776                       ifthen->true_block, ifthen->merge_block);
 777    }
 778
 779    /* Insert branch from end of true_block to merge_block */
 780    if (ifthen->false_block) {
 781       /* Append an unconditional Br(anch) instruction on the true_block */
 782       LLVMPositionBuilderAtEnd(ctx->builder, ifthen->true_block);
 783       LLVMBuildBr(ctx->builder, ifthen->merge_block);
 784    }
 785    else {
 786       /* No else clause.
 787        * Note that we've already inserted the branch at the end of
 788        * true_block.  See the very first LLVMBuildBr() call in this function.
 789        */
 790    }
 791
 792    /* Resume building code at end of the ifthen->merge_block */
 793    LLVMPositionBuilderAtEnd(ctx->builder, ifthen->merge_block);
 794 }
 795
 796
 797 /**
 798  * Allocate a scalar (or vector) variable.
 799  *
 800  * Although not strictly part of control flow, control flow has deep impact in
 801  * how variables should be allocated.
 802  *
 803  * The mem2reg optimization pass is the recommended way to dealing with mutable
 804  * variables, and SSA. It looks for allocas and if it can handle them, it
 805  * promotes them, but only looks for alloca instructions in the entry block of
 806  * the function. Being in the entry block guarantees that the alloca is only
 807  * executed once, which makes analysis simpler.
 808  *
 809  * See also:
 810  * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory
 811  */
 812 LLVMValueRef
 813 lp_build_alloca(LLVMBuilderRef builder,
 814                 LLVMTypeRef type,
 815                 const char *name)
 816 {
 817    LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder);
 818    LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
 819    LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function);
 820    LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block);
 821    LLVMBuilderRef first_builder = LLVMCreateBuilder();
 822    LLVMValueRef res;
 823
 824    LLVMPositionBuilderAtEnd(first_builder, first_block);
 825    LLVMPositionBuilderBefore(first_builder, first_instr);
 826
 827    res = LLVMBuildAlloca(first_builder, type, name);
 828
 829    LLVMDisposeBuilder(first_builder);
 830
 831    return res;
 832 }
 833
 834
 835 /**
 836  * Allocate an array of scalars/vectors.
 837  *
 838  * mem2reg pass is not capable of promoting structs or arrays to registers, but
 839  * we still put it in the first block anyway as failure to put allocas in the
 840  * first block may prevent the X86 backend from successfully align the stack as
 841  * required.
 842  *
 843  * Also the scalarrepl pass is supossedly more powerful and can promote
 844  * arrays in many cases.
 845  *
 846  * See also:
 847  * - http://www.llvm.org/docs/tutorial/OCamlLangImpl7.html#memory
 848  */
 849 LLVMValueRef
 850 lp_build_array_alloca(LLVMBuilderRef builder,
 851                       LLVMTypeRef type,
 852                       LLVMValueRef count,
 853                       const char *name)
 854 {
 855    LLVMBasicBlockRef current_block = LLVMGetInsertBlock(builder);
 856    LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
 857    LLVMBasicBlockRef first_block = LLVMGetEntryBasicBlock(function);
 858    LLVMValueRef first_instr = LLVMGetFirstInstruction(first_block);
 859    LLVMBuilderRef first_builder = LLVMCreateBuilder();
 860    LLVMValueRef res;
 861
 862    LLVMPositionBuilderBefore(first_builder, first_instr);
 863
 864    res = LLVMBuildArrayAlloca(first_builder, type, count, name);
 865
 866    LLVMDisposeBuilder(first_builder);
 867
 868    return res;
 869 }