2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
3 Free Software Foundation, Inc.
5 This file is part of GCC.
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 2, or (at your option) any later
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
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
24 #include "coretypes.h"
28 #include "hard-reg-set.h"
31 #include "insn-config.h"
33 #include "basic-block.h"
37 #include "tree-pass.h"
40 /* We want target macros for the mode switching code to be able to refer
41 to instruction attribute values. */
42 #include "insn-attr.h"
44 #ifdef OPTIMIZE_MODE_SWITCHING
46 /* The algorithm for setting the modes consists of scanning the insn list
47 and finding all the insns which require a specific mode. Each insn gets
48 a unique struct seginfo element. These structures are inserted into a list
49 for each basic block. For each entity, there is an array of bb_info over
50 the flow graph basic blocks (local var 'bb_info'), and contains a list
51 of all insns within that basic block, in the order they are encountered.
53 For each entity, any basic block WITHOUT any insns requiring a specific
54 mode are given a single entry, without a mode. (Each basic block
55 in the flow graph must have at least one entry in the segment table.)
57 The LCM algorithm is then run over the flow graph to determine where to
58 place the sets to the highest-priority value in respect of first the first
59 insn in any one block. Any adjustments required to the transparency
60 vectors are made, then the next iteration starts for the next-lower
61 priority mode, till for each entity all modes are exhausted.
63 More details are located in the code for optimize_mode_switching(). */
65 /* This structure contains the information for each insn which requires
66 either single or double mode to be set.
67 MODE is the mode this insn must be executed in.
68 INSN_PTR is the insn to be executed (may be the note that marks the
69 beginning of a basic block).
70 BBNUM is the flow graph basic block this insn occurs in.
71 NEXT is the next insn in the same basic block. */
78 HARD_REG_SET regs_live;
83 struct seginfo *seginfo;
87 /* These bitmaps are used for the LCM algorithm. */
89 static sbitmap *antic;
90 static sbitmap *transp;
93 static struct seginfo * new_seginfo (int, rtx, int, HARD_REG_SET);
94 static void add_seginfo (struct bb_info *, struct seginfo *);
95 static void reg_dies (rtx, HARD_REG_SET);
96 static void reg_becomes_live (rtx, rtx, void *);
97 static void make_preds_opaque (basic_block, int);
100 /* This function will allocate a new BBINFO structure, initialized
101 with the MODE, INSN, and basic block BB parameters. */
103 static struct seginfo *
104 new_seginfo (int mode, rtx insn, int bb, HARD_REG_SET regs_live)
107 ptr = XNEW (struct seginfo);
109 ptr->insn_ptr = insn;
112 COPY_HARD_REG_SET (ptr->regs_live, regs_live);
116 /* Add a seginfo element to the end of a list.
117 HEAD is a pointer to the list beginning.
118 INFO is the structure to be linked in. */
121 add_seginfo (struct bb_info *head, struct seginfo *info)
125 if (head->seginfo == NULL)
126 head->seginfo = info;
130 while (ptr->next != NULL)
136 /* Make all predecessors of basic block B opaque, recursively, till we hit
137 some that are already non-transparent, or an edge where aux is set; that
138 denotes that a mode set is to be done on that edge.
139 J is the bit number in the bitmaps that corresponds to the entity that
140 we are currently handling mode-switching for. */
143 make_preds_opaque (basic_block b, int j)
148 FOR_EACH_EDGE (e, ei, b->preds)
150 basic_block pb = e->src;
152 if (e->aux || ! TEST_BIT (transp[pb->index], j))
155 RESET_BIT (transp[pb->index], j);
156 make_preds_opaque (pb, j);
160 /* Record in LIVE that register REG died. */
163 reg_dies (rtx reg, HARD_REG_SET live)
171 if (regno < FIRST_PSEUDO_REGISTER)
172 for (nregs = hard_regno_nregs[regno][GET_MODE (reg)] - 1; nregs >= 0;
174 CLEAR_HARD_REG_BIT (live, regno + nregs);
177 /* Record in LIVE that register REG became live.
178 This is called via note_stores. */
181 reg_becomes_live (rtx reg, rtx setter ATTRIBUTE_UNUSED, void *live)
185 if (GET_CODE (reg) == SUBREG)
186 reg = SUBREG_REG (reg);
192 if (regno < FIRST_PSEUDO_REGISTER)
193 for (nregs = hard_regno_nregs[regno][GET_MODE (reg)] - 1; nregs >= 0;
195 SET_HARD_REG_BIT (* (HARD_REG_SET *) live, regno + nregs);
198 /* Make sure if MODE_ENTRY is defined the MODE_EXIT is defined
200 #if defined (MODE_ENTRY) != defined (MODE_EXIT)
201 #error "Both MODE_ENTRY and MODE_EXIT must be defined"
204 #if defined (MODE_ENTRY) && defined (MODE_EXIT)
205 /* Split the fallthrough edge to the exit block, so that we can note
206 that there NORMAL_MODE is required. Return the new block if it's
207 inserted before the exit block. Otherwise return null. */
210 create_pre_exit (int n_entities, int *entity_map, const int *num_modes)
214 basic_block pre_exit;
216 /* The only non-call predecessor at this stage is a block with a
217 fallthrough edge; there can be at most one, but there could be
218 none at all, e.g. when exit is called. */
220 FOR_EACH_EDGE (eg, ei, EXIT_BLOCK_PTR->preds)
221 if (eg->flags & EDGE_FALLTHRU)
223 basic_block src_bb = eg->src;
224 regset live_at_end = src_bb->il.rtl->global_live_at_end;
225 rtx last_insn, ret_reg;
227 gcc_assert (!pre_exit);
228 /* If this function returns a value at the end, we have to
229 insert the final mode switch before the return value copy
230 to its hard register. */
231 if (EDGE_COUNT (EXIT_BLOCK_PTR->preds) == 1
232 && NONJUMP_INSN_P ((last_insn = BB_END (src_bb)))
233 && GET_CODE (PATTERN (last_insn)) == USE
234 && GET_CODE ((ret_reg = XEXP (PATTERN (last_insn), 0))) == REG)
236 int ret_start = REGNO (ret_reg);
237 int nregs = hard_regno_nregs[ret_start][GET_MODE (ret_reg)];
238 int ret_end = ret_start + nregs;
240 int maybe_builtin_apply = 0;
241 int forced_late_switch = 0;
242 rtx before_return_copy;
246 rtx return_copy = PREV_INSN (last_insn);
247 rtx return_copy_pat, copy_reg;
248 int copy_start, copy_num;
251 if (INSN_P (return_copy))
253 if (GET_CODE (PATTERN (return_copy)) == USE
254 && GET_CODE (XEXP (PATTERN (return_copy), 0)) == REG
255 && (FUNCTION_VALUE_REGNO_P
256 (REGNO (XEXP (PATTERN (return_copy), 0)))))
258 maybe_builtin_apply = 1;
259 last_insn = return_copy;
262 if (GET_CODE (PATTERN (return_copy)) == ASM_INPUT
263 && strcmp (XSTR (PATTERN (return_copy), 0), "") == 0)
265 last_insn = return_copy;
268 /* If the return register is not (in its entirety)
269 likely spilled, the return copy might be
270 partially or completely optimized away. */
271 return_copy_pat = single_set (return_copy);
272 if (!return_copy_pat)
274 return_copy_pat = PATTERN (return_copy);
275 if (GET_CODE (return_copy_pat) != CLOBBER)
278 copy_reg = SET_DEST (return_copy_pat);
279 if (GET_CODE (copy_reg) == REG)
280 copy_start = REGNO (copy_reg);
281 else if (GET_CODE (copy_reg) == SUBREG
282 && GET_CODE (SUBREG_REG (copy_reg)) == REG)
283 copy_start = REGNO (SUBREG_REG (copy_reg));
286 if (copy_start >= FIRST_PSEUDO_REGISTER)
289 = hard_regno_nregs[copy_start][GET_MODE (copy_reg)];
291 /* If the return register is not likely spilled, - as is
292 the case for floating point on SH4 - then it might
293 be set by an arithmetic operation that needs a
294 different mode than the exit block. */
295 for (j = n_entities - 1; j >= 0; j--)
297 int e = entity_map[j];
298 int mode = MODE_NEEDED (e, return_copy);
300 if (mode != num_modes[e] && mode != MODE_EXIT (e))
305 /* For the SH4, floating point loads depend on fpscr,
306 thus we might need to put the final mode switch
307 after the return value copy. That is still OK,
308 because a floating point return value does not
309 conflict with address reloads. */
310 if (copy_start >= ret_start
311 && copy_start + copy_num <= ret_end
312 && OBJECT_P (SET_SRC (return_copy_pat)))
313 forced_late_switch = 1;
317 if (copy_start >= ret_start
318 && copy_start + copy_num <= ret_end)
320 else if (!maybe_builtin_apply
321 || !FUNCTION_VALUE_REGNO_P (copy_start))
323 last_insn = return_copy;
325 /* ??? Exception handling can lead to the return value
326 copy being already separated from the return value use,
328 Similarly, conditionally returning without a value,
329 and conditionally using builtin_return can lead to an
331 if (return_copy == BB_HEAD (src_bb))
336 last_insn = return_copy;
340 /* If we didn't see a full return value copy, verify that there
341 is a plausible reason for this. If some, but not all of the
342 return register is likely spilled, we can expect that there
343 is a copy for the likely spilled part. */
345 || forced_late_switch
347 || !(CLASS_LIKELY_SPILLED_P
348 (REGNO_REG_CLASS (ret_start)))
350 != hard_regno_nregs[ret_start][GET_MODE (ret_reg)])
351 /* For multi-hard-register floating point
352 values, sometimes the likely-spilled part
353 is ordinarily copied first, then the other
354 part is set with an arithmetic operation.
355 This doesn't actually cause reload
356 failures, so let it pass. */
357 || (GET_MODE_CLASS (GET_MODE (ret_reg)) != MODE_INT
360 if (INSN_P (last_insn))
363 = emit_note_before (NOTE_INSN_DELETED, last_insn);
364 /* Instructions preceding LAST_INSN in the same block might
365 require a different mode than MODE_EXIT, so if we might
366 have such instructions, keep them in a separate block
368 if (last_insn != BB_HEAD (src_bb))
369 src_bb = split_block (src_bb,
370 PREV_INSN (before_return_copy))->dest;
373 before_return_copy = last_insn;
374 pre_exit = split_block (src_bb, before_return_copy)->src;
378 pre_exit = split_edge (eg);
379 COPY_REG_SET (pre_exit->il.rtl->global_live_at_start, live_at_end);
380 COPY_REG_SET (pre_exit->il.rtl->global_live_at_end, live_at_end);
388 /* Find all insns that need a particular mode setting, and insert the
389 necessary mode switches. Return true if we did work. */
392 optimize_mode_switching (void)
399 struct edge_list *edge_list;
400 static const int num_modes[] = NUM_MODES_FOR_MODE_SWITCHING;
401 #define N_ENTITIES ARRAY_SIZE (num_modes)
402 int entity_map[N_ENTITIES];
403 struct bb_info *bb_info[N_ENTITIES];
406 int max_num_modes = 0;
408 basic_block post_entry ATTRIBUTE_UNUSED, pre_exit ATTRIBUTE_UNUSED;
412 for (e = N_ENTITIES - 1, n_entities = 0; e >= 0; e--)
413 if (OPTIMIZE_MODE_SWITCHING (e))
415 int entry_exit_extra = 0;
417 /* Create the list of segments within each basic block.
418 If NORMAL_MODE is defined, allow for two extra
419 blocks split from the entry and exit block. */
420 #if defined (MODE_ENTRY) && defined (MODE_EXIT)
421 entry_exit_extra = 3;
424 = XCNEWVEC (struct bb_info, last_basic_block + entry_exit_extra);
425 entity_map[n_entities++] = e;
426 if (num_modes[e] > max_num_modes)
427 max_num_modes = num_modes[e];
433 #if defined (MODE_ENTRY) && defined (MODE_EXIT)
434 /* Split the edge from the entry block, so that we can note that
435 there NORMAL_MODE is supplied. */
436 post_entry = split_edge (single_succ_edge (ENTRY_BLOCK_PTR));
437 pre_exit = create_pre_exit (n_entities, entity_map, num_modes);
440 /* Create the bitmap vectors. */
442 antic = sbitmap_vector_alloc (last_basic_block, n_entities);
443 transp = sbitmap_vector_alloc (last_basic_block, n_entities);
444 comp = sbitmap_vector_alloc (last_basic_block, n_entities);
446 sbitmap_vector_ones (transp, last_basic_block);
448 for (j = n_entities - 1; j >= 0; j--)
450 int e = entity_map[j];
451 int no_mode = num_modes[e];
452 struct bb_info *info = bb_info[j];
454 /* Determine what the first use (if any) need for a mode of entity E is.
455 This will be the mode that is anticipatable for this block.
456 Also compute the initial transparency settings. */
460 int last_mode = no_mode;
461 HARD_REG_SET live_now;
463 REG_SET_TO_HARD_REG_SET (live_now,
464 bb->il.rtl->global_live_at_start);
466 /* Pretend the mode is clobbered across abnormal edges. */
470 FOR_EACH_EDGE (e, ei, bb->preds)
471 if (e->flags & EDGE_COMPLEX)
475 ptr = new_seginfo (no_mode, BB_HEAD (bb), bb->index, live_now);
476 add_seginfo (info + bb->index, ptr);
477 RESET_BIT (transp[bb->index], j);
481 for (insn = BB_HEAD (bb);
482 insn != NULL && insn != NEXT_INSN (BB_END (bb));
483 insn = NEXT_INSN (insn))
487 int mode = MODE_NEEDED (e, insn);
490 if (mode != no_mode && mode != last_mode)
493 ptr = new_seginfo (mode, insn, bb->index, live_now);
494 add_seginfo (info + bb->index, ptr);
495 RESET_BIT (transp[bb->index], j);
498 last_mode = MODE_AFTER (last_mode, insn);
500 /* Update LIVE_NOW. */
501 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
502 if (REG_NOTE_KIND (link) == REG_DEAD)
503 reg_dies (XEXP (link, 0), live_now);
505 note_stores (PATTERN (insn), reg_becomes_live, &live_now);
506 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
507 if (REG_NOTE_KIND (link) == REG_UNUSED)
508 reg_dies (XEXP (link, 0), live_now);
512 info[bb->index].computing = last_mode;
513 /* Check for blocks without ANY mode requirements. */
514 if (last_mode == no_mode)
516 ptr = new_seginfo (no_mode, BB_END (bb), bb->index, live_now);
517 add_seginfo (info + bb->index, ptr);
520 #if defined (MODE_ENTRY) && defined (MODE_EXIT)
522 int mode = MODE_ENTRY (e);
528 /* By always making this nontransparent, we save
529 an extra check in make_preds_opaque. We also
530 need this to avoid confusing pre_edge_lcm when
531 antic is cleared but transp and comp are set. */
532 RESET_BIT (transp[bb->index], j);
534 /* Insert a fake computing definition of MODE into entry
535 blocks which compute no mode. This represents the mode on
537 info[bb->index].computing = mode;
540 info[pre_exit->index].seginfo->mode = MODE_EXIT (e);
543 #endif /* NORMAL_MODE */
546 kill = sbitmap_vector_alloc (last_basic_block, n_entities);
547 for (i = 0; i < max_num_modes; i++)
549 int current_mode[N_ENTITIES];
553 /* Set the anticipatable and computing arrays. */
554 sbitmap_vector_zero (antic, last_basic_block);
555 sbitmap_vector_zero (comp, last_basic_block);
556 for (j = n_entities - 1; j >= 0; j--)
558 int m = current_mode[j] = MODE_PRIORITY_TO_MODE (entity_map[j], i);
559 struct bb_info *info = bb_info[j];
563 if (info[bb->index].seginfo->mode == m)
564 SET_BIT (antic[bb->index], j);
566 if (info[bb->index].computing == m)
567 SET_BIT (comp[bb->index], j);
571 /* Calculate the optimal locations for the
572 placement mode switches to modes with priority I. */
575 sbitmap_not (kill[bb->index], transp[bb->index]);
576 edge_list = pre_edge_lcm (n_entities, transp, comp, antic,
577 kill, &insert, &delete);
579 for (j = n_entities - 1; j >= 0; j--)
581 /* Insert all mode sets that have been inserted by lcm. */
582 int no_mode = num_modes[entity_map[j]];
584 /* Wherever we have moved a mode setting upwards in the flow graph,
585 the blocks between the new setting site and the now redundant
586 computation ceases to be transparent for any lower-priority
587 mode of the same entity. First set the aux field of each
588 insertion site edge non-transparent, then propagate the new
589 non-transparency from the redundant computation upwards till
590 we hit an insertion site or an already non-transparent block. */
591 for (e = NUM_EDGES (edge_list) - 1; e >= 0; e--)
593 edge eg = INDEX_EDGE (edge_list, e);
596 HARD_REG_SET live_at_edge;
601 if (! TEST_BIT (insert[e], j))
606 mode = current_mode[j];
609 REG_SET_TO_HARD_REG_SET (live_at_edge,
610 src_bb->il.rtl->global_live_at_end);
613 EMIT_MODE_SET (entity_map[j], mode, live_at_edge);
614 mode_set = get_insns ();
617 /* Do not bother to insert empty sequence. */
618 if (mode_set == NULL_RTX)
621 /* We should not get an abnormal edge here. */
622 gcc_assert (! (eg->flags & EDGE_ABNORMAL));
625 insert_insn_on_edge (mode_set, eg);
628 FOR_EACH_BB_REVERSE (bb)
629 if (TEST_BIT (delete[bb->index], j))
631 make_preds_opaque (bb, j);
632 /* Cancel the 'deleted' mode set. */
633 bb_info[j][bb->index].seginfo->mode = no_mode;
637 sbitmap_vector_free (delete);
638 sbitmap_vector_free (insert);
639 clear_aux_for_edges ();
640 free_edge_list (edge_list);
643 /* Now output the remaining mode sets in all the segments. */
644 for (j = n_entities - 1; j >= 0; j--)
646 int no_mode = num_modes[entity_map[j]];
648 FOR_EACH_BB_REVERSE (bb)
650 struct seginfo *ptr, *next;
651 for (ptr = bb_info[j][bb->index].seginfo; ptr; ptr = next)
654 if (ptr->mode != no_mode)
659 EMIT_MODE_SET (entity_map[j], ptr->mode, ptr->regs_live);
660 mode_set = get_insns ();
663 /* Insert MODE_SET only if it is nonempty. */
664 if (mode_set != NULL_RTX)
667 if (NOTE_P (ptr->insn_ptr)
668 && (NOTE_LINE_NUMBER (ptr->insn_ptr)
669 == NOTE_INSN_BASIC_BLOCK))
670 emit_insn_after (mode_set, ptr->insn_ptr);
672 emit_insn_before (mode_set, ptr->insn_ptr);
683 /* Finished. Free up all the things we've allocated. */
685 sbitmap_vector_free (kill);
686 sbitmap_vector_free (antic);
687 sbitmap_vector_free (transp);
688 sbitmap_vector_free (comp);
691 commit_edge_insertions ();
693 #if defined (MODE_ENTRY) && defined (MODE_EXIT)
694 cleanup_cfg (CLEANUP_NO_INSN_DEL);
696 if (!need_commit && !emited)
700 max_regno = max_reg_num ();
701 allocate_reg_info (max_regno, FALSE, FALSE);
702 update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
703 (PROP_DEATH_NOTES | PROP_KILL_DEAD_CODE
704 | PROP_SCAN_DEAD_CODE));
709 #endif /* OPTIMIZE_MODE_SWITCHING */
712 gate_mode_switching (void)
714 #ifdef OPTIMIZE_MODE_SWITCHING
722 rest_of_handle_mode_switching (void)
724 #ifdef OPTIMIZE_MODE_SWITCHING
726 optimize_mode_switching ();
728 #endif /* OPTIMIZE_MODE_SWITCHING */
733 struct tree_opt_pass pass_mode_switching =
735 "mode-sw", /* name */
736 gate_mode_switching, /* gate */
737 rest_of_handle_mode_switching, /* execute */
740 0, /* static_pass_number */
741 TV_MODE_SWITCH, /* tv_id */
742 0, /* properties_required */
743 0, /* properties_provided */
744 0, /* properties_destroyed */
745 0, /* todo_flags_start */
746 TODO_dump_func, /* todo_flags_finish */