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 #include "config.h"
  28
  29 #include <assert.h>
  30
  31 #include "irnode_t.h"
  32 #include "irgraph_t.h"
  33
  34 #include "iroptimize.h"
  35 #include "iropt_t.h"
  36 #include "irgopt.h"
  37 #include "irgmod.h"
  38 #include "irgwalk.h"
  39
  40 #include "adt/pdeq.h"
  41
  42 #include "irflag_t.h"
  43 #include "iredges_t.h"
  44 #include "irtools.h"
  45
  46 /*------------------------------------------------------------------*/
  47 /* apply optimizations of iropt to all nodes.                       */
  48 /*------------------------------------------------------------------*/
  49
  50 /**
  51  * A wrapper around optimize_inplace_2() to be called from a walker.
  52  */
  53 static void optimize_in_place_wrapper (ir_node *n, void *env) {
  54         ir_node *optimized = optimize_in_place_2(n);
  55         (void) env;
  56
  57         if (optimized != n) {
  58                 exchange(n, optimized);
  59         }
  60 }
  61
  62 /**
  63  * Do local optimizations for a node.
  64  *
  65  * @param n  the IR-node where to start. Typically the End node
  66  *           of a graph
  67  *
  68  * @note current_ir_graph must be set
  69  */
  70 static inline void do_local_optimize(ir_node *n) {
  71         /* Handle graph state */
  72         assert(get_irg_phase_state(current_ir_graph) != phase_building);
  73
  74         if (get_opt_global_cse())
  75                 set_irg_pinned(current_ir_graph, op_pin_state_floats);
  76         set_irg_outs_inconsistent(current_ir_graph);
  77         set_irg_doms_inconsistent(current_ir_graph);
  78         set_irg_loopinfo_inconsistent(current_ir_graph);
  79
  80         /* Clean the value_table in irg for the CSE. */
  81         del_identities(current_ir_graph->value_table);
  82         current_ir_graph->value_table = new_identities();
  83
  84         /* walk over the graph */
  85         irg_walk(n, firm_clear_link, optimize_in_place_wrapper, NULL);
  86 }
  87
  88 /* Applies local optimizations (see iropt.h) to all nodes reachable from node n */
  89 void local_optimize_node(ir_node *n) {
  90         ir_graph *rem = current_ir_graph;
  91         current_ir_graph = get_irn_irg(n);
  92
  93         do_local_optimize(n);
  94
  95         current_ir_graph = rem;
  96 }
  97
  98 /**
  99  * Block-Walker: uses dominance depth to mark dead blocks.
 100  */
 101 static void kill_dead_blocks(ir_node *block, void *env) {
 102         (void) env;
 103
 104         if (get_Block_dom_depth(block) < 0) {
 105                 /*
 106                  * Note that the new dominance code correctly handles
 107                  * the End block, i.e. it is always reachable from Start
 108                  */
 109                 set_Block_dead(block);
 110         }
 111 }
 112
 113 /* Applies local optimizations (see iropt.h) to all nodes reachable from node n. */
 114 void local_optimize_graph(ir_graph *irg) {
 115         ir_graph *rem = current_ir_graph;
 116         current_ir_graph = irg;
 117
 118         if (get_irg_dom_state(irg) == dom_consistent)
 119                 irg_block_walk_graph(irg, NULL, kill_dead_blocks, NULL);
 120
 121         do_local_optimize(get_irg_end(irg));
 122
 123         current_ir_graph = rem;
 124 }
 125
 126 /**
 127  * Enqueue all users of a node to a wait queue.
 128  * Handles mode_T nodes.
 129  */
 130 static void enqueue_users(ir_node *n, pdeq *waitq) {
 131         const ir_edge_t *edge;
 132
 133         foreach_out_edge(n, edge) {
 134                 ir_node *succ = get_edge_src_irn(edge);
 135
 136                 if (get_irn_link(succ) != waitq) {
 137                         pdeq_putr(waitq, succ);
 138                         set_irn_link(succ, waitq);
 139                 }
 140                 if (get_irn_mode(succ) == mode_T) {
 141                 /* A mode_T node has Proj's. Because most optimizations
 142                         run on the Proj's we have to enqueue them also. */
 143                         enqueue_users(succ, waitq);
 144                 }
 145         }
 146 }
 147
 148 /**
 149  * Data flow optimization walker.
 150  * Optimizes all nodes and enqueue it's users
 151  * if done.
 152  */
 153 static void opt_walker(ir_node *n, void *env) {
 154         pdeq *waitq = env;
 155         ir_node *optimized;
 156
 157         optimized = optimize_in_place_2(n);
 158         set_irn_link(optimized, NULL);
 159
 160         if (optimized != n) {
 161                 enqueue_users(n, waitq);
 162                 exchange(n, optimized);
 163         }
 164 }
 165
 166 /* Applies local optimizations to all nodes in the graph until fixpoint. */
 167 int optimize_graph_df(ir_graph *irg) {
 168         pdeq     *waitq = new_pdeq();
 169         ir_graph *rem = current_ir_graph;
 170         ir_node  *end;
 171         int      state, changed;
 172
 173         current_ir_graph = irg;
 174
 175         state = edges_assure(irg);
 176
 177         if (get_opt_global_cse())
 178                 set_irg_pinned(current_ir_graph, op_pin_state_floats);
 179
 180         /* Clean the value_table in irg for the CSE. */
 181         del_identities(irg->value_table);
 182         irg->value_table = new_identities();
 183
 184         if (get_irg_dom_state(irg) == dom_consistent)
 185                 irg_block_walk_graph(irg, NULL, kill_dead_blocks, NULL);
 186
 187         /* invalidate info */
 188         set_irg_outs_inconsistent(irg);
 189         set_irg_doms_inconsistent(irg);
 190         set_irg_loopinfo_inconsistent(irg);
 191
 192         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
 193
 194         /* walk over the graph, but don't touch keep-alives */
 195         irg_walk_graph(irg, NULL, opt_walker, waitq);
 196
 197         /* any optimized nodes are stored in the wait queue,
 198          * so if it's not empty, the graph has been changed */
 199         changed = !pdeq_empty(waitq);
 200
 201         /* finish the wait queue */
 202         while (! pdeq_empty(waitq)) {
 203                 ir_node *n = pdeq_getl(waitq);
 204                 if (! is_Bad(n))
 205                         opt_walker(n, waitq);
 206         }
 207
 208         del_pdeq(waitq);
 209
 210         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
 211
 212         if (! state)
 213                 edges_deactivate(irg);
 214
 215         /* Finally kill BAD and doublets from the keep alives.
 216            Doing this AFTER edges where deactivated saves cycles */
 217         end  = get_irg_end(irg);
 218         remove_End_Bads_and_doublets(end);
 219
 220         current_ir_graph = rem;
 221         return changed;
 222 }