nsz Git - libfirm/blob - ir/ir/irgopt.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    Optimizations for a whole ir graph, i.e., a procedure.
  23  * @author   Christian Schaefer, Goetz Lindenmaier, Sebastian Felis,
  24  *           Michael Beck
  25  * @version  $Id$
  26  */
  27 #ifdef HAVE_CONFIG_H
  28 # include "config.h"
  29 #endif
  30
  31 #include <assert.h>
  32
  33 #include "irnode_t.h"
  34 #include "irgraph_t.h"
  35
  36 #include "iroptimize.h"
  37 #include "iropt_t.h"
  38 #include "irgopt.h"
  39 #include "irgmod.h"
  40 #include "irgwalk.h"
  41
  42 #include "adt/pdeq.h"
  43
  44 #include "irflag_t.h"
  45 #include "iredges_t.h"
  46 #include "irtools.h"
  47
  48 /*------------------------------------------------------------------*/
  49 /* apply optimizations of iropt to all nodes.                       */
  50 /*------------------------------------------------------------------*/
  51
  52 /**
  53  * A wrapper around optimize_inplace_2() to be called from a walker.
  54  */
  55 static void optimize_in_place_wrapper (ir_node *n, void *env) {
  56         ir_node *optimized = optimize_in_place_2(n);
  57         (void) env;
  58
  59         if (optimized != n) {
  60                 exchange(n, optimized);
  61         }
  62 }
  63
  64 /**
  65  * Do local optimizations for a node.
  66  *
  67  * @param n  the IR-node where to start. Typically the End node
  68  *           of a graph
  69  *
  70  * @note current_ir_graph must be set
  71  */
  72 static INLINE void do_local_optimize(ir_node *n) {
  73         /* Handle graph state */
  74         assert(get_irg_phase_state(current_ir_graph) != phase_building);
  75
  76         if (get_opt_global_cse())
  77                 set_irg_pinned(current_ir_graph, op_pin_state_floats);
  78         set_irg_outs_inconsistent(current_ir_graph);
  79         set_irg_doms_inconsistent(current_ir_graph);
  80         set_irg_loopinfo_inconsistent(current_ir_graph);
  81
  82         /* Clean the value_table in irg for the CSE. */
  83         del_identities(current_ir_graph->value_table);
  84         current_ir_graph->value_table = new_identities();
  85
  86         /* walk over the graph */
  87         irg_walk(n, firm_clear_link, optimize_in_place_wrapper, NULL);
  88 }
  89
  90 /* Applies local optimizations (see iropt.h) to all nodes reachable from node n */
  91 void local_optimize_node(ir_node *n) {
  92         ir_graph *rem = current_ir_graph;
  93         current_ir_graph = get_irn_irg(n);
  94
  95         do_local_optimize(n);
  96
  97         current_ir_graph = rem;
  98 }
  99
 100 /**
 101  * Block-Walker: uses dominance depth to mark dead blocks.
 102  */
 103 static void kill_dead_blocks(ir_node *block, void *env) {
 104         (void) env;
 105
 106         if (get_Block_dom_depth(block) < 0) {
 107                 /*
 108                  * Note that the new dominance code correctly handles
 109                  * the End block, i.e. it is always reachable from Start
 110                  */
 111                 set_Block_dead(block);
 112         }
 113 }
 114
 115 /* Applies local optimizations (see iropt.h) to all nodes reachable from node n. */
 116 void local_optimize_graph(ir_graph *irg) {
 117         ir_graph *rem = current_ir_graph;
 118         current_ir_graph = irg;
 119
 120         if (get_irg_dom_state(irg) == dom_consistent)
 121                 irg_block_walk_graph(irg, NULL, kill_dead_blocks, NULL);
 122
 123         do_local_optimize(get_irg_end(irg));
 124
 125         current_ir_graph = rem;
 126 }
 127
 128 /**
 129  * Enqueue all users of a node to a wait queue.
 130  * Handles mode_T nodes.
 131  */
 132 static void enqueue_users(ir_node *n, pdeq *waitq) {
 133         const ir_edge_t *edge;
 134
 135         foreach_out_edge(n, edge) {
 136                 ir_node *succ = get_edge_src_irn(edge);
 137
 138                 if (get_irn_link(succ) != waitq) {
 139                         pdeq_putr(waitq, succ);
 140                         set_irn_link(succ, waitq);
 141                 }
 142                 if (get_irn_mode(succ) == mode_T) {
 143                 /* A mode_T node has Proj's. Because most optimizations
 144                         run on the Proj's we have to enqueue them also. */
 145                         enqueue_users(succ, waitq);
 146                 }
 147         }
 148 }
 149
 150 /**
 151  * Data flow optimization walker.
 152  * Optimizes all nodes and enqueue it's users
 153  * if done.
 154  */
 155 static void opt_walker(ir_node *n, void *env) {
 156         pdeq *waitq = env;
 157         ir_node *optimized;
 158
 159         optimized = optimize_in_place_2(n);
 160         set_irn_link(optimized, NULL);
 161
 162         if (optimized != n) {
 163                 enqueue_users(n, waitq);
 164                 exchange(n, optimized);
 165         }
 166 }
 167
 168 /* Applies local optimizations to all nodes in the graph until fixpoint. */
 169 void optimize_graph_df(ir_graph *irg) {
 170         pdeq     *waitq = new_pdeq();
 171         ir_graph *rem = current_ir_graph;
 172         ir_node  *end;
 173         int      i, state, n_ka;
 174
 175         current_ir_graph = irg;
 176
 177         state = edges_assure(irg);
 178
 179         if (get_opt_global_cse())
 180                 set_irg_pinned(current_ir_graph, op_pin_state_floats);
 181
 182         /* Clean the value_table in irg for the CSE. */
 183         del_identities(irg->value_table);
 184         irg->value_table = new_identities();
 185
 186         if (get_irg_dom_state(irg) == dom_consistent)
 187                 irg_block_walk_graph(irg, NULL, kill_dead_blocks, NULL);
 188
 189         /* invalidate info */
 190         set_irg_outs_inconsistent(irg);
 191         set_irg_doms_inconsistent(irg);
 192         set_irg_loopinfo_inconsistent(irg);
 193
 194         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
 195
 196         end  = get_irg_end(irg);
 197         n_ka = get_End_n_keepalives(end);
 198
 199         /* walk over the graph, but don't touch keep-alives */
 200         irg_walk(get_irg_end_block(irg), NULL, opt_walker, waitq);
 201
 202         /*
 203          * Optimize keep-alives by removing superfluous ones.
 204          * Beware: the last transformation might add new keep-alives
 205          * that keep blocks that are where visited! So, check only the
 206          * "old" keep-alives, not the new ones!
 207          *
 208          * FIXME: it might be better to completely remove this
 209          * optimization here ...
 210          */
 211         for (i = n_ka - 1; i >= 0; --i) {
 212                 ir_node *ka = get_End_keepalive(end, i);
 213
 214                 if (irn_visited(ka) && !is_irn_keep(ka)) {
 215                         /* this node can be regularly visited, no need to keep it */
 216                         set_End_keepalive(end, i, get_irg_bad(irg));
 217                 }
 218         }
 219         /* now walk again and visit all not yet visited nodes */
 220         set_irg_visited(current_ir_graph, get_irg_visited(irg) - 1);
 221         irg_walk(get_irg_end(irg), NULL, opt_walker, waitq);
 222
 223         /* finish the wait queue */
 224         while (! pdeq_empty(waitq)) {
 225                 ir_node *n = pdeq_getl(waitq);
 226                 if (! is_Bad(n))
 227                         opt_walker(n, waitq);
 228         }
 229
 230         del_pdeq(waitq);
 231
 232         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
 233
 234         if (! state)
 235                 edges_deactivate(irg);
 236
 237         current_ir_graph = rem;
 238 }