1 /* Lower complex number operations to scalar operations.
2 Copyright (C) 2004, 2005 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"
28 #include "insn-codes.h"
29 #include "diagnostic.h"
32 #include "langhooks.h"
33 #include "tree-flow.h"
34 #include "tree-gimple.h"
35 #include "tree-iterator.h"
36 #include "tree-pass.h"
41 /* Extract the real or imaginary part of a complex variable or constant.
42 Make sure that it's a proper gimple_val and gimplify it if not.
43 Emit any new code before BSI. */
46 extract_component (block_stmt_iterator
*bsi
, tree t
, bool imagpart_p
)
50 inner_type
= TREE_TYPE (TREE_TYPE (t
));
51 switch (TREE_CODE (t
))
54 ret
= (imagpart_p
? TREE_IMAGPART (t
) : TREE_REALPART (t
));
58 ret
= TREE_OPERAND (t
, imagpart_p
);
63 ret
= build1 ((imagpart_p
? IMAGPART_EXPR
: REALPART_EXPR
),
71 return gimplify_val (bsi
, inner_type
, ret
);
74 /* Update an assignment to a complex variable in place. */
77 update_complex_assignment (block_stmt_iterator
*bsi
, tree r
, tree i
)
79 tree stmt
= bsi_stmt (*bsi
);
82 if (TREE_CODE (stmt
) == RETURN_EXPR
)
83 stmt
= TREE_OPERAND (stmt
, 0);
85 type
= TREE_TYPE (TREE_OPERAND (stmt
, 1));
86 TREE_OPERAND (stmt
, 1) = build (COMPLEX_EXPR
, type
, r
, i
);
87 mark_stmt_modified (stmt
);
90 /* Expand complex addition to scalars:
91 a + b = (ar + br) + i(ai + bi)
92 a - b = (ar - br) + i(ai + bi)
96 expand_complex_addition (block_stmt_iterator
*bsi
, tree inner_type
,
97 tree ar
, tree ai
, tree br
, tree bi
,
102 rr
= gimplify_build2 (bsi
, code
, inner_type
, ar
, br
);
103 ri
= gimplify_build2 (bsi
, code
, inner_type
, ai
, bi
);
105 update_complex_assignment (bsi
, rr
, ri
);
108 /* Expand a complex multiplication or division to a libcall to the c99
109 compliant routines. */
112 expand_complex_libcall (block_stmt_iterator
*bsi
, tree ar
, tree ai
,
113 tree br
, tree bi
, enum tree_code code
)
115 enum machine_mode mode
;
116 enum built_in_function bcode
;
117 tree args
, fn
, stmt
, type
;
119 args
= tree_cons (NULL
, bi
, NULL
);
120 args
= tree_cons (NULL
, br
, args
);
121 args
= tree_cons (NULL
, ai
, args
);
122 args
= tree_cons (NULL
, ar
, args
);
124 stmt
= bsi_stmt (*bsi
);
125 type
= TREE_TYPE (TREE_OPERAND (stmt
, 1));
127 mode
= TYPE_MODE (type
);
128 gcc_assert (GET_MODE_CLASS (mode
) == MODE_COMPLEX_FLOAT
);
129 if (code
== MULT_EXPR
)
130 bcode
= BUILT_IN_COMPLEX_MUL_MIN
+ mode
- MIN_MODE_COMPLEX_FLOAT
;
131 else if (code
== RDIV_EXPR
)
132 bcode
= BUILT_IN_COMPLEX_DIV_MIN
+ mode
- MIN_MODE_COMPLEX_FLOAT
;
135 fn
= built_in_decls
[bcode
];
137 TREE_OPERAND (stmt
, 1)
138 = build3 (CALL_EXPR
, type
, build_fold_addr_expr (fn
), args
, NULL
);
142 /* Expand complex multiplication to scalars:
143 a * b = (ar*br - ai*bi) + i(ar*bi + br*ai)
147 expand_complex_multiplication (block_stmt_iterator
*bsi
, tree inner_type
,
148 tree ar
, tree ai
, tree br
, tree bi
)
150 tree t1
, t2
, t3
, t4
, rr
, ri
;
152 if (flag_complex_method
== 2 && SCALAR_FLOAT_TYPE_P (inner_type
))
154 expand_complex_libcall (bsi
, ar
, ai
, br
, bi
, MULT_EXPR
);
158 t1
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, ar
, br
);
159 t2
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, ai
, bi
);
160 t3
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, ar
, bi
);
162 /* Avoid expanding redundant multiplication for the common
163 case of squaring a complex number. */
164 if (ar
== br
&& ai
== bi
)
167 t4
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, ai
, br
);
169 rr
= gimplify_build2 (bsi
, MINUS_EXPR
, inner_type
, t1
, t2
);
170 ri
= gimplify_build2 (bsi
, PLUS_EXPR
, inner_type
, t3
, t4
);
172 update_complex_assignment (bsi
, rr
, ri
);
175 /* Expand complex division to scalars, straightforward algorithm.
176 a / b = ((ar*br + ai*bi)/t) + i((ai*br - ar*bi)/t)
181 expand_complex_div_straight (block_stmt_iterator
*bsi
, tree inner_type
,
182 tree ar
, tree ai
, tree br
, tree bi
,
185 tree rr
, ri
, div
, t1
, t2
, t3
;
187 t1
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, br
, br
);
188 t2
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, bi
, bi
);
189 div
= gimplify_build2 (bsi
, PLUS_EXPR
, inner_type
, t1
, t2
);
191 t1
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, ar
, br
);
192 t2
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, ai
, bi
);
193 t3
= gimplify_build2 (bsi
, PLUS_EXPR
, inner_type
, t1
, t2
);
194 rr
= gimplify_build2 (bsi
, code
, inner_type
, t3
, div
);
196 t1
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, ai
, br
);
197 t2
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, ar
, bi
);
198 t3
= gimplify_build2 (bsi
, MINUS_EXPR
, inner_type
, t1
, t2
);
199 ri
= gimplify_build2 (bsi
, code
, inner_type
, t3
, div
);
201 update_complex_assignment (bsi
, rr
, ri
);
204 /* Expand complex division to scalars, modified algorithm to minimize
205 overflow with wide input ranges. */
208 expand_complex_div_wide (block_stmt_iterator
*bsi
, tree inner_type
,
209 tree ar
, tree ai
, tree br
, tree bi
,
212 tree rr
, ri
, ratio
, div
, t1
, t2
, tr
, ti
, cond
;
213 basic_block bb_cond
, bb_true
, bb_false
, bb_join
;
215 /* Examine |br| < |bi|, and branch. */
216 t1
= gimplify_build1 (bsi
, ABS_EXPR
, inner_type
, br
);
217 t2
= gimplify_build1 (bsi
, ABS_EXPR
, inner_type
, bi
);
218 cond
= fold (build (LT_EXPR
, boolean_type_node
, t1
, t2
));
221 bb_cond
= bb_true
= bb_false
= bb_join
= NULL
;
222 rr
= ri
= tr
= ti
= NULL
;
223 if (!TREE_CONSTANT (cond
))
227 cond
= build (COND_EXPR
, void_type_node
, cond
, NULL
, NULL
);
228 bsi_insert_before (bsi
, cond
, BSI_SAME_STMT
);
230 /* Split the original block, and create the TRUE and FALSE blocks. */
231 e
= split_block (bsi
->bb
, cond
);
234 bb_true
= create_empty_bb (bb_cond
);
235 bb_false
= create_empty_bb (bb_true
);
237 t1
= build (GOTO_EXPR
, void_type_node
, tree_block_label (bb_true
));
238 t2
= build (GOTO_EXPR
, void_type_node
, tree_block_label (bb_false
));
239 COND_EXPR_THEN (cond
) = t1
;
240 COND_EXPR_ELSE (cond
) = t2
;
242 /* Wire the blocks together. */
243 e
->flags
= EDGE_TRUE_VALUE
;
244 redirect_edge_succ (e
, bb_true
);
245 make_edge (bb_cond
, bb_false
, EDGE_FALSE_VALUE
);
246 make_edge (bb_true
, bb_join
, EDGE_FALLTHRU
);
247 make_edge (bb_false
, bb_join
, EDGE_FALLTHRU
);
249 /* Update dominance info. Note that bb_join's data was
250 updated by split_block. */
251 if (dom_info_available_p (CDI_DOMINATORS
))
253 set_immediate_dominator (CDI_DOMINATORS
, bb_true
, bb_cond
);
254 set_immediate_dominator (CDI_DOMINATORS
, bb_false
, bb_cond
);
257 rr
= make_rename_temp (inner_type
, NULL
);
258 ri
= make_rename_temp (inner_type
, NULL
);
261 /* In the TRUE branch, we compute
263 div = (br * ratio) + bi;
264 tr = (ar * ratio) + ai;
265 ti = (ai * ratio) - ar;
268 if (bb_true
|| integer_nonzerop (cond
))
272 *bsi
= bsi_last (bb_true
);
273 bsi_insert_after (bsi
, build_empty_stmt (), BSI_NEW_STMT
);
276 ratio
= gimplify_build2 (bsi
, code
, inner_type
, br
, bi
);
278 t1
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, br
, ratio
);
279 div
= gimplify_build2 (bsi
, PLUS_EXPR
, inner_type
, t1
, bi
);
281 t1
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, ar
, ratio
);
282 tr
= gimplify_build2 (bsi
, PLUS_EXPR
, inner_type
, t1
, ai
);
284 t1
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, ai
, ratio
);
285 ti
= gimplify_build2 (bsi
, MINUS_EXPR
, inner_type
, t1
, ar
);
287 tr
= gimplify_build2 (bsi
, code
, inner_type
, tr
, div
);
288 ti
= gimplify_build2 (bsi
, code
, inner_type
, ti
, div
);
292 t1
= build (MODIFY_EXPR
, inner_type
, rr
, tr
);
293 bsi_insert_before (bsi
, t1
, BSI_SAME_STMT
);
294 t1
= build (MODIFY_EXPR
, inner_type
, ri
, ti
);
295 bsi_insert_before (bsi
, t1
, BSI_SAME_STMT
);
300 /* In the FALSE branch, we compute
302 divisor = (d * ratio) + c;
303 tr = (b * ratio) + a;
304 ti = b - (a * ratio);
307 if (bb_false
|| integer_zerop (cond
))
311 *bsi
= bsi_last (bb_false
);
312 bsi_insert_after (bsi
, build_empty_stmt (), BSI_NEW_STMT
);
315 ratio
= gimplify_build2 (bsi
, code
, inner_type
, bi
, br
);
317 t1
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, bi
, ratio
);
318 div
= gimplify_build2 (bsi
, PLUS_EXPR
, inner_type
, t1
, br
);
320 t1
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, ai
, ratio
);
321 tr
= gimplify_build2 (bsi
, PLUS_EXPR
, inner_type
, t1
, ar
);
323 t1
= gimplify_build2 (bsi
, MULT_EXPR
, inner_type
, ar
, ratio
);
324 ti
= gimplify_build2 (bsi
, MINUS_EXPR
, inner_type
, ai
, t1
);
326 tr
= gimplify_build2 (bsi
, code
, inner_type
, tr
, div
);
327 ti
= gimplify_build2 (bsi
, code
, inner_type
, ti
, div
);
331 t1
= build (MODIFY_EXPR
, inner_type
, rr
, tr
);
332 bsi_insert_before (bsi
, t1
, BSI_SAME_STMT
);
333 t1
= build (MODIFY_EXPR
, inner_type
, ri
, ti
);
334 bsi_insert_before (bsi
, t1
, BSI_SAME_STMT
);
340 *bsi
= bsi_start (bb_join
);
344 update_complex_assignment (bsi
, rr
, ri
);
347 /* Expand complex division to scalars. */
350 expand_complex_division (block_stmt_iterator
*bsi
, tree inner_type
,
351 tree ar
, tree ai
, tree br
, tree bi
,
354 switch (flag_complex_method
)
357 /* straightforward implementation of complex divide acceptable. */
358 expand_complex_div_straight (bsi
, inner_type
, ar
, ai
, br
, bi
, code
);
362 if (SCALAR_FLOAT_TYPE_P (inner_type
))
364 expand_complex_libcall (bsi
, ar
, ai
, br
, bi
, code
);
370 /* wide ranges of inputs must work for complex divide. */
371 expand_complex_div_wide (bsi
, inner_type
, ar
, ai
, br
, bi
, code
);
379 /* Expand complex negation to scalars:
384 expand_complex_negation (block_stmt_iterator
*bsi
, tree inner_type
,
389 rr
= gimplify_build1 (bsi
, NEGATE_EXPR
, inner_type
, ar
);
390 ri
= gimplify_build1 (bsi
, NEGATE_EXPR
, inner_type
, ai
);
392 update_complex_assignment (bsi
, rr
, ri
);
395 /* Expand complex conjugate to scalars:
400 expand_complex_conjugate (block_stmt_iterator
*bsi
, tree inner_type
,
405 ri
= gimplify_build1 (bsi
, NEGATE_EXPR
, inner_type
, ai
);
407 update_complex_assignment (bsi
, ar
, ri
);
410 /* Expand complex comparison (EQ or NE only). */
413 expand_complex_comparison (block_stmt_iterator
*bsi
, tree ar
, tree ai
,
414 tree br
, tree bi
, enum tree_code code
)
416 tree cr
, ci
, cc
, stmt
, expr
, type
;
418 cr
= gimplify_build2 (bsi
, code
, boolean_type_node
, ar
, br
);
419 ci
= gimplify_build2 (bsi
, code
, boolean_type_node
, ai
, bi
);
420 cc
= gimplify_build2 (bsi
,
421 (code
== EQ_EXPR
? TRUTH_AND_EXPR
: TRUTH_OR_EXPR
),
422 boolean_type_node
, cr
, ci
);
424 stmt
= expr
= bsi_stmt (*bsi
);
426 switch (TREE_CODE (stmt
))
429 expr
= TREE_OPERAND (stmt
, 0);
432 type
= TREE_TYPE (TREE_OPERAND (expr
, 1));
433 TREE_OPERAND (expr
, 1) = fold_convert (type
, cc
);
436 TREE_OPERAND (stmt
, 0) = cc
;
442 mark_stmt_modified (stmt
);
445 /* Process one statement. If we identify a complex operation, expand it. */
448 expand_complex_operations_1 (block_stmt_iterator
*bsi
)
450 tree stmt
= bsi_stmt (*bsi
);
451 tree rhs
, type
, inner_type
;
452 tree ac
, ar
, ai
, bc
, br
, bi
;
455 switch (TREE_CODE (stmt
))
458 stmt
= TREE_OPERAND (stmt
, 0);
461 if (TREE_CODE (stmt
) != MODIFY_EXPR
)
466 rhs
= TREE_OPERAND (stmt
, 1);
470 rhs
= TREE_OPERAND (stmt
, 0);
477 type
= TREE_TYPE (rhs
);
478 code
= TREE_CODE (rhs
);
480 /* Initial filter for operations we handle. */
493 if (TREE_CODE (type
) != COMPLEX_TYPE
)
495 inner_type
= TREE_TYPE (type
);
500 inner_type
= TREE_TYPE (TREE_OPERAND (rhs
, 1));
501 if (TREE_CODE (inner_type
) != COMPLEX_TYPE
)
509 /* Extract the components of the two complex values. Make sure and
510 handle the common case of the same value used twice specially. */
511 ac
= TREE_OPERAND (rhs
, 0);
512 ar
= extract_component (bsi
, ac
, 0);
513 ai
= extract_component (bsi
, ac
, 1);
515 if (TREE_CODE_CLASS (code
) == tcc_unary
)
519 bc
= TREE_OPERAND (rhs
, 1);
524 br
= extract_component (bsi
, bc
, 0);
525 bi
= extract_component (bsi
, bc
, 1);
533 expand_complex_addition (bsi
, inner_type
, ar
, ai
, br
, bi
, code
);
537 expand_complex_multiplication (bsi
, inner_type
, ar
, ai
, br
, bi
);
545 expand_complex_division (bsi
, inner_type
, ar
, ai
, br
, bi
, code
);
549 expand_complex_negation (bsi
, inner_type
, ar
, ai
);
553 expand_complex_conjugate (bsi
, inner_type
, ar
, ai
);
558 expand_complex_comparison (bsi
, ar
, ai
, br
, bi
, code
);
564 update_stmt_if_modified (stmt
);
568 tree_lower_complex (void)
570 int old_last_basic_block
= last_basic_block
;
571 block_stmt_iterator bsi
;
576 if (bb
->index
>= old_last_basic_block
)
578 for (bsi
= bsi_start (bb
); !bsi_end_p (bsi
); bsi_next (&bsi
))
579 expand_complex_operations_1 (&bsi
);
584 struct tree_opt_pass pass_lower_complex
=
586 "cplxlower", /* name */
588 tree_lower_complex
, /* execute */
591 0, /* static_pass_number */
593 PROP_cfg
, /* properties_required */
594 0, /* properties_provided */
595 0, /* properties_destroyed */
596 0, /* todo_flags_start */
597 TODO_dump_func
| TODO_ggc_collect
598 | TODO_verify_stmts
, /* todo_flags_finish */