From baeb3a23513b9045c1a50bbe21124a4f8a9b6cd6 Mon Sep 17 00:00:00 2001 From: Brian Paul Date: Wed, 6 Jan 2010 17:53:12 -0700 Subject: llvmpipe: checkpoint commit of new if/else/endif flow control Totally untested at this point. More work to do. --- src/gallium/drivers/llvmpipe/lp_bld_flow.c | 243 ++++++++++++++++++++++++++++- src/gallium/drivers/llvmpipe/lp_bld_flow.h | 27 ++++ 2 files changed, 269 insertions(+), 1 deletion(-) diff --git a/src/gallium/drivers/llvmpipe/lp_bld_flow.c b/src/gallium/drivers/llvmpipe/lp_bld_flow.c index e42b653b67..230edc6a5c 100644 --- a/src/gallium/drivers/llvmpipe/lp_bld_flow.c +++ b/src/gallium/drivers/llvmpipe/lp_bld_flow.c @@ -41,6 +41,8 @@ #define LP_BUILD_FLOW_MAX_VARIABLES 32 #define LP_BUILD_FLOW_MAX_DEPTH 32 +#define LP_BUILD_IF_MAX_VARIABLES 8 + /** * Enumeration of all possible flow constructs. @@ -48,6 +50,7 @@ enum lp_build_flow_construct_kind { LP_BUILD_FLOW_SCOPE, LP_BUILD_FLOW_SKIP, + LP_BUILD_FLOW_IF }; @@ -73,7 +76,24 @@ struct lp_build_flow_skip /** Number of variables declared at the beginning */ unsigned num_variables; - LLVMValueRef *phi; + LLVMValueRef *phi; /**< array [num_variables] */ +}; + + +/** + * if/else/endif. + */ +struct lp_build_flow_if +{ + unsigned num_variables; + + /** phi variables in the true clause */ + LLVMValueRef true_variables[LP_BUILD_IF_MAX_VARIABLES]; + unsigned num_true_variables; + + /** phi variables in the false clause */ + LLVMValueRef false_variables[LP_BUILD_IF_MAX_VARIABLES]; + unsigned num_false_variables; }; @@ -84,6 +104,7 @@ union lp_build_flow_construct_data { struct lp_build_flow_scope scope; struct lp_build_flow_skip skip; + struct lp_build_flow_if ifthen; }; @@ -540,3 +561,223 @@ lp_build_loop_end(LLVMBuilderRef builder, LLVMPositionBuilderAtEnd(builder, after_block); } + + +/* + Example of if/then/else building: + + int x; + if (cond) { + x = 1 + 2; + } + else { + x = 2 + 3; + } + + Is built with: + + flow = lp_build_flow_create(builder); + ... + + lp_build_flow_scope_declare(flow, "x"); + + lp_build_if(ctx, flow, builder, cond); + x = LLVMAdd(1, 2); + lp_build_if_phi_var(ctx, "x"); + lp_build_else(ctx); + x = LLVMAdd(2, 3); + lp_build_if_phi_var(ctx, "x"); + lp_build_endif(ctx); + + ... + + flow = lp_build_flow_end(flow); + */ + + + +/** + * Begin an if/else/endif construct. + */ +void +lp_build_if(struct lp_build_if_state *ctx, + struct lp_build_flow_context *flow, + LLVMBuilderRef builder, + LLVMValueRef condition) +{ + LLVMBasicBlockRef block = LLVMGetInsertBlock(builder); + LLVMValueRef function = LLVMGetBasicBlockParent(block); + struct lp_build_flow_if *ifthen; + + memset(ctx, 0, sizeof(*ctx)); + ctx->builder = builder; + ctx->flow = flow; + ctx->condition = condition; + ctx->entry_block = block; + + /* push/create new scope */ + ifthen = &lp_build_flow_push(flow, LP_BUILD_FLOW_IF)->ifthen; + assert(ifthen); + + ifthen->num_variables = flow->num_variables; + ifthen->num_true_variables = 0; + ifthen->num_false_variables = 0; + + /* allocate the block for the if/true clause */ + ctx->true_block = LLVMAppendBasicBlock(function, "true block"); + /* XXX is this correct ??? */ + LLVMPositionBuilderAtEnd(builder, ctx->true_block); +} + + +/** + * Begin else-part of a conditional + */ +void +lp_build_else(struct lp_build_if_state *ctx) +{ + LLVMBasicBlockRef block = LLVMGetInsertBlock(ctx->builder); + LLVMValueRef function = LLVMGetBasicBlockParent(block); + struct lp_build_flow_if *ifthen; + + ifthen = &lp_build_flow_peek(ctx->flow, LP_BUILD_FLOW_IF)->ifthen; + assert(ifthen); + + /* allocate the block for the else/false clause */ + ctx->false_block = LLVMAppendBasicBlock(function, "false block"); + /* XXX is this correct ??? */ + LLVMPositionBuilderAtEnd(ctx->builder, ctx->false_block); +} + + +/** + * End a conditional. + * This involves building a "merge" block at the endif which + * contains the phi instructions. + */ +void +lp_build_endif(struct lp_build_if_state *ctx) +{ + LLVMBasicBlockRef block = LLVMGetInsertBlock(ctx->builder); + LLVMValueRef function = LLVMGetBasicBlockParent(block); + LLVMBasicBlockRef merge_block = LLVMAppendBasicBlock(function, "endif block"); + LLVMValueRef phi[LP_BUILD_FLOW_MAX_VARIABLES]; + struct lp_build_flow_if *ifthen; + unsigned i; + + /* build the endif/merge block now */ + /* XXX this is probably wrong */ + LLVMPositionBuilderAtEnd(ctx->builder, merge_block); + + ifthen = &lp_build_flow_pop(ctx->flow, LP_BUILD_FLOW_IF)->ifthen; + assert(ifthen); + + memset(phi, 0, sizeof(phi)); + + /* build phi nodes for any variables which were declared inside if part */ + + for (i = 0; i < ifthen->num_variables; i++) { + LLVMValueRef *var = ctx->flow->variables[i]; + const char *name = LLVMGetValueName(*var); + unsigned j; + + /* search true-clause variables list for 'name' */ + for (j = 0; j < ifthen->num_true_variables; j++) { + LLVMValueRef v = ifthen->true_variables[j]; + if (strcmp(LLVMGetValueName(v), name) == 0) { + /* add phi */ + if (!phi[i]) + phi[i] = LLVMBuildPhi(ctx->builder, LLVMTypeOf(*var), ""); + LLVMAddIncoming(phi[i], &v, &ctx->true_block, 1); + } + } + + /* search false-clause variables list for 'name' */ + for (j = 0; j < ifthen->num_false_variables; j++) { + LLVMValueRef v = ifthen->false_variables[j]; + if (strcmp(LLVMGetValueName(v), name) == 0) { + /* add phi */ + if (!phi[i]) + phi[i] = LLVMBuildPhi(ctx->builder, LLVMTypeOf(*var), ""); + LLVMAddIncoming(phi[i], &v, &ctx->false_block, 1); + } + } + + /* "return" new phi variable to calling code */ + if (phi[i]) + *var = phi[i]; + } + + /*** + *** Insert the various branch instructions here. + *** XXX need to verify all the builder/block positioning is correct. + ***/ + + /* Insert the conditional branch instruction at the end of entry_block */ + LLVMPositionBuilderAtEnd(ctx->builder, ctx->entry_block); + + if (ctx->false_block) { + /* we have an else clause */ + LLVMBuildCondBr(ctx->builder, ctx->condition, + ctx->true_block, ctx->false_block); + } + else { + /* no else clause */ + LLVMBuildCondBr(ctx->builder, ctx->condition, + ctx->true_block, merge_block); + } + + /* Append an unconditional Br(anch) instruction on the true_block */ + LLVMPositionBuilderAtEnd(ctx->builder, ctx->true_block); + LLVMBuildBr(ctx->builder, merge_block); + if (ctx->false_block) { + /* Append an unconditional Br(anch) instruction on the false_block */ + LLVMPositionBuilderAtEnd(ctx->builder, ctx->false_block); + LLVMBuildBr(ctx->builder, merge_block); + } + + + /* Finish-up: continue building at end of the merge_block */ + /* XXX is this right? */ + LLVMPositionBuilderAtEnd(ctx->builder, merge_block); +} + + +/** + * Declare a variable that needs to be merged with another variable + * via a phi function. + * This function must be called after lp_build_if() and lp_build_endif(). + */ +void +lp_build_if_phi_var(struct lp_build_if_state *ctx, LLVMValueRef var) +{ + struct lp_build_flow_if *ifthen; + const char *name; + + name = LLVMGetValueName(var); + assert(name && "variable requires a name"); + + /* make sure the var existed before the if/then/else */ + { + boolean found = FALSE; + uint i; + for (i = 0; i < ctx->flow->num_variables; i++) { + LLVMValueRef *var = ctx->flow->variables[i]; + if (strcmp(LLVMGetValueName(*var), name) == 0) { + found = TRUE; + break; + } + } + assert(found); + } + + ifthen = &lp_build_flow_pop(ctx->flow, LP_BUILD_FLOW_IF)->ifthen; + + if (ctx->false_block) { + ifthen->false_variables[ifthen->num_false_variables++] = var; + } + else { + assert(ctx->true_block); + ifthen->true_variables[ifthen->num_true_variables++] = var; + } +} diff --git a/src/gallium/drivers/llvmpipe/lp_bld_flow.h b/src/gallium/drivers/llvmpipe/lp_bld_flow.h index e61999ff06..1f294b8a49 100644 --- a/src/gallium/drivers/llvmpipe/lp_bld_flow.h +++ b/src/gallium/drivers/llvmpipe/lp_bld_flow.h @@ -126,4 +126,31 @@ lp_build_loop_end(LLVMBuilderRef builder, + +struct lp_build_if_state +{ + LLVMBuilderRef builder; + struct lp_build_flow_context *flow; + LLVMValueRef condition; + LLVMBasicBlockRef entry_block, true_block, false_block; +}; + + +void +lp_build_if(struct lp_build_if_state *ctx, + struct lp_build_flow_context *flow, + LLVMBuilderRef builder, + LLVMValueRef condition); + +void +lp_build_if_phi_var(struct lp_build_if_state *ctx, LLVMValueRef var); + +void +lp_build_else(struct lp_build_if_state *ctx); + +void +lp_build_endif(struct lp_build_if_state *ctx); + + + #endif /* !LP_BLD_FLOW_H */ -- cgit v1.2.3