2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2007, 2008,
3 2009 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 3, 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 COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
30 #include "insn-config.h"
32 #include "basic-block.h"
36 #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
, const_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 remove_from_hard_reg_set (live
, GET_MODE (reg
), regno
);
175 /* Record in LIVE that register REG became live.
176 This is called via note_stores. */
179 reg_becomes_live (rtx reg
, const_rtx setter ATTRIBUTE_UNUSED
, void *live
)
183 if (GET_CODE (reg
) == SUBREG
)
184 reg
= SUBREG_REG (reg
);
190 if (regno
< FIRST_PSEUDO_REGISTER
)
191 add_to_hard_reg_set ((HARD_REG_SET
*) live
, GET_MODE (reg
), regno
);
194 /* Make sure if MODE_ENTRY is defined the MODE_EXIT is defined
196 #if defined (MODE_ENTRY) != defined (MODE_EXIT)
197 #error "Both MODE_ENTRY and MODE_EXIT must be defined"
200 #if defined (MODE_ENTRY) && defined (MODE_EXIT)
201 /* Split the fallthrough edge to the exit block, so that we can note
202 that there NORMAL_MODE is required. Return the new block if it's
203 inserted before the exit block. Otherwise return null. */
206 create_pre_exit (int n_entities
, int *entity_map
, const int *num_modes
)
210 basic_block pre_exit
;
212 /* The only non-call predecessor at this stage is a block with a
213 fallthrough edge; there can be at most one, but there could be
214 none at all, e.g. when exit is called. */
216 FOR_EACH_EDGE (eg
, ei
, EXIT_BLOCK_PTR
->preds
)
217 if (eg
->flags
& EDGE_FALLTHRU
)
219 basic_block src_bb
= eg
->src
;
220 rtx last_insn
, ret_reg
;
222 gcc_assert (!pre_exit
);
223 /* If this function returns a value at the end, we have to
224 insert the final mode switch before the return value copy
225 to its hard register. */
226 if (EDGE_COUNT (EXIT_BLOCK_PTR
->preds
) == 1
227 && NONJUMP_INSN_P ((last_insn
= BB_END (src_bb
)))
228 && GET_CODE (PATTERN (last_insn
)) == USE
229 && GET_CODE ((ret_reg
= XEXP (PATTERN (last_insn
), 0))) == REG
)
231 int ret_start
= REGNO (ret_reg
);
232 int nregs
= hard_regno_nregs
[ret_start
][GET_MODE (ret_reg
)];
233 int ret_end
= ret_start
+ nregs
;
235 int maybe_builtin_apply
= 0;
236 int forced_late_switch
= 0;
237 rtx before_return_copy
;
241 rtx return_copy
= PREV_INSN (last_insn
);
242 rtx return_copy_pat
, copy_reg
;
243 int copy_start
, copy_num
;
246 if (INSN_P (return_copy
))
248 /* When using SJLJ exceptions, the call to the
249 unregister function is inserted between the
250 clobber of the return value and the copy.
251 We do not want to split the block before this
252 or any other call; if we have not found the
253 copy yet, the copy must have been deleted. */
254 if (CALL_P (return_copy
))
259 return_copy_pat
= PATTERN (return_copy
);
260 switch (GET_CODE (return_copy_pat
))
263 /* Skip __builtin_apply pattern. */
264 if (GET_CODE (XEXP (return_copy_pat
, 0)) == REG
265 && (targetm
.calls
.function_value_regno_p
266 (REGNO (XEXP (return_copy_pat
, 0)))))
268 maybe_builtin_apply
= 1;
269 last_insn
= return_copy
;
275 /* Skip barrier insns. */
276 if (!MEM_VOLATILE_P (return_copy_pat
))
282 case UNSPEC_VOLATILE
:
283 last_insn
= return_copy
;
290 /* If the return register is not (in its entirety)
291 likely spilled, the return copy might be
292 partially or completely optimized away. */
293 return_copy_pat
= single_set (return_copy
);
294 if (!return_copy_pat
)
296 return_copy_pat
= PATTERN (return_copy
);
297 if (GET_CODE (return_copy_pat
) != CLOBBER
)
301 /* This might be (clobber (reg [<result>]))
302 when not optimizing. Then check if
303 the previous insn is the clobber for
304 the return register. */
305 copy_reg
= SET_DEST (return_copy_pat
);
306 if (GET_CODE (copy_reg
) == REG
307 && !HARD_REGISTER_NUM_P (REGNO (copy_reg
)))
309 if (INSN_P (PREV_INSN (return_copy
)))
311 return_copy
= PREV_INSN (return_copy
);
312 return_copy_pat
= PATTERN (return_copy
);
313 if (GET_CODE (return_copy_pat
) != CLOBBER
)
319 copy_reg
= SET_DEST (return_copy_pat
);
320 if (GET_CODE (copy_reg
) == REG
)
321 copy_start
= REGNO (copy_reg
);
322 else if (GET_CODE (copy_reg
) == SUBREG
323 && GET_CODE (SUBREG_REG (copy_reg
)) == REG
)
324 copy_start
= REGNO (SUBREG_REG (copy_reg
));
327 if (copy_start
>= FIRST_PSEUDO_REGISTER
)
330 = hard_regno_nregs
[copy_start
][GET_MODE (copy_reg
)];
332 /* If the return register is not likely spilled, - as is
333 the case for floating point on SH4 - then it might
334 be set by an arithmetic operation that needs a
335 different mode than the exit block. */
336 for (j
= n_entities
- 1; j
>= 0; j
--)
338 int e
= entity_map
[j
];
339 int mode
= MODE_NEEDED (e
, return_copy
);
341 if (mode
!= num_modes
[e
] && mode
!= MODE_EXIT (e
))
346 /* For the SH4, floating point loads depend on fpscr,
347 thus we might need to put the final mode switch
348 after the return value copy. That is still OK,
349 because a floating point return value does not
350 conflict with address reloads. */
351 if (copy_start
>= ret_start
352 && copy_start
+ copy_num
<= ret_end
353 && OBJECT_P (SET_SRC (return_copy_pat
)))
354 forced_late_switch
= 1;
358 if (copy_start
>= ret_start
359 && copy_start
+ copy_num
<= ret_end
)
361 else if (!maybe_builtin_apply
362 || !targetm
.calls
.function_value_regno_p
365 last_insn
= return_copy
;
367 /* ??? Exception handling can lead to the return value
368 copy being already separated from the return value use,
370 Similarly, conditionally returning without a value,
371 and conditionally using builtin_return can lead to an
373 if (return_copy
== BB_HEAD (src_bb
))
378 last_insn
= return_copy
;
382 /* If we didn't see a full return value copy, verify that there
383 is a plausible reason for this. If some, but not all of the
384 return register is likely spilled, we can expect that there
385 is a copy for the likely spilled part. */
387 || forced_late_switch
389 || !(CLASS_LIKELY_SPILLED_P
390 (REGNO_REG_CLASS (ret_start
)))
392 != hard_regno_nregs
[ret_start
][GET_MODE (ret_reg
)])
393 /* For multi-hard-register floating point
394 values, sometimes the likely-spilled part
395 is ordinarily copied first, then the other
396 part is set with an arithmetic operation.
397 This doesn't actually cause reload
398 failures, so let it pass. */
399 || (GET_MODE_CLASS (GET_MODE (ret_reg
)) != MODE_INT
402 if (INSN_P (last_insn
))
405 = emit_note_before (NOTE_INSN_DELETED
, last_insn
);
406 /* Instructions preceding LAST_INSN in the same block might
407 require a different mode than MODE_EXIT, so if we might
408 have such instructions, keep them in a separate block
410 if (last_insn
!= BB_HEAD (src_bb
))
411 src_bb
= split_block (src_bb
,
412 PREV_INSN (before_return_copy
))->dest
;
415 before_return_copy
= last_insn
;
416 pre_exit
= split_block (src_bb
, before_return_copy
)->src
;
420 pre_exit
= split_edge (eg
);
428 /* Find all insns that need a particular mode setting, and insert the
429 necessary mode switches. Return true if we did work. */
432 optimize_mode_switching (void)
439 struct edge_list
*edge_list
;
440 static const int num_modes
[] = NUM_MODES_FOR_MODE_SWITCHING
;
441 #define N_ENTITIES ARRAY_SIZE (num_modes)
442 int entity_map
[N_ENTITIES
];
443 struct bb_info
*bb_info
[N_ENTITIES
];
446 int max_num_modes
= 0;
448 basic_block post_entry ATTRIBUTE_UNUSED
, pre_exit ATTRIBUTE_UNUSED
;
450 for (e
= N_ENTITIES
- 1, n_entities
= 0; e
>= 0; e
--)
451 if (OPTIMIZE_MODE_SWITCHING (e
))
453 int entry_exit_extra
= 0;
455 /* Create the list of segments within each basic block.
456 If NORMAL_MODE is defined, allow for two extra
457 blocks split from the entry and exit block. */
458 #if defined (MODE_ENTRY) && defined (MODE_EXIT)
459 entry_exit_extra
= 3;
462 = XCNEWVEC (struct bb_info
, last_basic_block
+ entry_exit_extra
);
463 entity_map
[n_entities
++] = e
;
464 if (num_modes
[e
] > max_num_modes
)
465 max_num_modes
= num_modes
[e
];
471 #if defined (MODE_ENTRY) && defined (MODE_EXIT)
472 /* Split the edge from the entry block, so that we can note that
473 there NORMAL_MODE is supplied. */
474 post_entry
= split_edge (single_succ_edge (ENTRY_BLOCK_PTR
));
475 pre_exit
= create_pre_exit (n_entities
, entity_map
, num_modes
);
480 /* Create the bitmap vectors. */
482 antic
= sbitmap_vector_alloc (last_basic_block
, n_entities
);
483 transp
= sbitmap_vector_alloc (last_basic_block
, n_entities
);
484 comp
= sbitmap_vector_alloc (last_basic_block
, n_entities
);
486 sbitmap_vector_ones (transp
, last_basic_block
);
488 for (j
= n_entities
- 1; j
>= 0; j
--)
490 int e
= entity_map
[j
];
491 int no_mode
= num_modes
[e
];
492 struct bb_info
*info
= bb_info
[j
];
494 /* Determine what the first use (if any) need for a mode of entity E is.
495 This will be the mode that is anticipatable for this block.
496 Also compute the initial transparency settings. */
500 int last_mode
= no_mode
;
501 HARD_REG_SET live_now
;
503 REG_SET_TO_HARD_REG_SET (live_now
, df_get_live_in (bb
));
505 /* Pretend the mode is clobbered across abnormal edges. */
509 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
510 if (e
->flags
& EDGE_COMPLEX
)
514 ptr
= new_seginfo (no_mode
, BB_HEAD (bb
), bb
->index
, live_now
);
515 add_seginfo (info
+ bb
->index
, ptr
);
516 RESET_BIT (transp
[bb
->index
], j
);
520 for (insn
= BB_HEAD (bb
);
521 insn
!= NULL
&& insn
!= NEXT_INSN (BB_END (bb
));
522 insn
= NEXT_INSN (insn
))
526 int mode
= MODE_NEEDED (e
, insn
);
529 if (mode
!= no_mode
&& mode
!= last_mode
)
532 ptr
= new_seginfo (mode
, insn
, bb
->index
, live_now
);
533 add_seginfo (info
+ bb
->index
, ptr
);
534 RESET_BIT (transp
[bb
->index
], j
);
537 last_mode
= MODE_AFTER (last_mode
, insn
);
539 /* Update LIVE_NOW. */
540 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
541 if (REG_NOTE_KIND (link
) == REG_DEAD
)
542 reg_dies (XEXP (link
, 0), &live_now
);
544 note_stores (PATTERN (insn
), reg_becomes_live
, &live_now
);
545 for (link
= REG_NOTES (insn
); link
; link
= XEXP (link
, 1))
546 if (REG_NOTE_KIND (link
) == REG_UNUSED
)
547 reg_dies (XEXP (link
, 0), &live_now
);
551 info
[bb
->index
].computing
= last_mode
;
552 /* Check for blocks without ANY mode requirements. */
553 if (last_mode
== no_mode
)
555 ptr
= new_seginfo (no_mode
, BB_END (bb
), bb
->index
, live_now
);
556 add_seginfo (info
+ bb
->index
, ptr
);
559 #if defined (MODE_ENTRY) && defined (MODE_EXIT)
561 int mode
= MODE_ENTRY (e
);
567 /* By always making this nontransparent, we save
568 an extra check in make_preds_opaque. We also
569 need this to avoid confusing pre_edge_lcm when
570 antic is cleared but transp and comp are set. */
571 RESET_BIT (transp
[bb
->index
], j
);
573 /* Insert a fake computing definition of MODE into entry
574 blocks which compute no mode. This represents the mode on
576 info
[bb
->index
].computing
= mode
;
579 info
[pre_exit
->index
].seginfo
->mode
= MODE_EXIT (e
);
582 #endif /* NORMAL_MODE */
585 kill
= sbitmap_vector_alloc (last_basic_block
, n_entities
);
586 for (i
= 0; i
< max_num_modes
; i
++)
588 int current_mode
[N_ENTITIES
];
592 /* Set the anticipatable and computing arrays. */
593 sbitmap_vector_zero (antic
, last_basic_block
);
594 sbitmap_vector_zero (comp
, last_basic_block
);
595 for (j
= n_entities
- 1; j
>= 0; j
--)
597 int m
= current_mode
[j
] = MODE_PRIORITY_TO_MODE (entity_map
[j
], i
);
598 struct bb_info
*info
= bb_info
[j
];
602 if (info
[bb
->index
].seginfo
->mode
== m
)
603 SET_BIT (antic
[bb
->index
], j
);
605 if (info
[bb
->index
].computing
== m
)
606 SET_BIT (comp
[bb
->index
], j
);
610 /* Calculate the optimal locations for the
611 placement mode switches to modes with priority I. */
614 sbitmap_not (kill
[bb
->index
], transp
[bb
->index
]);
615 edge_list
= pre_edge_lcm (n_entities
, transp
, comp
, antic
,
616 kill
, &insert
, &del
);
618 for (j
= n_entities
- 1; j
>= 0; j
--)
620 /* Insert all mode sets that have been inserted by lcm. */
621 int no_mode
= num_modes
[entity_map
[j
]];
623 /* Wherever we have moved a mode setting upwards in the flow graph,
624 the blocks between the new setting site and the now redundant
625 computation ceases to be transparent for any lower-priority
626 mode of the same entity. First set the aux field of each
627 insertion site edge non-transparent, then propagate the new
628 non-transparency from the redundant computation upwards till
629 we hit an insertion site or an already non-transparent block. */
630 for (e
= NUM_EDGES (edge_list
) - 1; e
>= 0; e
--)
632 edge eg
= INDEX_EDGE (edge_list
, e
);
635 HARD_REG_SET live_at_edge
;
640 if (! TEST_BIT (insert
[e
], j
))
645 mode
= current_mode
[j
];
648 REG_SET_TO_HARD_REG_SET (live_at_edge
, df_get_live_out (src_bb
));
651 EMIT_MODE_SET (entity_map
[j
], mode
, live_at_edge
);
652 mode_set
= get_insns ();
655 /* Do not bother to insert empty sequence. */
656 if (mode_set
== NULL_RTX
)
659 /* We should not get an abnormal edge here. */
660 gcc_assert (! (eg
->flags
& EDGE_ABNORMAL
));
663 insert_insn_on_edge (mode_set
, eg
);
666 FOR_EACH_BB_REVERSE (bb
)
667 if (TEST_BIT (del
[bb
->index
], j
))
669 make_preds_opaque (bb
, j
);
670 /* Cancel the 'deleted' mode set. */
671 bb_info
[j
][bb
->index
].seginfo
->mode
= no_mode
;
675 sbitmap_vector_free (del
);
676 sbitmap_vector_free (insert
);
677 clear_aux_for_edges ();
678 free_edge_list (edge_list
);
681 /* Now output the remaining mode sets in all the segments. */
682 for (j
= n_entities
- 1; j
>= 0; j
--)
684 int no_mode
= num_modes
[entity_map
[j
]];
686 FOR_EACH_BB_REVERSE (bb
)
688 struct seginfo
*ptr
, *next
;
689 for (ptr
= bb_info
[j
][bb
->index
].seginfo
; ptr
; ptr
= next
)
692 if (ptr
->mode
!= no_mode
)
697 EMIT_MODE_SET (entity_map
[j
], ptr
->mode
, ptr
->regs_live
);
698 mode_set
= get_insns ();
701 /* Insert MODE_SET only if it is nonempty. */
702 if (mode_set
!= NULL_RTX
)
705 if (NOTE_INSN_BASIC_BLOCK_P (ptr
->insn_ptr
))
706 emit_insn_after (mode_set
, ptr
->insn_ptr
);
708 emit_insn_before (mode_set
, ptr
->insn_ptr
);
719 /* Finished. Free up all the things we've allocated. */
720 sbitmap_vector_free (kill
);
721 sbitmap_vector_free (antic
);
722 sbitmap_vector_free (transp
);
723 sbitmap_vector_free (comp
);
726 commit_edge_insertions ();
728 #if defined (MODE_ENTRY) && defined (MODE_EXIT)
729 cleanup_cfg (CLEANUP_NO_INSN_DEL
);
731 if (!need_commit
&& !emited
)
738 #endif /* OPTIMIZE_MODE_SWITCHING */
741 gate_mode_switching (void)
743 #ifdef OPTIMIZE_MODE_SWITCHING
751 rest_of_handle_mode_switching (void)
753 #ifdef OPTIMIZE_MODE_SWITCHING
754 optimize_mode_switching ();
755 #endif /* OPTIMIZE_MODE_SWITCHING */
760 struct rtl_opt_pass pass_mode_switching
=
764 "mode_sw", /* name */
765 gate_mode_switching
, /* gate */
766 rest_of_handle_mode_switching
, /* execute */
769 0, /* static_pass_number */
770 TV_MODE_SWITCH
, /* tv_id */
771 0, /* properties_required */
772 0, /* properties_provided */
773 0, /* properties_destroyed */
774 0, /* todo_flags_start */
775 TODO_df_finish
| TODO_verify_rtl_sharing
|
776 TODO_dump_func
/* todo_flags_finish */