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
 574
 575 /*
 576   Example of if/then/else building:
 577
 578      int x;
 579      if (cond) {
 580         x = 1 + 2;
 581      }
 582      else {
 583         x = 2 + 3;
 584      }
 585
 586   Is built with:
 587
 588      LLVMValueRef x = LLVMGetUndef();  // or something else
 589
 590      flow = lp_build_flow_create(builder);
 591
 592         lp_build_flow_scope_begin(flow);
 593
 594            // x needs a phi node
 595            lp_build_flow_scope_declare(flow, &x);
 596
 597            lp_build_if(ctx, flow, builder, cond);
 598               x = LLVMAdd(1, 2);
 599            lp_build_else(ctx);
 600               x = LLVMAdd(2, 3);
 601            lp_build_endif(ctx);
 602
 603         lp_build_flow_scope_end(flow);
 604
 605      lp_build_flow_destroy(flow);
 606  */
 607
 608
 609
 610 /**
 611  * Begin an if/else/endif construct.
 612  */
 613 void
 614 lp_build_if(struct lp_build_if_state *ctx,
 615             struct lp_build_flow_context *flow,
 616             LLVMBuilderRef builder,
 617             LLVMValueRef condition)
 618 {
 619    LLVMBasicBlockRef block = LLVMGetInsertBlock(builder);
 620    struct lp_build_flow_if *ifthen;
 621    unsigned i;
 622
 623    memset(ctx, 0, sizeof(*ctx));
 624    ctx->builder = builder;
 625    ctx->flow = flow;
 626
 627    /* push/create new scope */
 628    ifthen = &lp_build_flow_push(flow, LP_BUILD_FLOW_IF)->ifthen;
 629    assert(ifthen);
 630
 631    ifthen->num_variables = flow->num_variables;
 632    ifthen->condition = condition;
 633    ifthen->entry_block = block;
 634
 635    /* create a Phi node for each variable in this flow scope */
 636    ifthen->phi = MALLOC(ifthen->num_variables * sizeof(*ifthen->phi));
 637    if (!ifthen->phi) {
 638       ifthen->num_variables = 0;
 639       return;
 640    }
 641
 642    /* create endif/merge basic block for the phi functions */
 643    ifthen->merge_block = lp_build_insert_new_block(builder, "endif-block");
 644    LLVMPositionBuilderAtEnd(builder, ifthen->merge_block);
 645
 646    /* create a phi node for each variable */
 647    for (i = 0; i < flow->num_variables; i++) {
 648       ifthen->phi[i] = LLVMBuildPhi(builder, LLVMTypeOf(*flow->variables[i]), "");
 649
 650       /* add add the initial value of the var from the entry block */
 651       if (!LLVMIsUndef(*flow->variables[i]))
 652          LLVMAddIncoming(ifthen->phi[i], flow->variables[i],
 653                          &ifthen->entry_block, 1);
 654    }
 655
 656    /* create/insert true_block before merge_block */
 657    ifthen->true_block = LLVMInsertBasicBlock(ifthen->merge_block, "if-true-block");
 658
 659    /* successive code goes into the true block */
 660    LLVMPositionBuilderAtEnd(builder, ifthen->true_block);
 661 }
 662
 663
 664 /**
 665  * Begin else-part of a conditional
 666  */
 667 void
 668 lp_build_else(struct lp_build_if_state *ctx)
 669 {
 670    struct lp_build_flow_context *flow = ctx->flow;
 671    struct lp_build_flow_if *ifthen;
 672    unsigned i;
 673
 674    ifthen = &lp_build_flow_peek(flow, LP_BUILD_FLOW_IF)->ifthen;
 675    assert(ifthen);
 676
 677    /* for each variable, update the Phi node with a (variable, block) pair */
 678    LLVMPositionBuilderAtEnd(ctx->builder, ifthen->merge_block);
 679    for (i = 0; i < flow->num_variables; i++) {
 680       assert(*flow->variables[i]);
 681       LLVMAddIncoming(ifthen->phi[i], flow->variables[i], &ifthen->true_block, 1);
 682    }
 683
 684    /* create/insert false_block before the merge block */
 685    ifthen->false_block = LLVMInsertBasicBlock(ifthen->merge_block, "if-false-block");
 686
 687    /* successive code goes into the else block */
 688    LLVMPositionBuilderAtEnd(ctx->builder, ifthen->false_block);
 689 }
 690
 691
 692 /**
 693  * End a conditional.
 694  */
 695 void
 696 lp_build_endif(struct lp_build_if_state *ctx)
 697 {
 698    struct lp_build_flow_context *flow = ctx->flow;
 699    struct lp_build_flow_if *ifthen;
 700    LLVMBasicBlockRef curBlock = LLVMGetInsertBlock(ctx->builder);
 701    unsigned i;
 702
 703    ifthen = &lp_build_flow_pop(flow, LP_BUILD_FLOW_IF)->ifthen;
 704    assert(ifthen);
 705
 706    /* Insert branch to the merge block from current block */
 707    LLVMBuildBr(ctx->builder, ifthen->merge_block);
 708
 709    if (ifthen->false_block) {
 710       LLVMPositionBuilderAtEnd(ctx->builder, ifthen->merge_block);
 711       /* for each variable, update the Phi node with a (variable, block) pair */
 712       for (i = 0; i < flow->num_variables; i++) {
 713          assert(*flow->variables[i]);
 714          LLVMAddIncoming(ifthen->phi[i], flow->variables[i], &curBlock, 1);
 715          /* replace the variable ref with the phi function */
 716          *flow->variables[i] = ifthen->phi[i];
 717       }
 718    }
 719    else {
 720       /* no else clause */
 721       LLVMPositionBuilderAtEnd(ctx->builder, ifthen->merge_block);
 722       for (i = 0; i < flow->num_variables; i++) {
 723          assert(*flow->variables[i]);
 724          LLVMAddIncoming(ifthen->phi[i], flow->variables[i], &ifthen->true_block, 1);
 725
 726          /* replace the variable ref with the phi function */
 727          *flow->variables[i] = ifthen->phi[i];
 728       }
 729    }
 730
 731    FREE(ifthen->phi);
 732
 733    /***
 734     *** Now patch in the various branch instructions.
 735     ***/
 736
 737    /* Insert the conditional branch instruction at the end of entry_block */
 738    LLVMPositionBuilderAtEnd(ctx->builder, ifthen->entry_block);
 739    if (ifthen->false_block) {
 740       /* we have an else clause */
 741       LLVMBuildCondBr(ctx->builder, ifthen->condition,
 742                       ifthen->true_block, ifthen->false_block);
 743    }
 744    else {
 745       /* no else clause */
 746       LLVMBuildCondBr(ctx->builder, ifthen->condition,
 747                       ifthen->true_block, ifthen->merge_block);
 748    }
 749
 750    /* Insert branch from end of true_block to merge_block */
 751    if (ifthen->false_block) {
 752       /* Append an unconditional Br(anch) instruction on the true_block */
 753       LLVMPositionBuilderAtEnd(ctx->builder, ifthen->true_block);
 754       LLVMBuildBr(ctx->builder, ifthen->merge_block);
 755    }
 756    else {
 757       /* No else clause.
 758        * Note that we've already inserted the branch at the end of
 759        * true_block.  See the very first LLVMBuildBr() call in this function.
 760        */
 761    }
 762
 763    /* Resume building code at end of the ifthen->merge_block */
 764    LLVMPositionBuilderAtEnd(ctx->builder, ifthen->merge_block);
 765 }