irgopt.h 7.09 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

Michael Beck's avatar
Michael Beck committed
20
/**
Matthias Braun's avatar
Matthias Braun committed
21
22
23
24
 * @file
 * @brief   Optimizations for a whole ir graph, i.e., a procedure.
 * @author  Christian Schaefer, Goetz Lindenmaier, Sebastian Felis
 * @version $Id$
Götz Lindenmaier's avatar
Götz Lindenmaier committed
25
 */
Matthias Braun's avatar
Matthias Braun committed
26
27
#ifndef FIRM_IR_IRGOPT_H
#define FIRM_IR_IRGOPT_H
Boris Boesler's avatar
Boris Boesler committed
28

29
#include "firm_types.h"
Christian Schäfer's avatar
Christian Schäfer committed
30

31
32
/** Applies local optimizations (see iropt.h) to all nodes reachable from node n.
 *
Michael Beck's avatar
Michael Beck committed
33
34
 * @param n The node to be optimized.
 */
35
36
void local_optimize_node(ir_node *n);

Beyhan's avatar
Beyhan committed
37
38
/** Applies local optimizations (see iropt.h) to all nodes in the graph.
 *
Michael Beck's avatar
Michael Beck committed
39
40
 * @param irg  The graph to be optimized.
 *
Michael Beck's avatar
Michael Beck committed
41
 * After applying local_optimize_graph() to a IR-graph, Bad nodes
42
 * only occur as predecessor of Block and Phi nodes.
Michael Beck's avatar
Michael Beck committed
43
 */
Michael Beck's avatar
Michael Beck committed
44
void local_optimize_graph(ir_graph *irg);
Christian Schäfer's avatar
Christian Schäfer committed
45

46
47
/** Applies local optimizations (see iropt.h) to all nodes in the graph.
 *
48
49
 * After applying optimize_graph_df() to a IR-graph, Bad nodes
 * only occur as predecessor of Block and Phi nodes.
50
 *
51
52
53
 * This version uses fixpoint iteration.
 *
 * @param irg  The graph to be optimized.
54
 *
55
 * @return non-zero if the optimization could be applied, 0 else
56
 */
57
int optimize_graph_df(ir_graph *irg);
58

59
60
61
62
63
64
65
66
67
68
69
/**
 * Creates an ir_graph pass for optimize_graph_df().
 *
 * @param name     the name of this pass or NULL
 * @param verify   should this pass be verified?
 * @param dump     should this pass result be dumped?
 *
 * @return  the newly created ir_graph pass
 */
ir_graph_pass_t *optimize_graph_df_pass(const char *name, int verify, int dump);

Michael Beck's avatar
Michael Beck committed
70
/** Performs dead node elimination by copying the ir graph to a new obstack.
71
72
 *
 *  The major intention of this pass is to free memory occupied by
73
74
75
 *  dead nodes and outdated analyzes information.  Further this
 *  function removes Bad predecessors from Blocks and the corresponding
 *  inputs to Phi nodes.  This opens optimization potential for other
76
77
78
79
80
81
 *  optimizations.  Further this phase reduces dead Block<->Jmp
 *  self-cycles to Bad nodes.
 *
 *  Dead_node_elimination is only performed if options `optimize' and
 *  `opt_dead_node_elimination' are set.  The graph may
 *  not be in state phase_building.  The outs datasturcture is freed,
82
 *  the outs state set to outs_none.  Backedge information is conserved.
83
84
85
 *  Removes old attributes of nodes.  Sets link field to NULL.
 *  Callee information must be freed (irg_callee_info_none).
 *
Michael Beck's avatar
Michael Beck committed
86
87
 * @param irg  The graph to be optimized.
 */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
88
void dead_node_elimination(ir_graph *irg);
Christian Schäfer's avatar
Christian Schäfer committed
89

Sebastian Hack's avatar
Sebastian Hack committed
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
typedef struct _survive_dce_t survive_dce_t;

/**
 * Make a new Survive DCE environment.
 */
survive_dce_t *new_survive_dce(void);

/**
 * Free a Survive DCE environment.
 */
void free_survive_dce(survive_dce_t *sd);

/**
 * Register a node pointer to be patched upon DCE.
 * When DCE occurs, the node pointer specified by @p place will be
 * patched to the new address of the node it is pointing to.
 *
 * @param sd    The Survive DCE environment.
 * @param place The address of the node pointer.
 */
void survive_dce_register_irn(survive_dce_t *sd, ir_node **place);

112
/**  Cleans the control flow from Bad predecessors.
Beyhan's avatar
Beyhan committed
113
 *
114
 * Removes Bad predecessors from Blocks and the corresponding
Beyhan's avatar
Beyhan committed
115
116
117
 * inputs to Phi nodes as in dead_node_elimination but without
 * copying the graph.
 *
118
119
 * Conserves loop information.
 *
Beyhan's avatar
Beyhan committed
120
121
 * @param irg  The graph to be optimized.
 */
122
123
void remove_bad_predecessors(ir_graph *irg);

Michael Beck's avatar
Michael Beck committed
124
/** Inlines a method at the given call site.
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
 *
 *  Removes the call node and splits the basic block the call node
 *  belongs to.  Inserts a copy of the called graph between these nodes.
 *  Assumes that call is a Call node in current_ir_graph and that
 *  the type in the Call nodes type attribute is the same as the
 *  type of the called graph.
 *  Further it assumes that all Phi nodes in a block of current_ir_graph
 *  are assembled in a "link" list in the link field of the corresponding
 *  block nodes.  Further assumes that all Proj nodes are in a "link" list
 *  in the nodes producing the tuple.  (This is only an optical feature
 *  for the graph.)  Conserves this feature for the old
 *  nodes of the graph.  This precondition can be established by a call to
 *  collect_phisprojs(), see irgmod.h.
 *  As dead_node_elimination this function reduces dead Block<->Jmp
 *  self-cycles to Bad nodes.
 *
 *  Called_graph must be unequal to current_ir_graph.   Will not inline
 *  if they are equal.
 *  Sets visited masterflag in current_ir_graph to the max of the flag in
 *  current and called graph.
 *  Assumes that both, the called and the calling graph are in state
146
 *  "op_pin_state_pinned".
Michael Beck's avatar
Michael Beck committed
147
 *  It is recommended to call local_optimize_graph() after inlining as this
148
149
150
151
152
153
154
155
 *  function leaves a set of obscure Tuple nodes, e.g. a Proj-Tuple-Jmp
 *  combination as control flow operation.
 *
 *  @param call          the call node that should be inlined
 *  @param called_graph  the IR-graph that is called at call
 *
 *  @return zero if method could not be inlined (recursion for instance),
 *          non-zero if all went ok
Michael Beck's avatar
Michael Beck committed
156
 */
157
int inline_method(ir_node *call, ir_graph *called_graph);
158

Michael Beck's avatar
Michael Beck committed
159
160
/** Code Placement.
 *
161
 * Pins all floating nodes to a block where they
Michael Beck's avatar
Michael Beck committed
162
163
164
165
166
167
168
169
170
171
172
173
174
 * will be executed only if needed.   Depends on the flag opt_global_cse.
 * Graph may not be in phase_building.  Does not schedule control dead
 * code.  Uses dominator information which it computes if the irg is not
 * in state dom_consistent.  Destroys the out information as it moves nodes
 * to other blocks.  Optimizes Tuples in Control edges.
 * @todo This is not tested!
 *
 * Call remove_critical_cf_edges() before place_code().  This normalizes
 * the control flow graph so that for all operations a basic block exists
 * where they can be optimally placed.
 *
 * @todo A more powerful code placement would move operations past Phi nodes
 * out of loops.
Michael Beck's avatar
Michael Beck committed
175
 */
Michael Beck's avatar
Michael Beck committed
176
void place_code(ir_graph *irg);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
177

Michael Beck's avatar
Michael Beck committed
178
/** Places an empty basic block on critical control flow edges thereby
Michael Beck's avatar
Michael Beck committed
179
180
181
182
 * removing them.
 *
 * A critical control flow edge is an edge from a block with several
 * control exits to a block with several control entries (See Muchnic
183
 * p. 407). Exception edges are always ignored.
Michael Beck's avatar
Michael Beck committed
184
 *
185
 * @param irg  IR Graph
Michael Beck's avatar
Michael Beck committed
186
 */
187
188
void remove_critical_cf_edges(ir_graph *irg);

189
190
191
192
193
194
195
196
197
198
199
200
/** Places an empty basic block on critical control flow edges thereby
 * removing them.
 *
 * A critical control flow edge is an edge from a block with several
 * control exits to a block with several control entries (See Muchnic
 * p. 407).
 *
 * @param irg                     IR Graph
 * @param ignore_exception_edges  if non-zero, exception edges will be ignored
 */
void remove_critical_cf_edges_ex(ir_graph *irg, int ignore_exception_edges);

Matthias Braun's avatar
Matthias Braun committed
201
#endif