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 /* Build a temporary. Make sure and register it to be renamed. */
38 tree t = create_tmp_var (type, NULL);
39 add_referenced_tmp_var (t);
40 bitmap_set_bit (vars_to_rename, var_ann (t)->uid);
44 /* Force EXP to be a gimple_val. */
47 gimplify_val (block_stmt_iterator *bsi, tree type, tree exp)
49 tree t, new_stmt, orig_stmt;
51 if (is_gimple_val (exp))
55 new_stmt = build (MODIFY_EXPR, type, t, exp);
57 orig_stmt = bsi_stmt (*bsi);
58 SET_EXPR_LOCUS (new_stmt, EXPR_LOCUS (orig_stmt));
59 TREE_BLOCK (new_stmt) = TREE_BLOCK (orig_stmt);
61 bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
66 /* Extract the real or imaginary part of a complex variable or constant.
67 Make sure that it's a proper gimple_val and gimplify it if not.
68 Emit any new code before BSI. */
71 extract_component (block_stmt_iterator *bsi, tree t, bool imagpart_p)
75 inner_type = TREE_TYPE (TREE_TYPE (t));
76 switch (TREE_CODE (t))
79 ret = (imagpart_p ? TREE_IMAGPART (t) : TREE_REALPART (t));
83 ret = TREE_OPERAND (t, imagpart_p);
88 ret = build1 ((imagpart_p ? IMAGPART_EXPR : REALPART_EXPR),
96 return gimplify_val (bsi, inner_type, ret);
99 /* Build a binary operation and gimplify it. Emit code before BSI.
100 Return the gimple_val holding the result. */
103 do_binop (block_stmt_iterator *bsi, enum tree_code code,
104 tree type, tree a, tree b)
108 ret = fold (build (code, type, a, b));
111 return gimplify_val (bsi, type, ret);
114 /* Build a unary operation and gimplify it. Emit code before BSI.
115 Return the gimple_val holding the result. */
118 do_unop (block_stmt_iterator *bsi, enum tree_code code, tree type, tree a)
122 ret = fold (build1 (code, type, a));
125 return gimplify_val (bsi, type, ret);
128 /* Update an assignment to a complex variable in place. */
131 update_complex_assignment (block_stmt_iterator *bsi, tree r, tree i)
133 tree stmt = bsi_stmt (*bsi);
137 if (TREE_CODE (stmt) == RETURN_EXPR)
138 stmt = TREE_OPERAND (stmt, 0);
140 type = TREE_TYPE (TREE_OPERAND (stmt, 1));
141 TREE_OPERAND (stmt, 1) = build (COMPLEX_EXPR, type, r, i);
144 /* Expand complex addition to scalars:
145 a + b = (ar + br) + i(ai + bi)
146 a - b = (ar - br) + i(ai + bi)
150 expand_complex_addition (block_stmt_iterator *bsi, tree inner_type,
151 tree ar, tree ai, tree br, tree bi,
156 rr = do_binop (bsi, code, inner_type, ar, br);
157 ri = do_binop (bsi, code, inner_type, ai, bi);
159 update_complex_assignment (bsi, rr, ri);
162 /* Expand complex multiplication to scalars:
163 a * b = (ar*br - ai*bi) + i(ar*bi + br*ai)
167 expand_complex_multiplication (block_stmt_iterator *bsi, tree inner_type,
168 tree ar, tree ai, tree br, tree bi)
170 tree t1, t2, t3, t4, rr, ri;
172 t1 = do_binop (bsi, MULT_EXPR, inner_type, ar, br);
173 t2 = do_binop (bsi, MULT_EXPR, inner_type, ai, bi);
174 t3 = do_binop (bsi, MULT_EXPR, inner_type, ar, bi);
176 /* Avoid expanding redundant multiplication for the common
177 case of squaring a complex number. */
178 if (ar == br && ai == bi)
181 t4 = do_binop (bsi, MULT_EXPR, inner_type, ai, br);
183 rr = do_binop (bsi, MINUS_EXPR, inner_type, t1, t2);
184 ri = do_binop (bsi, PLUS_EXPR, inner_type, t3, t4);
186 update_complex_assignment (bsi, rr, ri);
189 /* Expand complex division to scalars, straightforward algorithm.
190 a / b = ((ar*br + ai*bi)/t) + i((ai*br - ar*bi)/t)
195 expand_complex_div_straight (block_stmt_iterator *bsi, tree inner_type,
196 tree ar, tree ai, tree br, tree bi,
199 tree rr, ri, div, t1, t2, t3;
201 t1 = do_binop (bsi, MULT_EXPR, inner_type, br, br);
202 t2 = do_binop (bsi, MULT_EXPR, inner_type, bi, bi);
203 div = do_binop (bsi, PLUS_EXPR, inner_type, t1, t2);
205 t1 = do_binop (bsi, MULT_EXPR, inner_type, ar, br);
206 t2 = do_binop (bsi, MULT_EXPR, inner_type, ai, bi);
207 t3 = do_binop (bsi, PLUS_EXPR, inner_type, t1, t2);
208 rr = do_binop (bsi, code, inner_type, t3, div);
210 t1 = do_binop (bsi, MULT_EXPR, inner_type, ai, br);
211 t2 = do_binop (bsi, MULT_EXPR, inner_type, ar, bi);
212 t3 = do_binop (bsi, MINUS_EXPR, inner_type, t1, t2);
213 ri = do_binop (bsi, code, inner_type, t3, div);
215 update_complex_assignment (bsi, rr, ri);
218 /* Expand complex division to scalars, modified algorithm to minimize
219 overflow with wide input ranges. */
222 expand_complex_div_wide (block_stmt_iterator *bsi, tree inner_type,
223 tree ar, tree ai, tree br, tree bi,
226 tree rr, ri, ratio, div, t1, t2, min, max, cond;
228 /* Examine |br| < |bi|, and branch. */
229 t1 = do_unop (bsi, ABS_EXPR, inner_type, br);
230 t2 = do_unop (bsi, ABS_EXPR, inner_type, bi);
231 cond = fold (build (LT_EXPR, boolean_type_node, t1, t2));
234 if (TREE_CONSTANT (cond))
236 if (integer_zerop (cond))
243 basic_block bb_cond, bb_true, bb_false, bb_join;
247 l1 = create_artificial_label ();
248 t1 = build (GOTO_EXPR, void_type_node, l1);
249 l2 = create_artificial_label ();
250 t2 = build (GOTO_EXPR, void_type_node, l2);
251 cond = build (COND_EXPR, void_type_node, cond, t1, t2);
252 bsi_insert_before (bsi, cond, BSI_SAME_STMT);
254 min = make_temp (inner_type);
255 max = make_temp (inner_type);
256 l3 = create_artificial_label ();
258 /* Split the original block, and create the TRUE and FALSE blocks. */
259 e = split_block (bsi->bb, cond);
262 bb_true = create_empty_bb (bb_cond);
263 bb_false = create_empty_bb (bb_true);
265 /* Wire the blocks together. */
266 e->flags = EDGE_TRUE_VALUE;
267 redirect_edge_succ (e, bb_true);
268 make_edge (bb_cond, bb_false, EDGE_FALSE_VALUE);
269 make_edge (bb_true, bb_join, 0);
270 make_edge (bb_false, bb_join, 0);
272 /* Update dominance info. Note that bb_join's data was
273 updated by split_block. */
274 if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
276 set_immediate_dominator (CDI_DOMINATORS, bb_true, bb_cond);
277 set_immediate_dominator (CDI_DOMINATORS, bb_false, bb_cond);
280 /* Compute min and max for TRUE block. */
281 *bsi = bsi_start (bb_true);
282 t1 = build (LABEL_EXPR, void_type_node, l1);
283 bsi_insert_after (bsi, t1, BSI_NEW_STMT);
284 t1 = build (MODIFY_EXPR, inner_type, min, br);
285 bsi_insert_after (bsi, t1, BSI_NEW_STMT);
286 t1 = build (MODIFY_EXPR, inner_type, max, bi);
287 bsi_insert_after (bsi, t1, BSI_NEW_STMT);
289 /* Compute min and max for FALSE block. */
290 *bsi = bsi_start (bb_false);
291 t1 = build (LABEL_EXPR, void_type_node, l2);
292 bsi_insert_after (bsi, t1, BSI_NEW_STMT);
293 t1 = build (MODIFY_EXPR, inner_type, min, bi);
294 bsi_insert_after (bsi, t1, BSI_NEW_STMT);
295 t1 = build (MODIFY_EXPR, inner_type, max, br);
296 bsi_insert_after (bsi, t1, BSI_NEW_STMT);
298 /* Insert the join label into the tail of the original block. */
299 *bsi = bsi_start (bb_join);
300 t1 = build (LABEL_EXPR, void_type_node, l3);
301 bsi_insert_before (bsi, t1, BSI_SAME_STMT);
304 /* Now we have MIN(|br|, |bi|) and MAX(|br|, |bi|). We now use the
305 ratio min/max to scale both the dividend and divisor. */
306 ratio = do_binop (bsi, code, inner_type, min, max);
308 /* Calculate the divisor: min*ratio + max. */
309 t1 = do_binop (bsi, MULT_EXPR, inner_type, min, ratio);
310 div = do_binop (bsi, PLUS_EXPR, inner_type, t1, max);
312 /* Result is now ((ar + ai*ratio)/div) + i((ai - ar*ratio)/div). */
313 t1 = do_binop (bsi, MULT_EXPR, inner_type, ai, ratio);
314 t2 = do_binop (bsi, PLUS_EXPR, inner_type, ar, t1);
315 rr = do_binop (bsi, code, inner_type, t2, div);
317 t1 = do_binop (bsi, MULT_EXPR, inner_type, ar, ratio);
318 t2 = do_binop (bsi, MINUS_EXPR, inner_type, ai, t1);
319 ri = do_binop (bsi, code, inner_type, t2, div);
321 update_complex_assignment (bsi, rr, ri);
324 /* Expand complex division to scalars. */
327 expand_complex_division (block_stmt_iterator *bsi, tree inner_type,
328 tree ar, tree ai, tree br, tree bi,
331 switch (flag_complex_divide_method)
334 /* straightforward implementation of complex divide acceptable. */
335 expand_complex_div_straight (bsi, inner_type, ar, ai, br, bi, code);
338 /* wide ranges of inputs must work for complex divide. */
339 expand_complex_div_wide (bsi, inner_type, ar, ai, br, bi, code);
342 /* C99-like requirements for complex divide (not yet implemented). */
347 /* Expand complex negation to scalars:
352 expand_complex_negation (block_stmt_iterator *bsi, tree inner_type,
357 rr = do_unop (bsi, NEGATE_EXPR, inner_type, ar);
358 ri = do_unop (bsi, NEGATE_EXPR, inner_type, ai);
360 update_complex_assignment (bsi, rr, ri);
363 /* Expand complex conjugate to scalars:
368 expand_complex_conjugate (block_stmt_iterator *bsi, tree inner_type,
373 ri = do_unop (bsi, NEGATE_EXPR, inner_type, ai);
375 update_complex_assignment (bsi, ar, ri);
378 /* Expand complex comparison (EQ or NE only). */
381 expand_complex_comparison (block_stmt_iterator *bsi, tree ar, tree ai,
382 tree br, tree bi, enum tree_code code)
384 tree cr, ci, cc, stmt, type;
386 cr = do_binop (bsi, code, boolean_type_node, ar, br);
387 ci = do_binop (bsi, code, boolean_type_node, ai, bi);
388 cc = do_binop (bsi, (code == EQ_EXPR ? TRUTH_AND_EXPR : TRUTH_OR_EXPR),
389 boolean_type_node, cr, ci);
391 stmt = bsi_stmt (*bsi);
394 switch (TREE_CODE (stmt))
397 stmt = TREE_OPERAND (stmt, 0);
400 type = TREE_TYPE (TREE_OPERAND (stmt, 1));
401 TREE_OPERAND (stmt, 1) = convert (type, cc);
404 TREE_OPERAND (stmt, 0) = cc;
411 /* Process one statement. If we identify a complex operation, expand it. */
414 expand_complex_operations_1 (block_stmt_iterator *bsi)
416 tree stmt = bsi_stmt (*bsi);
417 tree rhs, type, inner_type;
418 tree ac, ar, ai, bc, br, bi;
421 switch (TREE_CODE (stmt))
424 stmt = TREE_OPERAND (stmt, 0);
427 if (TREE_CODE (stmt) != MODIFY_EXPR)
432 rhs = TREE_OPERAND (stmt, 1);
436 rhs = TREE_OPERAND (stmt, 0);
443 type = TREE_TYPE (rhs);
444 code = TREE_CODE (rhs);
446 /* Initial filter for operations we handle. */
459 if (TREE_CODE (type) != COMPLEX_TYPE)
461 inner_type = TREE_TYPE (type);
466 inner_type = TREE_TYPE (TREE_OPERAND (rhs, 1));
467 if (TREE_CODE (inner_type) != COMPLEX_TYPE)
475 /* Extract the components of the two complex values. Make sure and
476 handle the common case of the same value used twice specially. */
477 ac = TREE_OPERAND (rhs, 0);
478 ar = extract_component (bsi, ac, 0);
479 ai = extract_component (bsi, ac, 1);
481 if (TREE_CODE_CLASS (code) == '1')
485 bc = TREE_OPERAND (rhs, 1);
490 br = extract_component (bsi, bc, 0);
491 bi = extract_component (bsi, bc, 1);
499 expand_complex_addition (bsi, inner_type, ar, ai, br, bi, code);
503 expand_complex_multiplication (bsi, inner_type, ar, ai, br, bi);
511 expand_complex_division (bsi, inner_type, ar, ai, br, bi, code);
515 expand_complex_negation (bsi, inner_type, ar, ai);
519 expand_complex_conjugate (bsi, inner_type, ar, ai);
524 expand_complex_comparison (bsi, ar, ai, br, bi, code);
532 /* Main loop to process each statement. */
533 /* ??? Could use dominator bits to propagate from complex_expr at the
534 same time. This might reveal more constants, particularly in cases
535 such as (complex = complex op scalar). This may not be relevant
536 after SRA and subsequent cleanups. Proof of this would be if we
537 verify that the code generated by expand_complex_div_wide is
538 simplified properly to straight-line code. */
541 expand_complex_operations (void)
543 int old_last_basic_block = last_basic_block;
544 block_stmt_iterator bsi;
549 if (bb->index >= old_last_basic_block)
551 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
552 expand_complex_operations_1 (&bsi);
556 struct tree_opt_pass pass_lower_complex =
558 "complex", /* name */
560 expand_complex_operations, /* execute */
563 0, /* static_pass_number */
565 PROP_cfg, /* properties_required */
566 0, /* properties_provided */
567 0, /* properties_destroyed */
568 0, /* todo_flags_start */
569 TODO_dump_func | TODO_rename_vars
570 | TODO_ggc_collect | TODO_verify_ssa
571 | TODO_verify_stmts | TODO_verify_flow /* todo_flags_finish */