src/gallium/drivers/llvmpipe/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 /**
  46  * Enumeration of all possible flow constructs.
  47  */
  48 enum lp_build_flow_construct_kind {
  49    lP_BUILD_FLOW_SCOPE,
  50    LP_BUILD_FLOW_SKIP,
  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;
  77 };
  78
  79
  80 /**
  81  * Union of all possible flow constructs' data
  82  */
  83 union lp_build_flow_construct_data
  84 {
  85    struct lp_build_flow_scope scope;
  86    struct lp_build_flow_skip skip;
  87 };
  88
  89
  90 /**
  91  * Element of the flow construct stack.
  92  */
  93 struct lp_build_flow_construct
  94 {
  95    enum lp_build_flow_construct_kind kind;
  96    union lp_build_flow_construct_data data;
  97 };
  98
  99
 100 /**
 101  * All necessary data to generate LLVM control flow constructs.
 102  *
 103  * Besides keeping track of the control flow construct themselves we also
 104  * need to keep track of variables in order to generate SSA Phi values.
 105  */
 106 struct lp_build_flow_context
 107 {
 108    LLVMBuilderRef builder;
 109
 110    /**
 111     * Control flow stack.
 112     */
 113    struct lp_build_flow_construct constructs[LP_BUILD_FLOW_MAX_DEPTH];
 114    unsigned num_constructs;
 115
 116    /**
 117     * Variable stack
 118     */
 119    LLVMValueRef *variables[LP_BUILD_FLOW_MAX_VARIABLES];
 120    unsigned num_variables;
 121 };
 122
 123
 124 struct lp_build_flow_context *
 125 lp_build_flow_create(LLVMBuilderRef builder)
 126 {
 127    struct lp_build_flow_context *flow;
 128
 129    flow = CALLOC_STRUCT(lp_build_flow_context);
 130    if(!flow)
 131       return NULL;
 132
 133    flow->builder = builder;
 134
 135    return flow;
 136 }
 137
 138
 139 void
 140 lp_build_flow_destroy(struct lp_build_flow_context *flow)
 141 {
 142    assert(flow->num_constructs == 0);
 143    assert(flow->num_variables == 0);
 144    FREE(flow);
 145 }
 146
 147
 148 static union lp_build_flow_construct_data *
 149 lp_build_flow_push(struct lp_build_flow_context *flow,
 150                    enum lp_build_flow_construct_kind kind)
 151 {
 152    assert(flow->num_constructs < LP_BUILD_FLOW_MAX_DEPTH);
 153    if(flow->num_constructs >= LP_BUILD_FLOW_MAX_DEPTH)
 154       return NULL;
 155
 156    flow->constructs[flow->num_constructs].kind = kind;
 157    return &flow->constructs[flow->num_constructs++].data;
 158 }
 159
 160
 161 static union lp_build_flow_construct_data *
 162 lp_build_flow_peek(struct lp_build_flow_context *flow,
 163                    enum lp_build_flow_construct_kind kind)
 164 {
 165    assert(flow->num_constructs);
 166    if(!flow->num_constructs)
 167       return NULL;
 168
 169    assert(flow->constructs[flow->num_constructs - 1].kind == kind);
 170    if(flow->constructs[flow->num_constructs - 1].kind != kind)
 171       return NULL;
 172
 173    return &flow->constructs[flow->num_constructs - 1].data;
 174 }
 175
 176
 177 static union lp_build_flow_construct_data *
 178 lp_build_flow_pop(struct lp_build_flow_context *flow,
 179                   enum lp_build_flow_construct_kind kind)
 180 {
 181    assert(flow->num_constructs);
 182    if(!flow->num_constructs)
 183       return NULL;
 184
 185    assert(flow->constructs[flow->num_constructs - 1].kind == kind);
 186    if(flow->constructs[flow->num_constructs - 1].kind != kind)
 187       return NULL;
 188
 189    return &flow->constructs[--flow->num_constructs].data;
 190 }
 191
 192
 193 /**
 194  * Begin a variable scope.
 195  *
 196  *
 197  */
 198 void
 199 lp_build_flow_scope_begin(struct lp_build_flow_context *flow)
 200 {
 201    struct lp_build_flow_scope *scope;
 202
 203    scope = &lp_build_flow_push(flow, lP_BUILD_FLOW_SCOPE)->scope;
 204    if(!scope)
 205       return;
 206
 207    scope->num_variables = 0;
 208 }
 209
 210
 211 /**
 212  * Declare a variable.
 213  *
 214  * A variable is a named entity which can have different LLVMValueRef's at
 215  * different points of the program. This is relevant for control flow because
 216  * when there are mutiple branches to a same location we need to replace
 217  * the variable's value with a Phi function as explained in
 218  * http://en.wikipedia.org/wiki/Static_single_assignment_form .
 219  *
 220  * We keep track of variables by keeping around a pointer to where their
 221  * current.
 222  *
 223  * There are a few cautions to observe:
 224  *
 225  * - Variable's value must not be NULL. If there is no initial value then
 226  *   LLVMGetUndef() should be used.
 227  *
 228  * - Variable's value must be kept up-to-date. If the variable is going to be
 229  *   modified by a function then a pointer should be passed so that its value
 230  *   is accurate. Failure to do this will cause some of the variables'
 231  *   transient values to be lost, leading to wrong results.
 232  *
 233  * - A program should be written from top to bottom, by always appending
 234  *   instructions to the bottom with a single LLVMBuilderRef. Inserting and/or
 235  *   modifying existing statements will most likely lead to wrong results.
 236  *
 237  */
 238 void
 239 lp_build_flow_scope_declare(struct lp_build_flow_context *flow,
 240                             LLVMValueRef *variable)
 241 {
 242    struct lp_build_flow_scope *scope;
 243
 244    scope = &lp_build_flow_peek(flow, lP_BUILD_FLOW_SCOPE)->scope;
 245    if(!scope)
 246       return;
 247
 248    assert(*variable);
 249    if(!*variable)
 250       return;
 251
 252    assert(flow->num_variables < LP_BUILD_FLOW_MAX_VARIABLES);
 253    if(flow->num_variables >= LP_BUILD_FLOW_MAX_VARIABLES)
 254       return;
 255
 256    flow->variables[flow->num_variables++] = variable;
 257    ++scope->num_variables;
 258 }
 259
 260
 261 void
 262 lp_build_flow_scope_end(struct lp_build_flow_context *flow)
 263 {
 264    struct lp_build_flow_scope *scope;
 265
 266    scope = &lp_build_flow_pop(flow, lP_BUILD_FLOW_SCOPE)->scope;
 267    if(!scope)
 268       return;
 269
 270    assert(flow->num_variables >= scope->num_variables);
 271    if(flow->num_variables < scope->num_variables) {
 272       flow->num_variables = 0;
 273       return;
 274    }
 275
 276    flow->num_variables -= scope->num_variables;
 277 }
 278
 279
 280 static LLVMBasicBlockRef
 281 lp_build_flow_insert_block(struct lp_build_flow_context *flow)
 282 {
 283    LLVMBasicBlockRef current_block;
 284    LLVMBasicBlockRef next_block;
 285    LLVMBasicBlockRef new_block;
 286
 287    current_block = LLVMGetInsertBlock(flow->builder);
 288
 289    next_block = LLVMGetNextBasicBlock(current_block);
 290    if(next_block) {
 291       new_block = LLVMInsertBasicBlock(next_block, "");
 292    }
 293    else {
 294       LLVMValueRef function = LLVMGetBasicBlockParent(current_block);
 295       new_block = LLVMAppendBasicBlock(function, "");
 296    }
 297
 298    return new_block;
 299 }
 300
 301 void
 302 lp_build_flow_skip_begin(struct lp_build_flow_context *flow)
 303 {
 304    struct lp_build_flow_skip *skip;
 305    LLVMBuilderRef builder;
 306    unsigned i;
 307
 308    skip = &lp_build_flow_push(flow, LP_BUILD_FLOW_SKIP)->skip;
 309    if(!skip)
 310       return;
 311
 312    skip->block = lp_build_flow_insert_block(flow);
 313    skip->num_variables = flow->num_variables;
 314    if(!skip->num_variables) {
 315       skip->phi = NULL;
 316       return;
 317    }
 318
 319    skip->phi = MALLOC(skip->num_variables * sizeof *skip->phi);
 320    if(!skip->phi) {
 321       skip->num_variables = 0;
 322       return;
 323    }
 324
 325    builder = LLVMCreateBuilder();
 326    LLVMPositionBuilderAtEnd(builder, skip->block);
 327
 328    for(i = 0; i < skip->num_variables; ++i)
 329       skip->phi[i] = LLVMBuildPhi(builder, LLVMTypeOf(*flow->variables[i]), "");
 330
 331    LLVMDisposeBuilder(builder);
 332 }
 333
 334
 335 void
 336 lp_build_flow_skip_cond_break(struct lp_build_flow_context *flow,
 337                               LLVMValueRef cond)
 338 {
 339    struct lp_build_flow_skip *skip;
 340    LLVMBasicBlockRef current_block;
 341    LLVMBasicBlockRef new_block;
 342    unsigned i;
 343
 344    skip = &lp_build_flow_peek(flow, LP_BUILD_FLOW_SKIP)->skip;
 345    if(!skip)
 346       return;
 347
 348    current_block = LLVMGetInsertBlock(flow->builder);
 349
 350    new_block = lp_build_flow_insert_block(flow);
 351
 352    for(i = 0; i < skip->num_variables; ++i) {
 353       assert(*flow->variables[i]);
 354       LLVMAddIncoming(skip->phi[i], flow->variables[i], &current_block, 1);
 355    }
 356
 357    LLVMBuildCondBr(flow->builder, cond, skip->block, new_block);
 358
 359    LLVMPositionBuilderAtEnd(flow->builder, new_block);
 360  }
 361
 362
 363 void
 364 lp_build_flow_skip_end(struct lp_build_flow_context *flow)
 365 {
 366    struct lp_build_flow_skip *skip;
 367    LLVMBasicBlockRef current_block;
 368    unsigned i;
 369
 370    skip = &lp_build_flow_pop(flow, LP_BUILD_FLOW_SKIP)->skip;
 371    if(!skip)
 372       return;
 373
 374    current_block = LLVMGetInsertBlock(flow->builder);
 375
 376    for(i = 0; i < skip->num_variables; ++i) {
 377       assert(*flow->variables[i]);
 378       LLVMAddIncoming(skip->phi[i], flow->variables[i], &current_block, 1);
 379       *flow->variables[i] = skip->phi[i];
 380    }
 381
 382    LLVMBuildBr(flow->builder, skip->block);
 383    LLVMPositionBuilderAtEnd(flow->builder, skip->block);
 384
 385    FREE(skip->phi);
 386 }
 387
 388
 389 void
 390 lp_build_mask_begin(struct lp_build_mask_context *mask,
 391                     struct lp_build_flow_context *flow,
 392                     union lp_type type,
 393                     LLVMValueRef value)
 394 {
 395    memset(mask, 0, sizeof *mask);
 396
 397    mask->flow = flow;
 398    mask->reg_type = LLVMIntType(type.width * type.length);
 399    mask->value = value;
 400
 401    lp_build_flow_scope_begin(flow);
 402    lp_build_flow_scope_declare(flow, &mask->value);
 403    lp_build_flow_skip_begin(flow);
 404 }
 405
 406
 407 void
 408 lp_build_mask_update(struct lp_build_mask_context *mask,
 409                      LLVMValueRef value)
 410 {
 411    LLVMBuilderRef builder = mask->flow->builder;
 412    LLVMValueRef cond;
 413
 414    mask->value = LLVMBuildAnd(builder, mask->value, value, "");
 415
 416    cond = LLVMBuildICmp(builder,
 417                         LLVMIntEQ,
 418                         LLVMBuildBitCast(builder, mask->value, mask->reg_type, ""),
 419                         LLVMConstNull(mask->reg_type),
 420                         "");
 421
 422    lp_build_flow_skip_cond_break(mask->flow, cond);
 423 }
 424
 425
 426 LLVMValueRef
 427 lp_build_mask_end(struct lp_build_mask_context *mask)
 428 {
 429    lp_build_flow_skip_end(mask->flow);
 430    lp_build_flow_scope_end(mask->flow);
 431    return mask->value;
 432 }
 433
 434
 435
 436 void
 437 lp_build_loop_begin(LLVMBuilderRef builder,
 438                     LLVMValueRef start,
 439                     struct lp_build_loop_state *state)
 440 {
 441    LLVMBasicBlockRef block = LLVMGetInsertBlock(builder);
 442    LLVMValueRef function = LLVMGetBasicBlockParent(block);
 443
 444    state->block = LLVMAppendBasicBlock(function, "loop");
 445
 446    LLVMBuildBr(builder, state->block);
 447
 448    LLVMPositionBuilderAtEnd(builder, state->block);
 449
 450    state->counter = LLVMBuildPhi(builder, LLVMTypeOf(start), "");
 451
 452    LLVMAddIncoming(state->counter, &start, &block, 1);
 453
 454 }
 455
 456
 457 void
 458 lp_build_loop_end(LLVMBuilderRef builder,
 459                   LLVMValueRef end,
 460                   LLVMValueRef step,
 461                   struct lp_build_loop_state *state)
 462 {
 463    LLVMBasicBlockRef block = LLVMGetInsertBlock(builder);
 464    LLVMValueRef function = LLVMGetBasicBlockParent(block);
 465    LLVMValueRef next;
 466    LLVMValueRef cond;
 467    LLVMBasicBlockRef after_block;
 468
 469    if (!step)
 470       step = LLVMConstInt(LLVMTypeOf(end), 1, 0);
 471
 472    next = LLVMBuildAdd(builder, state->counter, step, "");
 473
 474    cond = LLVMBuildICmp(builder, LLVMIntNE, next, end, "");
 475
 476    after_block = LLVMAppendBasicBlock(function, "");
 477
 478    LLVMBuildCondBr(builder, cond, after_block, state->block);
 479
 480    LLVMAddIncoming(state->counter, &next, &block, 1);
 481
 482    LLVMPositionBuilderAtEnd(builder, after_block);
 483 }
 484