|
0
|
1 /* Generic partial redundancy elimination with lazy code motion support.
|
|
|
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008
|
|
|
3 Free Software Foundation, Inc.
|
|
|
4
|
|
|
5 This file is part of GCC.
|
|
|
6
|
|
|
7 GCC is free software; you can redistribute it and/or modify it under
|
|
|
8 the terms of the GNU General Public License as published by the Free
|
|
|
9 Software Foundation; either version 3, or (at your option) any later
|
|
|
10 version.
|
|
|
11
|
|
|
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
15 for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU General Public License
|
|
|
18 along with GCC; see the file COPYING3. If not see
|
|
|
19 <http://www.gnu.org/licenses/>. */
|
|
|
20
|
|
|
21 /* These routines are meant to be used by various optimization
|
|
|
22 passes which can be modeled as lazy code motion problems.
|
|
|
23 Including, but not limited to:
|
|
|
24
|
|
|
25 * Traditional partial redundancy elimination.
|
|
|
26
|
|
|
27 * Placement of caller/caller register save/restores.
|
|
|
28
|
|
|
29 * Load/store motion.
|
|
|
30
|
|
|
31 * Copy motion.
|
|
|
32
|
|
|
33 * Conversion of flat register files to a stacked register
|
|
|
34 model.
|
|
|
35
|
|
|
36 * Dead load/store elimination.
|
|
|
37
|
|
|
38 These routines accept as input:
|
|
|
39
|
|
|
40 * Basic block information (number of blocks, lists of
|
|
|
41 predecessors and successors). Note the granularity
|
|
|
42 does not need to be basic block, they could be statements
|
|
|
43 or functions.
|
|
|
44
|
|
|
45 * Bitmaps of local properties (computed, transparent and
|
|
|
46 anticipatable expressions).
|
|
|
47
|
|
|
48 The output of these routines is bitmap of redundant computations
|
|
|
49 and a bitmap of optimal placement points. */
|
|
|
50
|
|
|
51
|
|
|
52 #include "config.h"
|
|
|
53 #include "system.h"
|
|
|
54 #include "coretypes.h"
|
|
|
55 #include "tm.h"
|
|
|
56 #include "rtl.h"
|
|
|
57 #include "regs.h"
|
|
|
58 #include "hard-reg-set.h"
|
|
|
59 #include "flags.h"
|
|
|
60 #include "real.h"
|
|
|
61 #include "insn-config.h"
|
|
|
62 #include "recog.h"
|
|
|
63 #include "basic-block.h"
|
|
|
64 #include "output.h"
|
|
|
65 #include "tm_p.h"
|
|
|
66 #include "function.h"
|
|
|
67
|
|
|
68 /* We want target macros for the mode switching code to be able to refer
|
|
|
69 to instruction attribute values. */
|
|
|
70 #include "insn-attr.h"
|
|
|
71
|
|
|
72 /* Edge based LCM routines. */
|
|
|
73 static void compute_antinout_edge (sbitmap *, sbitmap *, sbitmap *, sbitmap *);
|
|
|
74 static void compute_earliest (struct edge_list *, int, sbitmap *, sbitmap *,
|
|
|
75 sbitmap *, sbitmap *, sbitmap *);
|
|
|
76 static void compute_laterin (struct edge_list *, sbitmap *, sbitmap *,
|
|
|
77 sbitmap *, sbitmap *);
|
|
|
78 static void compute_insert_delete (struct edge_list *edge_list, sbitmap *,
|
|
|
79 sbitmap *, sbitmap *, sbitmap *, sbitmap *);
|
|
|
80
|
|
|
81 /* Edge based LCM routines on a reverse flowgraph. */
|
|
|
82 static void compute_farthest (struct edge_list *, int, sbitmap *, sbitmap *,
|
|
|
83 sbitmap*, sbitmap *, sbitmap *);
|
|
|
84 static void compute_nearerout (struct edge_list *, sbitmap *, sbitmap *,
|
|
|
85 sbitmap *, sbitmap *);
|
|
|
86 static void compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *,
|
|
|
87 sbitmap *, sbitmap *, sbitmap *,
|
|
|
88 sbitmap *);
|
|
|
89
|
|
|
90 /* Edge based lcm routines. */
|
|
|
91
|
|
|
92 /* Compute expression anticipatability at entrance and exit of each block.
|
|
|
93 This is done based on the flow graph, and not on the pred-succ lists.
|
|
|
94 Other than that, its pretty much identical to compute_antinout. */
|
|
|
95
|
|
|
96 static void
|
|
|
97 compute_antinout_edge (sbitmap *antloc, sbitmap *transp, sbitmap *antin,
|
|
|
98 sbitmap *antout)
|
|
|
99 {
|
|
|
100 basic_block bb;
|
|
|
101 edge e;
|
|
|
102 basic_block *worklist, *qin, *qout, *qend;
|
|
|
103 unsigned int qlen;
|
|
|
104 edge_iterator ei;
|
|
|
105
|
|
|
106 /* Allocate a worklist array/queue. Entries are only added to the
|
|
|
107 list if they were not already on the list. So the size is
|
|
|
108 bounded by the number of basic blocks. */
|
|
|
109 qin = qout = worklist = XNEWVEC (basic_block, n_basic_blocks);
|
|
|
110
|
|
|
111 /* We want a maximal solution, so make an optimistic initialization of
|
|
|
112 ANTIN. */
|
|
|
113 sbitmap_vector_ones (antin, last_basic_block);
|
|
|
114
|
|
|
115 /* Put every block on the worklist; this is necessary because of the
|
|
|
116 optimistic initialization of ANTIN above. */
|
|
|
117 FOR_EACH_BB_REVERSE (bb)
|
|
|
118 {
|
|
|
119 *qin++ = bb;
|
|
|
120 bb->aux = bb;
|
|
|
121 }
|
|
|
122
|
|
|
123 qin = worklist;
|
|
|
124 qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
|
|
|
125 qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
|
|
|
126
|
|
|
127 /* Mark blocks which are predecessors of the exit block so that we
|
|
|
128 can easily identify them below. */
|
|
|
129 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
|
|
|
130 e->src->aux = EXIT_BLOCK_PTR;
|
|
|
131
|
|
|
132 /* Iterate until the worklist is empty. */
|
|
|
133 while (qlen)
|
|
|
134 {
|
|
|
135 /* Take the first entry off the worklist. */
|
|
|
136 bb = *qout++;
|
|
|
137 qlen--;
|
|
|
138
|
|
|
139 if (qout >= qend)
|
|
|
140 qout = worklist;
|
|
|
141
|
|
|
142 if (bb->aux == EXIT_BLOCK_PTR)
|
|
|
143 /* Do not clear the aux field for blocks which are predecessors of
|
|
|
144 the EXIT block. That way we never add then to the worklist
|
|
|
145 again. */
|
|
|
146 sbitmap_zero (antout[bb->index]);
|
|
|
147 else
|
|
|
148 {
|
|
|
149 /* Clear the aux field of this block so that it can be added to
|
|
|
150 the worklist again if necessary. */
|
|
|
151 bb->aux = NULL;
|
|
|
152 sbitmap_intersection_of_succs (antout[bb->index], antin, bb->index);
|
|
|
153 }
|
|
|
154
|
|
|
155 if (sbitmap_a_or_b_and_c_cg (antin[bb->index], antloc[bb->index],
|
|
|
156 transp[bb->index], antout[bb->index]))
|
|
|
157 /* If the in state of this block changed, then we need
|
|
|
158 to add the predecessors of this block to the worklist
|
|
|
159 if they are not already on the worklist. */
|
|
|
160 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
161 if (!e->src->aux && e->src != ENTRY_BLOCK_PTR)
|
|
|
162 {
|
|
|
163 *qin++ = e->src;
|
|
|
164 e->src->aux = e;
|
|
|
165 qlen++;
|
|
|
166 if (qin >= qend)
|
|
|
167 qin = worklist;
|
|
|
168 }
|
|
|
169 }
|
|
|
170
|
|
|
171 clear_aux_for_edges ();
|
|
|
172 clear_aux_for_blocks ();
|
|
|
173 free (worklist);
|
|
|
174 }
|
|
|
175
|
|
|
176 /* Compute the earliest vector for edge based lcm. */
|
|
|
177
|
|
|
178 static void
|
|
|
179 compute_earliest (struct edge_list *edge_list, int n_exprs, sbitmap *antin,
|
|
|
180 sbitmap *antout, sbitmap *avout, sbitmap *kill,
|
|
|
181 sbitmap *earliest)
|
|
|
182 {
|
|
|
183 sbitmap difference, temp_bitmap;
|
|
|
184 int x, num_edges;
|
|
|
185 basic_block pred, succ;
|
|
|
186
|
|
|
187 num_edges = NUM_EDGES (edge_list);
|
|
|
188
|
|
|
189 difference = sbitmap_alloc (n_exprs);
|
|
|
190 temp_bitmap = sbitmap_alloc (n_exprs);
|
|
|
191
|
|
|
192 for (x = 0; x < num_edges; x++)
|
|
|
193 {
|
|
|
194 pred = INDEX_EDGE_PRED_BB (edge_list, x);
|
|
|
195 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
|
|
|
196 if (pred == ENTRY_BLOCK_PTR)
|
|
|
197 sbitmap_copy (earliest[x], antin[succ->index]);
|
|
|
198 else
|
|
|
199 {
|
|
|
200 if (succ == EXIT_BLOCK_PTR)
|
|
|
201 sbitmap_zero (earliest[x]);
|
|
|
202 else
|
|
|
203 {
|
|
|
204 sbitmap_difference (difference, antin[succ->index],
|
|
|
205 avout[pred->index]);
|
|
|
206 sbitmap_not (temp_bitmap, antout[pred->index]);
|
|
|
207 sbitmap_a_and_b_or_c (earliest[x], difference,
|
|
|
208 kill[pred->index], temp_bitmap);
|
|
|
209 }
|
|
|
210 }
|
|
|
211 }
|
|
|
212
|
|
|
213 sbitmap_free (temp_bitmap);
|
|
|
214 sbitmap_free (difference);
|
|
|
215 }
|
|
|
216
|
|
|
217 /* later(p,s) is dependent on the calculation of laterin(p).
|
|
|
218 laterin(p) is dependent on the calculation of later(p2,p).
|
|
|
219
|
|
|
220 laterin(ENTRY) is defined as all 0's
|
|
|
221 later(ENTRY, succs(ENTRY)) are defined using laterin(ENTRY)
|
|
|
222 laterin(succs(ENTRY)) is defined by later(ENTRY, succs(ENTRY)).
|
|
|
223
|
|
|
224 If we progress in this manner, starting with all basic blocks
|
|
|
225 in the work list, anytime we change later(bb), we need to add
|
|
|
226 succs(bb) to the worklist if they are not already on the worklist.
|
|
|
227
|
|
|
228 Boundary conditions:
|
|
|
229
|
|
|
230 We prime the worklist all the normal basic blocks. The ENTRY block can
|
|
|
231 never be added to the worklist since it is never the successor of any
|
|
|
232 block. We explicitly prevent the EXIT block from being added to the
|
|
|
233 worklist.
|
|
|
234
|
|
|
235 We optimistically initialize LATER. That is the only time this routine
|
|
|
236 will compute LATER for an edge out of the entry block since the entry
|
|
|
237 block is never on the worklist. Thus, LATERIN is neither used nor
|
|
|
238 computed for the ENTRY block.
|
|
|
239
|
|
|
240 Since the EXIT block is never added to the worklist, we will neither
|
|
|
241 use nor compute LATERIN for the exit block. Edges which reach the
|
|
|
242 EXIT block are handled in the normal fashion inside the loop. However,
|
|
|
243 the insertion/deletion computation needs LATERIN(EXIT), so we have
|
|
|
244 to compute it. */
|
|
|
245
|
|
|
246 static void
|
|
|
247 compute_laterin (struct edge_list *edge_list, sbitmap *earliest,
|
|
|
248 sbitmap *antloc, sbitmap *later, sbitmap *laterin)
|
|
|
249 {
|
|
|
250 int num_edges, i;
|
|
|
251 edge e;
|
|
|
252 basic_block *worklist, *qin, *qout, *qend, bb;
|
|
|
253 unsigned int qlen;
|
|
|
254 edge_iterator ei;
|
|
|
255
|
|
|
256 num_edges = NUM_EDGES (edge_list);
|
|
|
257
|
|
|
258 /* Allocate a worklist array/queue. Entries are only added to the
|
|
|
259 list if they were not already on the list. So the size is
|
|
|
260 bounded by the number of basic blocks. */
|
|
|
261 qin = qout = worklist
|
|
|
262 = XNEWVEC (basic_block, n_basic_blocks);
|
|
|
263
|
|
|
264 /* Initialize a mapping from each edge to its index. */
|
|
|
265 for (i = 0; i < num_edges; i++)
|
|
|
266 INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
|
|
|
267
|
|
|
268 /* We want a maximal solution, so initially consider LATER true for
|
|
|
269 all edges. This allows propagation through a loop since the incoming
|
|
|
270 loop edge will have LATER set, so if all the other incoming edges
|
|
|
271 to the loop are set, then LATERIN will be set for the head of the
|
|
|
272 loop.
|
|
|
273
|
|
|
274 If the optimistic setting of LATER on that edge was incorrect (for
|
|
|
275 example the expression is ANTLOC in a block within the loop) then
|
|
|
276 this algorithm will detect it when we process the block at the head
|
|
|
277 of the optimistic edge. That will requeue the affected blocks. */
|
|
|
278 sbitmap_vector_ones (later, num_edges);
|
|
|
279
|
|
|
280 /* Note that even though we want an optimistic setting of LATER, we
|
|
|
281 do not want to be overly optimistic. Consider an outgoing edge from
|
|
|
282 the entry block. That edge should always have a LATER value the
|
|
|
283 same as EARLIEST for that edge. */
|
|
|
284 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
|
|
|
285 sbitmap_copy (later[(size_t) e->aux], earliest[(size_t) e->aux]);
|
|
|
286
|
|
|
287 /* Add all the blocks to the worklist. This prevents an early exit from
|
|
|
288 the loop given our optimistic initialization of LATER above. */
|
|
|
289 FOR_EACH_BB (bb)
|
|
|
290 {
|
|
|
291 *qin++ = bb;
|
|
|
292 bb->aux = bb;
|
|
|
293 }
|
|
|
294
|
|
|
295 /* Note that we do not use the last allocated element for our queue,
|
|
|
296 as EXIT_BLOCK is never inserted into it. */
|
|
|
297 qin = worklist;
|
|
|
298 qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
|
|
|
299 qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
|
|
|
300
|
|
|
301 /* Iterate until the worklist is empty. */
|
|
|
302 while (qlen)
|
|
|
303 {
|
|
|
304 /* Take the first entry off the worklist. */
|
|
|
305 bb = *qout++;
|
|
|
306 bb->aux = NULL;
|
|
|
307 qlen--;
|
|
|
308 if (qout >= qend)
|
|
|
309 qout = worklist;
|
|
|
310
|
|
|
311 /* Compute the intersection of LATERIN for each incoming edge to B. */
|
|
|
312 sbitmap_ones (laterin[bb->index]);
|
|
|
313 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
314 sbitmap_a_and_b (laterin[bb->index], laterin[bb->index],
|
|
|
315 later[(size_t)e->aux]);
|
|
|
316
|
|
|
317 /* Calculate LATER for all outgoing edges. */
|
|
|
318 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
319 if (sbitmap_union_of_diff_cg (later[(size_t) e->aux],
|
|
|
320 earliest[(size_t) e->aux],
|
|
|
321 laterin[e->src->index],
|
|
|
322 antloc[e->src->index])
|
|
|
323 /* If LATER for an outgoing edge was changed, then we need
|
|
|
324 to add the target of the outgoing edge to the worklist. */
|
|
|
325 && e->dest != EXIT_BLOCK_PTR && e->dest->aux == 0)
|
|
|
326 {
|
|
|
327 *qin++ = e->dest;
|
|
|
328 e->dest->aux = e;
|
|
|
329 qlen++;
|
|
|
330 if (qin >= qend)
|
|
|
331 qin = worklist;
|
|
|
332 }
|
|
|
333 }
|
|
|
334
|
|
|
335 /* Computation of insertion and deletion points requires computing LATERIN
|
|
|
336 for the EXIT block. We allocated an extra entry in the LATERIN array
|
|
|
337 for just this purpose. */
|
|
|
338 sbitmap_ones (laterin[last_basic_block]);
|
|
|
339 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
|
|
|
340 sbitmap_a_and_b (laterin[last_basic_block],
|
|
|
341 laterin[last_basic_block],
|
|
|
342 later[(size_t) e->aux]);
|
|
|
343
|
|
|
344 clear_aux_for_edges ();
|
|
|
345 free (worklist);
|
|
|
346 }
|
|
|
347
|
|
|
348 /* Compute the insertion and deletion points for edge based LCM. */
|
|
|
349
|
|
|
350 static void
|
|
|
351 compute_insert_delete (struct edge_list *edge_list, sbitmap *antloc,
|
|
|
352 sbitmap *later, sbitmap *laterin, sbitmap *insert,
|
|
|
353 sbitmap *del)
|
|
|
354 {
|
|
|
355 int x;
|
|
|
356 basic_block bb;
|
|
|
357
|
|
|
358 FOR_EACH_BB (bb)
|
|
|
359 sbitmap_difference (del[bb->index], antloc[bb->index],
|
|
|
360 laterin[bb->index]);
|
|
|
361
|
|
|
362 for (x = 0; x < NUM_EDGES (edge_list); x++)
|
|
|
363 {
|
|
|
364 basic_block b = INDEX_EDGE_SUCC_BB (edge_list, x);
|
|
|
365
|
|
|
366 if (b == EXIT_BLOCK_PTR)
|
|
|
367 sbitmap_difference (insert[x], later[x], laterin[last_basic_block]);
|
|
|
368 else
|
|
|
369 sbitmap_difference (insert[x], later[x], laterin[b->index]);
|
|
|
370 }
|
|
|
371 }
|
|
|
372
|
|
|
373 /* Given local properties TRANSP, ANTLOC, AVOUT, KILL return the insert and
|
|
|
374 delete vectors for edge based LCM. Returns an edgelist which is used to
|
|
|
375 map the insert vector to what edge an expression should be inserted on. */
|
|
|
376
|
|
|
377 struct edge_list *
|
|
|
378 pre_edge_lcm (int n_exprs, sbitmap *transp,
|
|
|
379 sbitmap *avloc, sbitmap *antloc, sbitmap *kill,
|
|
|
380 sbitmap **insert, sbitmap **del)
|
|
|
381 {
|
|
|
382 sbitmap *antin, *antout, *earliest;
|
|
|
383 sbitmap *avin, *avout;
|
|
|
384 sbitmap *later, *laterin;
|
|
|
385 struct edge_list *edge_list;
|
|
|
386 int num_edges;
|
|
|
387
|
|
|
388 edge_list = create_edge_list ();
|
|
|
389 num_edges = NUM_EDGES (edge_list);
|
|
|
390
|
|
|
391 #ifdef LCM_DEBUG_INFO
|
|
|
392 if (dump_file)
|
|
|
393 {
|
|
|
394 fprintf (dump_file, "Edge List:\n");
|
|
|
395 verify_edge_list (dump_file, edge_list);
|
|
|
396 print_edge_list (dump_file, edge_list);
|
|
|
397 dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block);
|
|
|
398 dump_sbitmap_vector (dump_file, "antloc", "", antloc, last_basic_block);
|
|
|
399 dump_sbitmap_vector (dump_file, "avloc", "", avloc, last_basic_block);
|
|
|
400 dump_sbitmap_vector (dump_file, "kill", "", kill, last_basic_block);
|
|
|
401 }
|
|
|
402 #endif
|
|
|
403
|
|
|
404 /* Compute global availability. */
|
|
|
405 avin = sbitmap_vector_alloc (last_basic_block, n_exprs);
|
|
|
406 avout = sbitmap_vector_alloc (last_basic_block, n_exprs);
|
|
|
407 compute_available (avloc, kill, avout, avin);
|
|
|
408 sbitmap_vector_free (avin);
|
|
|
409
|
|
|
410 /* Compute global anticipatability. */
|
|
|
411 antin = sbitmap_vector_alloc (last_basic_block, n_exprs);
|
|
|
412 antout = sbitmap_vector_alloc (last_basic_block, n_exprs);
|
|
|
413 compute_antinout_edge (antloc, transp, antin, antout);
|
|
|
414
|
|
|
415 #ifdef LCM_DEBUG_INFO
|
|
|
416 if (dump_file)
|
|
|
417 {
|
|
|
418 dump_sbitmap_vector (dump_file, "antin", "", antin, last_basic_block);
|
|
|
419 dump_sbitmap_vector (dump_file, "antout", "", antout, last_basic_block);
|
|
|
420 }
|
|
|
421 #endif
|
|
|
422
|
|
|
423 /* Compute earliestness. */
|
|
|
424 earliest = sbitmap_vector_alloc (num_edges, n_exprs);
|
|
|
425 compute_earliest (edge_list, n_exprs, antin, antout, avout, kill, earliest);
|
|
|
426
|
|
|
427 #ifdef LCM_DEBUG_INFO
|
|
|
428 if (dump_file)
|
|
|
429 dump_sbitmap_vector (dump_file, "earliest", "", earliest, num_edges);
|
|
|
430 #endif
|
|
|
431
|
|
|
432 sbitmap_vector_free (antout);
|
|
|
433 sbitmap_vector_free (antin);
|
|
|
434 sbitmap_vector_free (avout);
|
|
|
435
|
|
|
436 later = sbitmap_vector_alloc (num_edges, n_exprs);
|
|
|
437
|
|
|
438 /* Allocate an extra element for the exit block in the laterin vector. */
|
|
|
439 laterin = sbitmap_vector_alloc (last_basic_block + 1, n_exprs);
|
|
|
440 compute_laterin (edge_list, earliest, antloc, later, laterin);
|
|
|
441
|
|
|
442 #ifdef LCM_DEBUG_INFO
|
|
|
443 if (dump_file)
|
|
|
444 {
|
|
|
445 dump_sbitmap_vector (dump_file, "laterin", "", laterin, last_basic_block + 1);
|
|
|
446 dump_sbitmap_vector (dump_file, "later", "", later, num_edges);
|
|
|
447 }
|
|
|
448 #endif
|
|
|
449
|
|
|
450 sbitmap_vector_free (earliest);
|
|
|
451
|
|
|
452 *insert = sbitmap_vector_alloc (num_edges, n_exprs);
|
|
|
453 *del = sbitmap_vector_alloc (last_basic_block, n_exprs);
|
|
|
454 compute_insert_delete (edge_list, antloc, later, laterin, *insert, *del);
|
|
|
455
|
|
|
456 sbitmap_vector_free (laterin);
|
|
|
457 sbitmap_vector_free (later);
|
|
|
458
|
|
|
459 #ifdef LCM_DEBUG_INFO
|
|
|
460 if (dump_file)
|
|
|
461 {
|
|
|
462 dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
|
|
|
463 dump_sbitmap_vector (dump_file, "pre_delete_map", "", *del,
|
|
|
464 last_basic_block);
|
|
|
465 }
|
|
|
466 #endif
|
|
|
467
|
|
|
468 return edge_list;
|
|
|
469 }
|
|
|
470
|
|
|
471 /* Compute the AVIN and AVOUT vectors from the AVLOC and KILL vectors.
|
|
|
472 Return the number of passes we performed to iterate to a solution. */
|
|
|
473
|
|
|
474 void
|
|
|
475 compute_available (sbitmap *avloc, sbitmap *kill, sbitmap *avout,
|
|
|
476 sbitmap *avin)
|
|
|
477 {
|
|
|
478 edge e;
|
|
|
479 basic_block *worklist, *qin, *qout, *qend, bb;
|
|
|
480 unsigned int qlen;
|
|
|
481 edge_iterator ei;
|
|
|
482
|
|
|
483 /* Allocate a worklist array/queue. Entries are only added to the
|
|
|
484 list if they were not already on the list. So the size is
|
|
|
485 bounded by the number of basic blocks. */
|
|
|
486 qin = qout = worklist =
|
|
|
487 XNEWVEC (basic_block, n_basic_blocks - NUM_FIXED_BLOCKS);
|
|
|
488
|
|
|
489 /* We want a maximal solution. */
|
|
|
490 sbitmap_vector_ones (avout, last_basic_block);
|
|
|
491
|
|
|
492 /* Put every block on the worklist; this is necessary because of the
|
|
|
493 optimistic initialization of AVOUT above. */
|
|
|
494 FOR_EACH_BB (bb)
|
|
|
495 {
|
|
|
496 *qin++ = bb;
|
|
|
497 bb->aux = bb;
|
|
|
498 }
|
|
|
499
|
|
|
500 qin = worklist;
|
|
|
501 qend = &worklist[n_basic_blocks - NUM_FIXED_BLOCKS];
|
|
|
502 qlen = n_basic_blocks - NUM_FIXED_BLOCKS;
|
|
|
503
|
|
|
504 /* Mark blocks which are successors of the entry block so that we
|
|
|
505 can easily identify them below. */
|
|
|
506 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
|
|
|
507 e->dest->aux = ENTRY_BLOCK_PTR;
|
|
|
508
|
|
|
509 /* Iterate until the worklist is empty. */
|
|
|
510 while (qlen)
|
|
|
511 {
|
|
|
512 /* Take the first entry off the worklist. */
|
|
|
513 bb = *qout++;
|
|
|
514 qlen--;
|
|
|
515
|
|
|
516 if (qout >= qend)
|
|
|
517 qout = worklist;
|
|
|
518
|
|
|
519 /* If one of the predecessor blocks is the ENTRY block, then the
|
|
|
520 intersection of avouts is the null set. We can identify such blocks
|
|
|
521 by the special value in the AUX field in the block structure. */
|
|
|
522 if (bb->aux == ENTRY_BLOCK_PTR)
|
|
|
523 /* Do not clear the aux field for blocks which are successors of the
|
|
|
524 ENTRY block. That way we never add then to the worklist again. */
|
|
|
525 sbitmap_zero (avin[bb->index]);
|
|
|
526 else
|
|
|
527 {
|
|
|
528 /* Clear the aux field of this block so that it can be added to
|
|
|
529 the worklist again if necessary. */
|
|
|
530 bb->aux = NULL;
|
|
|
531 sbitmap_intersection_of_preds (avin[bb->index], avout, bb->index);
|
|
|
532 }
|
|
|
533
|
|
|
534 if (sbitmap_union_of_diff_cg (avout[bb->index], avloc[bb->index],
|
|
|
535 avin[bb->index], kill[bb->index]))
|
|
|
536 /* If the out state of this block changed, then we need
|
|
|
537 to add the successors of this block to the worklist
|
|
|
538 if they are not already on the worklist. */
|
|
|
539 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
540 if (!e->dest->aux && e->dest != EXIT_BLOCK_PTR)
|
|
|
541 {
|
|
|
542 *qin++ = e->dest;
|
|
|
543 e->dest->aux = e;
|
|
|
544 qlen++;
|
|
|
545
|
|
|
546 if (qin >= qend)
|
|
|
547 qin = worklist;
|
|
|
548 }
|
|
|
549 }
|
|
|
550
|
|
|
551 clear_aux_for_edges ();
|
|
|
552 clear_aux_for_blocks ();
|
|
|
553 free (worklist);
|
|
|
554 }
|
|
|
555
|
|
|
556 /* Compute the farthest vector for edge based lcm. */
|
|
|
557
|
|
|
558 static void
|
|
|
559 compute_farthest (struct edge_list *edge_list, int n_exprs,
|
|
|
560 sbitmap *st_avout, sbitmap *st_avin, sbitmap *st_antin,
|
|
|
561 sbitmap *kill, sbitmap *farthest)
|
|
|
562 {
|
|
|
563 sbitmap difference, temp_bitmap;
|
|
|
564 int x, num_edges;
|
|
|
565 basic_block pred, succ;
|
|
|
566
|
|
|
567 num_edges = NUM_EDGES (edge_list);
|
|
|
568
|
|
|
569 difference = sbitmap_alloc (n_exprs);
|
|
|
570 temp_bitmap = sbitmap_alloc (n_exprs);
|
|
|
571
|
|
|
572 for (x = 0; x < num_edges; x++)
|
|
|
573 {
|
|
|
574 pred = INDEX_EDGE_PRED_BB (edge_list, x);
|
|
|
575 succ = INDEX_EDGE_SUCC_BB (edge_list, x);
|
|
|
576 if (succ == EXIT_BLOCK_PTR)
|
|
|
577 sbitmap_copy (farthest[x], st_avout[pred->index]);
|
|
|
578 else
|
|
|
579 {
|
|
|
580 if (pred == ENTRY_BLOCK_PTR)
|
|
|
581 sbitmap_zero (farthest[x]);
|
|
|
582 else
|
|
|
583 {
|
|
|
584 sbitmap_difference (difference, st_avout[pred->index],
|
|
|
585 st_antin[succ->index]);
|
|
|
586 sbitmap_not (temp_bitmap, st_avin[succ->index]);
|
|
|
587 sbitmap_a_and_b_or_c (farthest[x], difference,
|
|
|
588 kill[succ->index], temp_bitmap);
|
|
|
589 }
|
|
|
590 }
|
|
|
591 }
|
|
|
592
|
|
|
593 sbitmap_free (temp_bitmap);
|
|
|
594 sbitmap_free (difference);
|
|
|
595 }
|
|
|
596
|
|
|
597 /* Compute nearer and nearerout vectors for edge based lcm.
|
|
|
598
|
|
|
599 This is the mirror of compute_laterin, additional comments on the
|
|
|
600 implementation can be found before compute_laterin. */
|
|
|
601
|
|
|
602 static void
|
|
|
603 compute_nearerout (struct edge_list *edge_list, sbitmap *farthest,
|
|
|
604 sbitmap *st_avloc, sbitmap *nearer, sbitmap *nearerout)
|
|
|
605 {
|
|
|
606 int num_edges, i;
|
|
|
607 edge e;
|
|
|
608 basic_block *worklist, *tos, bb;
|
|
|
609 edge_iterator ei;
|
|
|
610
|
|
|
611 num_edges = NUM_EDGES (edge_list);
|
|
|
612
|
|
|
613 /* Allocate a worklist array/queue. Entries are only added to the
|
|
|
614 list if they were not already on the list. So the size is
|
|
|
615 bounded by the number of basic blocks. */
|
|
|
616 tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1);
|
|
|
617
|
|
|
618 /* Initialize NEARER for each edge and build a mapping from an edge to
|
|
|
619 its index. */
|
|
|
620 for (i = 0; i < num_edges; i++)
|
|
|
621 INDEX_EDGE (edge_list, i)->aux = (void *) (size_t) i;
|
|
|
622
|
|
|
623 /* We want a maximal solution. */
|
|
|
624 sbitmap_vector_ones (nearer, num_edges);
|
|
|
625
|
|
|
626 /* Note that even though we want an optimistic setting of NEARER, we
|
|
|
627 do not want to be overly optimistic. Consider an incoming edge to
|
|
|
628 the exit block. That edge should always have a NEARER value the
|
|
|
629 same as FARTHEST for that edge. */
|
|
|
630 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
|
|
|
631 sbitmap_copy (nearer[(size_t)e->aux], farthest[(size_t)e->aux]);
|
|
|
632
|
|
|
633 /* Add all the blocks to the worklist. This prevents an early exit
|
|
|
634 from the loop given our optimistic initialization of NEARER. */
|
|
|
635 FOR_EACH_BB (bb)
|
|
|
636 {
|
|
|
637 *tos++ = bb;
|
|
|
638 bb->aux = bb;
|
|
|
639 }
|
|
|
640
|
|
|
641 /* Iterate until the worklist is empty. */
|
|
|
642 while (tos != worklist)
|
|
|
643 {
|
|
|
644 /* Take the first entry off the worklist. */
|
|
|
645 bb = *--tos;
|
|
|
646 bb->aux = NULL;
|
|
|
647
|
|
|
648 /* Compute the intersection of NEARER for each outgoing edge from B. */
|
|
|
649 sbitmap_ones (nearerout[bb->index]);
|
|
|
650 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
651 sbitmap_a_and_b (nearerout[bb->index], nearerout[bb->index],
|
|
|
652 nearer[(size_t) e->aux]);
|
|
|
653
|
|
|
654 /* Calculate NEARER for all incoming edges. */
|
|
|
655 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
656 if (sbitmap_union_of_diff_cg (nearer[(size_t) e->aux],
|
|
|
657 farthest[(size_t) e->aux],
|
|
|
658 nearerout[e->dest->index],
|
|
|
659 st_avloc[e->dest->index])
|
|
|
660 /* If NEARER for an incoming edge was changed, then we need
|
|
|
661 to add the source of the incoming edge to the worklist. */
|
|
|
662 && e->src != ENTRY_BLOCK_PTR && e->src->aux == 0)
|
|
|
663 {
|
|
|
664 *tos++ = e->src;
|
|
|
665 e->src->aux = e;
|
|
|
666 }
|
|
|
667 }
|
|
|
668
|
|
|
669 /* Computation of insertion and deletion points requires computing NEAREROUT
|
|
|
670 for the ENTRY block. We allocated an extra entry in the NEAREROUT array
|
|
|
671 for just this purpose. */
|
|
|
672 sbitmap_ones (nearerout[last_basic_block]);
|
|
|
673 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
|
|
|
674 sbitmap_a_and_b (nearerout[last_basic_block],
|
|
|
675 nearerout[last_basic_block],
|
|
|
676 nearer[(size_t) e->aux]);
|
|
|
677
|
|
|
678 clear_aux_for_edges ();
|
|
|
679 free (tos);
|
|
|
680 }
|
|
|
681
|
|
|
682 /* Compute the insertion and deletion points for edge based LCM. */
|
|
|
683
|
|
|
684 static void
|
|
|
685 compute_rev_insert_delete (struct edge_list *edge_list, sbitmap *st_avloc,
|
|
|
686 sbitmap *nearer, sbitmap *nearerout,
|
|
|
687 sbitmap *insert, sbitmap *del)
|
|
|
688 {
|
|
|
689 int x;
|
|
|
690 basic_block bb;
|
|
|
691
|
|
|
692 FOR_EACH_BB (bb)
|
|
|
693 sbitmap_difference (del[bb->index], st_avloc[bb->index],
|
|
|
694 nearerout[bb->index]);
|
|
|
695
|
|
|
696 for (x = 0; x < NUM_EDGES (edge_list); x++)
|
|
|
697 {
|
|
|
698 basic_block b = INDEX_EDGE_PRED_BB (edge_list, x);
|
|
|
699 if (b == ENTRY_BLOCK_PTR)
|
|
|
700 sbitmap_difference (insert[x], nearer[x], nearerout[last_basic_block]);
|
|
|
701 else
|
|
|
702 sbitmap_difference (insert[x], nearer[x], nearerout[b->index]);
|
|
|
703 }
|
|
|
704 }
|
|
|
705
|
|
|
706 /* Given local properties TRANSP, ST_AVLOC, ST_ANTLOC, KILL return the
|
|
|
707 insert and delete vectors for edge based reverse LCM. Returns an
|
|
|
708 edgelist which is used to map the insert vector to what edge
|
|
|
709 an expression should be inserted on. */
|
|
|
710
|
|
|
711 struct edge_list *
|
|
|
712 pre_edge_rev_lcm (int n_exprs, sbitmap *transp,
|
|
|
713 sbitmap *st_avloc, sbitmap *st_antloc, sbitmap *kill,
|
|
|
714 sbitmap **insert, sbitmap **del)
|
|
|
715 {
|
|
|
716 sbitmap *st_antin, *st_antout;
|
|
|
717 sbitmap *st_avout, *st_avin, *farthest;
|
|
|
718 sbitmap *nearer, *nearerout;
|
|
|
719 struct edge_list *edge_list;
|
|
|
720 int num_edges;
|
|
|
721
|
|
|
722 edge_list = create_edge_list ();
|
|
|
723 num_edges = NUM_EDGES (edge_list);
|
|
|
724
|
|
|
725 st_antin = sbitmap_vector_alloc (last_basic_block, n_exprs);
|
|
|
726 st_antout = sbitmap_vector_alloc (last_basic_block, n_exprs);
|
|
|
727 sbitmap_vector_zero (st_antin, last_basic_block);
|
|
|
728 sbitmap_vector_zero (st_antout, last_basic_block);
|
|
|
729 compute_antinout_edge (st_antloc, transp, st_antin, st_antout);
|
|
|
730
|
|
|
731 /* Compute global anticipatability. */
|
|
|
732 st_avout = sbitmap_vector_alloc (last_basic_block, n_exprs);
|
|
|
733 st_avin = sbitmap_vector_alloc (last_basic_block, n_exprs);
|
|
|
734 compute_available (st_avloc, kill, st_avout, st_avin);
|
|
|
735
|
|
|
736 #ifdef LCM_DEBUG_INFO
|
|
|
737 if (dump_file)
|
|
|
738 {
|
|
|
739 fprintf (dump_file, "Edge List:\n");
|
|
|
740 verify_edge_list (dump_file, edge_list);
|
|
|
741 print_edge_list (dump_file, edge_list);
|
|
|
742 dump_sbitmap_vector (dump_file, "transp", "", transp, last_basic_block);
|
|
|
743 dump_sbitmap_vector (dump_file, "st_avloc", "", st_avloc, last_basic_block);
|
|
|
744 dump_sbitmap_vector (dump_file, "st_antloc", "", st_antloc, last_basic_block);
|
|
|
745 dump_sbitmap_vector (dump_file, "st_antin", "", st_antin, last_basic_block);
|
|
|
746 dump_sbitmap_vector (dump_file, "st_antout", "", st_antout, last_basic_block);
|
|
|
747 dump_sbitmap_vector (dump_file, "st_kill", "", kill, last_basic_block);
|
|
|
748 }
|
|
|
749 #endif
|
|
|
750
|
|
|
751 #ifdef LCM_DEBUG_INFO
|
|
|
752 if (dump_file)
|
|
|
753 {
|
|
|
754 dump_sbitmap_vector (dump_file, "st_avout", "", st_avout, last_basic_block);
|
|
|
755 dump_sbitmap_vector (dump_file, "st_avin", "", st_avin, last_basic_block);
|
|
|
756 }
|
|
|
757 #endif
|
|
|
758
|
|
|
759 /* Compute farthestness. */
|
|
|
760 farthest = sbitmap_vector_alloc (num_edges, n_exprs);
|
|
|
761 compute_farthest (edge_list, n_exprs, st_avout, st_avin, st_antin,
|
|
|
762 kill, farthest);
|
|
|
763
|
|
|
764 #ifdef LCM_DEBUG_INFO
|
|
|
765 if (dump_file)
|
|
|
766 dump_sbitmap_vector (dump_file, "farthest", "", farthest, num_edges);
|
|
|
767 #endif
|
|
|
768
|
|
|
769 sbitmap_vector_free (st_antin);
|
|
|
770 sbitmap_vector_free (st_antout);
|
|
|
771
|
|
|
772 sbitmap_vector_free (st_avin);
|
|
|
773 sbitmap_vector_free (st_avout);
|
|
|
774
|
|
|
775 nearer = sbitmap_vector_alloc (num_edges, n_exprs);
|
|
|
776
|
|
|
777 /* Allocate an extra element for the entry block. */
|
|
|
778 nearerout = sbitmap_vector_alloc (last_basic_block + 1, n_exprs);
|
|
|
779 compute_nearerout (edge_list, farthest, st_avloc, nearer, nearerout);
|
|
|
780
|
|
|
781 #ifdef LCM_DEBUG_INFO
|
|
|
782 if (dump_file)
|
|
|
783 {
|
|
|
784 dump_sbitmap_vector (dump_file, "nearerout", "", nearerout,
|
|
|
785 last_basic_block + 1);
|
|
|
786 dump_sbitmap_vector (dump_file, "nearer", "", nearer, num_edges);
|
|
|
787 }
|
|
|
788 #endif
|
|
|
789
|
|
|
790 sbitmap_vector_free (farthest);
|
|
|
791
|
|
|
792 *insert = sbitmap_vector_alloc (num_edges, n_exprs);
|
|
|
793 *del = sbitmap_vector_alloc (last_basic_block, n_exprs);
|
|
|
794 compute_rev_insert_delete (edge_list, st_avloc, nearer, nearerout,
|
|
|
795 *insert, *del);
|
|
|
796
|
|
|
797 sbitmap_vector_free (nearerout);
|
|
|
798 sbitmap_vector_free (nearer);
|
|
|
799
|
|
|
800 #ifdef LCM_DEBUG_INFO
|
|
|
801 if (dump_file)
|
|
|
802 {
|
|
|
803 dump_sbitmap_vector (dump_file, "pre_insert_map", "", *insert, num_edges);
|
|
|
804 dump_sbitmap_vector (dump_file, "pre_delete_map", "", *del,
|
|
|
805 last_basic_block);
|
|
|
806 }
|
|
|
807 #endif
|
|
|
808 return edge_list;
|
|
|
809 }
|
|
|
810
|
