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