|
0
|
1 /* RTL factoring (sequence abstraction).
|
|
|
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 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 under
|
|
|
7 the terms of the GNU General Public License as published by the Free
|
|
|
8 Software Foundation; either version 3, or (at your option) any later
|
|
|
9 version.
|
|
|
10
|
|
|
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
|
|
|
12 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 COPYING3. If not see
|
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
|
19
|
|
|
20 #include "config.h"
|
|
|
21 #include "system.h"
|
|
|
22 #include "coretypes.h"
|
|
|
23 #include "tm.h"
|
|
|
24 #include "rtl.h"
|
|
|
25 #include "obstack.h"
|
|
|
26 #include "basic-block.h"
|
|
|
27 #include "resource.h"
|
|
|
28 #include "flags.h"
|
|
|
29 #include "ggc.h"
|
|
|
30 #include "regs.h"
|
|
|
31 #include "params.h"
|
|
|
32 #include "expr.h"
|
|
|
33 #include "tm_p.h"
|
|
|
34 #include "tree-pass.h"
|
|
|
35 #include "tree-flow.h"
|
|
|
36 #include "timevar.h"
|
|
|
37 #include "output.h"
|
|
|
38 #include "df.h"
|
|
|
39 #include "addresses.h"
|
|
|
40
|
|
|
41 /* Sequence abstraction:
|
|
|
42
|
|
|
43 It is a size optimization method. The main idea of this technique is to
|
|
|
44 find identical sequences of code, which can be turned into procedures and
|
|
|
45 then replace all occurrences with calls to the newly created subroutine.
|
|
|
46 It is kind of an opposite of function inlining.
|
|
|
47
|
|
|
48 There are four major parts of this file:
|
|
|
49
|
|
|
50 sequence fingerprint
|
|
|
51 In order to avoid the comparison of every insn with every other, hash
|
|
|
52 value will be designed for every insn by COMPUTE_HASH.
|
|
|
53 These hash values are used for grouping the sequence candidates. So
|
|
|
54 we only need to compare every insn with every other in same hash group.
|
|
|
55
|
|
|
56 FILL_HASH_BUCKET creates all hash values and stores into HASH_BUCKETS.
|
|
|
57 The result is used by COLLECT_PATTERN_SEQS.
|
|
|
58
|
|
|
59 code matching
|
|
|
60 In code matching the algorithm compares every two possible sequence
|
|
|
61 candidates which last insns are in the same hash group. If these
|
|
|
62 sequences are identical they will be stored and do further searches for
|
|
|
63 finding more sequences which are identical with the first one.
|
|
|
64
|
|
|
65 COLLECT_PATTERN_SEQS does the code matching and stores the results into
|
|
|
66 PATTERN_SEQS.
|
|
|
67
|
|
|
68 gain computation
|
|
|
69 This part computes the gain of abstraction which could be archived when
|
|
|
70 turning the pattern sequence into a pseudo-function and its matching
|
|
|
71 sequences into pseudo-calls. After it the most effective sequences will
|
|
|
72 be marked for abstraction.
|
|
|
73
|
|
|
74 RECOMPUTE_GAIN does the gain computation. The sequences with the maximum
|
|
|
75 gain is on the top of PATTERN_SEQS.
|
|
|
76
|
|
|
77 abstract code
|
|
|
78 This part turns the pattern sequence into a pseudo-function and its
|
|
|
79 matching sequences into pseudo-calls.
|
|
|
80
|
|
|
81 ABSTRACT_BEST_SEQ does the code merging.
|
|
|
82
|
|
|
83
|
|
|
84 C code example:
|
|
|
85
|
|
|
86 // Original source // After sequence abstraction
|
|
|
87 { {
|
|
|
88 void *jump_label;
|
|
|
89 ... ...
|
|
|
90 jump_label = &&exit_0;
|
|
|
91 entry_0:
|
|
|
92 I0; I0;
|
|
|
93 I1; I1;
|
|
|
94 I2; I2;
|
|
|
95 I3; I3;
|
|
|
96 goto *jump_label;
|
|
|
97 exit_0:
|
|
|
98 ... ...
|
|
|
99 jump_label = &&exit_1;
|
|
|
100 goto entry_0;
|
|
|
101 I0;
|
|
|
102 I1;
|
|
|
103 I2;
|
|
|
104 I3;
|
|
|
105 exit_1:
|
|
|
106 ... ...
|
|
|
107 jump_label = &&exit_2;
|
|
|
108 goto entry_0;
|
|
|
109 I0;
|
|
|
110 I1;
|
|
|
111 I2;
|
|
|
112 I3;
|
|
|
113 exit_2:
|
|
|
114 ... ...
|
|
|
115 jump_label = &&exit_3;
|
|
|
116 goto entry_0;
|
|
|
117 I0;
|
|
|
118 I1;
|
|
|
119 I2;
|
|
|
120 I3;
|
|
|
121 exit_3:
|
|
|
122 ... ...
|
|
|
123 } }
|
|
|
124
|
|
|
125
|
|
|
126 TODO:
|
|
|
127 - Use REG_ALLOC_ORDER when choosing link register.
|
|
|
128 - Handle JUMP_INSNs. Also handle volatile function calls (handle them
|
|
|
129 similar to unconditional jumps.)
|
|
|
130 - Test command line option -fpic.
|
|
|
131 */
|
|
|
132
|
|
|
133 /* Predicate yielding nonzero iff X is an abstractable insn. Non-jump insns are
|
|
|
134 abstractable. */
|
|
|
135 #define ABSTRACTABLE_INSN_P(X) (INSN_P (X) && !JUMP_P (X))
|
|
|
136
|
|
|
137 /* First parameter of the htab_create function call. */
|
|
|
138 #define HASH_INIT 1023
|
|
|
139
|
|
|
140 /* Multiplier for cost of sequence call to avoid abstracting short
|
|
|
141 sequences. */
|
|
|
142 #ifndef SEQ_CALL_COST_MULTIPLIER
|
|
|
143 #define SEQ_CALL_COST_MULTIPLIER 2
|
|
|
144 #endif
|
|
|
145
|
|
|
146 /* Recomputes the cost of MSEQ pattern/matching sequence. */
|
|
|
147 #define RECOMPUTE_COST(SEQ) \
|
|
|
148 { \
|
|
|
149 int l; \
|
|
|
150 rtx x = SEQ->insn; \
|
|
|
151 SEQ->cost = 0; \
|
|
|
152 for (l = 0; l < SEQ->abstracted_length; l++) \
|
|
|
153 { \
|
|
|
154 SEQ->cost += compute_rtx_cost (x); \
|
|
|
155 x = prev_insn_in_block (x); \
|
|
|
156 } \
|
|
|
157 }
|
|
|
158
|
|
|
159 /* A sequence matching a pattern sequence. */
|
|
|
160 typedef struct matching_seq_def
|
|
|
161 {
|
|
|
162 /* The last insn in the matching sequence. */
|
|
|
163 rtx insn;
|
|
|
164
|
|
|
165 /* Index of INSN instruction. */
|
|
|
166 unsigned long idx;
|
|
|
167
|
|
|
168 /* The number of insns matching in this sequence and the pattern sequence.
|
|
|
169 */
|
|
|
170 int matching_length;
|
|
|
171
|
|
|
172 /* The number of insns selected to abstract from this sequence. Less than
|
|
|
173 or equal to MATCHING_LENGTH. */
|
|
|
174 int abstracted_length;
|
|
|
175
|
|
|
176 /* The cost of the sequence. */
|
|
|
177 int cost;
|
|
|
178
|
|
|
179 /* The next sequence in the chain matching the same pattern. */
|
|
|
180 struct matching_seq_def *next_matching_seq;
|
|
|
181 } *matching_seq;
|
|
|
182
|
|
|
183
|
|
|
184 /* A pattern instruction sequence. */
|
|
|
185 typedef struct pattern_seq_def
|
|
|
186 {
|
|
|
187 /* The last insn in the pattern sequence. */
|
|
|
188 rtx insn;
|
|
|
189
|
|
|
190 /* Index of INSN instruction. */
|
|
|
191 unsigned long idx;
|
|
|
192
|
|
|
193 /* The gain of transforming the pattern sequence into a pseudo-function and
|
|
|
194 the matching sequences into pseudo-calls. */
|
|
|
195 int gain;
|
|
|
196
|
|
|
197 /* The maximum of the ABSTRACTED_LENGTH of the matching sequences. */
|
|
|
198 int abstracted_length;
|
|
|
199
|
|
|
200 /* The cost of the sequence. */
|
|
|
201 int cost;
|
|
|
202
|
|
|
203 /* The register used to hold the return address during the pseudo-call. */
|
|
|
204 rtx link_reg;
|
|
|
205
|
|
|
206 /* The sequences matching this pattern. */
|
|
|
207 matching_seq matching_seqs;
|
|
|
208
|
|
|
209 /* The next pattern sequence in the chain. */
|
|
|
210 struct pattern_seq_def *next_pattern_seq;
|
|
|
211 } *pattern_seq;
|
|
|
212
|
|
|
213
|
|
|
214 /* A block of a pattern sequence. */
|
|
|
215 typedef struct seq_block_def
|
|
|
216 {
|
|
|
217 /* The number of insns in the block. */
|
|
|
218 int length;
|
|
|
219
|
|
|
220 /* The code_label of the block. */
|
|
|
221 rtx label;
|
|
|
222
|
|
|
223 /* The sequences entering the pattern sequence at LABEL. */
|
|
|
224 matching_seq matching_seqs;
|
|
|
225
|
|
|
226 /* The next block in the chain. The blocks are sorted by LENGTH in
|
|
|
227 ascending order. */
|
|
|
228 struct seq_block_def *next_seq_block;
|
|
|
229 } *seq_block;
|
|
|
230
|
|
|
231 /* Contains same sequence candidates for further searching. */
|
|
|
232 typedef struct hash_bucket_def
|
|
|
233 {
|
|
|
234 /* The hash value of the group. */
|
|
|
235 unsigned int hash;
|
|
|
236
|
|
|
237 /* List of sequence candidates. */
|
|
|
238 htab_t seq_candidates;
|
|
|
239 } *p_hash_bucket;
|
|
|
240 typedef const struct hash_bucket_def *const_p_hash_bucket;
|
|
|
241
|
|
|
242 /* Contains the last insn of the sequence, and its index value. */
|
|
|
243 typedef struct hash_elem_def
|
|
|
244 {
|
|
|
245 /* Unique index; ordered by FILL_HASH_BUCKET. */
|
|
|
246 unsigned long idx;
|
|
|
247
|
|
|
248 /* The last insn in the sequence. */
|
|
|
249 rtx insn;
|
|
|
250
|
|
|
251 /* The cached length of the insn. */
|
|
|
252 int length;
|
|
|
253 } *p_hash_elem;
|
|
|
254 typedef const struct hash_elem_def *const_p_hash_elem;
|
|
|
255
|
|
|
256 /* The list of same sequence candidates. */
|
|
|
257 static htab_t hash_buckets;
|
|
|
258
|
|
|
259 /* The pattern sequences collected from the current functions. */
|
|
|
260 static pattern_seq pattern_seqs;
|
|
|
261
|
|
|
262 /* The blocks of the current pattern sequence. */
|
|
|
263 static seq_block seq_blocks;
|
|
|
264
|
|
|
265 /* Cost of calling sequence. */
|
|
|
266 static int seq_call_cost;
|
|
|
267
|
|
|
268 /* Cost of jump. */
|
|
|
269 static int seq_jump_cost;
|
|
|
270
|
|
|
271 /* Cost of returning. */
|
|
|
272 static int seq_return_cost;
|
|
|
273
|
|
|
274 /* Returns the first insn preceding INSN for which INSN_P is true and belongs to
|
|
|
275 the same basic block. Returns NULL_RTX if no such insn can be found. */
|
|
|
276
|
|
|
277 static rtx
|
|
|
278 prev_insn_in_block (rtx insn)
|
|
|
279 {
|
|
|
280 basic_block bb = BLOCK_FOR_INSN (insn);
|
|
|
281
|
|
|
282 if (!bb)
|
|
|
283 return NULL_RTX;
|
|
|
284
|
|
|
285 while (insn != BB_HEAD (bb))
|
|
|
286 {
|
|
|
287 insn = PREV_INSN (insn);
|
|
|
288 if (INSN_P (insn))
|
|
|
289 return insn;
|
|
|
290 }
|
|
|
291 return NULL_RTX;
|
|
|
292 }
|
|
|
293
|
|
|
294 /* Returns the hash value of INSN. */
|
|
|
295
|
|
|
296 static unsigned int
|
|
|
297 compute_hash (rtx insn)
|
|
|
298 {
|
|
|
299 unsigned int hash = 0;
|
|
|
300 rtx prev;
|
|
|
301
|
|
|
302 hash = INSN_CODE (insn) * 100;
|
|
|
303
|
|
|
304 prev = prev_insn_in_block (insn);
|
|
|
305 if (prev)
|
|
|
306 hash += INSN_CODE (prev);
|
|
|
307
|
|
|
308 return hash;
|
|
|
309 }
|
|
|
310
|
|
|
311 /* Compute the cost of INSN rtx for abstraction. */
|
|
|
312
|
|
|
313 static int
|
|
|
314 compute_rtx_cost (rtx insn)
|
|
|
315 {
|
|
|
316 struct hash_bucket_def tmp_bucket;
|
|
|
317 p_hash_bucket bucket;
|
|
|
318 struct hash_elem_def tmp_elem;
|
|
|
319 p_hash_elem elem = NULL;
|
|
|
320 int cost = -1;
|
|
|
321
|
|
|
322 /* Compute hash value for INSN. */
|
|
|
323 tmp_bucket.hash = compute_hash (insn);
|
|
|
324
|
|
|
325 /* Select the hash group. */
|
|
|
326 bucket = (p_hash_bucket) htab_find (hash_buckets, &tmp_bucket);
|
|
|
327
|
|
|
328 if (bucket)
|
|
|
329 {
|
|
|
330 tmp_elem.insn = insn;
|
|
|
331
|
|
|
332 /* Select the insn. */
|
|
|
333 elem = (p_hash_elem) htab_find (bucket->seq_candidates, &tmp_elem);
|
|
|
334
|
|
|
335 /* If INSN is parsed the cost will be the cached length. */
|
|
|
336 if (elem)
|
|
|
337 cost = elem->length;
|
|
|
338 }
|
|
|
339
|
|
|
340 /* If we can't parse the INSN cost will be the instruction length. */
|
|
|
341 if (cost == -1)
|
|
|
342 {
|
|
|
343 cost = get_attr_length (insn);
|
|
|
344
|
|
|
345 /* Cache the length. */
|
|
|
346 if (elem)
|
|
|
347 elem->length = cost;
|
|
|
348 }
|
|
|
349
|
|
|
350 /* If we can't get an accurate estimate for a complex instruction,
|
|
|
351 assume that it has the same cost as a single fast instruction. */
|
|
|
352 return cost != 0 ? cost : COSTS_N_INSNS (1);
|
|
|
353 }
|
|
|
354
|
|
|
355 /* Determines the number of common insns in the sequences ending in INSN1 and
|
|
|
356 INSN2. Returns with LEN number of common insns and COST cost of sequence.
|
|
|
357 */
|
|
|
358
|
|
|
359 static void
|
|
|
360 matching_length (rtx insn1, rtx insn2, int* len, int* cost)
|
|
|
361 {
|
|
|
362 rtx x1;
|
|
|
363 rtx x2;
|
|
|
364
|
|
|
365 x1 = insn1;
|
|
|
366 x2 = insn2;
|
|
|
367 *len = 0;
|
|
|
368 *cost = 0;
|
|
|
369 while (x1 && x2 && (x1 != insn2) && (x2 != insn1)
|
|
|
370 && rtx_equal_p (PATTERN (x1), PATTERN (x2)))
|
|
|
371 {
|
|
|
372 (*len)++;
|
|
|
373 (*cost) += compute_rtx_cost (x1);
|
|
|
374 x1 = prev_insn_in_block (x1);
|
|
|
375 x2 = prev_insn_in_block (x2);
|
|
|
376 }
|
|
|
377 }
|
|
|
378
|
|
|
379 /* Adds E0 as a pattern sequence to PATTERN_SEQS with E1 as a matching
|
|
|
380 sequence. */
|
|
|
381
|
|
|
382 static void
|
|
|
383 match_seqs (p_hash_elem e0, p_hash_elem e1)
|
|
|
384 {
|
|
|
385 int len;
|
|
|
386 int cost;
|
|
|
387 matching_seq mseq, p_prev, p_next;
|
|
|
388
|
|
|
389 /* Determines the cost of the sequence and return without doing anything
|
|
|
390 if it is too small to produce any gain. */
|
|
|
391 matching_length (e0->insn, e1->insn, &len, &cost);
|
|
|
392 if (cost <= seq_call_cost)
|
|
|
393 return;
|
|
|
394
|
|
|
395 /* Prepend a new PATTERN_SEQ to PATTERN_SEQS if the last pattern sequence
|
|
|
396 does not end in E0->INSN. This assumes that once the E0->INSN changes
|
|
|
397 the old value will never appear again. */
|
|
|
398 if (!pattern_seqs || pattern_seqs->insn != e0->insn)
|
|
|
399 {
|
|
|
400 pattern_seq pseq =
|
|
|
401 (pattern_seq) xmalloc (sizeof (struct pattern_seq_def));
|
|
|
402 pseq->insn = e0->insn;
|
|
|
403 pseq->idx = e0->idx;
|
|
|
404 pseq->gain = 0; /* Set to zero to force recomputing. */
|
|
|
405 pseq->abstracted_length = 0;
|
|
|
406 pseq->cost = 0;
|
|
|
407 pseq->link_reg = NULL_RTX;
|
|
|
408 pseq->matching_seqs = NULL;
|
|
|
409 pseq->next_pattern_seq = pattern_seqs;
|
|
|
410 pattern_seqs = pseq;
|
|
|
411 }
|
|
|
412
|
|
|
413 /* Find the position of E1 in the matching sequences list. */
|
|
|
414 p_prev = NULL;
|
|
|
415 p_next = pattern_seqs->matching_seqs;
|
|
|
416 while (p_next && p_next->idx < e1->idx)
|
|
|
417 {
|
|
|
418 p_prev = p_next;
|
|
|
419 p_next = p_next->next_matching_seq;
|
|
|
420 }
|
|
|
421
|
|
|
422 /* Add a new E1 matching sequence to the pattern sequence. We know that
|
|
|
423 it ends in E0->INSN. */
|
|
|
424 mseq = (matching_seq) xmalloc (sizeof (struct matching_seq_def));
|
|
|
425 mseq->insn = e1->insn;
|
|
|
426 mseq->idx = e1->idx;
|
|
|
427 mseq->matching_length = len;
|
|
|
428 mseq->abstracted_length = 0;
|
|
|
429 mseq->cost = cost;
|
|
|
430
|
|
|
431 if (p_prev == NULL)
|
|
|
432 pattern_seqs->matching_seqs = mseq;
|
|
|
433 else
|
|
|
434 p_prev->next_matching_seq = mseq;
|
|
|
435 mseq->next_matching_seq = p_next;
|
|
|
436 }
|
|
|
437
|
|
|
438 /* Collects all pattern sequences and their matching sequences and puts them
|
|
|
439 into PATTERN_SEQS. */
|
|
|
440
|
|
|
441 static void
|
|
|
442 collect_pattern_seqs (void)
|
|
|
443 {
|
|
|
444 htab_iterator hti0, hti1, hti2;
|
|
|
445 p_hash_bucket hash_bucket;
|
|
|
446 p_hash_elem e0, e1;
|
|
|
447 #if defined STACK_REGS || defined HAVE_cc0
|
|
|
448 basic_block bb;
|
|
|
449 bitmap_head dont_collect;
|
|
|
450
|
|
|
451 /* Extra initialization step to ensure that no stack registers (if present)
|
|
|
452 or cc0 code (if present) are live across abnormal edges.
|
|
|
453 Set a flag in DONT_COLLECT for an insn if a stack register is live
|
|
|
454 after the insn or the insn is cc0 setter or user. */
|
|
|
455 bitmap_initialize (&dont_collect, NULL);
|
|
|
456
|
|
|
457 #ifdef STACK_REGS
|
|
|
458 FOR_EACH_BB (bb)
|
|
|
459 {
|
|
|
460 regset_head live;
|
|
|
461 rtx insn;
|
|
|
462 rtx prev;
|
|
|
463
|
|
|
464 /* Initialize liveness propagation. */
|
|
|
465 INIT_REG_SET (&live);
|
|
|
466 bitmap_copy (&live, DF_LR_OUT (bb));
|
|
|
467 df_simulate_initialize_backwards (bb, &live);
|
|
|
468
|
|
|
469 /* Propagate liveness info and mark insns where a stack reg is live. */
|
|
|
470 insn = BB_END (bb);
|
|
|
471 for (insn = BB_END (bb); ; insn = prev)
|
|
|
472 {
|
|
|
473 prev = PREV_INSN (insn);
|
|
|
474 if (INSN_P (insn))
|
|
|
475 {
|
|
|
476 int reg;
|
|
|
477 for (reg = FIRST_STACK_REG; reg <= LAST_STACK_REG; reg++)
|
|
|
478 {
|
|
|
479 if (REGNO_REG_SET_P (&live, reg))
|
|
|
480 {
|
|
|
481 bitmap_set_bit (&dont_collect, INSN_UID (insn));
|
|
|
482 break;
|
|
|
483 }
|
|
|
484 }
|
|
|
485
|
|
|
486 }
|
|
|
487 if (insn == BB_HEAD (bb))
|
|
|
488 break;
|
|
|
489 df_simulate_one_insn_backwards (bb, insn, &live);
|
|
|
490 insn = prev;
|
|
|
491 }
|
|
|
492
|
|
|
493 /* Free unused data. */
|
|
|
494 CLEAR_REG_SET (&live);
|
|
|
495 }
|
|
|
496 #endif
|
|
|
497
|
|
|
498 #ifdef HAVE_cc0
|
|
|
499 /* Mark CC0 setters and users as ineligible for collection into sequences.
|
|
|
500 This is an over-conservative fix, since it is OK to include
|
|
|
501 a cc0_setter, but only if we also include the corresponding cc0_user,
|
|
|
502 and vice versa. */
|
|
|
503 FOR_EACH_BB (bb)
|
|
|
504 {
|
|
|
505 rtx insn;
|
|
|
506 rtx next_tail;
|
|
|
507
|
|
|
508 next_tail = NEXT_INSN (BB_END (bb));
|
|
|
509
|
|
|
510 for (insn = BB_HEAD (bb); insn != next_tail; insn = NEXT_INSN (insn))
|
|
|
511 {
|
|
|
512 if (INSN_P (insn) && reg_mentioned_p (cc0_rtx, PATTERN (insn)))
|
|
|
513 bitmap_set_bit (&dont_collect, INSN_UID (insn));
|
|
|
514 }
|
|
|
515 }
|
|
|
516 #endif
|
|
|
517
|
|
|
518 #endif /* defined STACK_REGS || defined HAVE_cc0 */
|
|
|
519
|
|
|
520 /* Initialize PATTERN_SEQS to empty. */
|
|
|
521 pattern_seqs = 0;
|
|
|
522
|
|
|
523 /* Try to match every abstractable insn with every other insn in the same
|
|
|
524 HASH_BUCKET. */
|
|
|
525
|
|
|
526 FOR_EACH_HTAB_ELEMENT (hash_buckets, hash_bucket, p_hash_bucket, hti0)
|
|
|
527 if (htab_elements (hash_bucket->seq_candidates) > 1)
|
|
|
528 FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e0, p_hash_elem, hti1)
|
|
|
529 FOR_EACH_HTAB_ELEMENT (hash_bucket->seq_candidates, e1, p_hash_elem,
|
|
|
530 hti2)
|
|
|
531 if (e0 != e1
|
|
|
532 #if defined STACK_REGS || defined HAVE_cc0
|
|
|
533 && !bitmap_bit_p (&dont_collect, INSN_UID (e0->insn))
|
|
|
534 && !bitmap_bit_p (&dont_collect, INSN_UID (e1->insn))
|
|
|
535 #endif
|
|
|
536 )
|
|
|
537 match_seqs (e0, e1);
|
|
|
538 #if defined STACK_REGS || defined HAVE_cc0
|
|
|
539 /* Free unused data. */
|
|
|
540 bitmap_clear (&dont_collect);
|
|
|
541 #endif
|
|
|
542 }
|
|
|
543
|
|
|
544 /* Transforms a regset to a HARD_REG_SET. Every hard register in REGS is added
|
|
|
545 to hregs. Additionally, the hard counterpart of every renumbered pseudo
|
|
|
546 register is also added. */
|
|
|
547
|
|
|
548 static void
|
|
|
549 renumbered_reg_set_to_hard_reg_set (HARD_REG_SET * hregs, regset regs)
|
|
|
550 {
|
|
|
551 int r;
|
|
|
552
|
|
|
553 REG_SET_TO_HARD_REG_SET (*hregs, regs);
|
|
|
554 for (r = FIRST_PSEUDO_REGISTER; r < max_regno; r++)
|
|
|
555 if (REGNO_REG_SET_P (regs, r) && reg_renumber[r] >= 0)
|
|
|
556 SET_HARD_REG_BIT (*hregs, reg_renumber[r]);
|
|
|
557 }
|
|
|
558
|
|
|
559 /* Clears the bits in REGS for all registers, which are live in the sequence
|
|
|
560 give by its last INSN and its LENGTH. */
|
|
|
561
|
|
|
562 static void
|
|
|
563 clear_regs_live_in_seq (HARD_REG_SET * regs, rtx insn, int length)
|
|
|
564 {
|
|
|
565 basic_block bb;
|
|
|
566 regset_head live;
|
|
|
567 HARD_REG_SET hlive;
|
|
|
568 rtx x;
|
|
|
569 int i;
|
|
|
570
|
|
|
571 /* Initialize liveness propagation. */
|
|
|
572 bb = BLOCK_FOR_INSN (insn);
|
|
|
573 INIT_REG_SET (&live);
|
|
|
574 bitmap_copy (&live, DF_LR_OUT (bb));
|
|
|
575 df_simulate_initialize_backwards (bb, &live);
|
|
|
576
|
|
|
577 /* Propagate until INSN if found. */
|
|
|
578 for (x = BB_END (bb); x != insn; x = PREV_INSN (x))
|
|
|
579 df_simulate_one_insn_backwards (bb, x, &live);
|
|
|
580
|
|
|
581 /* Clear registers live after INSN. */
|
|
|
582 renumbered_reg_set_to_hard_reg_set (&hlive, &live);
|
|
|
583 AND_COMPL_HARD_REG_SET (*regs, hlive);
|
|
|
584
|
|
|
585 /* Clear registers live in and before the sequence. */
|
|
|
586 for (i = 0; i < length;)
|
|
|
587 {
|
|
|
588 rtx prev = PREV_INSN (x);
|
|
|
589 df_simulate_one_insn_backwards (bb, x, &live);
|
|
|
590
|
|
|
591 if (INSN_P (x))
|
|
|
592 {
|
|
|
593 renumbered_reg_set_to_hard_reg_set (&hlive, &live);
|
|
|
594 AND_COMPL_HARD_REG_SET (*regs, hlive);
|
|
|
595 i++;
|
|
|
596 }
|
|
|
597
|
|
|
598 x = prev;
|
|
|
599 }
|
|
|
600
|
|
|
601 /* Free unused data. */
|
|
|
602 CLEAR_REG_SET (&live);
|
|
|
603 }
|
|
|
604
|
|
|
605 /* Computes the gain of turning PSEQ into a pseudo-function and its matching
|
|
|
606 sequences into pseudo-calls. Also computes and caches the number of insns to
|
|
|
607 abstract from the matching sequences. */
|
|
|
608
|
|
|
609 static void
|
|
|
610 recompute_gain_for_pattern_seq (pattern_seq pseq)
|
|
|
611 {
|
|
|
612 matching_seq mseq;
|
|
|
613 rtx x;
|
|
|
614 int i;
|
|
|
615 int hascall;
|
|
|
616 HARD_REG_SET linkregs;
|
|
|
617
|
|
|
618 /* Initialize data. */
|
|
|
619 SET_HARD_REG_SET (linkregs);
|
|
|
620 pseq->link_reg = NULL_RTX;
|
|
|
621 pseq->abstracted_length = 0;
|
|
|
622
|
|
|
623 pseq->gain = -(seq_call_cost - seq_jump_cost + seq_return_cost);
|
|
|
624
|
|
|
625 /* Determine ABSTRACTED_LENGTH and COST for matching sequences of PSEQ.
|
|
|
626 ABSTRACTED_LENGTH may be less than MATCHING_LENGTH if sequences in the
|
|
|
627 same block overlap. */
|
|
|
628
|
|
|
629 for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
|
|
|
630 {
|
|
|
631 /* Determine ABSTRACTED_LENGTH. */
|
|
|
632 if (mseq->next_matching_seq)
|
|
|
633 mseq->abstracted_length = (int)(mseq->next_matching_seq->idx -
|
|
|
634 mseq->idx);
|
|
|
635 else
|
|
|
636 mseq->abstracted_length = mseq->matching_length;
|
|
|
637
|
|
|
638 if (mseq->abstracted_length > mseq->matching_length)
|
|
|
639 mseq->abstracted_length = mseq->matching_length;
|
|
|
640
|
|
|
641 /* Compute the cost of sequence. */
|
|
|
642 RECOMPUTE_COST (mseq);
|
|
|
643
|
|
|
644 /* If COST is big enough registers live in this matching sequence
|
|
|
645 should not be used as a link register. Also set ABSTRACTED_LENGTH
|
|
|
646 of PSEQ. */
|
|
|
647 if (mseq->cost > seq_call_cost)
|
|
|
648 {
|
|
|
649 clear_regs_live_in_seq (&linkregs, mseq->insn,
|
|
|
650 mseq->abstracted_length);
|
|
|
651 if (mseq->abstracted_length > pseq->abstracted_length)
|
|
|
652 pseq->abstracted_length = mseq->abstracted_length;
|
|
|
653 }
|
|
|
654 }
|
|
|
655
|
|
|
656 /* Modify ABSTRACTED_LENGTH of PSEQ if pattern sequence overlaps with one
|
|
|
657 of the matching sequences. */
|
|
|
658 for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
|
|
|
659 {
|
|
|
660 x = pseq->insn;
|
|
|
661 for (i = 0; (i < pseq->abstracted_length) && (x != mseq->insn); i++)
|
|
|
662 x = prev_insn_in_block (x);
|
|
|
663 pseq->abstracted_length = i;
|
|
|
664 }
|
|
|
665
|
|
|
666 /* Compute the cost of pattern sequence. */
|
|
|
667 RECOMPUTE_COST (pseq);
|
|
|
668
|
|
|
669 /* No gain if COST is too small. */
|
|
|
670 if (pseq->cost <= seq_call_cost)
|
|
|
671 {
|
|
|
672 pseq->gain = -1;
|
|
|
673 return;
|
|
|
674 }
|
|
|
675
|
|
|
676 /* Ensure that no matching sequence is longer than the pattern sequence. */
|
|
|
677 for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
|
|
|
678 {
|
|
|
679 if (mseq->abstracted_length > pseq->abstracted_length)
|
|
|
680 {
|
|
|
681 mseq->abstracted_length = pseq->abstracted_length;
|
|
|
682 RECOMPUTE_COST (mseq);
|
|
|
683 }
|
|
|
684 /* Once the length is stabilizing the gain can be calculated. */
|
|
|
685 if (mseq->cost > seq_call_cost)
|
|
|
686 pseq->gain += mseq->cost - seq_call_cost;
|
|
|
687 }
|
|
|
688
|
|
|
689 /* No need to do further work if there is no gain. */
|
|
|
690 if (pseq->gain <= 0)
|
|
|
691 return;
|
|
|
692
|
|
|
693 /* Should not use registers live in the pattern sequence as link register.
|
|
|
694 */
|
|
|
695 clear_regs_live_in_seq (&linkregs, pseq->insn, pseq->abstracted_length);
|
|
|
696
|
|
|
697 /* Determine whether pattern sequence contains a call_insn. */
|
|
|
698 hascall = 0;
|
|
|
699 x = pseq->insn;
|
|
|
700 for (i = 0; i < pseq->abstracted_length; i++)
|
|
|
701 {
|
|
|
702 if (CALL_P (x))
|
|
|
703 {
|
|
|
704 hascall = 1;
|
|
|
705 break;
|
|
|
706 }
|
|
|
707 x = prev_insn_in_block (x);
|
|
|
708 }
|
|
|
709
|
|
|
710 /* Should not use a register as a link register if - it is a fixed
|
|
|
711 register, or - the sequence contains a call insn and the register is a
|
|
|
712 call used register, or - the register needs to be saved if used in a
|
|
|
713 function but was not used before (since saving it can invalidate already
|
|
|
714 computed frame pointer offsets), or - the register cannot be used as a
|
|
|
715 base register. */
|
|
|
716
|
|
|
717 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
|
|
|
718 if (fixed_regs[i]
|
|
|
719 #ifdef REGNO_OK_FOR_INDIRECT_JUMP_P
|
|
|
720 || (!REGNO_OK_FOR_INDIRECT_JUMP_P (i, Pmode))
|
|
|
721 #else
|
|
|
722 || (!ok_for_base_p_1 (i, Pmode, MEM, SCRATCH))
|
|
|
723 || (!reg_class_subset_p (REGNO_REG_CLASS (i),
|
|
|
724 base_reg_class (VOIDmode, MEM, SCRATCH)))
|
|
|
725 #endif
|
|
|
726 || (hascall && call_used_regs[i])
|
|
|
727 || (!call_used_regs[i] && !df_regs_ever_live_p (i)))
|
|
|
728 CLEAR_HARD_REG_BIT (linkregs, i);
|
|
|
729
|
|
|
730 /* Find an appropriate register to be used as the link register. */
|
|
|
731 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
|
|
|
732 if (TEST_HARD_REG_BIT (linkregs, i))
|
|
|
733 {
|
|
|
734 pseq->link_reg = gen_rtx_REG (Pmode, i);
|
|
|
735 break;
|
|
|
736 }
|
|
|
737
|
|
|
738 /* Abstraction is not possible if no link register is available, so set
|
|
|
739 gain to 0. */
|
|
|
740 if (!pseq->link_reg)
|
|
|
741 pseq->gain = 0;
|
|
|
742 }
|
|
|
743
|
|
|
744 /* Deallocates memory occupied by PSEQ and its matching seqs. */
|
|
|
745
|
|
|
746 static void
|
|
|
747 free_pattern_seq (pattern_seq pseq)
|
|
|
748 {
|
|
|
749 while (pseq->matching_seqs)
|
|
|
750 {
|
|
|
751 matching_seq mseq = pseq->matching_seqs;
|
|
|
752 pseq->matching_seqs = mseq->next_matching_seq;
|
|
|
753 free (mseq);
|
|
|
754 }
|
|
|
755 free (pseq);
|
|
|
756 }
|
|
|
757
|
|
|
758
|
|
|
759 /* Computes the gain for pattern sequences. Pattern sequences producing no gain
|
|
|
760 are deleted. The pattern sequence with the biggest gain is moved to the first
|
|
|
761 place of PATTERN_SEQS. */
|
|
|
762
|
|
|
763 static void
|
|
|
764 recompute_gain (void)
|
|
|
765 {
|
|
|
766 pattern_seq *pseq;
|
|
|
767 int maxgain;
|
|
|
768
|
|
|
769 maxgain = 0;
|
|
|
770 for (pseq = &pattern_seqs; *pseq;)
|
|
|
771 {
|
|
|
772 if ((*pseq)->gain <= 0)
|
|
|
773 recompute_gain_for_pattern_seq (*pseq);
|
|
|
774
|
|
|
775 if ((*pseq)->gain > 0)
|
|
|
776 {
|
|
|
777 if ((*pseq)->gain > maxgain)
|
|
|
778 {
|
|
|
779 pattern_seq temp = *pseq;
|
|
|
780 (*pseq) = temp->next_pattern_seq;
|
|
|
781 temp->next_pattern_seq = pattern_seqs;
|
|
|
782 pattern_seqs = temp;
|
|
|
783 maxgain = pattern_seqs->gain;
|
|
|
784 }
|
|
|
785 else
|
|
|
786 {
|
|
|
787 pseq = &(*pseq)->next_pattern_seq;
|
|
|
788 }
|
|
|
789 }
|
|
|
790 else
|
|
|
791 {
|
|
|
792 pattern_seq temp = *pseq;
|
|
|
793 *pseq = temp->next_pattern_seq;
|
|
|
794 free_pattern_seq (temp);
|
|
|
795 }
|
|
|
796 }
|
|
|
797 }
|
|
|
798
|
|
|
799 /* Updated those pattern sequences and matching sequences, which overlap with
|
|
|
800 the sequence given by INSN and LEN. Deletes sequences shrinking below a
|
|
|
801 limit. */
|
|
|
802
|
|
|
803 static void
|
|
|
804 erase_from_pattern_seqs (rtx insn, int len)
|
|
|
805 {
|
|
|
806 pattern_seq *pseq;
|
|
|
807 matching_seq *mseq;
|
|
|
808 rtx x;
|
|
|
809 int plen, mlen;
|
|
|
810 int pcost, mcost;
|
|
|
811
|
|
|
812 while (len > 0)
|
|
|
813 {
|
|
|
814 for (pseq = &pattern_seqs; *pseq;)
|
|
|
815 {
|
|
|
816 plen = 0;
|
|
|
817 pcost = 0;
|
|
|
818 for (x = (*pseq)->insn; x && (x != insn);
|
|
|
819 x = prev_insn_in_block (x))
|
|
|
820 {
|
|
|
821 plen++;
|
|
|
822 pcost += compute_rtx_cost (x);
|
|
|
823 }
|
|
|
824
|
|
|
825 if (pcost <= seq_call_cost)
|
|
|
826 {
|
|
|
827 pattern_seq temp = *pseq;
|
|
|
828 *pseq = temp->next_pattern_seq;
|
|
|
829 free_pattern_seq (temp);
|
|
|
830 }
|
|
|
831 else
|
|
|
832 {
|
|
|
833 for (mseq = &(*pseq)->matching_seqs; *mseq;)
|
|
|
834 {
|
|
|
835 mlen = 0;
|
|
|
836 mcost = 0;
|
|
|
837 for (x = (*mseq)->insn;
|
|
|
838 x && (x != insn) && (mlen < plen)
|
|
|
839 && (mlen < (*mseq)->matching_length);
|
|
|
840 x = prev_insn_in_block (x))
|
|
|
841 {
|
|
|
842 mlen++;
|
|
|
843 mcost += compute_rtx_cost (x);
|
|
|
844 }
|
|
|
845
|
|
|
846 if (mcost <= seq_call_cost)
|
|
|
847 {
|
|
|
848 matching_seq temp = *mseq;
|
|
|
849 *mseq = temp->next_matching_seq;
|
|
|
850 free (temp);
|
|
|
851 /* Set to 0 to force gain recomputation. */
|
|
|
852 (*pseq)->gain = 0;
|
|
|
853 }
|
|
|
854 else
|
|
|
855 {
|
|
|
856 if (mlen < (*mseq)->matching_length)
|
|
|
857 {
|
|
|
858 (*mseq)->cost = mcost;
|
|
|
859 (*mseq)->matching_length = mlen;
|
|
|
860 /* Set to 0 to force gain recomputation. */
|
|
|
861 (*pseq)->gain = 0;
|
|
|
862 }
|
|
|
863 mseq = &(*mseq)->next_matching_seq;
|
|
|
864 }
|
|
|
865 }
|
|
|
866
|
|
|
867 pseq = &(*pseq)->next_pattern_seq;
|
|
|
868 }
|
|
|
869 }
|
|
|
870
|
|
|
871 len--;
|
|
|
872 insn = prev_insn_in_block (insn);
|
|
|
873 }
|
|
|
874 }
|
|
|
875
|
|
|
876 /* Updates those pattern sequences and matching sequences, which overlap with
|
|
|
877 the pattern sequence with the biggest gain and its matching sequences. */
|
|
|
878
|
|
|
879 static void
|
|
|
880 update_pattern_seqs (void)
|
|
|
881 {
|
|
|
882 pattern_seq bestpseq;
|
|
|
883 matching_seq mseq;
|
|
|
884
|
|
|
885 bestpseq = pattern_seqs;
|
|
|
886 pattern_seqs = bestpseq->next_pattern_seq;
|
|
|
887
|
|
|
888 for (mseq = bestpseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
|
|
|
889 if (mseq->cost > seq_call_cost)
|
|
|
890 erase_from_pattern_seqs (mseq->insn, mseq->abstracted_length);
|
|
|
891 erase_from_pattern_seqs (bestpseq->insn, bestpseq->abstracted_length);
|
|
|
892
|
|
|
893 bestpseq->next_pattern_seq = pattern_seqs;
|
|
|
894 pattern_seqs = bestpseq;
|
|
|
895 }
|
|
|
896
|
|
|
897 /* Groups together those matching sequences of the best pattern sequence, which
|
|
|
898 have the same ABSTRACTED_LENGTH and puts these groups in ascending order.
|
|
|
899 SEQ_BLOCKS contains the result. */
|
|
|
900
|
|
|
901 static void
|
|
|
902 determine_seq_blocks (void)
|
|
|
903 {
|
|
|
904 seq_block sb;
|
|
|
905 matching_seq *mseq;
|
|
|
906 matching_seq m;
|
|
|
907
|
|
|
908 /* Initialize SEQ_BLOCKS to empty. */
|
|
|
909 seq_blocks = 0;
|
|
|
910
|
|
|
911 /* Process all matching sequences. */
|
|
|
912 for (mseq = &pattern_seqs->matching_seqs; *mseq;)
|
|
|
913 {
|
|
|
914 /* Deal only with matching sequences being long enough. */
|
|
|
915 if ((*mseq)->cost <= seq_call_cost)
|
|
|
916 {
|
|
|
917 mseq = &(*mseq)->next_matching_seq;
|
|
|
918 continue;
|
|
|
919 }
|
|
|
920
|
|
|
921 /* Ensure that SB contains a seq_block with the appropriate length.
|
|
|
922 Insert a new seq_block if necessary. */
|
|
|
923 if (!seq_blocks || ((*mseq)->abstracted_length < seq_blocks->length))
|
|
|
924 {
|
|
|
925 sb = (seq_block) xmalloc (sizeof (struct seq_block_def));
|
|
|
926 sb->length = (*mseq)->abstracted_length;
|
|
|
927 sb->label = NULL_RTX;
|
|
|
928 sb->matching_seqs = 0;
|
|
|
929 sb->next_seq_block = seq_blocks;
|
|
|
930 seq_blocks = sb;
|
|
|
931 }
|
|
|
932 else
|
|
|
933 {
|
|
|
934 for (sb = seq_blocks; sb; sb = sb->next_seq_block)
|
|
|
935 {
|
|
|
936 if ((*mseq)->abstracted_length == sb->length)
|
|
|
937 break;
|
|
|
938 if (!sb->next_seq_block
|
|
|
939 || ((*mseq)->abstracted_length <
|
|
|
940 sb->next_seq_block->length))
|
|
|
941 {
|
|
|
942 seq_block temp =
|
|
|
943 (seq_block) xmalloc (sizeof (struct seq_block_def));
|
|
|
944 temp->length = (*mseq)->abstracted_length;
|
|
|
945 temp->label = NULL_RTX;
|
|
|
946 temp->matching_seqs = 0;
|
|
|
947 temp->next_seq_block = sb->next_seq_block;
|
|
|
948 sb->next_seq_block = temp;
|
|
|
949 }
|
|
|
950 }
|
|
|
951 }
|
|
|
952
|
|
|
953 /* Remove the matching sequence from the linked list of the pattern
|
|
|
954 sequence and link it to SB. */
|
|
|
955 m = *mseq;
|
|
|
956 *mseq = m->next_matching_seq;
|
|
|
957 m->next_matching_seq = sb->matching_seqs;
|
|
|
958 sb->matching_seqs = m;
|
|
|
959 }
|
|
|
960 }
|
|
|
961
|
|
|
962 /* Builds a symbol_ref for LABEL. */
|
|
|
963
|
|
|
964 static rtx
|
|
|
965 gen_symbol_ref_rtx_for_label (const_rtx label)
|
|
|
966 {
|
|
|
967 char name[20];
|
|
|
968 rtx sym;
|
|
|
969
|
|
|
970 ASM_GENERATE_INTERNAL_LABEL (name, "L", CODE_LABEL_NUMBER (label));
|
|
|
971 sym = gen_rtx_SYMBOL_REF (Pmode, ggc_strdup (name));
|
|
|
972 SYMBOL_REF_FLAGS (sym) = SYMBOL_FLAG_LOCAL;
|
|
|
973 return sym;
|
|
|
974 }
|
|
|
975
|
|
|
976 /* Splits basic block at the requested insn and rebuilds dataflow. */
|
|
|
977
|
|
|
978 static basic_block
|
|
|
979 split_block_and_df_analyze (basic_block bb, rtx insn)
|
|
|
980 {
|
|
|
981 basic_block next;
|
|
|
982 next = split_block (bb, insn)->dest;
|
|
|
983 df_analyze ();
|
|
|
984 return next;
|
|
|
985 }
|
|
|
986
|
|
|
987 /* Ensures that INSN is the last insn in its block and returns the block label
|
|
|
988 of the next block. */
|
|
|
989
|
|
|
990 static rtx
|
|
|
991 block_label_after (rtx insn)
|
|
|
992 {
|
|
|
993 basic_block bb = BLOCK_FOR_INSN (insn);
|
|
|
994 if ((insn == BB_END (bb)) && (bb->next_bb != EXIT_BLOCK_PTR))
|
|
|
995 return block_label (bb->next_bb);
|
|
|
996 else
|
|
|
997 return block_label (split_block_and_df_analyze (bb, insn));
|
|
|
998 }
|
|
|
999
|
|
|
1000 /* Ensures that the last insns of the best pattern and its matching sequences
|
|
|
1001 are the last insns in their block. Additionally, extends the live set at the
|
|
|
1002 end of the pattern sequence with the live sets at the end of the matching
|
|
|
1003 sequences. */
|
|
|
1004
|
|
|
1005 static void
|
|
|
1006 split_blocks_after_seqs (void)
|
|
|
1007 {
|
|
|
1008 seq_block sb;
|
|
|
1009 matching_seq mseq;
|
|
|
1010
|
|
|
1011 block_label_after (pattern_seqs->insn);
|
|
|
1012 for (sb = seq_blocks; sb; sb = sb->next_seq_block)
|
|
|
1013 {
|
|
|
1014 for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
|
|
|
1015 {
|
|
|
1016 block_label_after (mseq->insn);
|
|
|
1017 IOR_REG_SET (df_get_live_out (BLOCK_FOR_INSN (pattern_seqs->insn)),
|
|
|
1018 df_get_live_out (BLOCK_FOR_INSN (mseq->insn)));
|
|
|
1019 }
|
|
|
1020 }
|
|
|
1021 }
|
|
|
1022
|
|
|
1023 /* Splits the best pattern sequence according to SEQ_BLOCKS. Emits pseudo-call
|
|
|
1024 and -return insns before and after the sequence. */
|
|
|
1025
|
|
|
1026 static void
|
|
|
1027 split_pattern_seq (void)
|
|
|
1028 {
|
|
|
1029 rtx insn;
|
|
|
1030 basic_block bb;
|
|
|
1031 rtx retlabel, retjmp, saveinsn;
|
|
|
1032 int i;
|
|
|
1033 seq_block sb;
|
|
|
1034
|
|
|
1035 insn = pattern_seqs->insn;
|
|
|
1036 bb = BLOCK_FOR_INSN (insn);
|
|
|
1037
|
|
|
1038 /* Get the label after the sequence. This will be the return address. The
|
|
|
1039 label will be referenced using a symbol_ref so protect it from
|
|
|
1040 deleting. */
|
|
|
1041 retlabel = block_label_after (insn);
|
|
|
1042 LABEL_PRESERVE_P (retlabel) = 1;
|
|
|
1043
|
|
|
1044 /* Emit an indirect jump via the link register after the sequence acting
|
|
|
1045 as the return insn. Also emit a barrier and update the basic block. */
|
|
|
1046 if (!find_reg_note (BB_END (bb), REG_NORETURN, NULL))
|
|
|
1047 retjmp = emit_jump_insn_after (gen_indirect_jump (pattern_seqs->link_reg),
|
|
|
1048 BB_END (bb));
|
|
|
1049 emit_barrier_after (BB_END (bb));
|
|
|
1050
|
|
|
1051 /* Replace all outgoing edges with a new one to the block of RETLABEL. */
|
|
|
1052 while (EDGE_COUNT (bb->succs) != 0)
|
|
|
1053 remove_edge (EDGE_SUCC (bb, 0));
|
|
|
1054 make_edge (bb, BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL);
|
|
|
1055
|
|
|
1056 /* Split the sequence according to SEQ_BLOCKS and cache the label of the
|
|
|
1057 resulting basic blocks. */
|
|
|
1058 i = 0;
|
|
|
1059 for (sb = seq_blocks; sb; sb = sb->next_seq_block)
|
|
|
1060 {
|
|
|
1061 for (; i < sb->length; i++)
|
|
|
1062 insn = prev_insn_in_block (insn);
|
|
|
1063
|
|
|
1064 sb->label = block_label (split_block_and_df_analyze (bb, insn));
|
|
|
1065 }
|
|
|
1066
|
|
|
1067 /* Emit an insn saving the return address to the link register before the
|
|
|
1068 sequence. */
|
|
|
1069 saveinsn = emit_insn_after (gen_move_insn (pattern_seqs->link_reg,
|
|
|
1070 gen_symbol_ref_rtx_for_label
|
|
|
1071 (retlabel)), BB_END (bb));
|
|
|
1072 /* Update liveness info. */
|
|
|
1073 SET_REGNO_REG_SET (df_get_live_out (bb),
|
|
|
1074 REGNO (pattern_seqs->link_reg));
|
|
|
1075 }
|
|
|
1076
|
|
|
1077 /* Deletes the insns of the matching sequences of the best pattern sequence and
|
|
|
1078 replaces them with pseudo-calls to the pattern sequence. */
|
|
|
1079
|
|
|
1080 static void
|
|
|
1081 erase_matching_seqs (void)
|
|
|
1082 {
|
|
|
1083 seq_block sb;
|
|
|
1084 matching_seq mseq;
|
|
|
1085 rtx insn;
|
|
|
1086 basic_block bb;
|
|
|
1087 rtx retlabel, saveinsn, callinsn;
|
|
|
1088 int i;
|
|
|
1089
|
|
|
1090 for (sb = seq_blocks; sb; sb = sb->next_seq_block)
|
|
|
1091 {
|
|
|
1092 for (mseq = sb->matching_seqs; mseq; mseq = mseq->next_matching_seq)
|
|
|
1093 {
|
|
|
1094 insn = mseq->insn;
|
|
|
1095 bb = BLOCK_FOR_INSN (insn);
|
|
|
1096
|
|
|
1097 /* Get the label after the sequence. This will be the return
|
|
|
1098 address. The label will be referenced using a symbol_ref so
|
|
|
1099 protect it from deleting. */
|
|
|
1100 retlabel = block_label_after (insn);
|
|
|
1101 LABEL_PRESERVE_P (retlabel) = 1;
|
|
|
1102
|
|
|
1103 /* Delete the insns of the sequence. */
|
|
|
1104 for (i = 0; i < sb->length; i++)
|
|
|
1105 insn = prev_insn_in_block (insn);
|
|
|
1106 delete_basic_block (split_block_and_df_analyze (bb, insn));
|
|
|
1107
|
|
|
1108 /* Emit an insn saving the return address to the link register
|
|
|
1109 before the deleted sequence. */
|
|
|
1110 saveinsn = emit_insn_after (gen_move_insn (pattern_seqs->link_reg,
|
|
|
1111 gen_symbol_ref_rtx_for_label
|
|
|
1112 (retlabel)),
|
|
|
1113 BB_END (bb));
|
|
|
1114 BLOCK_FOR_INSN (saveinsn) = bb;
|
|
|
1115
|
|
|
1116 /* Emit a jump to the appropriate part of the pattern sequence
|
|
|
1117 after the save insn. Also update the basic block. */
|
|
|
1118 callinsn = emit_jump_insn_after (gen_jump (sb->label), saveinsn);
|
|
|
1119 JUMP_LABEL (callinsn) = sb->label;
|
|
|
1120 LABEL_NUSES (sb->label)++;
|
|
|
1121 BLOCK_FOR_INSN (callinsn) = bb;
|
|
|
1122 BB_END (bb) = callinsn;
|
|
|
1123
|
|
|
1124 /* Maintain control flow and liveness information. */
|
|
|
1125 SET_REGNO_REG_SET (df_get_live_out (bb),
|
|
|
1126 REGNO (pattern_seqs->link_reg));
|
|
|
1127 emit_barrier_after (BB_END (bb));
|
|
|
1128 make_single_succ_edge (bb, BLOCK_FOR_INSN (sb->label), 0);
|
|
|
1129 IOR_REG_SET (df_get_live_out (bb),
|
|
|
1130 df_get_live_in (BLOCK_FOR_INSN (sb->label)));
|
|
|
1131
|
|
|
1132 make_edge (BLOCK_FOR_INSN (seq_blocks->label),
|
|
|
1133 BLOCK_FOR_INSN (retlabel), EDGE_ABNORMAL);
|
|
|
1134 }
|
|
|
1135 }
|
|
|
1136 }
|
|
|
1137
|
|
|
1138 /* Deallocates SEQ_BLOCKS and all the matching sequences. */
|
|
|
1139
|
|
|
1140 static void
|
|
|
1141 free_seq_blocks (void)
|
|
|
1142 {
|
|
|
1143 while (seq_blocks)
|
|
|
1144 {
|
|
|
1145 seq_block sb = seq_blocks;
|
|
|
1146 while (sb->matching_seqs)
|
|
|
1147 {
|
|
|
1148 matching_seq mseq = sb->matching_seqs;
|
|
|
1149 sb->matching_seqs = mseq->next_matching_seq;
|
|
|
1150 free (mseq);
|
|
|
1151 }
|
|
|
1152 seq_blocks = sb->next_seq_block;
|
|
|
1153 free (sb);
|
|
|
1154 }
|
|
|
1155 }
|
|
|
1156
|
|
|
1157 /* Transforms the best pattern sequence into a pseudo-function and its matching
|
|
|
1158 sequences to pseudo-calls. Afterwards the best pattern sequence is removed
|
|
|
1159 from PATTERN_SEQS. */
|
|
|
1160
|
|
|
1161 static void
|
|
|
1162 abstract_best_seq (void)
|
|
|
1163 {
|
|
|
1164 pattern_seq bestpseq;
|
|
|
1165
|
|
|
1166 /* Do the abstraction. */
|
|
|
1167 determine_seq_blocks ();
|
|
|
1168 split_blocks_after_seqs ();
|
|
|
1169 split_pattern_seq ();
|
|
|
1170 erase_matching_seqs ();
|
|
|
1171 free_seq_blocks ();
|
|
|
1172
|
|
|
1173 /* Record the usage of the link register. */
|
|
|
1174 df_set_regs_ever_live (REGNO (pattern_seqs->link_reg), true);
|
|
|
1175
|
|
|
1176 /* Remove the best pattern sequence. */
|
|
|
1177 bestpseq = pattern_seqs;
|
|
|
1178 pattern_seqs = bestpseq->next_pattern_seq;
|
|
|
1179 free_pattern_seq (bestpseq);
|
|
|
1180 }
|
|
|
1181
|
|
|
1182 /* Prints info on the pattern sequences to the dump file. */
|
|
|
1183
|
|
|
1184 static void
|
|
|
1185 dump_pattern_seqs (void)
|
|
|
1186 {
|
|
|
1187 pattern_seq pseq;
|
|
|
1188 matching_seq mseq;
|
|
|
1189
|
|
|
1190 if (!dump_file)
|
|
|
1191 return;
|
|
|
1192
|
|
|
1193 fprintf (dump_file, ";; Pattern sequences\n");
|
|
|
1194 for (pseq = pattern_seqs; pseq; pseq = pseq->next_pattern_seq)
|
|
|
1195 {
|
|
|
1196 fprintf (dump_file, "Pattern sequence at insn %d matches sequences at",
|
|
|
1197 INSN_UID (pseq->insn));
|
|
|
1198 for (mseq = pseq->matching_seqs; mseq; mseq = mseq->next_matching_seq)
|
|
|
1199 {
|
|
|
1200 fprintf (dump_file, " insn %d (length %d)", INSN_UID (mseq->insn),
|
|
|
1201 mseq->matching_length);
|
|
|
1202 if (mseq->next_matching_seq)
|
|
|
1203 fprintf (dump_file, ",");
|
|
|
1204 }
|
|
|
1205 fprintf (dump_file, ".\n");
|
|
|
1206 }
|
|
|
1207 fprintf (dump_file, "\n");
|
|
|
1208 }
|
|
|
1209
|
|
|
1210 /* Prints info on the best pattern sequence transformed in the ITER-th
|
|
|
1211 iteration to the dump file. */
|
|
|
1212
|
|
|
1213 static void
|
|
|
1214 dump_best_pattern_seq (int iter)
|
|
|
1215 {
|
|
|
1216 matching_seq mseq;
|
|
|
1217
|
|
|
1218 if (!dump_file)
|
|
|
1219 return;
|
|
|
1220
|
|
|
1221 fprintf (dump_file, ";; Iteration %d\n", iter);
|
|
|
1222 fprintf (dump_file,
|
|
|
1223 "Best pattern sequence with %d gain is at insn %d (length %d).\n",
|
|
|
1224 pattern_seqs->gain, INSN_UID (pattern_seqs->insn),
|
|
|
1225 pattern_seqs->abstracted_length);
|
|
|
1226 fprintf (dump_file, "Matching sequences are at");
|
|
|
1227 for (mseq = pattern_seqs->matching_seqs; mseq;
|
|
|
1228 mseq = mseq->next_matching_seq)
|
|
|
1229 {
|
|
|
1230 fprintf (dump_file, " insn %d (length %d)", INSN_UID (mseq->insn),
|
|
|
1231 mseq->abstracted_length);
|
|
|
1232 if (mseq->next_matching_seq)
|
|
|
1233 fprintf (dump_file, ",");
|
|
|
1234 }
|
|
|
1235 fprintf (dump_file, ".\n");
|
|
|
1236 fprintf (dump_file, "Using reg %d as link register.\n\n",
|
|
|
1237 REGNO (pattern_seqs->link_reg));
|
|
|
1238 }
|
|
|
1239
|
|
|
1240 /* Htab hash function for hash_bucket_def structure. */
|
|
|
1241
|
|
|
1242 static unsigned int
|
|
|
1243 htab_hash_bucket (const void *p)
|
|
|
1244 {
|
|
|
1245 const_p_hash_bucket bucket = (const_p_hash_bucket) p;
|
|
|
1246 return bucket->hash;
|
|
|
1247 }
|
|
|
1248
|
|
|
1249 /* Htab equal function for hash_bucket_def structure. */
|
|
|
1250
|
|
|
1251 static int
|
|
|
1252 htab_eq_bucket (const void *p0, const void *p1)
|
|
|
1253 {
|
|
|
1254 return htab_hash_bucket (p0) == htab_hash_bucket (p1);
|
|
|
1255 }
|
|
|
1256
|
|
|
1257 /* Htab delete function for hash_bucket_def structure. */
|
|
|
1258
|
|
|
1259 static void
|
|
|
1260 htab_del_bucket (void *p)
|
|
|
1261 {
|
|
|
1262 p_hash_bucket bucket = (p_hash_bucket) p;
|
|
|
1263
|
|
|
1264 if (bucket->seq_candidates)
|
|
|
1265 htab_delete (bucket->seq_candidates);
|
|
|
1266
|
|
|
1267 free (bucket);
|
|
|
1268 }
|
|
|
1269
|
|
|
1270 /* Htab hash function for hash_bucket_def structure. */
|
|
|
1271
|
|
|
1272 static unsigned int
|
|
|
1273 htab_hash_elem (const void *p)
|
|
|
1274 {
|
|
|
1275 const_p_hash_elem elem = (const_p_hash_elem) p;
|
|
|
1276 return htab_hash_pointer (elem->insn);
|
|
|
1277 }
|
|
|
1278
|
|
|
1279 /* Htab equal function for hash_bucket_def structure. */
|
|
|
1280
|
|
|
1281 static int
|
|
|
1282 htab_eq_elem (const void *p0, const void *p1)
|
|
|
1283 {
|
|
|
1284 return htab_hash_elem (p0) == htab_hash_elem (p1);
|
|
|
1285 }
|
|
|
1286
|
|
|
1287 /* Htab delete function for hash_bucket_def structure. */
|
|
|
1288
|
|
|
1289 static void
|
|
|
1290 htab_del_elem (void *p)
|
|
|
1291 {
|
|
|
1292 p_hash_elem elem = (p_hash_elem) p;
|
|
|
1293 free (elem);
|
|
|
1294 }
|
|
|
1295
|
|
|
1296 /* Creates a hash value for each sequence candidate and saves them
|
|
|
1297 in HASH_BUCKET. */
|
|
|
1298
|
|
|
1299 static void
|
|
|
1300 fill_hash_bucket (void)
|
|
|
1301 {
|
|
|
1302 basic_block bb;
|
|
|
1303 rtx insn;
|
|
|
1304 void **slot;
|
|
|
1305 p_hash_bucket bucket;
|
|
|
1306 struct hash_bucket_def tmp_bucket;
|
|
|
1307 p_hash_elem elem;
|
|
|
1308 unsigned long insn_idx;
|
|
|
1309
|
|
|
1310 insn_idx = 0;
|
|
|
1311 FOR_EACH_BB (bb)
|
|
|
1312 {
|
|
|
1313 FOR_BB_INSNS_REVERSE (bb, insn)
|
|
|
1314 {
|
|
|
1315 if (!ABSTRACTABLE_INSN_P (insn))
|
|
|
1316 continue;
|
|
|
1317
|
|
|
1318 /* Compute hash value for INSN. */
|
|
|
1319 tmp_bucket.hash = compute_hash (insn);
|
|
|
1320
|
|
|
1321 /* Select the hash group. */
|
|
|
1322 bucket = (p_hash_bucket) htab_find (hash_buckets, &tmp_bucket);
|
|
|
1323
|
|
|
1324 if (!bucket)
|
|
|
1325 {
|
|
|
1326 /* Create a new hash group. */
|
|
|
1327 bucket = (p_hash_bucket) xcalloc (1,
|
|
|
1328 sizeof (struct hash_bucket_def));
|
|
|
1329 bucket->hash = tmp_bucket.hash;
|
|
|
1330 bucket->seq_candidates = NULL;
|
|
|
1331
|
|
|
1332 slot = htab_find_slot (hash_buckets, &tmp_bucket, INSERT);
|
|
|
1333 *slot = bucket;
|
|
|
1334 }
|
|
|
1335
|
|
|
1336 /* Create new list for storing sequence candidates. */
|
|
|
1337 if (!bucket->seq_candidates)
|
|
|
1338 bucket->seq_candidates = htab_create (HASH_INIT,
|
|
|
1339 htab_hash_elem,
|
|
|
1340 htab_eq_elem,
|
|
|
1341 htab_del_elem);
|
|
|
1342
|
|
|
1343 elem = (p_hash_elem) xcalloc (1, sizeof (struct hash_elem_def));
|
|
|
1344 elem->insn = insn;
|
|
|
1345 elem->idx = insn_idx;
|
|
|
1346 elem->length = get_attr_length (insn);
|
|
|
1347
|
|
|
1348 /* Insert INSN into BUCKET hash bucket. */
|
|
|
1349 slot = htab_find_slot (bucket->seq_candidates, elem, INSERT);
|
|
|
1350 *slot = elem;
|
|
|
1351
|
|
|
1352 insn_idx++;
|
|
|
1353 }
|
|
|
1354 }
|
|
|
1355 }
|
|
|
1356
|
|
|
1357 /* Computes the cost of calling sequence and the cost of return. */
|
|
|
1358
|
|
|
1359 static void
|
|
|
1360 compute_init_costs (void)
|
|
|
1361 {
|
|
|
1362 rtx rtx_jump, rtx_store, rtx_return, reg, label;
|
|
|
1363 basic_block bb;
|
|
|
1364
|
|
|
1365 FOR_EACH_BB (bb)
|
|
|
1366 if (BB_HEAD (bb))
|
|
|
1367 break;
|
|
|
1368
|
|
|
1369 label = block_label (bb);
|
|
|
1370 reg = gen_rtx_REG (Pmode, 0);
|
|
|
1371
|
|
|
1372 /* Pattern for indirect jump. */
|
|
|
1373 rtx_jump = gen_indirect_jump (reg);
|
|
|
1374
|
|
|
1375 /* Pattern for storing address. */
|
|
|
1376 rtx_store = gen_rtx_SET (VOIDmode, reg, gen_symbol_ref_rtx_for_label (label));
|
|
|
1377
|
|
|
1378 /* Pattern for return insn. */
|
|
|
1379 rtx_return = gen_jump (label);
|
|
|
1380
|
|
|
1381 /* The cost of jump. */
|
|
|
1382 seq_jump_cost = compute_rtx_cost (make_jump_insn_raw (rtx_jump));
|
|
|
1383
|
|
|
1384 /* The cost of calling sequence. */
|
|
|
1385 seq_call_cost = seq_jump_cost + compute_rtx_cost (make_insn_raw (rtx_store));
|
|
|
1386
|
|
|
1387 /* The cost of return. */
|
|
|
1388 seq_return_cost = compute_rtx_cost (make_jump_insn_raw (rtx_return));
|
|
|
1389
|
|
|
1390 /* Simple heuristic for minimal sequence cost. */
|
|
|
1391 seq_call_cost = (int)(seq_call_cost * (double)SEQ_CALL_COST_MULTIPLIER);
|
|
|
1392 }
|
|
|
1393
|
|
|
1394 /* Finds equivalent insn sequences in the current function and retains only one
|
|
|
1395 instance of them which is turned into a pseudo-function. The additional
|
|
|
1396 copies are erased and replaced by pseudo-calls to the retained sequence. */
|
|
|
1397
|
|
|
1398 static void
|
|
|
1399 rtl_seqabstr (void)
|
|
|
1400 {
|
|
|
1401 int iter;
|
|
|
1402 df_set_flags (DF_LR_RUN_DCE);
|
|
|
1403 df_analyze ();
|
|
|
1404
|
|
|
1405 /* Create a hash list for COLLECT_PATTERN_SEQS. */
|
|
|
1406 hash_buckets = htab_create (HASH_INIT, htab_hash_bucket , htab_eq_bucket ,
|
|
|
1407 htab_del_bucket);
|
|
|
1408 fill_hash_bucket ();
|
|
|
1409
|
|
|
1410 /* Compute the common cost of abstraction. */
|
|
|
1411 compute_init_costs ();
|
|
|
1412
|
|
|
1413 /* Build an initial set of pattern sequences from the current function. */
|
|
|
1414 collect_pattern_seqs ();
|
|
|
1415 dump_pattern_seqs ();
|
|
|
1416
|
|
|
1417 /* Iterate until there are no sequences to abstract. */
|
|
|
1418 for (iter = 1;; iter++)
|
|
|
1419 {
|
|
|
1420 /* Recompute gain for sequences if necessary and select sequence with
|
|
|
1421 biggest gain. */
|
|
|
1422 recompute_gain ();
|
|
|
1423 if (!pattern_seqs)
|
|
|
1424 break;
|
|
|
1425 dump_best_pattern_seq (iter);
|
|
|
1426 /* Update the cached info of the other sequences and force gain
|
|
|
1427 recomputation where needed. */
|
|
|
1428 update_pattern_seqs ();
|
|
|
1429 /* Turn best sequences into pseudo-functions and -calls. */
|
|
|
1430 abstract_best_seq ();
|
|
|
1431 }
|
|
|
1432
|
|
|
1433 /* Cleanup hash tables. */
|
|
|
1434 htab_delete (hash_buckets);
|
|
|
1435 }
|
|
|
1436
|
|
|
1437 /* The gate function for TREE_OPT_PASS. */
|
|
|
1438
|
|
|
1439 static bool
|
|
|
1440 gate_rtl_seqabstr (void)
|
|
|
1441 {
|
|
|
1442 return flag_rtl_seqabstr;
|
|
|
1443 }
|
|
|
1444
|
|
|
1445 /* The entry point of the sequence abstraction algorithm. */
|
|
|
1446
|
|
|
1447 static unsigned int
|
|
|
1448 rest_of_rtl_seqabstr (void)
|
|
|
1449 {
|
|
|
1450 /* Abstract out common insn sequences. */
|
|
|
1451 rtl_seqabstr ();
|
|
|
1452 return 0;
|
|
|
1453 }
|
|
|
1454
|
|
|
1455 struct rtl_opt_pass pass_rtl_seqabstr =
|
|
|
1456 {
|
|
|
1457 {
|
|
|
1458 RTL_PASS,
|
|
|
1459 "seqabstr", /* name */
|
|
|
1460 gate_rtl_seqabstr, /* gate */
|
|
|
1461 rest_of_rtl_seqabstr, /* execute */
|
|
|
1462 NULL, /* sub */
|
|
|
1463 NULL, /* next */
|
|
|
1464 0, /* static_pass_number */
|
|
|
1465 TV_SEQABSTR, /* tv_id */
|
|
|
1466 0, /* properties_required */
|
|
|
1467 0, /* properties_provided */
|
|
|
1468 0, /* properties_destroyed */
|
|
|
1469 0, /* todo_flags_start */
|
|
|
1470 TODO_df_finish | TODO_verify_rtl_sharing |
|
|
|
1471 TODO_dump_func |
|
|
|
1472 TODO_ggc_collect /* todo_flags_finish */
|
|
|
1473 }
|
|
|
1474 };
|
