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, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, 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 /* Check if DEF's uses include more than one floating-point division,
  58    and if so replace them by multiplications with the reciprocal.  If
  59    PHI is true, insert the reciprocal calculation before BSI, otherwise
  60    insert it after and move BSI to the new statement.
  61
  62    Does not check the type of DEF, nor that DEF is a GIMPLE register.
  63    This is done in the caller for speed, because otherwise this routine
  64    would be called for every definition and phi node.  */
  65 static void
  66 execute_cse_reciprocals_1 (block_stmt_iterator *bsi, tree def, bool phi)
  67 {
  68   use_operand_p use_p;
  69   imm_use_iterator use_iter;
  70   tree t, new_stmt, type;
  71   int count = 0;
  72
  73   /* Find uses.  */
  74   FOR_EACH_IMM_USE_FAST (use_p, use_iter, def)
  75     {
  76       tree use_stmt = USE_STMT (use_p);
  77       if (TREE_CODE (use_stmt) == MODIFY_EXPR
  78           && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == RDIV_EXPR
  79           && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 1) == def)
  80         {
  81           if (++count == 2)
  82             break;
  83         }
  84     }
  85
  86   if (count < 2)
  87     return;
  88
  89   /* Make a variable with the replacement and substitute it.  */
  90   type = TREE_TYPE (def);
  91   t = make_rename_temp (type, "reciptmp");
  92   new_stmt = build2 (MODIFY_EXPR, void_type_node, t,
  93                      fold_build2 (RDIV_EXPR, type, build_real (type, dconst1),
  94                                   def));
  95
  96   if (phi)
  97     bsi_insert_before (bsi, new_stmt, BSI_SAME_STMT);
  98   else
  99     bsi_insert_after (bsi, new_stmt, BSI_NEW_STMT);
 100
 101   FOR_EACH_IMM_USE_SAFE (use_p, use_iter, def)
 102     {
 103       tree use_stmt = USE_STMT (use_p);
 104       if (use_stmt != new_stmt
 105           && TREE_CODE (use_stmt) == MODIFY_EXPR
 106           && TREE_CODE (TREE_OPERAND (use_stmt, 1)) == RDIV_EXPR
 107           && TREE_OPERAND (TREE_OPERAND (use_stmt, 1), 1) == def)
 108         {
 109           TREE_SET_CODE (TREE_OPERAND (use_stmt, 1), MULT_EXPR);
 110           SET_USE (use_p, t);
 111         }
 112     }
 113 }
 114
 115 static void
 116 execute_cse_reciprocals (void)
 117 {
 118   basic_block bb;
 119   FOR_EACH_BB (bb)
 120     {
 121       block_stmt_iterator bsi;
 122       tree phi, def;
 123       for (bsi = bsi_start (bb);
 124            !bsi_end_p (bsi) && TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR;
 125            bsi_next (&bsi))
 126         ;
 127
 128       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 129         {
 130           def = PHI_RESULT (phi);
 131           if (FLOAT_TYPE_P (TREE_TYPE (def))
 132               && is_gimple_reg (def))
 133             execute_cse_reciprocals_1 (&bsi, def, true);
 134         }
 135
 136       for (; !bsi_end_p (bsi); bsi_next (&bsi))
 137         {
 138           tree stmt = bsi_stmt (bsi);
 139           if (TREE_CODE (stmt) == MODIFY_EXPR
 140               && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
 141               && FLOAT_TYPE_P (TREE_TYPE (def))
 142               && is_gimple_reg (def))
 143             execute_cse_reciprocals_1 (&bsi, def, false);
 144         }
 145     }
 146 }
 147
 148 struct tree_opt_pass pass_cse_reciprocals =
 149 {
 150   "recip",                              /* name */
 151   gate_cse_reciprocals,                 /* gate */
 152   execute_cse_reciprocals,              /* execute */
 153   NULL,                                 /* sub */
 154   NULL,                                 /* next */
 155   0,                                    /* static_pass_number */
 156   0,                                    /* tv_id */
 157   PROP_ssa,                             /* properties_required */
 158   0,                                    /* properties_provided */
 159   0,                                    /* properties_destroyed */
 160   0,                                    /* todo_flags_start */
 161   TODO_dump_func | TODO_update_ssa | TODO_verify_ssa
 162     | TODO_verify_stmts,                /* todo_flags_finish */
 163   0                                     /* letter */
 164 };