|
111
|
1 /* Rematerialize pseudos values.
|
|
131
|
2 Copyright (C) 2014-2018 Free Software Foundation, Inc.
|
|
111
|
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
|
|
|
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 /* This code objective is to rematerialize spilled pseudo values. To
|
|
|
22 do this we calculate available insn candidates. The candidate is
|
|
|
23 available at some point if there is dominated set of insns with the
|
|
|
24 same pattern, the insn inputs are not dying or modified on any path
|
|
|
25 from the set, the outputs are not modified.
|
|
|
26
|
|
|
27 The insns containing memory or spilled pseudos (except for the
|
|
|
28 rematerialized pseudo) are not considered as such insns are not
|
|
|
29 profitable in comparison with regular loads of spilled pseudo
|
|
|
30 values. That simplifies the implementation as we don't need to
|
|
|
31 deal with memory aliasing.
|
|
|
32
|
|
|
33 To speed up available candidate calculation, we calculate partially
|
|
|
34 available candidates first and use them for initialization of the
|
|
|
35 availability. That is because (partial) availability sets are
|
|
|
36 sparse.
|
|
|
37
|
|
|
38 The rematerialization sub-pass could be improved further in the
|
|
|
39 following ways:
|
|
|
40
|
|
|
41 o We could make longer live ranges of inputs in the
|
|
|
42 rematerialization candidates if their hard registers are not used
|
|
|
43 for other purposes. This could be complicated if we need to
|
|
|
44 update BB live info information as LRA does not use
|
|
|
45 DF-infrastructure for compile-time reasons. This problem could
|
|
|
46 be overcome if constrain making live ranges longer only in BB/EBB
|
|
|
47 scope.
|
|
|
48 o We could use cost-based decision to choose rematerialization insn
|
|
|
49 (currently all insns without memory is can be used).
|
|
|
50 o We could use other free hard regs for unused output pseudos in
|
|
|
51 rematerialization candidates although such cases probably will
|
|
|
52 be very rare. */
|
|
|
53
|
|
|
54
|
|
|
55 #include "config.h"
|
|
|
56 #include "system.h"
|
|
|
57 #include "coretypes.h"
|
|
|
58 #include "backend.h"
|
|
|
59 #include "rtl.h"
|
|
|
60 #include "df.h"
|
|
|
61 #include "insn-config.h"
|
|
|
62 #include "regs.h"
|
|
|
63 #include "memmodel.h"
|
|
|
64 #include "ira.h"
|
|
|
65 #include "recog.h"
|
|
|
66 #include "lra.h"
|
|
|
67 #include "lra-int.h"
|
|
|
68
|
|
|
69 /* Number of candidates for rematerialization. */
|
|
|
70 static unsigned int cands_num;
|
|
|
71
|
|
|
72 /* The following is used for representation of call_used_reg_set in
|
|
|
73 form array whose elements are hard register numbers with nonzero bit
|
|
|
74 in CALL_USED_REG_SET. */
|
|
|
75 static int call_used_regs_arr_len;
|
|
|
76 static int call_used_regs_arr[FIRST_PSEUDO_REGISTER];
|
|
|
77
|
|
|
78 /* Bitmap used for different calculations. */
|
|
|
79 static bitmap_head temp_bitmap;
|
|
|
80
|
|
|
81 /* Registers accessed via subreg_p. */
|
|
|
82 static bitmap_head subreg_regs;
|
|
|
83
|
|
|
84 typedef struct cand *cand_t;
|
|
|
85 typedef const struct cand *const_cand_t;
|
|
|
86
|
|
|
87 /* Insn candidates for rematerialization. The candidate insn should
|
|
|
88 have the following properies:
|
|
|
89 o no any memory (as access to memory is non-profitable)
|
|
|
90 o no INOUT regs (it means no non-paradoxical subreg of output reg)
|
|
|
91 o one output spilled pseudo (or reload pseudo of a spilled pseudo)
|
|
|
92 o all other pseudos are with assigned hard regs. */
|
|
|
93 struct cand
|
|
|
94 {
|
|
|
95 /* Index of the candidates in all_cands. */
|
|
|
96 int index;
|
|
|
97 /* Insn pseudo regno for rematerialization. */
|
|
|
98 int regno;
|
|
|
99 /* The candidate insn. */
|
|
|
100 rtx_insn *insn;
|
|
|
101 /* Non-negative if a reload pseudo is in the insn instead of the
|
|
|
102 pseudo for rematerialization. */
|
|
|
103 int reload_regno;
|
|
|
104 /* Number of the operand containing the regno or its reload
|
|
|
105 regno. */
|
|
|
106 int nop;
|
|
|
107 /* Next candidate for the same regno. */
|
|
|
108 cand_t next_regno_cand;
|
|
|
109 };
|
|
|
110
|
|
|
111 /* Vector containing all candidates. */
|
|
|
112 static vec<cand_t> all_cands;
|
|
|
113 /* Map: insn -> candidate representing it. It is null if the insn can
|
|
|
114 not be used for rematerialization. */
|
|
|
115 static cand_t *insn_to_cand;
|
|
|
116 /* A secondary map, for candidates that involve two insns, where the
|
|
|
117 second one makes the equivalence. The candidate must not be used
|
|
|
118 before seeing this activation insn. */
|
|
|
119 static cand_t *insn_to_cand_activation;
|
|
|
120
|
|
|
121 /* Map regno -> candidates can be used for the regno
|
|
|
122 rematerialization. */
|
|
|
123 static cand_t *regno_cands;
|
|
|
124
|
|
|
125 /* Data about basic blocks used for the rematerialization
|
|
|
126 sub-pass. */
|
|
|
127 struct remat_bb_data
|
|
|
128 {
|
|
|
129 /* Basic block about which the below data are. */
|
|
|
130 basic_block bb;
|
|
|
131 /* Registers changed in the basic block: */
|
|
|
132 bitmap_head changed_regs;
|
|
|
133 /* Registers becoming dead in the BB. */
|
|
|
134 bitmap_head dead_regs;
|
|
|
135 /* Cands present in the BB whose in/out regs are not changed after
|
|
|
136 the cands occurence and are not dead (except the reload
|
|
|
137 regno). */
|
|
|
138 bitmap_head gen_cands;
|
|
|
139 bitmap_head livein_cands; /* cands whose inputs live at the BB start. */
|
|
|
140 bitmap_head pavin_cands; /* cands partially available at BB entry. */
|
|
|
141 bitmap_head pavout_cands; /* cands partially available at BB exit. */
|
|
|
142 bitmap_head avin_cands; /* cands available at the entry of the BB. */
|
|
|
143 bitmap_head avout_cands; /* cands available at the exit of the BB. */
|
|
|
144 };
|
|
|
145
|
|
|
146 /* Array for all BB data. Indexed by the corresponding BB index. */
|
|
|
147 typedef struct remat_bb_data *remat_bb_data_t;
|
|
|
148
|
|
|
149 /* Basic blocks for data flow problems -- all bocks except the special
|
|
|
150 ones. */
|
|
|
151 static bitmap_head all_blocks;
|
|
|
152
|
|
|
153 /* All basic block data are referred through the following array. */
|
|
|
154 static remat_bb_data_t remat_bb_data;
|
|
|
155
|
|
|
156 /* Two small functions for access to the bb data. */
|
|
|
157 static inline remat_bb_data_t
|
|
|
158 get_remat_bb_data (basic_block bb)
|
|
|
159 {
|
|
|
160 return &remat_bb_data[(bb)->index];
|
|
|
161 }
|
|
|
162
|
|
|
163 static inline remat_bb_data_t
|
|
|
164 get_remat_bb_data_by_index (int index)
|
|
|
165 {
|
|
|
166 return &remat_bb_data[index];
|
|
|
167 }
|
|
|
168
|
|
|
169
|
|
|
170
|
|
|
171 /* Hash table for the candidates. Different insns (e.g. structurally
|
|
|
172 the same insns or even insns with different unused output regs) can
|
|
|
173 be represented by the same candidate in the table. */
|
|
|
174 static htab_t cand_table;
|
|
|
175
|
|
|
176 /* Hash function for candidate CAND. */
|
|
|
177 static hashval_t
|
|
|
178 cand_hash (const void *cand)
|
|
|
179 {
|
|
|
180 const_cand_t c = (const_cand_t) cand;
|
|
|
181 lra_insn_recog_data_t id = lra_get_insn_recog_data (c->insn);
|
|
|
182 struct lra_static_insn_data *static_id = id->insn_static_data;
|
|
|
183 int nops = static_id->n_operands;
|
|
|
184 hashval_t hash = 0;
|
|
|
185
|
|
|
186 for (int i = 0; i < nops; i++)
|
|
|
187 if (i == c->nop)
|
|
|
188 hash = iterative_hash_object (c->regno, hash);
|
|
|
189 else if (static_id->operand[i].type == OP_IN)
|
|
|
190 hash = iterative_hash_object (*id->operand_loc[i], hash);
|
|
|
191 return hash;
|
|
|
192 }
|
|
|
193
|
|
|
194 /* Equal function for candidates CAND1 and CAND2. They are equal if
|
|
|
195 the corresponding candidate insns have the same code, the same
|
|
|
196 regno for rematerialization, the same input operands. */
|
|
|
197 static int
|
|
|
198 cand_eq_p (const void *cand1, const void *cand2)
|
|
|
199 {
|
|
|
200 const_cand_t c1 = (const_cand_t) cand1;
|
|
|
201 const_cand_t c2 = (const_cand_t) cand2;
|
|
|
202 lra_insn_recog_data_t id1 = lra_get_insn_recog_data (c1->insn);
|
|
|
203 lra_insn_recog_data_t id2 = lra_get_insn_recog_data (c2->insn);
|
|
|
204 struct lra_static_insn_data *static_id1 = id1->insn_static_data;
|
|
|
205 int nops = static_id1->n_operands;
|
|
|
206
|
|
|
207 if (c1->regno != c2->regno
|
|
|
208 || INSN_CODE (c1->insn) < 0
|
|
|
209 || INSN_CODE (c1->insn) != INSN_CODE (c2->insn))
|
|
|
210 return false;
|
|
|
211 gcc_assert (c1->nop == c2->nop);
|
|
|
212 for (int i = 0; i < nops; i++)
|
|
|
213 if (i != c1->nop && static_id1->operand[i].type == OP_IN
|
|
|
214 && *id1->operand_loc[i] != *id2->operand_loc[i])
|
|
|
215 return false;
|
|
|
216 return true;
|
|
|
217 }
|
|
|
218
|
|
|
219 /* Insert candidate CAND into the table if it is not there yet.
|
|
|
220 Return candidate which is in the table. */
|
|
|
221 static cand_t
|
|
|
222 insert_cand (cand_t cand)
|
|
|
223 {
|
|
|
224 void **entry_ptr;
|
|
|
225
|
|
|
226 entry_ptr = htab_find_slot (cand_table, cand, INSERT);
|
|
|
227 if (*entry_ptr == NULL)
|
|
|
228 *entry_ptr = (void *) cand;
|
|
|
229 return (cand_t) *entry_ptr;
|
|
|
230 }
|
|
|
231
|
|
|
232 /* Free candidate CAND memory. */
|
|
|
233 static void
|
|
|
234 free_cand (void *cand)
|
|
|
235 {
|
|
|
236 free (cand);
|
|
|
237 }
|
|
|
238
|
|
|
239 /* Initiate the candidate table. */
|
|
|
240 static void
|
|
|
241 initiate_cand_table (void)
|
|
|
242 {
|
|
|
243 cand_table = htab_create (8000, cand_hash, cand_eq_p,
|
|
|
244 (htab_del) free_cand);
|
|
|
245 }
|
|
|
246
|
|
|
247 /* Finish the candidate table. */
|
|
|
248 static void
|
|
|
249 finish_cand_table (void)
|
|
|
250 {
|
|
|
251 htab_delete (cand_table);
|
|
|
252 }
|
|
|
253
|
|
|
254
|
|
|
255
|
|
|
256 /* Return true if X contains memory or some UNSPEC. We can not just
|
|
|
257 check insn operands as memory or unspec might be not an operand
|
|
|
258 itself but contain an operand. Insn with memory access is not
|
|
|
259 profitable for rematerialization. Rematerialization of UNSPEC
|
|
|
260 might result in wrong code generation as the UNPEC effect is
|
|
|
261 unknown (e.g. generating a label). */
|
|
|
262 static bool
|
|
|
263 bad_for_rematerialization_p (rtx x)
|
|
|
264 {
|
|
|
265 int i, j;
|
|
|
266 const char *fmt;
|
|
|
267 enum rtx_code code;
|
|
|
268
|
|
|
269 if (MEM_P (x) || GET_CODE (x) == UNSPEC || GET_CODE (x) == UNSPEC_VOLATILE)
|
|
|
270 return true;
|
|
|
271 code = GET_CODE (x);
|
|
|
272 fmt = GET_RTX_FORMAT (code);
|
|
|
273 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
|
|
|
274 {
|
|
|
275 if (fmt[i] == 'e')
|
|
|
276 {
|
|
|
277 if (bad_for_rematerialization_p (XEXP (x, i)))
|
|
|
278 return true;
|
|
|
279 }
|
|
|
280 else if (fmt[i] == 'E')
|
|
|
281 {
|
|
|
282 for (j = XVECLEN (x, i) - 1; j >= 0; j--)
|
|
|
283 if (bad_for_rematerialization_p (XVECEXP (x, i, j)))
|
|
|
284 return true;
|
|
|
285 }
|
|
|
286 }
|
|
|
287 return false;
|
|
|
288 }
|
|
|
289
|
|
|
290 /* If INSN can not be used for rematerialization, return negative
|
|
|
291 value. If INSN can be considered as a candidate for
|
|
|
292 rematerialization, return value which is the operand number of the
|
|
|
293 pseudo for which the insn can be used for rematerialization. Here
|
|
|
294 we consider the insns without any memory, spilled pseudo (except
|
|
|
295 for the rematerialization pseudo), or dying or unused regs. */
|
|
|
296 static int
|
|
|
297 operand_to_remat (rtx_insn *insn)
|
|
|
298 {
|
|
|
299 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
|
|
|
300 struct lra_static_insn_data *static_id = id->insn_static_data;
|
|
|
301 struct lra_insn_reg *reg, *found_reg = NULL;
|
|
|
302
|
|
|
303 /* Don't rematerialize insns which can change PC. */
|
|
|
304 if (JUMP_P (insn) || CALL_P (insn))
|
|
|
305 return -1;
|
|
|
306 /* First find a pseudo which can be rematerialized. */
|
|
|
307 for (reg = id->regs; reg != NULL; reg = reg->next)
|
|
|
308 {
|
|
|
309 /* True FRAME_POINTER_NEEDED might be because we can not follow
|
|
|
310 changing sp offsets, e.g. alloca is used. If the insn contains
|
|
|
311 stack pointer in such case, we can not rematerialize it as we
|
|
|
312 can not know sp offset at a rematerialization place. */
|
|
|
313 if (reg->regno == STACK_POINTER_REGNUM && frame_pointer_needed)
|
|
|
314 return -1;
|
|
|
315 else if (reg->type == OP_OUT && ! reg->subreg_p
|
|
|
316 && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
|
|
|
317 {
|
|
|
318 /* We permits only one spilled reg. */
|
|
|
319 if (found_reg != NULL)
|
|
|
320 return -1;
|
|
|
321 found_reg = reg;
|
|
|
322 }
|
|
|
323 /* IRA calculates conflicts separately for subregs of two words
|
|
|
324 pseudo. Even if the pseudo lives, e.g. one its subreg can be
|
|
|
325 used lately, another subreg hard register can be already used
|
|
|
326 for something else. In such case, it is not safe to
|
|
|
327 rematerialize the insn. */
|
|
|
328 if (reg->regno >= FIRST_PSEUDO_REGISTER
|
|
|
329 && bitmap_bit_p (&subreg_regs, reg->regno))
|
|
|
330 return -1;
|
|
|
331
|
|
|
332 /* Don't allow hard registers to be rematerialized. */
|
|
|
333 if (reg->regno < FIRST_PSEUDO_REGISTER)
|
|
|
334 return -1;
|
|
|
335 }
|
|
|
336 if (found_reg == NULL)
|
|
|
337 return -1;
|
|
|
338 if (found_reg->regno < FIRST_PSEUDO_REGISTER)
|
|
|
339 return -1;
|
|
|
340 if (bad_for_rematerialization_p (PATTERN (insn)))
|
|
|
341 return -1;
|
|
|
342 /* Check the other regs are not spilled. */
|
|
|
343 for (reg = id->regs; reg != NULL; reg = reg->next)
|
|
|
344 if (found_reg == reg)
|
|
|
345 continue;
|
|
|
346 else if (reg->type == OP_INOUT)
|
|
|
347 return -1;
|
|
|
348 else if (reg->regno >= FIRST_PSEUDO_REGISTER
|
|
|
349 && reg_renumber[reg->regno] < 0)
|
|
|
350 /* Another spilled reg. */
|
|
|
351 return -1;
|
|
|
352 else if (reg->type == OP_IN)
|
|
|
353 {
|
|
|
354 if (find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
|
|
|
355 /* We don't want to make live ranges longer. */
|
|
|
356 return -1;
|
|
|
357 /* Check that there is no output reg as the input one. */
|
|
|
358 for (struct lra_insn_reg *reg2 = id->regs;
|
|
|
359 reg2 != NULL;
|
|
|
360 reg2 = reg2->next)
|
|
|
361 if (reg2->type == OP_OUT && reg->regno == reg2->regno)
|
|
|
362 return -1;
|
|
|
363 if (reg->regno < FIRST_PSEUDO_REGISTER)
|
|
|
364 for (struct lra_insn_reg *reg2 = static_id->hard_regs;
|
|
|
365 reg2 != NULL;
|
|
|
366 reg2 = reg2->next)
|
|
|
367 if (reg2->type == OP_OUT
|
|
|
368 && reg->regno <= reg2->regno
|
|
|
369 && (reg2->regno
|
|
|
370 < (int) end_hard_regno (reg->biggest_mode, reg->regno)))
|
|
|
371 return -1;
|
|
|
372 }
|
|
|
373 /* Check hard coded insn registers. */
|
|
|
374 for (struct lra_insn_reg *reg = static_id->hard_regs;
|
|
|
375 reg != NULL;
|
|
|
376 reg = reg->next)
|
|
|
377 if (reg->type == OP_INOUT)
|
|
|
378 return -1;
|
|
|
379 else if (reg->type == OP_IN)
|
|
|
380 {
|
|
|
381 /* Check that there is no output hard reg as the input
|
|
|
382 one. */
|
|
|
383 for (struct lra_insn_reg *reg2 = static_id->hard_regs;
|
|
|
384 reg2 != NULL;
|
|
|
385 reg2 = reg2->next)
|
|
|
386 if (reg2->type == OP_OUT && reg->regno == reg2->regno)
|
|
|
387 return -1;
|
|
|
388 }
|
|
|
389 /* Find the rematerialization operand. */
|
|
|
390 int nop = static_id->n_operands;
|
|
|
391 for (int i = 0; i < nop; i++)
|
|
|
392 if (REG_P (*id->operand_loc[i])
|
|
|
393 && (int) REGNO (*id->operand_loc[i]) == found_reg->regno)
|
|
|
394 return i;
|
|
|
395 return -1;
|
|
|
396 }
|
|
|
397
|
|
|
398 /* Create candidate for INSN with rematerialization operand NOP and
|
|
|
399 REGNO. Insert the candidate into the table and set up the
|
|
|
400 corresponding INSN_TO_CAND element. */
|
|
|
401 static void
|
|
|
402 create_cand (rtx_insn *insn, int nop, int regno, rtx_insn *activation = NULL)
|
|
|
403 {
|
|
|
404 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
|
|
|
405 rtx reg = *id->operand_loc[nop];
|
|
|
406 gcc_assert (REG_P (reg));
|
|
|
407 int op_regno = REGNO (reg);
|
|
|
408 gcc_assert (op_regno >= FIRST_PSEUDO_REGISTER);
|
|
|
409 cand_t cand = XNEW (struct cand);
|
|
|
410 cand->insn = insn;
|
|
|
411 cand->nop = nop;
|
|
|
412 cand->regno = regno;
|
|
|
413 cand->reload_regno = op_regno == regno ? -1 : op_regno;
|
|
|
414 gcc_assert (cand->regno >= 0);
|
|
|
415 cand_t cand_in_table = insert_cand (cand);
|
|
|
416 insn_to_cand[INSN_UID (insn)] = cand_in_table;
|
|
|
417 if (cand != cand_in_table)
|
|
|
418 free (cand);
|
|
|
419 else
|
|
|
420 {
|
|
|
421 /* A new cand. */
|
|
|
422 cand->index = all_cands.length ();
|
|
|
423 all_cands.safe_push (cand);
|
|
|
424 cand->next_regno_cand = regno_cands[cand->regno];
|
|
|
425 regno_cands[cand->regno] = cand;
|
|
|
426 }
|
|
|
427 if (activation)
|
|
|
428 insn_to_cand_activation[INSN_UID (activation)] = cand_in_table;
|
|
|
429 }
|
|
|
430
|
|
|
431 /* Create rematerialization candidates (inserting them into the
|
|
|
432 table). */
|
|
|
433 static void
|
|
|
434 create_cands (void)
|
|
|
435 {
|
|
|
436 rtx_insn *insn;
|
|
|
437 struct potential_cand
|
|
|
438 {
|
|
|
439 rtx_insn *insn;
|
|
|
440 int nop;
|
|
|
441 };
|
|
|
442 struct potential_cand *regno_potential_cand;
|
|
|
443
|
|
|
444 /* Create candidates. */
|
|
|
445 regno_potential_cand = XCNEWVEC (struct potential_cand, max_reg_num ());
|
|
|
446 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
|
|
|
447 if (NONDEBUG_INSN_P (insn))
|
|
|
448 {
|
|
|
449 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
|
|
|
450 int keep_regno = -1;
|
|
|
451 rtx set = single_set (insn);
|
|
|
452 int nop;
|
|
|
453
|
|
|
454 /* See if this is an output reload for a previous insn. */
|
|
|
455 if (set != NULL
|
|
|
456 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
|
|
|
457 {
|
|
|
458 rtx dstreg = SET_DEST (set);
|
|
|
459 int src_regno = REGNO (SET_SRC (set));
|
|
|
460 int dst_regno = REGNO (dstreg);
|
|
|
461 rtx_insn *insn2 = regno_potential_cand[src_regno].insn;
|
|
|
462
|
|
|
463 if (insn2 != NULL
|
|
|
464 && dst_regno >= FIRST_PSEUDO_REGISTER
|
|
|
465 && reg_renumber[dst_regno] < 0
|
|
|
466 && BLOCK_FOR_INSN (insn2) == BLOCK_FOR_INSN (insn))
|
|
|
467 {
|
|
|
468 create_cand (insn2, regno_potential_cand[src_regno].nop,
|
|
|
469 dst_regno, insn);
|
|
|
470 goto done;
|
|
|
471 }
|
|
|
472 }
|
|
|
473
|
|
|
474 nop = operand_to_remat (insn);
|
|
|
475 if (nop >= 0)
|
|
|
476 {
|
|
|
477 gcc_assert (REG_P (*id->operand_loc[nop]));
|
|
|
478 int regno = REGNO (*id->operand_loc[nop]);
|
|
|
479 gcc_assert (regno >= FIRST_PSEUDO_REGISTER);
|
|
|
480 /* If we're setting an unrenumbered pseudo, make a candidate immediately.
|
|
|
481 If it's an output reload register, save it for later; the code above
|
|
|
482 looks for output reload insns later on. */
|
|
|
483 if (reg_renumber[regno] < 0)
|
|
|
484 create_cand (insn, nop, regno);
|
|
|
485 else if (regno >= lra_constraint_new_regno_start)
|
|
|
486 {
|
|
|
487 regno_potential_cand[regno].insn = insn;
|
|
|
488 regno_potential_cand[regno].nop = nop;
|
|
|
489 keep_regno = regno;
|
|
|
490 }
|
|
|
491 }
|
|
|
492
|
|
|
493 done:
|
|
|
494 for (struct lra_insn_reg *reg = id->regs; reg != NULL; reg = reg->next)
|
|
|
495 if (reg->type != OP_IN && reg->regno != keep_regno
|
|
|
496 && reg->regno >= FIRST_PSEUDO_REGISTER)
|
|
|
497 regno_potential_cand[reg->regno].insn = NULL;
|
|
|
498 }
|
|
|
499 cands_num = all_cands.length ();
|
|
|
500 free (regno_potential_cand);
|
|
|
501 }
|
|
|
502
|
|
|
503
|
|
|
504
|
|
|
505 /* Create and initialize BB data. */
|
|
|
506 static void
|
|
|
507 create_remat_bb_data (void)
|
|
|
508 {
|
|
|
509 basic_block bb;
|
|
|
510 remat_bb_data_t bb_info;
|
|
|
511
|
|
|
512 remat_bb_data = XNEWVEC (struct remat_bb_data,
|
|
|
513 last_basic_block_for_fn (cfun));
|
|
|
514 FOR_ALL_BB_FN (bb, cfun)
|
|
|
515 {
|
|
|
516 gcc_checking_assert (bb->index >= 0
|
|
|
517 && bb->index < last_basic_block_for_fn (cfun));
|
|
|
518 bb_info = get_remat_bb_data (bb);
|
|
|
519 bb_info->bb = bb;
|
|
|
520 bitmap_initialize (&bb_info->changed_regs, ®_obstack);
|
|
|
521 bitmap_initialize (&bb_info->dead_regs, ®_obstack);
|
|
|
522 bitmap_initialize (&bb_info->gen_cands, ®_obstack);
|
|
|
523 bitmap_initialize (&bb_info->livein_cands, ®_obstack);
|
|
|
524 bitmap_initialize (&bb_info->pavin_cands, ®_obstack);
|
|
|
525 bitmap_initialize (&bb_info->pavout_cands, ®_obstack);
|
|
|
526 bitmap_initialize (&bb_info->avin_cands, ®_obstack);
|
|
|
527 bitmap_initialize (&bb_info->avout_cands, ®_obstack);
|
|
|
528 }
|
|
|
529 }
|
|
|
530
|
|
|
531 /* Dump all candidates to DUMP_FILE. */
|
|
|
532 static void
|
|
|
533 dump_cands (FILE *dump_file)
|
|
|
534 {
|
|
|
535 int i;
|
|
|
536 cand_t cand;
|
|
|
537
|
|
|
538 fprintf (dump_file, "\nCands:\n");
|
|
|
539 for (i = 0; i < (int) cands_num; i++)
|
|
|
540 {
|
|
|
541 cand = all_cands[i];
|
|
|
542 fprintf (dump_file, "%d (nop=%d, remat_regno=%d, reload_regno=%d):\n",
|
|
|
543 i, cand->nop, cand->regno, cand->reload_regno);
|
|
|
544 print_inline_rtx (dump_file, cand->insn, 6);
|
|
|
545 fprintf (dump_file, "\n");
|
|
|
546 }
|
|
|
547 }
|
|
|
548
|
|
|
549 /* Dump all candidates and BB data. */
|
|
|
550 static void
|
|
|
551 dump_candidates_and_remat_bb_data (void)
|
|
|
552 {
|
|
|
553 basic_block bb;
|
|
|
554
|
|
|
555 if (lra_dump_file == NULL)
|
|
|
556 return;
|
|
|
557 dump_cands (lra_dump_file);
|
|
|
558 FOR_EACH_BB_FN (bb, cfun)
|
|
|
559 {
|
|
|
560 fprintf (lra_dump_file, "\nBB %d:\n", bb->index);
|
|
|
561 /* Livein */
|
|
|
562 fprintf (lra_dump_file, " register live in:");
|
|
|
563 dump_regset (df_get_live_in (bb), lra_dump_file);
|
|
|
564 putc ('\n', lra_dump_file);
|
|
|
565 /* Liveout */
|
|
|
566 fprintf (lra_dump_file, " register live out:");
|
|
|
567 dump_regset (df_get_live_out (bb), lra_dump_file);
|
|
|
568 putc ('\n', lra_dump_file);
|
|
|
569 /* Changed/dead regs: */
|
|
|
570 fprintf (lra_dump_file, " changed regs:");
|
|
|
571 dump_regset (&get_remat_bb_data (bb)->changed_regs, lra_dump_file);
|
|
|
572 putc ('\n', lra_dump_file);
|
|
|
573 fprintf (lra_dump_file, " dead regs:");
|
|
|
574 dump_regset (&get_remat_bb_data (bb)->dead_regs, lra_dump_file);
|
|
|
575 putc ('\n', lra_dump_file);
|
|
|
576 lra_dump_bitmap_with_title ("cands generated in BB",
|
|
|
577 &get_remat_bb_data (bb)->gen_cands, bb->index);
|
|
|
578 lra_dump_bitmap_with_title ("livein cands in BB",
|
|
|
579 &get_remat_bb_data (bb)->livein_cands, bb->index);
|
|
|
580 lra_dump_bitmap_with_title ("pavin cands in BB",
|
|
|
581 &get_remat_bb_data (bb)->pavin_cands, bb->index);
|
|
|
582 lra_dump_bitmap_with_title ("pavout cands in BB",
|
|
|
583 &get_remat_bb_data (bb)->pavout_cands, bb->index);
|
|
|
584 lra_dump_bitmap_with_title ("avin cands in BB",
|
|
|
585 &get_remat_bb_data (bb)->avin_cands, bb->index);
|
|
|
586 lra_dump_bitmap_with_title ("avout cands in BB",
|
|
|
587 &get_remat_bb_data (bb)->avout_cands, bb->index);
|
|
|
588 }
|
|
|
589 fprintf (lra_dump_file, "subreg regs:");
|
|
|
590 dump_regset (&subreg_regs, lra_dump_file);
|
|
|
591 putc ('\n', lra_dump_file);
|
|
|
592 }
|
|
|
593
|
|
|
594 /* Free all BB data. */
|
|
|
595 static void
|
|
|
596 finish_remat_bb_data (void)
|
|
|
597 {
|
|
|
598 basic_block bb;
|
|
|
599
|
|
|
600 FOR_EACH_BB_FN (bb, cfun)
|
|
|
601 {
|
|
|
602 bitmap_clear (&get_remat_bb_data (bb)->avout_cands);
|
|
|
603 bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
|
|
|
604 bitmap_clear (&get_remat_bb_data (bb)->pavout_cands);
|
|
|
605 bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
|
|
|
606 bitmap_clear (&get_remat_bb_data (bb)->livein_cands);
|
|
|
607 bitmap_clear (&get_remat_bb_data (bb)->gen_cands);
|
|
|
608 bitmap_clear (&get_remat_bb_data (bb)->dead_regs);
|
|
|
609 bitmap_clear (&get_remat_bb_data (bb)->changed_regs);
|
|
|
610 }
|
|
|
611 free (remat_bb_data);
|
|
|
612 }
|
|
|
613
|
|
|
614
|
|
|
615
|
|
|
616 /* Update changed_regs, dead_regs, subreg_regs of BB from INSN. */
|
|
|
617 static void
|
|
|
618 set_bb_regs (basic_block bb, rtx_insn *insn)
|
|
|
619 {
|
|
|
620 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
|
|
|
621 remat_bb_data_t bb_info = get_remat_bb_data (bb);
|
|
|
622 struct lra_insn_reg *reg;
|
|
|
623
|
|
|
624 for (reg = id->regs; reg != NULL; reg = reg->next)
|
|
|
625 {
|
|
|
626 unsigned regno = reg->regno;
|
|
|
627 if (reg->type != OP_IN)
|
|
|
628 bitmap_set_bit (&bb_info->changed_regs, regno);
|
|
|
629 else if (find_regno_note (insn, REG_DEAD, regno) != NULL)
|
|
|
630 bitmap_set_bit (&bb_info->dead_regs, regno);
|
|
|
631 if (regno >= FIRST_PSEUDO_REGISTER && reg->subreg_p)
|
|
|
632 bitmap_set_bit (&subreg_regs, regno);
|
|
|
633 }
|
|
|
634 if (CALL_P (insn))
|
|
|
635 for (int i = 0; i < call_used_regs_arr_len; i++)
|
|
|
636 bitmap_set_bit (&get_remat_bb_data (bb)->dead_regs,
|
|
|
637 call_used_regs_arr[i]);
|
|
|
638 }
|
|
|
639
|
|
|
640 /* Calculate changed_regs and dead_regs for each BB. */
|
|
|
641 static void
|
|
|
642 calculate_local_reg_remat_bb_data (void)
|
|
|
643 {
|
|
|
644 basic_block bb;
|
|
|
645 rtx_insn *insn;
|
|
|
646
|
|
|
647 FOR_EACH_BB_FN (bb, cfun)
|
|
|
648 FOR_BB_INSNS (bb, insn)
|
|
|
649 if (NONDEBUG_INSN_P (insn))
|
|
|
650 set_bb_regs (bb, insn);
|
|
|
651 }
|
|
|
652
|
|
|
653
|
|
|
654
|
|
|
655 /* Return true if REG overlaps an input operand of INSN. */
|
|
|
656 static bool
|
|
|
657 reg_overlap_for_remat_p (lra_insn_reg *reg, rtx_insn *insn)
|
|
|
658 {
|
|
|
659 int iter;
|
|
|
660 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
|
|
|
661 struct lra_static_insn_data *static_id = id->insn_static_data;
|
|
|
662 unsigned regno = reg->regno;
|
|
|
663 int nregs;
|
|
|
664
|
|
|
665 if (regno >= FIRST_PSEUDO_REGISTER && reg_renumber[regno] >= 0)
|
|
|
666 regno = reg_renumber[regno];
|
|
|
667 if (regno >= FIRST_PSEUDO_REGISTER)
|
|
|
668 nregs = 1;
|
|
|
669 else
|
|
|
670 nregs = hard_regno_nregs (regno, reg->biggest_mode);
|
|
|
671
|
|
|
672 struct lra_insn_reg *reg2;
|
|
|
673
|
|
|
674 for (iter = 0; iter < 2; iter++)
|
|
|
675 for (reg2 = (iter == 0 ? id->regs : static_id->hard_regs);
|
|
|
676 reg2 != NULL;
|
|
|
677 reg2 = reg2->next)
|
|
|
678 {
|
|
|
679 if (reg2->type != OP_IN)
|
|
|
680 continue;
|
|
|
681 unsigned regno2 = reg2->regno;
|
|
|
682 int nregs2;
|
|
|
683
|
|
|
684 if (regno2 >= FIRST_PSEUDO_REGISTER && reg_renumber[regno2] >= 0)
|
|
|
685 regno2 = reg_renumber[regno2];
|
|
|
686 if (regno2 >= FIRST_PSEUDO_REGISTER)
|
|
|
687 nregs2 = 1;
|
|
|
688 else
|
|
|
689 nregs2 = hard_regno_nregs (regno2, reg->biggest_mode);
|
|
|
690
|
|
|
691 if ((regno2 + nregs2 - 1 >= regno && regno2 < regno + nregs)
|
|
|
692 || (regno + nregs - 1 >= regno2 && regno < regno2 + nregs2))
|
|
|
693 return true;
|
|
|
694 }
|
|
|
695 return false;
|
|
|
696 }
|
|
|
697
|
|
|
698 /* Return true if a call used register is an input operand of INSN. */
|
|
|
699 static bool
|
|
|
700 call_used_input_regno_present_p (rtx_insn *insn)
|
|
|
701 {
|
|
|
702 int iter;
|
|
|
703 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
|
|
|
704 struct lra_static_insn_data *static_id = id->insn_static_data;
|
|
|
705 struct lra_insn_reg *reg;
|
|
|
706
|
|
|
707 for (iter = 0; iter < 2; iter++)
|
|
|
708 for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
|
|
|
709 reg != NULL;
|
|
|
710 reg = reg->next)
|
|
131
|
711 if (reg->type == OP_IN && reg->regno < FIRST_PSEUDO_REGISTER
|
|
111
|
712 && TEST_HARD_REG_BIT (call_used_reg_set, reg->regno))
|
|
|
713 return true;
|
|
|
714 return false;
|
|
|
715 }
|
|
|
716
|
|
|
717 /* Calculate livein_cands for each BB. */
|
|
|
718 static void
|
|
|
719 calculate_livein_cands (void)
|
|
|
720 {
|
|
|
721 basic_block bb;
|
|
|
722
|
|
|
723 FOR_EACH_BB_FN (bb, cfun)
|
|
|
724 {
|
|
|
725 bitmap livein_regs = df_get_live_in (bb);
|
|
|
726 bitmap livein_cands = &get_remat_bb_data (bb)->livein_cands;
|
|
|
727 for (unsigned int i = 0; i < cands_num; i++)
|
|
|
728 {
|
|
|
729 cand_t cand = all_cands[i];
|
|
|
730 lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
|
|
|
731 struct lra_insn_reg *reg;
|
|
|
732
|
|
|
733 for (reg = id->regs; reg != NULL; reg = reg->next)
|
|
|
734 if (reg->type == OP_IN && ! bitmap_bit_p (livein_regs, reg->regno))
|
|
|
735 break;
|
|
|
736 if (reg == NULL)
|
|
|
737 bitmap_set_bit (livein_cands, i);
|
|
|
738 }
|
|
|
739 }
|
|
|
740 }
|
|
|
741
|
|
|
742 /* Calculate gen_cands for each BB. */
|
|
|
743 static void
|
|
|
744 calculate_gen_cands (void)
|
|
|
745 {
|
|
|
746 basic_block bb;
|
|
|
747 bitmap gen_cands;
|
|
|
748 rtx_insn *insn;
|
|
|
749
|
|
|
750 FOR_EACH_BB_FN (bb, cfun)
|
|
|
751 {
|
|
|
752 gen_cands = &get_remat_bb_data (bb)->gen_cands;
|
|
|
753 auto_bitmap gen_insns (®_obstack);
|
|
|
754 FOR_BB_INSNS (bb, insn)
|
|
|
755 if (INSN_P (insn))
|
|
|
756 {
|
|
|
757 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
|
|
|
758 struct lra_static_insn_data *static_id = id->insn_static_data;
|
|
|
759 struct lra_insn_reg *reg;
|
|
|
760 unsigned int uid;
|
|
|
761 bitmap_iterator bi;
|
|
|
762 cand_t cand;
|
|
|
763 rtx set;
|
|
|
764 int iter;
|
|
|
765 int src_regno = -1, dst_regno = -1;
|
|
|
766
|
|
|
767 if ((set = single_set (insn)) != NULL
|
|
|
768 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
|
|
|
769 {
|
|
|
770 src_regno = REGNO (SET_SRC (set));
|
|
|
771 dst_regno = REGNO (SET_DEST (set));
|
|
|
772 }
|
|
|
773
|
|
|
774 /* Update gen_cands: */
|
|
|
775 bitmap_clear (&temp_bitmap);
|
|
|
776 for (iter = 0; iter < 2; iter++)
|
|
|
777 for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
|
|
|
778 reg != NULL;
|
|
|
779 reg = reg->next)
|
|
|
780 if (reg->type != OP_IN
|
|
|
781 || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
|
|
|
782 EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
|
|
|
783 {
|
|
|
784 rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
|
|
|
785
|
|
|
786 cand = insn_to_cand[INSN_UID (insn2)];
|
|
|
787 gcc_assert (cand != NULL);
|
|
|
788 /* Ignore the reload insn. */
|
|
|
789 if (src_regno == cand->reload_regno
|
|
|
790 && dst_regno == cand->regno)
|
|
|
791 continue;
|
|
|
792 if (cand->regno == reg->regno
|
|
|
793 || reg_overlap_for_remat_p (reg, insn2))
|
|
|
794 {
|
|
|
795 bitmap_clear_bit (gen_cands, cand->index);
|
|
|
796 bitmap_set_bit (&temp_bitmap, uid);
|
|
|
797 }
|
|
|
798 }
|
|
|
799
|
|
|
800 if (CALL_P (insn))
|
|
|
801 EXECUTE_IF_SET_IN_BITMAP (gen_insns, 0, uid, bi)
|
|
|
802 {
|
|
|
803 rtx_insn *insn2 = lra_insn_recog_data[uid]->insn;
|
|
|
804
|
|
|
805 cand = insn_to_cand[INSN_UID (insn2)];
|
|
|
806 gcc_assert (cand != NULL);
|
|
|
807 if (call_used_input_regno_present_p (insn2))
|
|
|
808 {
|
|
|
809 bitmap_clear_bit (gen_cands, cand->index);
|
|
|
810 bitmap_set_bit (&temp_bitmap, uid);
|
|
|
811 }
|
|
|
812 }
|
|
|
813 bitmap_and_compl_into (gen_insns, &temp_bitmap);
|
|
|
814
|
|
|
815 cand = insn_to_cand[INSN_UID (insn)];
|
|
|
816 if (cand != NULL)
|
|
|
817 {
|
|
|
818 bitmap_set_bit (gen_cands, cand->index);
|
|
|
819 bitmap_set_bit (gen_insns, INSN_UID (insn));
|
|
|
820 }
|
|
|
821 }
|
|
|
822 }
|
|
|
823 }
|
|
|
824
|
|
|
825
|
|
|
826
|
|
|
827 /* The common transfer function used by the DF equation solver to
|
|
|
828 propagate (partial) availability info BB_IN to BB_OUT through block
|
|
|
829 with BB_INDEX according to the following equation:
|
|
|
830
|
|
|
831 bb.out = ((bb.in & bb.livein) - bb.killed) OR bb.gen
|
|
|
832 */
|
|
|
833 static bool
|
|
|
834 cand_trans_fun (int bb_index, bitmap bb_in, bitmap bb_out)
|
|
|
835 {
|
|
|
836 remat_bb_data_t bb_info;
|
|
|
837 bitmap bb_livein, bb_changed_regs, bb_dead_regs;
|
|
|
838 unsigned int cid;
|
|
|
839 bitmap_iterator bi;
|
|
|
840
|
|
|
841 bb_info = get_remat_bb_data_by_index (bb_index);
|
|
|
842 bb_livein = &bb_info->livein_cands;
|
|
|
843 bb_changed_regs = &bb_info->changed_regs;
|
|
|
844 bb_dead_regs = &bb_info->dead_regs;
|
|
|
845 /* Calculate killed avin cands -- cands whose regs are changed or
|
|
|
846 becoming dead in the BB. We calculate it here as we hope that
|
|
|
847 repeated calculations are compensated by smaller size of BB_IN in
|
|
|
848 comparison with all candidates number. */
|
|
|
849 bitmap_clear (&temp_bitmap);
|
|
|
850 EXECUTE_IF_SET_IN_BITMAP (bb_in, 0, cid, bi)
|
|
|
851 {
|
|
|
852 cand_t cand = all_cands[cid];
|
|
|
853 lra_insn_recog_data_t id = lra_get_insn_recog_data (cand->insn);
|
|
|
854 struct lra_insn_reg *reg;
|
|
|
855
|
|
|
856 if (! bitmap_bit_p (bb_livein, cid))
|
|
|
857 {
|
|
|
858 bitmap_set_bit (&temp_bitmap, cid);
|
|
|
859 continue;
|
|
|
860 }
|
|
|
861 for (reg = id->regs; reg != NULL; reg = reg->next)
|
|
|
862 /* Ignore all outputs which are not the regno for
|
|
|
863 rematerialization. */
|
|
|
864 if (reg->type == OP_OUT && reg->regno != cand->regno)
|
|
|
865 continue;
|
|
|
866 else if (bitmap_bit_p (bb_changed_regs, reg->regno)
|
|
|
867 || bitmap_bit_p (bb_dead_regs, reg->regno))
|
|
|
868 {
|
|
|
869 bitmap_set_bit (&temp_bitmap, cid);
|
|
|
870 break;
|
|
|
871 }
|
|
|
872 /* Check regno for rematerialization. */
|
|
|
873 if (bitmap_bit_p (bb_changed_regs, cand->regno)
|
|
|
874 || bitmap_bit_p (bb_dead_regs, cand->regno))
|
|
|
875 bitmap_set_bit (&temp_bitmap, cid);
|
|
|
876 }
|
|
|
877 return bitmap_ior_and_compl (bb_out,
|
|
|
878 &bb_info->gen_cands, bb_in, &temp_bitmap);
|
|
|
879 }
|
|
|
880
|
|
|
881
|
|
|
882
|
|
|
883 /* The transfer function used by the DF equation solver to propagate
|
|
|
884 partial candidate availability info through block with BB_INDEX
|
|
|
885 according to the following equation:
|
|
|
886
|
|
|
887 bb.pavout = ((bb.pavin & bb.livein) - bb.killed) OR bb.gen
|
|
|
888 */
|
|
|
889 static bool
|
|
|
890 cand_pav_trans_fun (int bb_index)
|
|
|
891 {
|
|
|
892 remat_bb_data_t bb_info;
|
|
|
893
|
|
|
894 bb_info = get_remat_bb_data_by_index (bb_index);
|
|
|
895 return cand_trans_fun (bb_index, &bb_info->pavin_cands,
|
|
|
896 &bb_info->pavout_cands);
|
|
|
897 }
|
|
|
898
|
|
|
899 /* The confluence function used by the DF equation solver to set up
|
|
|
900 cand_pav info for a block BB without predecessor. */
|
|
|
901 static void
|
|
|
902 cand_pav_con_fun_0 (basic_block bb)
|
|
|
903 {
|
|
|
904 bitmap_clear (&get_remat_bb_data (bb)->pavin_cands);
|
|
|
905 }
|
|
|
906
|
|
|
907 /* The confluence function used by the DF equation solver to propagate
|
|
|
908 partial candidate availability info from predecessor to successor
|
|
|
909 on edge E (pred->bb) according to the following equation:
|
|
|
910
|
|
|
911 bb.pavin_cands = 0 for entry block | OR (pavout_cands of predecessors)
|
|
|
912 */
|
|
|
913 static bool
|
|
|
914 cand_pav_con_fun_n (edge e)
|
|
|
915 {
|
|
|
916 basic_block pred = e->src;
|
|
|
917 basic_block bb = e->dest;
|
|
|
918 remat_bb_data_t bb_info;
|
|
|
919 bitmap bb_pavin, pred_pavout;
|
|
|
920
|
|
|
921 bb_info = get_remat_bb_data (bb);
|
|
|
922 bb_pavin = &bb_info->pavin_cands;
|
|
|
923 pred_pavout = &get_remat_bb_data (pred)->pavout_cands;
|
|
|
924 return bitmap_ior_into (bb_pavin, pred_pavout);
|
|
|
925 }
|
|
|
926
|
|
|
927
|
|
|
928
|
|
|
929 /* The transfer function used by the DF equation solver to propagate
|
|
|
930 candidate availability info through block with BB_INDEX according
|
|
|
931 to the following equation:
|
|
|
932
|
|
|
933 bb.avout = ((bb.avin & bb.livein) - bb.killed) OR bb.gen
|
|
|
934 */
|
|
|
935 static bool
|
|
|
936 cand_av_trans_fun (int bb_index)
|
|
|
937 {
|
|
|
938 remat_bb_data_t bb_info;
|
|
|
939
|
|
|
940 bb_info = get_remat_bb_data_by_index (bb_index);
|
|
|
941 return cand_trans_fun (bb_index, &bb_info->avin_cands,
|
|
|
942 &bb_info->avout_cands);
|
|
|
943 }
|
|
|
944
|
|
|
945 /* The confluence function used by the DF equation solver to set up
|
|
|
946 cand_av info for a block BB without predecessor. */
|
|
|
947 static void
|
|
|
948 cand_av_con_fun_0 (basic_block bb)
|
|
|
949 {
|
|
|
950 bitmap_clear (&get_remat_bb_data (bb)->avin_cands);
|
|
|
951 }
|
|
|
952
|
|
|
953 /* The confluence function used by the DF equation solver to propagate
|
|
|
954 cand_av info from predecessor to successor on edge E (pred->bb)
|
|
|
955 according to the following equation:
|
|
|
956
|
|
|
957 bb.avin_cands = 0 for entry block | AND (avout_cands of predecessors)
|
|
|
958 */
|
|
|
959 static bool
|
|
|
960 cand_av_con_fun_n (edge e)
|
|
|
961 {
|
|
|
962 basic_block pred = e->src;
|
|
|
963 basic_block bb = e->dest;
|
|
|
964 remat_bb_data_t bb_info;
|
|
|
965 bitmap bb_avin, pred_avout;
|
|
|
966
|
|
|
967 bb_info = get_remat_bb_data (bb);
|
|
|
968 bb_avin = &bb_info->avin_cands;
|
|
|
969 pred_avout = &get_remat_bb_data (pred)->avout_cands;
|
|
|
970 return bitmap_and_into (bb_avin, pred_avout);
|
|
|
971 }
|
|
|
972
|
|
|
973 /* Calculate available candidates for each BB. */
|
|
|
974 static void
|
|
|
975 calculate_global_remat_bb_data (void)
|
|
|
976 {
|
|
|
977 basic_block bb;
|
|
|
978
|
|
|
979 df_simple_dataflow
|
|
|
980 (DF_FORWARD, NULL, cand_pav_con_fun_0, cand_pav_con_fun_n,
|
|
|
981 cand_pav_trans_fun, &all_blocks,
|
|
|
982 df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
|
|
|
983 /* Initialize avin by pavin. */
|
|
|
984 FOR_EACH_BB_FN (bb, cfun)
|
|
|
985 bitmap_copy (&get_remat_bb_data (bb)->avin_cands,
|
|
|
986 &get_remat_bb_data (bb)->pavin_cands);
|
|
|
987 df_simple_dataflow
|
|
|
988 (DF_FORWARD, NULL, cand_av_con_fun_0, cand_av_con_fun_n,
|
|
|
989 cand_av_trans_fun, &all_blocks,
|
|
|
990 df_get_postorder (DF_FORWARD), df_get_n_blocks (DF_FORWARD));
|
|
|
991 }
|
|
|
992
|
|
|
993
|
|
|
994
|
|
|
995 /* Setup sp offset attribute to SP_OFFSET for all INSNS. */
|
|
|
996 static void
|
|
131
|
997 change_sp_offset (rtx_insn *insns, poly_int64 sp_offset)
|
|
111
|
998 {
|
|
|
999 for (rtx_insn *insn = insns; insn != NULL; insn = NEXT_INSN (insn))
|
|
|
1000 eliminate_regs_in_insn (insn, false, false, sp_offset);
|
|
|
1001 }
|
|
|
1002
|
|
|
1003 /* Return start hard register of REG (can be a hard or a pseudo reg)
|
|
|
1004 or -1 (if it is a spilled pseudo). Return number of hard registers
|
|
|
1005 occupied by REG through parameter NREGS if the start hard reg is
|
|
|
1006 not negative. */
|
|
|
1007 static int
|
|
|
1008 get_hard_regs (struct lra_insn_reg *reg, int &nregs)
|
|
|
1009 {
|
|
|
1010 int regno = reg->regno;
|
|
|
1011 int hard_regno = regno < FIRST_PSEUDO_REGISTER ? regno : reg_renumber[regno];
|
|
|
1012
|
|
|
1013 if (hard_regno >= 0)
|
|
|
1014 nregs = hard_regno_nregs (hard_regno, reg->biggest_mode);
|
|
|
1015 return hard_regno;
|
|
|
1016 }
|
|
|
1017
|
|
|
1018 /* Make copy of and register scratch pseudos in rematerialized insn
|
|
|
1019 REMAT_INSN. */
|
|
|
1020 static void
|
|
|
1021 update_scratch_ops (rtx_insn *remat_insn)
|
|
|
1022 {
|
|
|
1023 int hard_regno;
|
|
|
1024 lra_insn_recog_data_t id = lra_get_insn_recog_data (remat_insn);
|
|
|
1025 struct lra_static_insn_data *static_id = id->insn_static_data;
|
|
|
1026 for (int i = 0; i < static_id->n_operands; i++)
|
|
|
1027 {
|
|
|
1028 rtx *loc = id->operand_loc[i];
|
|
|
1029 if (! REG_P (*loc))
|
|
|
1030 continue;
|
|
|
1031 int regno = REGNO (*loc);
|
|
|
1032 if (! lra_former_scratch_p (regno))
|
|
|
1033 continue;
|
|
|
1034 hard_regno = reg_renumber[regno];
|
|
|
1035 *loc = lra_create_new_reg (GET_MODE (*loc), *loc,
|
|
|
1036 lra_get_allocno_class (regno),
|
|
|
1037 "scratch pseudo copy");
|
|
|
1038 if (hard_regno >= 0)
|
|
|
1039 {
|
|
|
1040 reg_renumber[REGNO (*loc)] = hard_regno;
|
|
|
1041 if (lra_dump_file)
|
|
|
1042 fprintf (lra_dump_file, " Assigning the same %d to r%d\n",
|
|
|
1043 REGNO (*loc), hard_regno);
|
|
|
1044 }
|
|
|
1045 lra_register_new_scratch_op (remat_insn, i);
|
|
|
1046 }
|
|
|
1047
|
|
|
1048 }
|
|
|
1049
|
|
|
1050 /* Insert rematerialization insns using the data-flow data calculated
|
|
|
1051 earlier. */
|
|
|
1052 static bool
|
|
|
1053 do_remat (void)
|
|
|
1054 {
|
|
|
1055 unsigned regno;
|
|
|
1056 rtx_insn *insn;
|
|
|
1057 basic_block bb;
|
|
|
1058 bool changed_p = false;
|
|
|
1059 /* Living hard regs and hard registers of living pseudos. */
|
|
|
1060 HARD_REG_SET live_hard_regs;
|
|
|
1061 bitmap_iterator bi;
|
|
|
1062
|
|
|
1063 auto_bitmap avail_cands (®_obstack);
|
|
|
1064 auto_bitmap active_cands (®_obstack);
|
|
|
1065 FOR_EACH_BB_FN (bb, cfun)
|
|
|
1066 {
|
|
|
1067 CLEAR_HARD_REG_SET (live_hard_regs);
|
|
|
1068 EXECUTE_IF_SET_IN_BITMAP (df_get_live_in (bb), 0, regno, bi)
|
|
|
1069 {
|
|
|
1070 int hard_regno = regno < FIRST_PSEUDO_REGISTER
|
|
|
1071 ? regno
|
|
|
1072 : reg_renumber[regno];
|
|
|
1073 if (hard_regno >= 0)
|
|
|
1074 SET_HARD_REG_BIT (live_hard_regs, hard_regno);
|
|
|
1075 }
|
|
|
1076 bitmap_and (avail_cands, &get_remat_bb_data (bb)->avin_cands,
|
|
|
1077 &get_remat_bb_data (bb)->livein_cands);
|
|
|
1078 /* Activating insns are always in the same block as their corresponding
|
|
|
1079 remat insn, so at the start of a block the two bitsets are equal. */
|
|
|
1080 bitmap_copy (active_cands, avail_cands);
|
|
|
1081 FOR_BB_INSNS (bb, insn)
|
|
|
1082 {
|
|
|
1083 if (!NONDEBUG_INSN_P (insn))
|
|
|
1084 continue;
|
|
|
1085
|
|
|
1086 lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
|
|
|
1087 struct lra_static_insn_data *static_id = id->insn_static_data;
|
|
|
1088 struct lra_insn_reg *reg;
|
|
|
1089 cand_t cand;
|
|
|
1090 unsigned int cid;
|
|
|
1091 bitmap_iterator bi;
|
|
|
1092 rtx set;
|
|
|
1093 int iter;
|
|
|
1094 int src_regno = -1, dst_regno = -1;
|
|
|
1095
|
|
|
1096 if ((set = single_set (insn)) != NULL
|
|
|
1097 && REG_P (SET_SRC (set)) && REG_P (SET_DEST (set)))
|
|
|
1098 {
|
|
|
1099 src_regno = REGNO (SET_SRC (set));
|
|
|
1100 dst_regno = REGNO (SET_DEST (set));
|
|
|
1101 }
|
|
|
1102
|
|
|
1103 cand = NULL;
|
|
|
1104 /* Check possibility of rematerialization (hard reg or
|
|
|
1105 unpsilled pseudo <- spilled pseudo): */
|
|
|
1106 if (dst_regno >= 0 && src_regno >= FIRST_PSEUDO_REGISTER
|
|
|
1107 && reg_renumber[src_regno] < 0
|
|
|
1108 && (dst_regno < FIRST_PSEUDO_REGISTER
|
|
|
1109 || reg_renumber[dst_regno] >= 0))
|
|
|
1110 {
|
|
|
1111 for (cand = regno_cands[src_regno];
|
|
|
1112 cand != NULL;
|
|
|
1113 cand = cand->next_regno_cand)
|
|
|
1114 if (bitmap_bit_p (avail_cands, cand->index)
|
|
|
1115 && bitmap_bit_p (active_cands, cand->index))
|
|
|
1116 break;
|
|
|
1117 }
|
|
|
1118 int i, hard_regno, nregs;
|
|
|
1119 int dst_hard_regno, dst_nregs;
|
|
|
1120 rtx_insn *remat_insn = NULL;
|
|
131
|
1121 poly_int64 cand_sp_offset = 0;
|
|
111
|
1122 if (cand != NULL)
|
|
|
1123 {
|
|
|
1124 lra_insn_recog_data_t cand_id
|
|
|
1125 = lra_get_insn_recog_data (cand->insn);
|
|
|
1126 struct lra_static_insn_data *static_cand_id
|
|
|
1127 = cand_id->insn_static_data;
|
|
|
1128 rtx saved_op = *cand_id->operand_loc[cand->nop];
|
|
|
1129
|
|
|
1130 /* Check clobbers do not kill something living. */
|
|
|
1131 gcc_assert (REG_P (saved_op));
|
|
|
1132 int ignore_regno = REGNO (saved_op);
|
|
|
1133
|
|
|
1134 dst_hard_regno = dst_regno < FIRST_PSEUDO_REGISTER
|
|
|
1135 ? dst_regno : reg_renumber[dst_regno];
|
|
|
1136 gcc_assert (dst_hard_regno >= 0);
|
|
|
1137 machine_mode mode = GET_MODE (SET_DEST (set));
|
|
|
1138 dst_nregs = hard_regno_nregs (dst_hard_regno, mode);
|
|
|
1139
|
|
|
1140 for (reg = cand_id->regs; reg != NULL; reg = reg->next)
|
|
|
1141 if (reg->type != OP_IN && reg->regno != ignore_regno)
|
|
|
1142 {
|
|
|
1143 hard_regno = get_hard_regs (reg, nregs);
|
|
|
1144 gcc_assert (hard_regno >= 0);
|
|
|
1145 for (i = 0; i < nregs; i++)
|
|
|
1146 if (TEST_HARD_REG_BIT (live_hard_regs, hard_regno + i))
|
|
|
1147 break;
|
|
|
1148 if (i < nregs)
|
|
|
1149 break;
|
|
|
1150 /* Ensure the clobber also doesn't overlap dst_regno. */
|
|
|
1151 if (hard_regno + nregs > dst_hard_regno
|
|
|
1152 && hard_regno < dst_hard_regno + dst_nregs)
|
|
|
1153 break;
|
|
|
1154 }
|
|
|
1155
|
|
|
1156 if (reg == NULL)
|
|
|
1157 {
|
|
|
1158 for (reg = static_cand_id->hard_regs;
|
|
|
1159 reg != NULL;
|
|
|
1160 reg = reg->next)
|
|
|
1161 if (reg->type != OP_IN)
|
|
|
1162 {
|
|
|
1163 if (TEST_HARD_REG_BIT (live_hard_regs, reg->regno))
|
|
|
1164 break;
|
|
|
1165 if (reg->regno >= dst_hard_regno
|
|
|
1166 && reg->regno < dst_hard_regno + dst_nregs)
|
|
|
1167 break;
|
|
|
1168 }
|
|
|
1169 }
|
|
|
1170
|
|
|
1171 if (reg == NULL)
|
|
|
1172 {
|
|
|
1173 *cand_id->operand_loc[cand->nop] = SET_DEST (set);
|
|
|
1174 lra_update_insn_regno_info (cand->insn);
|
|
|
1175 bool ok_p = lra_constrain_insn (cand->insn);
|
|
|
1176 if (ok_p)
|
|
|
1177 {
|
|
|
1178 rtx remat_pat = copy_insn (PATTERN (cand->insn));
|
|
|
1179
|
|
|
1180 start_sequence ();
|
|
|
1181 emit_insn (remat_pat);
|
|
|
1182 remat_insn = get_insns ();
|
|
|
1183 end_sequence ();
|
|
|
1184 if (recog_memoized (remat_insn) < 0)
|
|
|
1185 remat_insn = NULL;
|
|
|
1186 cand_sp_offset = cand_id->sp_offset;
|
|
|
1187 }
|
|
|
1188 *cand_id->operand_loc[cand->nop] = saved_op;
|
|
|
1189 lra_update_insn_regno_info (cand->insn);
|
|
|
1190 }
|
|
|
1191 }
|
|
|
1192
|
|
|
1193 bitmap_clear (&temp_bitmap);
|
|
|
1194 /* Update avail_cands (see analogous code for
|
|
|
1195 calculate_gen_cands). */
|
|
|
1196 for (iter = 0; iter < 2; iter++)
|
|
|
1197 for (reg = (iter == 0 ? id->regs : static_id->hard_regs);
|
|
|
1198 reg != NULL;
|
|
|
1199 reg = reg->next)
|
|
|
1200 if (reg->type != OP_IN
|
|
|
1201 || find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
|
|
|
1202 EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
|
|
|
1203 {
|
|
|
1204 cand = all_cands[cid];
|
|
|
1205
|
|
|
1206 /* Ignore the reload insn. */
|
|
|
1207 if (src_regno == cand->reload_regno
|
|
|
1208 && dst_regno == cand->regno)
|
|
|
1209 continue;
|
|
|
1210 if (cand->regno == reg->regno
|
|
|
1211 || reg_overlap_for_remat_p (reg, cand->insn))
|
|
|
1212 bitmap_set_bit (&temp_bitmap, cand->index);
|
|
|
1213 }
|
|
|
1214
|
|
|
1215 if (CALL_P (insn))
|
|
|
1216 EXECUTE_IF_SET_IN_BITMAP (avail_cands, 0, cid, bi)
|
|
|
1217 {
|
|
|
1218 cand = all_cands[cid];
|
|
|
1219
|
|
|
1220 if (call_used_input_regno_present_p (cand->insn))
|
|
|
1221 bitmap_set_bit (&temp_bitmap, cand->index);
|
|
|
1222 }
|
|
|
1223
|
|
|
1224 bitmap_and_compl_into (avail_cands, &temp_bitmap);
|
|
|
1225
|
|
|
1226 /* Now see whether a candidate is made active or available
|
|
|
1227 by this insn. */
|
|
|
1228 cand = insn_to_cand_activation[INSN_UID (insn)];
|
|
|
1229 if (cand)
|
|
|
1230 bitmap_set_bit (active_cands, cand->index);
|
|
|
1231
|
|
|
1232 cand = insn_to_cand[INSN_UID (insn)];
|
|
|
1233 if (cand != NULL)
|
|
|
1234 {
|
|
|
1235 bitmap_set_bit (avail_cands, cand->index);
|
|
|
1236 if (cand->reload_regno == -1)
|
|
|
1237 bitmap_set_bit (active_cands, cand->index);
|
|
|
1238 else
|
|
|
1239 bitmap_clear_bit (active_cands, cand->index);
|
|
|
1240 }
|
|
|
1241
|
|
|
1242 if (remat_insn != NULL)
|
|
|
1243 {
|
|
131
|
1244 poly_int64 sp_offset_change = cand_sp_offset - id->sp_offset;
|
|
|
1245 if (maybe_ne (sp_offset_change, 0))
|
|
111
|
1246 change_sp_offset (remat_insn, sp_offset_change);
|
|
|
1247 update_scratch_ops (remat_insn);
|
|
|
1248 lra_process_new_insns (insn, remat_insn, NULL,
|
|
|
1249 "Inserting rematerialization insn");
|
|
|
1250 lra_set_insn_deleted (insn);
|
|
|
1251 changed_p = true;
|
|
|
1252 continue;
|
|
|
1253 }
|
|
|
1254
|
|
|
1255 /* Update live hard regs: */
|
|
|
1256 for (reg = id->regs; reg != NULL; reg = reg->next)
|
|
|
1257 if (reg->type == OP_IN
|
|
|
1258 && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
|
|
|
1259 {
|
|
|
1260 if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
|
|
|
1261 continue;
|
|
|
1262 for (i = 0; i < nregs; i++)
|
|
|
1263 CLEAR_HARD_REG_BIT (live_hard_regs, hard_regno + i);
|
|
|
1264 }
|
|
|
1265 /* Process also hard regs (e.g. CC register) which are part
|
|
|
1266 of insn definition. */
|
|
|
1267 for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
|
|
|
1268 if (reg->type == OP_IN
|
|
|
1269 && find_regno_note (insn, REG_DEAD, reg->regno) != NULL)
|
|
|
1270 CLEAR_HARD_REG_BIT (live_hard_regs, reg->regno);
|
|
|
1271 /* Inputs have been processed, now process outputs. */
|
|
|
1272 for (reg = id->regs; reg != NULL; reg = reg->next)
|
|
|
1273 if (reg->type != OP_IN
|
|
|
1274 && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
|
|
|
1275 {
|
|
|
1276 if ((hard_regno = get_hard_regs (reg, nregs)) < 0)
|
|
|
1277 continue;
|
|
|
1278 for (i = 0; i < nregs; i++)
|
|
|
1279 SET_HARD_REG_BIT (live_hard_regs, hard_regno + i);
|
|
|
1280 }
|
|
|
1281 for (reg = static_id->hard_regs; reg != NULL; reg = reg->next)
|
|
|
1282 if (reg->type != OP_IN
|
|
|
1283 && find_regno_note (insn, REG_UNUSED, reg->regno) == NULL)
|
|
|
1284 SET_HARD_REG_BIT (live_hard_regs, reg->regno);
|
|
|
1285 }
|
|
|
1286 }
|
|
|
1287 return changed_p;
|
|
|
1288 }
|
|
|
1289
|
|
|
1290
|
|
|
1291
|
|
|
1292 /* Current number of rematerialization iteration. */
|
|
|
1293 int lra_rematerialization_iter;
|
|
|
1294
|
|
|
1295 /* Entry point of the rematerialization sub-pass. Return true if we
|
|
|
1296 did any rematerialization. */
|
|
|
1297 bool
|
|
|
1298 lra_remat (void)
|
|
|
1299 {
|
|
|
1300 basic_block bb;
|
|
|
1301 bool result;
|
|
|
1302 int max_regno = max_reg_num ();
|
|
|
1303
|
|
|
1304 if (! flag_lra_remat)
|
|
|
1305 return false;
|
|
|
1306 lra_rematerialization_iter++;
|
|
|
1307 if (lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES)
|
|
|
1308 return false;
|
|
|
1309 if (lra_dump_file != NULL)
|
|
|
1310 fprintf (lra_dump_file,
|
|
|
1311 "\n******** Rematerialization #%d: ********\n\n",
|
|
|
1312 lra_rematerialization_iter);
|
|
|
1313 timevar_push (TV_LRA_REMAT);
|
|
|
1314 insn_to_cand = XCNEWVEC (cand_t, get_max_uid ());
|
|
|
1315 insn_to_cand_activation = XCNEWVEC (cand_t, get_max_uid ());
|
|
|
1316 regno_cands = XCNEWVEC (cand_t, max_regno);
|
|
|
1317 all_cands.create (8000);
|
|
|
1318 call_used_regs_arr_len = 0;
|
|
|
1319 for (int i = 0; i < FIRST_PSEUDO_REGISTER; i++)
|
|
|
1320 if (call_used_regs[i])
|
|
|
1321 call_used_regs_arr[call_used_regs_arr_len++] = i;
|
|
|
1322 initiate_cand_table ();
|
|
|
1323 create_remat_bb_data ();
|
|
|
1324 bitmap_initialize (&temp_bitmap, ®_obstack);
|
|
|
1325 bitmap_initialize (&subreg_regs, ®_obstack);
|
|
|
1326 calculate_local_reg_remat_bb_data ();
|
|
|
1327 create_cands ();
|
|
|
1328 calculate_livein_cands ();
|
|
|
1329 calculate_gen_cands ();
|
|
|
1330 bitmap_initialize (&all_blocks, ®_obstack);
|
|
|
1331 FOR_ALL_BB_FN (bb, cfun)
|
|
|
1332 bitmap_set_bit (&all_blocks, bb->index);
|
|
|
1333 calculate_global_remat_bb_data ();
|
|
|
1334 dump_candidates_and_remat_bb_data ();
|
|
|
1335 result = do_remat ();
|
|
|
1336 all_cands.release ();
|
|
|
1337 bitmap_clear (&temp_bitmap);
|
|
|
1338 bitmap_clear (&subreg_regs);
|
|
|
1339 finish_remat_bb_data ();
|
|
|
1340 finish_cand_table ();
|
|
|
1341 bitmap_clear (&all_blocks);
|
|
|
1342 free (regno_cands);
|
|
|
1343 free (insn_to_cand);
|
|
|
1344 free (insn_to_cand_activation);
|
|
|
1345 timevar_pop (TV_LRA_REMAT);
|
|
|
1346 return result;
|
|
|
1347 }
|
