Re: define_constraints patch, revised

[Zack Weinberg <zackw at panix dot com>]

On Wed, Feb 22, 2006 at 05:35:47PM +0000, Joern RENNECKE wrote:
> In http://gcc.gnu.org/ml/gcc-patches/2006-02/msg01723.html, you wrote:
> >> Hmm, do you mean the situation where one constraint name is a proper
> >> prefix of another, or where there's an actual ambiguous operand 
> constraint?
> > The former would be nice, but the latter would be wonderful. I admit
> > I haven't actually thought much about how difficult it would be to
> > implement - there must be Well Known Algorithms for this kind of thing.
> 
> Yes, this can be reduced to the problem of determining if a context-free
> grammer is in LR(k), where k could be chosen as the longest 
> define_constraint
> matching string length.
> However, that is a rather costly test:
> http://portal.acm.org/citation.cfm?id=361227.361232

The paper leaves me un-enlightened as to whether you mean finding proper
prefixes, or finding ambiguous operand constraints.

Given the lack of existing proper prefixes, given also that it would turn
the rule about not starting constraint names with a letter reserved for
generic constraints into a special case of the general rule,
and finally given that I can see a nice straightforward way to implement
it (O(n^2), but n is the number of define_constraint forms in the MD,
so it should be fine) I propose to just forbid definition of any constraint
whose name contains another constraint name as a prefix.  The code will be
insensitive to the order of definitions.  I believe there are no other
situations which can produce ambiguous constraint strings.

zw