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