From 71138cbe1a0a7a2be0aaf0fed38431e3c05c9d49 Mon Sep 17 00:00:00 2001 From: Dale Weiler Date: Sat, 27 Mar 2021 20:32:24 -0400 Subject: [PATCH] rewrite dead code elimination for conditionals --- ast.cpp | 30 +++++++++++++------- fold.cpp | 84 +++++++++++++++++++++++++++----------------------------- fold.h | 16 +++++++++-- 3 files changed, 74 insertions(+), 56 deletions(-) diff --git a/ast.cpp b/ast.cpp index 6d3b28a..8b4a977 100644 --- a/ast.cpp +++ b/ast.cpp @@ -2293,7 +2293,6 @@ bool ast_ifthen::codegen(ast_function *func, bool lvalue, ir_value **out) ir_block *ontrue_endblock = nullptr; ir_block *onfalse_endblock = nullptr; ir_block *merge = nullptr; - int folded = 0; /* We don't output any value, thus also don't care about r/lvalue */ (void)out; @@ -2305,16 +2304,22 @@ bool ast_ifthen::codegen(ast_function *func, bool lvalue, ir_value **out) } m_outr = (ir_value*)1; + /* try constant folding away the condition */ + switch (fold::cond_ifthen((ast_value*)m_cond, this)) { + case 0: + return true; + case fold::ON_TRUE: + return m_on_true->codegen(func, false, out); + case fold::ON_FALSE: + return m_on_false->codegen(func, false, out); + } + /* generate the condition */ if (!m_cond->codegen(func, false, &condval)) return false; /* update the block which will get the jump - because short-logic or ternaries may have changed this */ cond = func->m_curblock; - /* try constant folding away the condition */ - if ((folded = fold::cond_ifthen(condval, func, this)) != -1) - return folded; - if (m_on_true) { /* create on-true block */ ontrue = ir_function_create_block(m_context, func->m_ir_func, func->makeLabel("ontrue")); @@ -2391,7 +2396,6 @@ bool ast_ternary::codegen(ast_function *func, bool lvalue, ir_value **out) ir_block *ontrue, *ontrue_out = nullptr; ir_block *onfalse, *onfalse_out = nullptr; ir_block *merge; - int folded = 0; /* Ternary can never create an lvalue... */ if (lvalue) @@ -2407,6 +2411,16 @@ bool ast_ternary::codegen(ast_function *func, bool lvalue, ir_value **out) return true; } + /* try constant folding away the condition */ + switch (fold::cond_ternary((ast_value*)m_cond, this)) { + case 0: + return true; + case fold::ON_TRUE: + return m_on_true->codegen(func, false, out); + case fold::ON_FALSE: + return m_on_false->codegen(func, false, out); + } + /* In the following, contraty to ast_ifthen, we assume both paths exist. */ /* generate the condition */ @@ -2415,10 +2429,6 @@ bool ast_ternary::codegen(ast_function *func, bool lvalue, ir_value **out) return false; cond_out = func->m_curblock; - /* try constant folding away the condition */ - if ((folded = fold::cond_ternary(condval, func, this)) != -1) - return folded; - /* create on-true block */ ontrue = ir_function_create_block(m_context, func->m_ir_func, func->makeLabel("tern_T")); if (!ontrue) diff --git a/fold.cpp b/fold.cpp index a982bf6..56ff7f2 100644 --- a/fold.cpp +++ b/fold.cpp @@ -1066,6 +1066,47 @@ bool fold::check_inexact_float(ast_value *a, ast_value *b) { return compile_warning(ctx(), WARN_INEXACT_COMPARES, "inexact value in comparison"); } +uint32_t fold::cond(ast_value* condval, ast_ifthen *branch) { + // Optimization is disabled. + if (!OPTS_OPTIMIZATION(OPTIM_CONST_FOLD_DCE)) { + // Generate code for both. + return ON_TRUE | ON_FALSE; + } + + // Only float literals can be DCE in conditions. + if (!isfloat(condval) || !fold_can_1(condval)) { + // Generate code for both. + return ON_TRUE | ON_FALSE; + } + + qcfloat_t value = immvalue_float(condval); + + bool is_true = value != 0.0f && branch->m_on_true; + bool is_false = value == 0.0f && branch->m_on_false; + + ++opts_optimizationcount[OPTIM_CONST_FOLD_DCE]; + + // Determine which path we want to take based on constant fold. + if (is_true) { + // Generate code only for true path. + return ON_TRUE; + } else if (is_false) { + // Generate code only for false path. + return ON_FALSE; + } + + // Generate code for no paths. + return 0; +} + +uint32_t fold::cond_ternary(ast_value *condval, ast_ternary *branch) { + return cond(condval, (ast_ifthen*)branch); +} + +uint32_t fold::cond_ifthen(ast_value *condval, ast_ifthen *branch) { + return cond(condval, branch); +} + ast_expression *fold::op_mul_vec(vec3_t vec, ast_value *sel, const char *set) { qcfloat_t x = (&vec.x)[set[0]-'x']; qcfloat_t y = (&vec.x)[set[1]-'x']; @@ -1082,7 +1123,6 @@ ast_expression *fold::op_mul_vec(vec3_t vec, ast_value *sel, const char *set) { return nullptr; } - ast_expression *fold::op_neg(ast_value *a) { if (isfloat(a)) { if (fold_can_1(a)) { @@ -1637,45 +1677,3 @@ ast_expression *fold::binary(lex_ctx_t ctx, int op, ast_expression *left, ast_ex return ret; return new ast_binary(ctx, op, left, right); } - -int fold::cond(ir_value *condval, ast_function *func, ast_ifthen *branch) { - if (isfloat(condval) && fold_can_1(condval) && OPTS_OPTIMIZATION(OPTIM_CONST_FOLD_DCE)) { - ir_block *elide; - ir_value *dummy; - bool istrue = (immvalue_float(condval) != 0.0f && branch->m_on_true); - bool isfalse = (immvalue_float(condval) == 0.0f && branch->m_on_false); - ast_expression *path = (istrue) ? branch->m_on_true : - (isfalse) ? branch->m_on_false : nullptr; - if (!path) { - /* - * no path to take implies that the evaluation is if(0) and there - * is no else block. so eliminate all the code. - */ - ++opts_optimizationcount[OPTIM_CONST_FOLD_DCE]; - return true; - } - - if (!(elide = ir_function_create_block(branch->m_context, func->m_ir_func, func->makeLabel((istrue) ? "ontrue" : "onfalse")))) - return false; - if (!path->codegen(func, false, &dummy)) - return false; - if (!ir_block_create_jump(func->m_curblock, branch->m_context, elide)) - return false; - /* - * now the branch has been eliminated and the correct block for the constant evaluation - * is expanded into the current block for the function. - */ - func->m_curblock = elide; - ++opts_optimizationcount[OPTIM_CONST_FOLD_DCE]; - return true; - } - return -1; /* nothing done */ -} - -int fold::cond_ternary(ir_value *condval, ast_function *func, ast_ternary *branch) { - return cond(condval, func, (ast_ifthen*)branch); -} - -int fold::cond_ifthen(ir_value *condval, ast_function *func, ast_ifthen *branch) { - return cond(condval, func, branch); -} diff --git a/fold.h b/fold.h index 693231f..929cf37 100644 --- a/fold.h +++ b/fold.h @@ -19,12 +19,22 @@ struct fold { fold(parser_t *parser); ~fold(); + // Bitmask describing which branches of a conditional to take after folding. + // Zero indicates all the branches can be removed. + // ON_TRUE means ON_FALSE can be removed. + // ON_FALSE means ON_TRUE can be removed. + // ON_TRUE | ON_FALSE means nothing can be removed. + enum { + ON_TRUE = 1 << 0, + ON_FALSE = 1 << 1, + }; + bool generate(ir_builder *ir); ast_expression *op(const oper_info *info, ast_expression **opexprs); ast_expression *intrinsic(const char *intrinsic, size_t n_args, ast_expression **args); - static int cond_ternary(ir_value *condval, ast_function *func, ast_ternary *branch); - static int cond_ifthen(ir_value *condval, ast_function *func, ast_ifthen *branch); + static uint32_t cond_ternary(ast_value *condval, ast_ternary *branch); + static uint32_t cond_ifthen(ast_value *condval, ast_ifthen *branch); static ast_expression *superfluous(ast_expression *left, ast_expression *right, int op); static ast_expression *binary(lex_ctx_t ctx, int op, ast_expression *left, ast_expression *right); @@ -94,7 +104,7 @@ protected: static qcfloat_t immvalue_float(ir_value *value); static vec3_t immvalue_vector(ir_value *value); - static int cond(ir_value *condval, ast_function *func, ast_ifthen *branch); + static uint32_t cond(ast_value *condval, ast_ifthen *branch); private: friend struct intrin; -- 2.39.2