gcc/tree-ssa-math-opts.c

   1 /* Global, SSA-based optimizations using mathematical identities.
   2    Copyright (C) 2005 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   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
   9 later version.
  10
  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
  14 for more details.
  15
  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, 51 Franklin Street, Fifth Floor, Boston, MA
  19 02110-1301, USA.  */
  20
  21 /* Currently, the only mini-pass in this file tries to CSE reciprocal
  22    operations.  These are common in sequences such as this one:
  23
  24         modulus = sqrt(x*x + y*y + z*z);
  25         x = x / modulus;
  26         y = y / modulus;
  27         z = z / modulus;
  28
  29    that can be optimized to
  30
  31         modulus = sqrt(x*x + y*y + z*z);
  32         rmodulus = 1.0 / modulus;
  33         x = x * rmodulus;
  34         y = y * rmodulus;
  35         z = z * rmodulus;
  36
  37    We do this for loop invariant divisors, and with this pass whenever
  38    we notice that a division has the same divisor multiple times.  */
  39
  40 #include "config.h"
  41 #include "system.h"
  42 #include "coretypes.h"
  43 #include "tm.h"
  44 #include "flags.h"
  45 #include "tree.h"
  46 #include "tree-flow.h"
  47 #include "real.h"
  48 #include "timevar.h"
  49 #include "tree-pass.h"
  50
  51 static bool
  52 gate_cse_reciprocals (void)
  53 {
  54   return optimize && !optimize_size && flag_unsafe_math_optimizations;
  55 }
  56
  57 /* Where to put the statement computing a reciprocal.  */
  58 enum place_reciprocal
  59 {
  60   PR_BEFORE_BSI,        /* Put it using bsi_insert_before.  */
  61   PR_AFTER_BSI,         /* Put it using bsi_insert_after.  */
  62   PR_ON_ENTRY_EDGE      /* Put it on the edge between the entry
  63                            and the first basic block.  */
  64 };
  65
  66 /* Check if DEF's uses include more than one floating-point division,
  67    and if so replace them by multiplications with the reciprocal.  Add
  68    the statement computing the reciprocal according to WHERE.
  69
  70    Does not check the type of DEF, nor that DEF is a GIMPLE register.
  71    This is done in the caller for speed, because otherwise this routine
  72    would be called for every definition and phi node.  */
  73 static void
  74 execute_cse_reciprocals_1 (block_stmt_iterator *bsi, tree def,
  75                            enum place_reciprocal where)
  76 {
  77   use_operand_p use_p;
  78   imm_use_iterator use_iter;
  79   tree t, new_stmt, type;
  80   int count = 0;
  81   bool ok = !flag_trapping_math;
  82
  83   /* Find uses.  */
  84   FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
  85     {
  86       tree use_stmt = USE_STMT (use_p);
  87       if (TREE_CODE (use_stmt) == MODIFY_EXPR
  88           && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == RDIV_EXPR
  89           && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 1) == def)
  90         {
  91           ++count;
  92           /* Check if this use post-dominates the insertion point.  */
  93           if (ok || dominated_by_p (CDI_POST_DOMINATORS, bsi->bb,
  94                                     bb_for_stmt (use_stmt)))
  95             ok = true;
  96         }
  97       if (count >= 2 && ok)
  98         break;
  99     }
 100
 101   if (count < 2 || !ok)
 102     return;
 103
 104   /* Make a variable with the replacement and substitute it.  */
 105   type = TREE_TYPE (def);
 106   t = make_rename_temp (type, "reciptmp");
 107   new_stmt = build2 (MODIFY_EXPR, void_type_node, t,
 108                      fold_build2 (RDIV_EXPR, type, build_real (type, dconst1),
 109                                   def));
 110
 111   if (where == PR_BEFORE_BSI)
 112     bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
 113   else if (where == PR_AFTER_BSI)
 114     bsi_insert_after (bsi, new_stmt, BSI_NEW_STMT);
 115   else if (where == PR_ON_ENTRY_EDGE)
 116     bsi_insert_on_edge (single_succ_edge (ENTRY_BLOCK_PTR), new_stmt);
 117   else
 118     gcc_unreachable ();
 119
 120   FOR_EACH_IMM_USE_SAFE (use_p, use_iter, def)
 121     {
 122       tree use_stmt = USE_STMT (use_p);
 123       if (use_stmt != new_stmt
 124           && TREE_CODE (use_stmt) == MODIFY_EXPR
 125           && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == RDIV_EXPR
 126           && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 1) == def)
 127         {
 128           TREE_SET_CODE (TREE_OPERAND (use_stmt, 1), MULT_EXPR);
 129           SET_USE (use_p, t);
 130         }
 131     }
 132 }
 133
 134 static void
 135 execute_cse_reciprocals (void)
 136 {
 137   basic_block bb;
 138   tree arg;
 139
 140   if (flag_trapping_math)
 141     calculate_dominance_info (CDI_POST_DOMINATORS);
 142
 143   if (single_succ_p (ENTRY_BLOCK_PTR))
 144     for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg))
 145       if (default_def (arg))
 146         {
 147           block_stmt_iterator bsi;
 148           bsi = bsi_start (single_succ (ENTRY_BLOCK_PTR));
 149           execute_cse_reciprocals_1 (&bsi, default_def (arg),
 150                                      PR_ON_ENTRY_EDGE);
 151         }
 152
 153   FOR_EACH_BB (bb)
 154     {
 155       block_stmt_iterator bsi;
 156       tree phi, def;
 157       for (bsi = bsi_start (bb);
 158            !bsi_end_p (bsi) && TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR;
 159            bsi_next (&bsi))
 160         ;
 161
 162       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 163         {
 164           def = PHI_RESULT (phi);
 165           if (FLOAT_TYPE_P (TREE_TYPE (def))
 166               && is_gimple_reg (def))
 167             execute_cse_reciprocals_1 (&bsi, def, PR_BEFORE_BSI);
 168         }
 169
 170       for (; !bsi_end_p (bsi); bsi_next (&bsi))
 171         {
 172           tree stmt = bsi_stmt (bsi);
 173           if (TREE_CODE (stmt) == MODIFY_EXPR
 174               && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
 175               && FLOAT_TYPE_P (TREE_TYPE (def))
 176               && TREE_CODE (def) == SSA_NAME)
 177             execute_cse_reciprocals_1 (&bsi, def, PR_AFTER_BSI);
 178         }
 179     }
 180
 181   if (flag_trapping_math)
 182     free_dominance_info (CDI_POST_DOMINATORS);
 183
 184   if (single_succ_p (ENTRY_BLOCK_PTR))
 185     bsi_commit_one_edge_insert (single_succ_edge (ENTRY_BLOCK_PTR), NULL);
 186 }
 187
 188 struct tree_opt_pass pass_cse_reciprocals =
 189 {
 190   "recip",                              /* name */
 191   gate_cse_reciprocals,                 /* gate */
 192   execute_cse_reciprocals,              /* execute */
 193   NULL,                                 /* sub */
 194   NULL,                                 /* next */
 195   0,                                    /* static_pass_number */
 196   0,                                    /* tv_id */
 197   PROP_ssa,                             /* properties_required */
 198   0,                                    /* properties_provided */
 199   0,                                    /* properties_destroyed */
 200   0,                                    /* todo_flags_start */
 201   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 202     | TODO_verify_stmts,                /* todo_flags_finish */
 203   0                                     /* letter */
 204 };