diff options
Diffstat (limited to 'gcc/tree-fold-const.c')
| -rw-r--r-- | gcc/tree-fold-const.c | 222 |
1 files changed, 222 insertions, 0 deletions
diff --git a/gcc/tree-fold-const.c b/gcc/tree-fold-const.c new file mode 100644 index 00000000000..90317ebff8e --- /dev/null +++ b/gcc/tree-fold-const.c @@ -0,0 +1,222 @@ +/* Fold GENERIC expressions. + Copyright (C) 2003 Free Software Foundation, Inc. + Contributed by Sebastian Pop <s.pop@laposte.net> + +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 "tm.h" +#include "errors.h" +#include "ggc.h" +#include "tree.h" +#include "tree-fold-const.h" + + + +/* Least common multiple. */ + +tree +tree_fold_lcm (tree a, + tree b) +{ + tree pgcd; + +#if defined ENABLE_CHECKING + if (TREE_CODE (a) != INTEGER_CST + || TREE_CODE (b) != INTEGER_CST) + abort (); +#endif + + if (integer_onep (a)) + return b; + + if (integer_onep (b)) + return a; + + if (integer_zerop (a) + || integer_zerop (b)) + return integer_zero_node; + + pgcd = tree_fold_gcd (a, b); + + if (integer_onep (pgcd)) + return tree_fold_multiply (integer_type_node, a, b); + else + return tree_fold_multiply + (integer_type_node, pgcd, + tree_fold_lcm (tree_fold_exact_div (integer_type_node, a, pgcd), + tree_fold_exact_div (integer_type_node, b, pgcd))); +} + +/* Greatest common divisor. */ + +tree +tree_fold_gcd (tree a, + tree b) +{ + tree a_mod_b; + tree type = TREE_TYPE (a); + +#if defined ENABLE_CHECKING + if (TREE_CODE (a) != INTEGER_CST + || TREE_CODE (b) != INTEGER_CST) + abort (); +#endif + + if (integer_zerop (a)) + return b; + + if (integer_zerop (b)) + return a; + + if (tree_int_cst_sgn (a) == -1) + a = tree_fold_multiply (type, a, + convert (type, integer_minus_one_node)); + + if (tree_int_cst_sgn (b) == -1) + b = tree_fold_multiply (type, b, + convert (type, integer_minus_one_node)); + + while (1) + { + a_mod_b = fold (build (CEIL_MOD_EXPR, type, a, b)); + + if (!TREE_INT_CST_LOW (a_mod_b) + && !TREE_INT_CST_HIGH (a_mod_b)) + return b; + + a = b; + b = a_mod_b; + } +} + +/* Bezout: Let a1 and a2 be two integers; there exist two integers u11 + and u12 such that, + + | u11 * a1 + u12 * a2 = gcd (a1, a2). + + This function computes the greatest common divisor using the + Blankinship algorithm. The gcd is returned, and the coefficients + of the unimodular matrix U are (u11, u12, u21, u22) such that, + + | U.A = S + + | (u11 u12) (a1) = (gcd) + | (u21 u22) (a2) (0) + + FIXME: Use lambda_..._hermite for implementing this function. +*/ + +tree +tree_fold_bezout (tree a1, + tree a2, + tree *u11, tree *u12, + tree *u21, tree *u22) +{ + tree s1, s2; + + /* Initialize S with the coefficients of A. */ + s1 = a1; + s2 = a2; + + /* Initialize the U matrix */ + *u11 = integer_one_node; + *u12 = integer_zero_node; + *u21 = integer_zero_node; + *u22 = integer_one_node; + + if (integer_zerop (a1) + || integer_zerop (a2)) + return integer_zero_node; + + while (!integer_zerop (s2)) + { + int sign; + tree z, zu21, zu22, zs2; + + sign = tree_int_cst_sgn (s1) * tree_int_cst_sgn (s2); + z = tree_fold_floor_div (integer_type_node, + tree_fold_abs (integer_type_node, s1), + tree_fold_abs (integer_type_node, s2)); + zu21 = tree_fold_multiply (integer_type_node, z, *u21); + zu22 = tree_fold_multiply (integer_type_node, z, *u22); + zs2 = tree_fold_multiply (integer_type_node, z, s2); + + /* row1 -= z * row2. */ + if (sign < 0) + { + *u11 = tree_fold_plus (integer_type_node, *u11, zu21); + *u12 = tree_fold_plus (integer_type_node, *u12, zu22); + s1 = tree_fold_plus (integer_type_node, s1, zs2); + } + else if (sign > 0) + { + *u11 = tree_fold_minus (integer_type_node, *u11, zu21); + *u12 = tree_fold_minus (integer_type_node, *u12, zu22); + s1 = tree_fold_minus (integer_type_node, s1, zs2); + } + else + /* Should not happen. */ + abort (); + + /* Interchange row1 and row2. */ + { + tree flip; + + flip = *u11; + *u11 = *u21; + *u21 = flip; + + flip = *u12; + *u12 = *u22; + *u22 = flip; + + flip = s1; + s1 = s2; + s2 = flip; + } + } + + if (tree_int_cst_sgn (s1) < 0) + { + *u11 = tree_fold_multiply (integer_type_node, *u11, + integer_minus_one_node); + *u12 = tree_fold_multiply (integer_type_node, *u12, + integer_minus_one_node); + s1 = tree_fold_multiply (integer_type_node, s1, integer_minus_one_node); + } + + return s1; +} + +/* The factorial. */ + +tree +tree_fold_factorial (tree f) +{ + if (tree_int_cst_sgn (f) <= 0) + return integer_one_node; + else + return tree_fold_multiply + (integer_type_node, f, + tree_fold_factorial (tree_fold_minus + (integer_type_node, f, integer_one_node))); +} + |