This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
PATCH for PR 2828: Testers needed!
- To: gcc-patches at gcc dot gnu dot org
- Subject: PATCH for PR 2828: Testers needed!
- From: Mark Mitchell <mark at codesourcery dot com>
- Date: Fri, 18 May 2001 16:54:32 -0700
- Organization: CodeSourcery, LLC
This patch fixes PR 2828. We were looping infinitely in
calculate_global_regs_live.
This regression is caused by the new cond_exec support; we were not
handling conditional execution as conservatively as necessary when
updating the liveness information.
With much help from Richard Henderson, I have prepared a draft patch,
which fixes the problem with a cross-compiler. However, I don't have
access to a target with conditional-execution, so I can't really test
the patch fully. If you have such a target (ARM was the platform with
the original bug), please apply the patch to the GCC 3.0 branch and
perform a bootstrap and test.
Let me know how it comes out.
Thanks!
--
An additional problem was that we had some missing documentation:
- COND_EXEC was not documented at all in the manual.
- The documentation on `struct basic_block_def' had information
about the implementation, but didn't say what a basic block was.
- Some of the fields of this structure didn't have documentation
explaining what they were.
- There was no explanation of the overall workings of the algorithm
used in calculate_global_regs_live.
A lot of this stuff is mind-numbingly obvious to the experts who wrote
it. But, it ain't obvious to anyone else. Let's try to clean things
up as we go, here, and invest the up-front time to get complete
documentation in place the next time around.
All but three lines of this patch are documentation and/or assertions.
--
Mark Mitchell mark@codesourcery.com
CodeSourcery, LLC http://www.codesourcery.com
2001-05-18 Mark Mitchell <mark@codesourcery.com>
* basic-block.h (struct basic_block_def): Add documentation about
what a basic block is, and what the various fields are used for.
* flow.c (calculate_globlal_regs_live): Add documentation about
how the algorithm works, and how we know that it will terminate.
Check that the the inductive assumption that guarantees
termination actually holds.
(mark_used_regs): Treat conditionally set registers as used.
(debug_regset): Add comment.
* rtl.texi (cond_exec): Add documentation.
Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.87.4.1
diff -c -p -r1.87.4.1 basic-block.h
*** basic-block.h 2001/05/13 07:09:50 1.87.4.1
--- basic-block.h 2001/05/18 23:53:49
***************
*** 1,5 ****
/* Define control and data flow tables, and regsets.
! Copyright (C) 1987, 1997, 1998, 1999, 2000 Free Software Foundation, Inc.
This file is part of GNU CC.
--- 1,5 ----
/* Define control and data flow tables, and regsets.
! Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
This file is part of GNU CC.
*************** typedef struct edge_def {
*** 141,147 ****
#define EDGE_COMPLEX (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH)
! /* Basic blocks need not start with a label nor end with a jump insn.
For example, a previous basic block may just "conditionally fall"
into the succeeding basic block, and the last basic block need not
end with a jump insn. Block 0 is a descendant of the entry block.
--- 141,160 ----
#define EDGE_COMPLEX (EDGE_ABNORMAL | EDGE_ABNORMAL_CALL | EDGE_EH)
! /* A basic block is a sequence of instructions with only entry and
! only one exit. If any one of the instructions are executed, they
! will all be executed, and in sequence from first to last.
!
! There may be COND_EXEC instructions in the basic block. The
! COND_EXEC *instructions* will be executed -- but if the condition
! is false the conditionally executed *expressions* will of course
! not be executed. We don't consider the conditionally executed
! expression (which might have side-effects) to be in a separate
! basic block because the program counter will always be at the same
! location after the COND_EXEC instruction, regardless of whether the
! condition is true or not.
!
! Basic blocks need not start with a label nor end with a jump insn.
For example, a previous basic block may just "conditionally fall"
into the succeeding basic block, and the last basic block need not
end with a jump insn. Block 0 is a descendant of the entry block.
*************** typedef struct basic_block_def {
*** 160,172 ****
/* The edges into and out of the block. */
edge pred, succ;
! /* Liveness info. Note that in SSA form, global_live_at_start does
! not reflect the use of regs in phi functions, since the liveness
! of these regs may depend on which edge was taken into the block. */
regset local_set;
regset cond_local_set;
regset global_live_at_start;
regset global_live_at_end;
/* Auxiliary info specific to a pass. */
--- 173,194 ----
/* The edges into and out of the block. */
edge pred, succ;
+
+ /* Liveness info. */
! /* The registers that are modified within this in block. */
regset local_set;
+ /* The registers that are conditionally modified within this block.
+ In other words, registers that are set only as part of a
+ COND_EXEC. */
regset cond_local_set;
+ /* The registers that are live on entry to this block.
+
+ Note that in SSA form, global_live_at_start does not reflect the
+ use of regs in phi functions, since the liveness of these regs
+ may depend on which edge was taken into the block. */
regset global_live_at_start;
+ /* The registers that are live on exit from this block. */
regset global_live_at_end;
/* Auxiliary info specific to a pass. */
Index: flow.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flow.c,v
retrieving revision 1.374.2.12
diff -c -p -r1.374.2.12 flow.c
*** flow.c 2001/05/16 04:10:54 1.374.2.12
--- flow.c 2001/05/18 23:53:50
*************** calculate_global_regs_live (blocks_in, b
*** 3279,3284 ****
--- 3279,3302 ----
if (blocks_out)
sbitmap_zero (blocks_out);
+ /* We work through the queue until there are no more blocks. What
+ is live at the end of this block is precisely the union of what
+ is live at the beginning of all its successors. So, we set its
+ GLOBAL_LIVE_AT_END field based on the GLOBAL_LIVE_AT_START field
+ for its successors. Then, we compute GLOBAL_LIVE_AT_START for
+ this block by walking through the instructions in this block in
+ reverse order and updating as we go. If that changed
+ GLOBAL_LIVE_AT_START, we add the predecessors of the block to the
+ queue; they will now need to recalculate GLOBAL_LIVE_AT_END.
+
+ We are guaranteed to terminate, because GLOBAL_LIVE_AT_START
+ never shrinks. If a register appears in GLOBAL_LIVE_AT_START, it
+ must either be live at the end of the block, or used within the
+ block. In the latter case, it will certainly never disappear
+ from GLOBAL_LIVE_AT_START. In the former case, the register
+ could go away only if it disappeared from GLOBAL_LIVE_AT_START
+ for one of the successor blocks. By induction, that cannot
+ occur. */
while (qhead != qtail)
{
int rescan, changed;
*************** calculate_global_regs_live (blocks_in, b
*** 3290,3296 ****
qhead = queue;
bb->aux = NULL;
! /* Begin by propogating live_at_start from the successor blocks. */
CLEAR_REG_SET (new_live_at_end);
for (e = bb->succ; e; e = e->succ_next)
{
--- 3308,3314 ----
qhead = queue;
bb->aux = NULL;
! /* Begin by propagating live_at_start from the successor blocks. */
CLEAR_REG_SET (new_live_at_end);
for (e = bb->succ; e; e = e->succ_next)
{
*************** calculate_global_regs_live (blocks_in, b
*** 3435,3440 ****
--- 3453,3470 ----
if (REG_SET_EQUAL_P (bb->global_live_at_start, new_live_at_end))
continue;
+ #ifdef ENABLE_CHECKING
+ /* If there are registers that were in GLOBAL_LIVE_AT_START,
+ but are no longer, then we are violating the inductive
+ assumption that guarantees termination of this algorithm. */
+ CLEAR_REG_SET (tmp);
+ if (bitmap_operation (tmp,
+ bb->global_live_at_start,
+ new_live_at_end,
+ BITMAP_AND_COMPL))
+ abort ();
+ #endif
+
COPY_REG_SET (bb->global_live_at_start, new_live_at_end);
}
*************** mark_set_regs (pbi, x, insn)
*** 4503,4509 ****
}
}
! /* Process a single SET rtx, X. */
static void
mark_set_1 (pbi, code, reg, cond, insn, flags)
--- 4533,4543 ----
}
}
! /* Process a single set, which appears in INSN. REG (which may not
! actually be a REG, it may also be a SUBREG, PARALLEL, etc.) is
! being set using the CODE (which may be SET, CLOBBER, or COND_EXEC).
! If the set is conditional (because it appear in a COND_EXEC), COND
! will be the condition. */
static void
mark_set_1 (pbi, code, reg, cond, insn, flags)
*************** mark_used_regs (pbi, x, cond, insn)
*** 5851,5856 ****
--- 5885,5898 ----
testreg = XEXP (testreg, 0);
}
+ /* A conditionally-executed SET must be handled
+ conservatively. If the condition is false, the register
+ will not be set so whatever value it had before this point
+ will remain live. In other words, the register is not
+ necessarily killed at this point, so we treat it as used. */
+ if (cond)
+ mark_dest = 1;
+
/* If this is a store into a register or group of registers,
recursively scan the value being stored. */
*************** dump_regset (r, outf)
*** 6179,6184 ****
--- 6221,6230 ----
reg_names[i]);
});
}
+
+ /* Print a human-reaable representation of R on the standard error
+ stream. This function is designed to be used from within the
+ debugger. */
void
debug_regset (r)
Index: rtl.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/rtl.texi,v
retrieving revision 1.35.2.3
diff -c -p -r1.35.2.3 rtl.texi
*** rtl.texi 2001/05/14 05:12:22 1.35.2.3
--- rtl.texi 2001/05/18 23:53:51
*************** but it is ok then because no further opt
*** 2190,2195 ****
--- 2190,2202 ----
However, the definition of the macro @code{NOTICE_UPDATE_CC}, if
any, must deal with such insns if you define any peephole optimizations.
+ @findex cond_exec
+ @item (cond_exec [@var{cond} @var{expr}])
+ Represents a conditionally executed expression. The @var{expr} is
+ executed only if the @var{cond} is non-zero. The @var{cond} expression
+ may not have side-effects, but the @var{expr} may very well have
+ side-effects.
+
@findex sequence
@item (sequence [@var{insns} @dots{}])
Represents a sequence of insns. Each of the @var{insns} that appears
*************** An expression for the side effect perfor
*** 2674,2680 ****
one of the following codes: @code{set}, @code{call}, @code{use},
@code{clobber}, @code{return}, @code{asm_input}, @code{asm_output},
@code{addr_vec}, @code{addr_diff_vec}, @code{trap_if}, @code{unspec},
! @code{unspec_volatile}, @code{parallel}, or @code{sequence}. If it is a @code{parallel},
each element of the @code{parallel} must be one these codes, except that
@code{parallel} expressions cannot be nested and @code{addr_vec} and
@code{addr_diff_vec} are not permitted inside a @code{parallel} expression.
--- 2681,2687 ----
one of the following codes: @code{set}, @code{call}, @code{use},
@code{clobber}, @code{return}, @code{asm_input}, @code{asm_output},
@code{addr_vec}, @code{addr_diff_vec}, @code{trap_if}, @code{unspec},
! @code{unspec_volatile}, @code{parallel}, @code{cond_exec}, or @code{sequence}. If it is a @code{parallel},
each element of the @code{parallel} must be one these codes, except that
@code{parallel} expressions cannot be nested and @code{addr_vec} and
@code{addr_diff_vec} are not permitted inside a @code{parallel} expression.