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