1 /* Lower complex operations to scalar operations.
2 Copyright (C) 2004 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
26 #include "tree-flow.h"
27 #include "tree-gimple.h"
28 #include "tree-iterator.h"
29 #include "tree-pass.h"
33 /* Force EXP to be a gimple_val. */
36 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
38 tree t, new_stmt, orig_stmt;
40 if (is_gimple_val (exp))
43 t = make_rename_temp (type, NULL);
44 new_stmt = build (MODIFY_EXPR, type, t, exp);
46 orig_stmt = bsi_stmt (*bsi);
47 SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
48 TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
50 bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
55 /* Extract the real or imaginary part of a complex variable or constant.
56 Make sure that it's a proper gimple_val and gimplify it if not.
57 Emit any new code before BSI. */
60 extract_component (block_stmt_iterator *bsi, tree t, bool imagpart_p)
64 inner_type = TREE_TYPE (TREE_TYPE (t));
65 switch (TREE_CODE (t))
68 ret = (imagpart_p ? TREE_IMAGPART (t) : TREE_REALPART (t));
72 ret = TREE_OPERAND (t, imagpart_p);
77 ret = build1 ((imagpart_p ? IMAGPART_EXPR : REALPART_EXPR),
85 return gimplify_val (bsi, inner_type, ret);
88 /* Build a binary operation and gimplify it. Emit code before BSI.
89 Return the gimple_val holding the result. */
92 do_binop (block_stmt_iterator *bsi, enum tree_code code,
93 tree type, tree a, tree b)
97 ret = fold (build (code, type, a, b));
100 return gimplify_val (bsi, type, ret);
103 /* Build a unary operation and gimplify it. Emit code before BSI.
104 Return the gimple_val holding the result. */
107 do_unop (block_stmt_iterator *bsi, enum tree_code code, tree type, tree a)
111 ret = fold (build1 (code, type, a));
114 return gimplify_val (bsi, type, ret);
117 /* Update an assignment to a complex variable in place. */
120 update_complex_assignment (block_stmt_iterator *bsi, tree r, tree i)
122 tree stmt = bsi_stmt (*bsi);
126 if (TREE_CODE (stmt) == RETURN_EXPR)
127 stmt = TREE_OPERAND (stmt, 0);
129 type = TREE_TYPE (TREE_OPERAND (stmt, 1));
130 TREE_OPERAND (stmt, 1) = build (COMPLEX_EXPR, type, r, i);
133 /* Expand complex addition to scalars:
134 a + b = (ar + br) + i(ai + bi)
135 a - b = (ar - br) + i(ai + bi)
139 expand_complex_addition (block_stmt_iterator *bsi, tree inner_type,
140 tree ar, tree ai, tree br, tree bi,
145 rr = do_binop (bsi, code, inner_type, ar, br);
146 ri = do_binop (bsi, code, inner_type, ai, bi);
148 update_complex_assignment (bsi, rr, ri);
151 /* Expand complex multiplication to scalars:
152 a * b = (ar*br - ai*bi) + i(ar*bi + br*ai)
156 expand_complex_multiplication (block_stmt_iterator *bsi, tree inner_type,
157 tree ar, tree ai, tree br, tree bi)
159 tree t1, t2, t3, t4, rr, ri;
161 t1 = do_binop (bsi, MULT_EXPR, inner_type, ar, br);
162 t2 = do_binop (bsi, MULT_EXPR, inner_type, ai, bi);
163 t3 = do_binop (bsi, MULT_EXPR, inner_type, ar, bi);
165 /* Avoid expanding redundant multiplication for the common
166 case of squaring a complex number. */
167 if (ar == br && ai == bi)
170 t4 = do_binop (bsi, MULT_EXPR, inner_type, ai, br);
172 rr = do_binop (bsi, MINUS_EXPR, inner_type, t1, t2);
173 ri = do_binop (bsi, PLUS_EXPR, inner_type, t3, t4);
175 update_complex_assignment (bsi, rr, ri);
178 /* Expand complex division to scalars, straightforward algorithm.
179 a / b = ((ar*br + ai*bi)/t) + i((ai*br - ar*bi)/t)
184 expand_complex_div_straight (block_stmt_iterator *bsi, tree inner_type,
185 tree ar, tree ai, tree br, tree bi,
188 tree rr, ri, div, t1, t2, t3;
190 t1 = do_binop (bsi, MULT_EXPR, inner_type, br, br);
191 t2 = do_binop (bsi, MULT_EXPR, inner_type, bi, bi);
192 div = do_binop (bsi, PLUS_EXPR, inner_type, t1, t2);
194 t1 = do_binop (bsi, MULT_EXPR, inner_type, ar, br);
195 t2 = do_binop (bsi, MULT_EXPR, inner_type, ai, bi);
196 t3 = do_binop (bsi, PLUS_EXPR, inner_type, t1, t2);
197 rr = do_binop (bsi, code, inner_type, t3, div);
199 t1 = do_binop (bsi, MULT_EXPR, inner_type, ai, br);
200 t2 = do_binop (bsi, MULT_EXPR, inner_type, ar, bi);
201 t3 = do_binop (bsi, MINUS_EXPR, inner_type, t1, t2);
202 ri = do_binop (bsi, code, inner_type, t3, div);
204 update_complex_assignment (bsi, rr, ri);
207 /* Expand complex division to scalars, modified algorithm to minimize
208 overflow with wide input ranges. */
211 expand_complex_div_wide (block_stmt_iterator *bsi, tree inner_type,
212 tree ar, tree ai, tree br, tree bi,
215 tree rr, ri, ratio, div, t1, t2, min, max, cond;
217 /* Examine |br| < |bi|, and branch. */
218 t1 = do_unop (bsi, ABS_EXPR, inner_type, br);
219 t2 = do_unop (bsi, ABS_EXPR, inner_type, bi);
220 cond = fold (build (LT_EXPR, boolean_type_node, t1, t2));
223 if (TREE_CONSTANT (cond))
225 if (integer_zerop (cond))
232 basic_block bb_cond, bb_true, bb_false, bb_join;
236 l1 = create_artificial_label ();
237 t1 = build (GOTO_EXPR, void_type_node, l1);
238 l2 = create_artificial_label ();
239 t2 = build (GOTO_EXPR, void_type_node, l2);
240 cond = build (COND_EXPR, void_type_node, cond, t1, t2);
241 bsi_insert_before (bsi, cond, BSI_SAME_STMT);
243 min = make_rename_temp (inner_type, NULL);
244 max = make_rename_temp (inner_type, NULL);
245 l3 = create_artificial_label ();
247 /* Split the original block, and create the TRUE and FALSE blocks. */
248 e = split_block (bsi->bb, cond);
251 bb_true = create_empty_bb (bb_cond);
252 bb_false = create_empty_bb (bb_true);
254 /* Wire the blocks together. */
255 e->flags = EDGE_TRUE_VALUE;
256 redirect_edge_succ (e, bb_true);
257 make_edge (bb_cond, bb_false, EDGE_FALSE_VALUE);
258 make_edge (bb_true, bb_join, 0);
259 make_edge (bb_false, bb_join, 0);
261 /* Update dominance info. Note that bb_join's data was
262 updated by split_block. */
263 if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
265 set_immediate_dominator (CDI_DOMINATORS, bb_true, bb_cond);
266 set_immediate_dominator (CDI_DOMINATORS, bb_false, bb_cond);
269 /* Compute min and max for TRUE block. */
270 *bsi = bsi_start (bb_true);
271 t1 = build (LABEL_EXPR, void_type_node, l1);
272 bsi_insert_after (bsi, t1, BSI_NEW_STMT);
273 t1 = build (MODIFY_EXPR, inner_type, min, br);
274 bsi_insert_after (bsi, t1, BSI_NEW_STMT);
275 t1 = build (MODIFY_EXPR, inner_type, max, bi);
276 bsi_insert_after (bsi, t1, BSI_NEW_STMT);
278 /* Compute min and max for FALSE block. */
279 *bsi = bsi_start (bb_false);
280 t1 = build (LABEL_EXPR, void_type_node, l2);
281 bsi_insert_after (bsi, t1, BSI_NEW_STMT);
282 t1 = build (MODIFY_EXPR, inner_type, min, bi);
283 bsi_insert_after (bsi, t1, BSI_NEW_STMT);
284 t1 = build (MODIFY_EXPR, inner_type, max, br);
285 bsi_insert_after (bsi, t1, BSI_NEW_STMT);
287 /* Insert the join label into the tail of the original block. */
288 *bsi = bsi_start (bb_join);
289 t1 = build (LABEL_EXPR, void_type_node, l3);
290 bsi_insert_before (bsi, t1, BSI_SAME_STMT);
293 /* Now we have MIN(|br|, |bi|) and MAX(|br|, |bi|). We now use the
294 ratio min/max to scale both the dividend and divisor. */
295 ratio = do_binop (bsi, code, inner_type, min, max);
297 /* Calculate the divisor: min*ratio + max. */
298 t1 = do_binop (bsi, MULT_EXPR, inner_type, min, ratio);
299 div = do_binop (bsi, PLUS_EXPR, inner_type, t1, max);
301 /* Result is now ((ar + ai*ratio)/div) + i((ai - ar*ratio)/div). */
302 t1 = do_binop (bsi, MULT_EXPR, inner_type, ai, ratio);
303 t2 = do_binop (bsi, PLUS_EXPR, inner_type, ar, t1);
304 rr = do_binop (bsi, code, inner_type, t2, div);
306 t1 = do_binop (bsi, MULT_EXPR, inner_type, ar, ratio);
307 t2 = do_binop (bsi, MINUS_EXPR, inner_type, ai, t1);
308 ri = do_binop (bsi, code, inner_type, t2, div);
310 update_complex_assignment (bsi, rr, ri);
313 /* Expand complex division to scalars. */
316 expand_complex_division (block_stmt_iterator *bsi, tree inner_type,
317 tree ar, tree ai, tree br, tree bi,
320 switch (flag_complex_divide_method)
323 /* straightforward implementation of complex divide acceptable. */
324 expand_complex_div_straight (bsi, inner_type, ar, ai, br, bi, code);
327 /* wide ranges of inputs must work for complex divide. */
328 expand_complex_div_wide (bsi, inner_type, ar, ai, br, bi, code);
331 /* C99-like requirements for complex divide (not yet implemented). */
336 /* Expand complex negation to scalars:
341 expand_complex_negation (block_stmt_iterator *bsi, tree inner_type,
346 rr = do_unop (bsi, NEGATE_EXPR, inner_type, ar);
347 ri = do_unop (bsi, NEGATE_EXPR, inner_type, ai);
349 update_complex_assignment (bsi, rr, ri);
352 /* Expand complex conjugate to scalars:
357 expand_complex_conjugate (block_stmt_iterator *bsi, tree inner_type,
362 ri = do_unop (bsi, NEGATE_EXPR, inner_type, ai);
364 update_complex_assignment (bsi, ar, ri);
367 /* Expand complex comparison (EQ or NE only). */
370 expand_complex_comparison (block_stmt_iterator *bsi, tree ar, tree ai,
371 tree br, tree bi, enum tree_code code)
373 tree cr, ci, cc, stmt, type;
375 cr = do_binop (bsi, code, boolean_type_node, ar, br);
376 ci = do_binop (bsi, code, boolean_type_node, ai, bi);
377 cc = do_binop (bsi, (code == EQ_EXPR ? TRUTH_AND_EXPR : TRUTH_OR_EXPR),
378 boolean_type_node, cr, ci);
380 stmt = bsi_stmt (*bsi);
383 switch (TREE_CODE (stmt))
386 stmt = TREE_OPERAND (stmt, 0);
389 type = TREE_TYPE (TREE_OPERAND (stmt, 1));
390 TREE_OPERAND (stmt, 1) = convert (type, cc);
393 TREE_OPERAND (stmt, 0) = cc;
400 /* Process one statement. If we identify a complex operation, expand it. */
403 expand_complex_operations_1 (block_stmt_iterator *bsi)
405 tree stmt = bsi_stmt (*bsi);
406 tree rhs, type, inner_type;
407 tree ac, ar, ai, bc, br, bi;
410 switch (TREE_CODE (stmt))
413 stmt = TREE_OPERAND (stmt, 0);
416 if (TREE_CODE (stmt) != MODIFY_EXPR)
421 rhs = TREE_OPERAND (stmt, 1);
425 rhs = TREE_OPERAND (stmt, 0);
432 type = TREE_TYPE (rhs);
433 code = TREE_CODE (rhs);
435 /* Initial filter for operations we handle. */
448 if (TREE_CODE (type) != COMPLEX_TYPE)
450 inner_type = TREE_TYPE (type);
455 inner_type = TREE_TYPE (TREE_OPERAND (rhs, 1));
456 if (TREE_CODE (inner_type) != COMPLEX_TYPE)
464 /* Extract the components of the two complex values. Make sure and
465 handle the common case of the same value used twice specially. */
466 ac = TREE_OPERAND (rhs, 0);
467 ar = extract_component (bsi, ac, 0);
468 ai = extract_component (bsi, ac, 1);
470 if (TREE_CODE_CLASS (code) == '1')
474 bc = TREE_OPERAND (rhs, 1);
479 br = extract_component (bsi, bc, 0);
480 bi = extract_component (bsi, bc, 1);
488 expand_complex_addition (bsi, inner_type, ar, ai, br, bi, code);
492 expand_complex_multiplication (bsi, inner_type, ar, ai, br, bi);
500 expand_complex_division (bsi, inner_type, ar, ai, br, bi, code);
504 expand_complex_negation (bsi, inner_type, ar, ai);
508 expand_complex_conjugate (bsi, inner_type, ar, ai);
513 expand_complex_comparison (bsi, ar, ai, br, bi, code);
521 /* Main loop to process each statement. */
522 /* ??? Could use dominator bits to propagate from complex_expr at the
523 same time. This might reveal more constants, particularly in cases
524 such as (complex = complex op scalar). This may not be relevant
525 after SRA and subsequent cleanups. Proof of this would be if we
526 verify that the code generated by expand_complex_div_wide is
527 simplified properly to straight-line code. */
530 expand_complex_operations (void)
532 int old_last_basic_block = last_basic_block;
533 block_stmt_iterator bsi;
538 if (bb->index >= old_last_basic_block)
540 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
541 expand_complex_operations_1 (&bsi);
545 struct tree_opt_pass pass_lower_complex =
547 "complex", /* name */
549 expand_complex_operations, /* execute */
552 0, /* static_pass_number */
554 PROP_cfg, /* properties_required */
555 0, /* properties_provided */
556 0, /* properties_destroyed */
557 0, /* todo_flags_start */
558 TODO_dump_func | TODO_rename_vars
559 | TODO_ggc_collect | TODO_verify_ssa
560 | TODO_verify_stmts | TODO_verify_flow /* todo_flags_finish */