diff options
Diffstat (limited to 'gcc/tree-complex.c')
| -rw-r--r-- | gcc/tree-complex.c | 572 |
1 files changed, 572 insertions, 0 deletions
diff --git a/gcc/tree-complex.c b/gcc/tree-complex.c new file mode 100644 index 00000000000..fe963041a05 --- /dev/null +++ b/gcc/tree-complex.c @@ -0,0 +1,572 @@ +/* Lower complex operations to scalar operations. + Copyright (C) 2004 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 2, or (at your option) any +later version. + +GCC is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING. If not, write to the Free +Software Foundation, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tree.h" +#include "tm.h" +#include "tree-flow.h" +#include "tree-simple.h" +#include "tree-iterator.h" +#include "tree-pass.h" +#include "flags.h" + + +/* Build a temporary. Make sure and register it to be renamed. */ + +static tree +make_temp (tree type) +{ + tree t = create_tmp_var (type, NULL); + add_referenced_tmp_var (t); + bitmap_set_bit (vars_to_rename, var_ann (t)->uid); + return t; +} + +/* Force EXP to be a gimple_val. */ + +static tree +gimplify_val (block_stmt_iterator *bsi, tree type, tree exp) +{ + tree t, new_stmt, orig_stmt; + + if (is_gimple_val (exp)) + return exp; + + t = make_temp (type); + new_stmt = build (MODIFY_EXPR, type, t, exp); + + orig_stmt = bsi_stmt (*bsi); + SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt)); + TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt); + + bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT); + + return t; +} + +/* Extract the real or imaginary part of a complex variable or constant. + Make sure that it's a proper gimple_val and gimplify it if not. + Emit any new code before BSI. */ + +static tree +extract_component (block_stmt_iterator *bsi, tree t, bool imagpart_p) +{ + tree ret, inner_type; + + inner_type = TREE_TYPE (TREE_TYPE (t)); + switch (TREE_CODE (t)) + { + case COMPLEX_CST: + ret = (imagpart_p ? TREE_IMAGPART (t) : TREE_REALPART (t)); + break; + + case COMPLEX_EXPR: + ret = TREE_OPERAND (t, imagpart_p); + break; + + case VAR_DECL: + case PARM_DECL: + ret = build1 ((imagpart_p ? IMAGPART_EXPR : REALPART_EXPR), + inner_type, t); + break; + + default: + abort (); + } + + return gimplify_val (bsi, inner_type, ret); +} + +/* Build a binary operation and gimplify it. Emit code before BSI. + Return the gimple_val holding the result. */ + +static tree +do_binop (block_stmt_iterator *bsi, enum tree_code code, + tree type, tree a, tree b) +{ + tree ret; + + ret = fold (build (code, type, a, b)); + STRIP_NOPS (ret); + + return gimplify_val (bsi, type, ret); +} + +/* Build a unary operation and gimplify it. Emit code before BSI. + Return the gimple_val holding the result. */ + +static tree +do_unop (block_stmt_iterator *bsi, enum tree_code code, tree type, tree a) +{ + tree ret; + + ret = fold (build1 (code, type, a)); + STRIP_NOPS (ret); + + return gimplify_val (bsi, type, ret); +} + +/* Update an assignment to a complex variable in place. */ + +static void +update_complex_assignment (block_stmt_iterator *bsi, tree r, tree i) +{ + tree stmt = bsi_stmt (*bsi); + tree type; + + modify_stmt (stmt); + if (TREE_CODE (stmt) == RETURN_EXPR) + stmt = TREE_OPERAND (stmt, 0); + + type = TREE_TYPE (TREE_OPERAND (stmt, 1)); + TREE_OPERAND (stmt, 1) = build (COMPLEX_EXPR, type, r, i); +} + +/* Expand complex addition to scalars: + a + b = (ar + br) + i(ai + bi) + a - b = (ar - br) + i(ai + bi) +*/ + +static void +expand_complex_addition (block_stmt_iterator *bsi, tree inner_type, + tree ar, tree ai, tree br, tree bi, + enum tree_code code) +{ + tree rr, ri; + + rr = do_binop (bsi, code, inner_type, ar, br); + ri = do_binop (bsi, code, inner_type, ai, bi); + + update_complex_assignment (bsi, rr, ri); +} + +/* Expand complex multiplication to scalars: + a * b = (ar*br - ai*bi) + i(ar*bi + br*ai) +*/ + +static void +expand_complex_multiplication (block_stmt_iterator *bsi, tree inner_type, + tree ar, tree ai, tree br, tree bi) +{ + tree t1, t2, t3, t4, rr, ri; + + t1 = do_binop (bsi, MULT_EXPR, inner_type, ar, br); + t2 = do_binop (bsi, MULT_EXPR, inner_type, ai, bi); + t3 = do_binop (bsi, MULT_EXPR, inner_type, ar, bi); + + /* Avoid expanding redundant multiplication for the common + case of squaring a complex number. */ + if (ar == br && ai == bi) + t4 = t3; + else + t4 = do_binop (bsi, MULT_EXPR, inner_type, ai, br); + + rr = do_binop (bsi, MINUS_EXPR, inner_type, t1, t2); + ri = do_binop (bsi, PLUS_EXPR, inner_type, t3, t4); + + update_complex_assignment (bsi, rr, ri); +} + +/* Expand complex division to scalars, straightforward algorithm. + a / b = ((ar*br + ai*bi)/t) + i((ai*br - ar*bi)/t) + t = br*br + bi*bi +*/ + +static void +expand_complex_div_straight (block_stmt_iterator *bsi, tree inner_type, + tree ar, tree ai, tree br, tree bi, + enum tree_code code) +{ + tree rr, ri, div, t1, t2, t3; + + t1 = do_binop (bsi, MULT_EXPR, inner_type, br, br); + t2 = do_binop (bsi, MULT_EXPR, inner_type, bi, bi); + div = do_binop (bsi, PLUS_EXPR, inner_type, t1, t2); + + t1 = do_binop (bsi, MULT_EXPR, inner_type, ar, br); + t2 = do_binop (bsi, MULT_EXPR, inner_type, ai, bi); + t3 = do_binop (bsi, PLUS_EXPR, inner_type, t1, t2); + rr = do_binop (bsi, code, inner_type, t3, div); + + t1 = do_binop (bsi, MULT_EXPR, inner_type, ai, br); + t2 = do_binop (bsi, MULT_EXPR, inner_type, ar, bi); + t3 = do_binop (bsi, MINUS_EXPR, inner_type, t1, t2); + ri = do_binop (bsi, code, inner_type, t3, div); + + update_complex_assignment (bsi, rr, ri); +} + +/* Expand complex division to scalars, modified algorithm to minimize + overflow with wide input ranges. */ + +static void +expand_complex_div_wide (block_stmt_iterator *bsi, tree inner_type, + tree ar, tree ai, tree br, tree bi, + enum tree_code code) +{ + tree rr, ri, ratio, div, t1, t2, min, max, cond; + + /* Examine |br| < |bi|, and branch. */ + t1 = do_unop (bsi, ABS_EXPR, inner_type, br); + t2 = do_unop (bsi, ABS_EXPR, inner_type, bi); + cond = fold (build (LT_EXPR, boolean_type_node, t1, t2)); + STRIP_NOPS (cond); + + if (TREE_CONSTANT (cond)) + { + if (integer_zerop (cond)) + min = bi, max = br; + else + min = br, max = bi; + } + else + { + basic_block bb_cond, bb_true, bb_false, bb_join; + tree l1, l2, l3; + edge e; + + l1 = create_artificial_label (); + t1 = build (GOTO_EXPR, void_type_node, l1); + l2 = create_artificial_label (); + t2 = build (GOTO_EXPR, void_type_node, l2); + cond = build (COND_EXPR, void_type_node, cond, t1, t2); + bsi_insert_before (bsi, cond, BSI_SAME_STMT); + + min = make_temp (inner_type); + max = make_temp (inner_type); + l3 = create_artificial_label (); + + /* Split the original block, and create the TRUE and FALSE blocks. */ + e = split_block (bsi->bb, cond); + bb_cond = e->src; + bb_join = e->dest; + bb_true = create_empty_bb (bb_cond); + bb_false = create_empty_bb (bb_true); + + /* Wire the blocks together. */ + e->flags = EDGE_TRUE_VALUE; + redirect_edge_succ (e, bb_true); + make_edge (bb_cond, bb_false, EDGE_FALSE_VALUE); + make_edge (bb_true, bb_join, 0); + make_edge (bb_false, bb_join, 0); + + /* Update dominance info. Note that bb_join's data was + updated by split_block. */ + if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK) + { + set_immediate_dominator (CDI_DOMINATORS, bb_true, bb_cond); + set_immediate_dominator (CDI_DOMINATORS, bb_false, bb_cond); + } + + /* Compute min and max for TRUE block. */ + *bsi = bsi_start (bb_true); + t1 = build (LABEL_EXPR, void_type_node, l1); + bsi_insert_after (bsi, t1, BSI_NEW_STMT); + t1 = build (MODIFY_EXPR, inner_type, min, br); + bsi_insert_after (bsi, t1, BSI_NEW_STMT); + t1 = build (MODIFY_EXPR, inner_type, max, bi); + bsi_insert_after (bsi, t1, BSI_NEW_STMT); + + /* Compute min and max for FALSE block. */ + *bsi = bsi_start (bb_false); + t1 = build (LABEL_EXPR, void_type_node, l2); + bsi_insert_after (bsi, t1, BSI_NEW_STMT); + t1 = build (MODIFY_EXPR, inner_type, min, bi); + bsi_insert_after (bsi, t1, BSI_NEW_STMT); + t1 = build (MODIFY_EXPR, inner_type, max, br); + bsi_insert_after (bsi, t1, BSI_NEW_STMT); + + /* Insert the join label into the tail of the original block. */ + *bsi = bsi_start (bb_join); + t1 = build (LABEL_EXPR, void_type_node, l3); + bsi_insert_before (bsi, t1, BSI_SAME_STMT); + } + + /* Now we have MIN(|br|, |bi|) and MAX(|br|, |bi|). We now use the + ratio min/max to scale both the dividend and divisor. */ + ratio = do_binop (bsi, code, inner_type, min, max); + + /* Calculate the divisor: min*ratio + max. */ + t1 = do_binop (bsi, MULT_EXPR, inner_type, min, ratio); + div = do_binop (bsi, PLUS_EXPR, inner_type, t1, max); + + /* Result is now ((ar + ai*ratio)/div) + i((ai - ar*ratio)/div). */ + t1 = do_binop (bsi, MULT_EXPR, inner_type, ai, ratio); + t2 = do_binop (bsi, PLUS_EXPR, inner_type, ar, t1); + rr = do_binop (bsi, code, inner_type, t2, div); + + t1 = do_binop (bsi, MULT_EXPR, inner_type, ar, ratio); + t2 = do_binop (bsi, MINUS_EXPR, inner_type, ai, t1); + ri = do_binop (bsi, code, inner_type, t2, div); + + update_complex_assignment (bsi, rr, ri); +} + +/* Expand complex division to scalars. */ + +static void +expand_complex_division (block_stmt_iterator *bsi, tree inner_type, + tree ar, tree ai, tree br, tree bi, + enum tree_code code) +{ + switch (flag_complex_divide_method) + { + case 0: + /* straightforward implementation of complex divide acceptable. */ + expand_complex_div_straight (bsi, inner_type, ar, ai, br, bi, code); + break; + case 1: + /* wide ranges of inputs must work for complex divide. */ + expand_complex_div_wide (bsi, inner_type, ar, ai, br, bi, code); + break; + default: + /* C99-like requirements for complex divide (not yet implemented). */ + abort (); + } +} + +/* Expand complex negation to scalars: + -a = (-ar) + i(-ai) +*/ + +static void +expand_complex_negation (block_stmt_iterator *bsi, tree inner_type, + tree ar, tree ai) +{ + tree rr, ri; + + rr = do_unop (bsi, NEGATE_EXPR, inner_type, ar); + ri = do_unop (bsi, NEGATE_EXPR, inner_type, ai); + + update_complex_assignment (bsi, rr, ri); +} + +/* Expand complex conjugate to scalars: + ~a = (ar) + i(-ai) +*/ + +static void +expand_complex_conjugate (block_stmt_iterator *bsi, tree inner_type, + tree ar, tree ai) +{ + tree ri; + + ri = do_unop (bsi, NEGATE_EXPR, inner_type, ai); + + update_complex_assignment (bsi, ar, ri); +} + +/* Expand complex comparison (EQ or NE only). */ + +static void +expand_complex_comparison (block_stmt_iterator *bsi, tree ar, tree ai, + tree br, tree bi, enum tree_code code) +{ + tree cr, ci, cc, stmt, type; + + cr = do_binop (bsi, code, boolean_type_node, ar, br); + ci = do_binop (bsi, code, boolean_type_node, ai, bi); + cc = do_binop (bsi, (code == EQ_EXPR ? TRUTH_AND_EXPR : TRUTH_OR_EXPR), + boolean_type_node, cr, ci); + + stmt = bsi_stmt (*bsi); + modify_stmt (stmt); + + switch (TREE_CODE (stmt)) + { + case RETURN_EXPR: + stmt = TREE_OPERAND (stmt, 0); + /* FALLTHRU */ + case MODIFY_EXPR: + type = TREE_TYPE (TREE_OPERAND (stmt, 1)); + TREE_OPERAND (stmt, 1) = convert (type, cc); + break; + case COND_EXPR: + TREE_OPERAND (stmt, 0) = cc; + break; + default: + abort (); + } +} + +/* Process one statement. If we identify a complex operation, expand it. */ + +static void +expand_complex_operations_1 (block_stmt_iterator *bsi) +{ + tree stmt = bsi_stmt (*bsi); + tree rhs, type, inner_type; + tree ac, ar, ai, bc, br, bi; + enum tree_code code; + + switch (TREE_CODE (stmt)) + { + case RETURN_EXPR: + stmt = TREE_OPERAND (stmt, 0); + if (!stmt) + return; + if (TREE_CODE (stmt) != MODIFY_EXPR) + return; + /* FALLTHRU */ + + case MODIFY_EXPR: + rhs = TREE_OPERAND (stmt, 1); + break; + + case COND_EXPR: + rhs = TREE_OPERAND (stmt, 0); + break; + + default: + return; + } + + type = TREE_TYPE (rhs); + code = TREE_CODE (rhs); + + /* Initial filter for operations we handle. */ + switch (code) + { + case PLUS_EXPR: + case MINUS_EXPR: + case MULT_EXPR: + case TRUNC_DIV_EXPR: + case CEIL_DIV_EXPR: + case FLOOR_DIV_EXPR: + case ROUND_DIV_EXPR: + case RDIV_EXPR: + case NEGATE_EXPR: + case CONJ_EXPR: + if (TREE_CODE (type) != COMPLEX_TYPE) + return; + inner_type = TREE_TYPE (type); + break; + + case EQ_EXPR: + case NE_EXPR: + inner_type = TREE_TYPE (TREE_OPERAND (rhs, 1)); + if (TREE_CODE (inner_type) != COMPLEX_TYPE) + return; + break; + + default: + return; + } + + /* Extract the components of the two complex values. Make sure and + handle the common case of the same value used twice specially. */ + ac = TREE_OPERAND (rhs, 0); + ar = extract_component (bsi, ac, 0); + ai = extract_component (bsi, ac, 1); + + if (TREE_CODE_CLASS (code) == '1') + bc = br = bi = NULL; + else + { + bc = TREE_OPERAND (rhs, 1); + if (ac == bc) + br = ar, bi = ai; + else + { + br = extract_component (bsi, bc, 0); + bi = extract_component (bsi, bc, 1); + } + } + + switch (code) + { + case PLUS_EXPR: + case MINUS_EXPR: + expand_complex_addition (bsi, inner_type, ar, ai, br, bi, code); + break; + + case MULT_EXPR: + expand_complex_multiplication (bsi, inner_type, ar, ai, br, bi); + break; + + case TRUNC_DIV_EXPR: + case CEIL_DIV_EXPR: + case FLOOR_DIV_EXPR: + case ROUND_DIV_EXPR: + case RDIV_EXPR: + expand_complex_division (bsi, inner_type, ar, ai, br, bi, code); + break; + + case NEGATE_EXPR: + expand_complex_negation (bsi, inner_type, ar, ai); + break; + + case CONJ_EXPR: + expand_complex_conjugate (bsi, inner_type, ar, ai); + break; + + case EQ_EXPR: + case NE_EXPR: + expand_complex_comparison (bsi, ar, ai, br, bi, code); + break; + + default: + abort (); + } +} + +/* Main loop to process each statement. */ +/* ??? Could use dominator bits to propagate from complex_expr at the + same time. This might reveal more constants, particularly in cases + such as (complex = complex op scalar). This may not be relevant + after SRA and subsequent cleanups. Proof of this would be if we + verify that the code generated by expand_complex_div_wide is + simplified properly to straight-line code. */ + +static void +expand_complex_operations (void) +{ + int old_last_basic_block = last_basic_block; + block_stmt_iterator bsi; + basic_block bb; + + FOR_EACH_BB (bb) + { + if (bb->index >= old_last_basic_block) + continue; + for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + expand_complex_operations_1 (&bsi); + } +} + +struct tree_opt_pass pass_lower_complex = +{ + "complex", /* name */ + NULL, /* gate */ + expand_complex_operations, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + 0, /* tv_id */ + PROP_cfg, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func | TODO_rename_vars + | TODO_ggc_collect | TODO_verify_ssa + | TODO_verify_stmts | TODO_verify_flow /* todo_flags_finish */ +}; |