This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: RFA: patch cheking dangerous insns in sched-ebb.c
Richard Henderson wrote:
> On Fri, Feb 21, 2003 at 10:57:59AM -0500, Vladimir N. Makarov wrote:
> > It can't. I add dependence not for all insns but for insns which can
> > cause an exception (they are TRAP_RISKY, IRISKY, PRISKY_CANDIDATE and
> > some PFREE_CANDIDATEs). TRAP_FREE, IFREE and some PFREE_CANDIDATEs can
> > be moved through the jump, in order words speculatively (of course if
> > they do not kill values on split edges in haifa scheduler sense. That
> > was implemented in sched-ebb).
>
> That is not the search loop I'm concerned about. Lets
> look at the code again:
>
> + for (insn = head; insn != NEXT_INSN (tail); insn = NEXT_INSN (insn))
> + if (GET_CODE (insn) == JUMP_INSN)
> + last_jump = insn;
> + else if (INSN_P (insn) && last_jump != NULL_RTX)
> + {
> + class = haifa_classify_insn (insn);
> + if (class == TRAP_RISKY || class == IRISKY
> + || class == PRISKY_CANDIDATE || class == PFREE_CANDIDATE)
>
> This loop iterates forward over the insns in the block, adding
> dependencies for those that are risky. This is indeed necessary.
>
> + for (prev = last_jump;
> + prev != PREV_INSN (head);
> + prev = PREV_INSN (prev))
> + /* ??? We could implement better checking PRISKY_CANDIATEs
> + analogous to sched-rgn.c. */
> + if (GET_CODE (prev) == JUMP_INSN
>
> This loop iterates backward over previous insns in the superblock.
> You only add dependencies for jump insns, but you still search the
> entire superblock.
>
Here is the code:
+ class = haifa_classify_insn (insn);
+ if (class == TRAP_RISKY || class == IRISKY
+ || class == PRISKY_CANDIDATE || class == PFREE_CANDIDATE)
+ for (prev = last_jump;
+ prev != PREV_INSN (head);
+ prev = PREV_INSN (prev))
+ /* ??? We could implement better checking PRISKY_CANDIATEs
+ analogous to sched-rgn.c. */
+ if (GET_CODE (prev) == JUMP_INSN
+ && (class != PFREE_CANDIDATE
+ || (flag_schedule_speculative_load
+ && block_has_similiar_load (BLOCK_FOR_INSN (prev),
+ insn))))
+ {
+ /* We can not change the mode of the backward
+ dependency because REG_DEP_ANTI has the lowest
+ rank. */
+ if (add_dependence (insn, prev, REG_DEP_ANTI))
+ add_forward_dependence (prev, insn, REG_DEP_ANTI);
+ break;
+ }
The function may add at most one dependency for insn to a jump (because the
nested loop contains break when the dependency has been found). The loop is
really not necessary for all insn except PFREE_CANDIDATE.
For PFREE_CANDIDATE, the function may add dependency on any preceding jump
(not only the last one). If the immediately preceding block in the EBB has
no analogous load (it is needed to prove that insn is exception free mainly
for loads of variables on the stack), it can still be in other preceding
blocks. If we look only at the immediately preceding block, we could lost
opportunity to move load speculatively. In some way (generated code
quality), this is an *improvement* in comparison with sched-rgn.c which
checked only the target block.
Actually I also don't like potentially n**2 algorithm (but that is the
nature of such tasks. Keith Cooper in his lectures told that the very back
end tasks like register allocation and insn scheduling are the hardest ones
in comparison with middle end or moreover front-end tasks). I choose such
code because
o insn scheduling itself is potentially n**2 algorithm.
o EBB is rare whole function (although some plumhall functions are one EBB).
o There are few PRISKY_CANDIDATE insns.
o The code will work only when load speculatively option is switched on
(which is not default).
That was my decision. If you are not agree, I could remove the nested loop
and check only immediately preceding block.
Meanwhile, I improved the code (made loop explicitly only for
PFREE_CANDIDATEs) and attached it. It can be improved more by creating and
modifying an additional structure (containing all preceding blocks and
adding a loop through the blocks in block_has_similiar_load. The algorithm
will be still potentially n**2 but faster).
So what would you prefer?
Vlad
>
> I claim that this search is not necessary.
>
> (1) Adding a dependency on the last jump insn prevents the
> trapping insn from being moved beyond it.
> (2) A jump insn depends on the previous jump insn. Thus by
> transitivity, we do not need to search backward to
> prevent a previous jump insn from somehow being
> scheduled after the trapping insn.
Index: sched-ebb.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/sched-ebb.c,v
retrieving revision 1.23
diff -c -p -r1.23 sched-ebb.c
*** sched-ebb.c 11 Feb 2003 12:33:52 -0000 1.23
--- sched-ebb.c 22 Feb 2003 14:47:55 -0000
*************** static const char *ebb_print_insn PARAMS
*** 56,61 ****
--- 56,63 ----
static int rank PARAMS ((rtx, rtx));
static int contributes_to_priority PARAMS ((rtx, rtx));
static void compute_jump_reg_dependencies PARAMS ((rtx, regset));
+ static int block_has_similiar_load PARAMS ((basic_block, rtx));
+ static void add_deps_for_risky_insns PARAMS ((rtx, rtx));
static basic_block schedule_ebb PARAMS ((rtx, rtx));
static basic_block fix_basic_block_boundaries PARAMS ((basic_block, basic_block, rtx, rtx));
static void add_missing_bbs PARAMS ((rtx, basic_block, basic_block));
*************** fix_basic_block_boundaries (bb, last, he
*** 339,344 ****
--- 341,446 ----
return bb->prev_bb;
}
+ /* Returns 1 if a clue for "similar load" 'insn2' is found in BLOCK,
+ and hence load_insn can move speculatively into BLOCK. All the
+ following must hold:
+
+ (1) both loads have 1 base register (PFREE_CANDIDATEs).
+ (2) load_insn and load1 have a def-use dependence upon
+ the same insn 'insn1'.
+ (3) load2 is in BLOCK
+
+ From all these we can conclude that the two loads access memory
+ addresses that differ at most by a constant, and hence if moving
+ load_insn would cause an exception, it would have been caused by
+ load2 anyhow. */
+
+ static int
+ block_has_similiar_load (block, load_insn)
+ basic_block block;
+ rtx load_insn;
+ {
+ rtx back_link;
+
+ for (back_link = LOG_LINKS (load_insn);
+ back_link;
+ back_link = XEXP (back_link, 1))
+ {
+ rtx insn1 = XEXP (back_link, 0);
+
+ if (GET_MODE (back_link) == VOIDmode)
+ {
+ /* Found a DEF-USE dependence (insn1, load_insn). */
+ rtx fore_link;
+
+ for (fore_link = INSN_DEPEND (insn1);
+ fore_link;
+ fore_link = XEXP (fore_link, 1))
+ {
+ rtx insn2 = XEXP (fore_link, 0);
+
+ if (GET_MODE (fore_link) == VOIDmode)
+ {
+ /* Found a DEF-USE dependence (insn1, insn2). */
+ if (haifa_classify_insn (insn2) != PFREE_CANDIDATE)
+ /* insn2 not guaranteed to be a 1 base reg load. */
+ continue;
+
+ if (BLOCK_FOR_INSN (insn2) == block)
+ /* insn2 is the similar load, in the target block. */
+ return 1;
+ }
+ }
+ }
+ }
+
+ /* Couldn't find a similar load. */
+ return 0;
+ }
+
+ /* The following function adds dependecies between jumps and risky
+ insns in given ebb. */
+
+ static void
+ add_deps_for_risky_insns (head, tail)
+ rtx head, tail;
+ {
+ rtx insn, prev;
+ int class;
+ rtx last_jump = NULL_RTX;
+ rtx prev_head = PREV_INSN (head);
+ rtx next_tail = NEXT_INSN (tail);
+
+ for (insn = head; insn != next_tail; insn = NEXT_INSN (insn))
+ if (GET_CODE (insn) == JUMP_INSN)
+ last_jump = insn;
+ else if (INSN_P (insn) && last_jump != NULL_RTX)
+ {
+ class = haifa_classify_insn (insn);
+ if (class == TRAP_RISKY || class == IRISKY
+ || class == PRISKY_CANDIDATE
+ || (class == PFREE_CANDIDATE && !flag_schedule_speculative_load))
+ {
+ /* ??? We could implement better checking PRISKY_CANDIATEs
+ analogous to sched-rgn.c. */
+ /* We can not change the mode of the backward
+ dependency because REG_DEP_ANTI has the lowest
+ rank. */
+ if (add_dependence (insn, last_jump, REG_DEP_ANTI))
+ add_forward_dependence (last_jump, insn, REG_DEP_ANTI);
+ }
+ else if (class == PFREE_CANDIDATE)
+ for (prev = last_jump; prev != prev_head; prev = PREV_INSN (prev))
+ if (GET_CODE (prev) == JUMP_INSN
+ && block_has_similiar_load (BLOCK_FOR_INSN (prev), insn))
+ {
+ if (add_dependence (insn, prev, REG_DEP_ANTI))
+ add_forward_dependence (prev, insn, REG_DEP_ANTI);
+ break;
+ }
+ }
+ }
+
/* Schedule a single extended basic block, defined by the boundaries HEAD
and TAIL. */
*************** schedule_ebb (head, tail)
*** 364,369 ****
--- 466,473 ----
/* Compute INSN_DEPEND. */
compute_forward_dependences (head, tail);
+
+ add_deps_for_risky_insns (head, tail);
if (targetm.sched.dependencies_evaluation_hook)
targetm.sched.dependencies_evaluation_hook (head, tail);