https://gcc.gnu.org/bugzilla/show_bug.cgi?id=123994
Richard Sandiford <rsandifo at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|NEW |ASSIGNED
Assignee|unassigned at gcc dot gnu.org |rsandifo at gcc dot
gnu.org
--- Comment #10 from Richard Sandiford <rsandifo at gcc dot gnu.org> ---
(In reply to Jeffrey A. Law from comment #9)
> Andrew, it's not clear to me we can compare insns like that in the rtl-ssa
> framework. Those operators providing an ordering, but I don't think it's
> always a global ordering.
>
> // Compare instructions by their positions in the function list described
> // above. Thus for two instructions in the same basic block, I1 < I2 if
> // I1 comes before I2 in the block.
> bool operator< (const insn_info &) const;
> bool operator<= (const insn_info &) const;
> bool operator>= (const insn_info &) const;
> bool operator> (const insn_info &) const;
>
> Let's assume the basic idea is that in the absence of loops if A > B, then A
> occurs after B. But there's not a viable global order in the presense of a
> irreducible loop -- which this test case has by the time we get into
> late-combine. I was a bit surprised by the irreducible loop, so I verified
> it by drawing the CFG by hand. Sure enough, it's got an irredicble loop.
The order is supposed to be (an) RPO, so Andrew's patch does look correct from
that point of view. Yours would work too. I suppose it's a trade-off between
the double comparison in Andrew's patch (commonly O(1), amortised worst case
O(log(n)), unamortised worst case O(n)) vs potentially skipping unnecessary
instructions when min_insn is already beyond the limit. The number of insns we
skip should be small, though, even with debug info, since next_nondebug_insn is
O(1).
There again, this shouldn't be performance-critical code, so it probably
doesn't matter much either way.
The root problem though is pretty embarrassing. The changes presented to
verify_insn_changes are also supposed to be in RPO. The change set in this PR
has a definition that is used in multiple degenerate phis, and although those
phi uses are still in RPO (because they haven't changed since the initial
build), I'd forgotten that phi_uses () works in reverse order :( This means
that the changes for other blocks are not properly ordered.
phi_uses has no defined order in general, because guaranteeing one would make
updates too expensive in the worst case. So either substitute_nondebug_uses
should be doing something to cope with unordered phis, or the insn-changes
stuff should require RPO only within EBBs. The latter seems more sensible on
the face of it.
Let me think about it a bit.
