[prev in list] [next in list] [prev in thread] [next in thread] 

List:       linux-sparse
Subject:    Re: Doing real symbol->pseudo conversion.
From:       Linus Torvalds <torvalds () osdl ! org>
Date:       2004-11-17 21:41:21
Message-ID: Pine.LNX.4.58.0411171322140.2222 () ppc970 ! osdl ! org
[Download RAW message or body]



On Wed, 17 Nov 2004, Christopher Li wrote:
>
> What is the new test case to break it?
> 
> Your previous partial domination example seems works correctly
> for me.

Oh, it seems to be pretty correct (I'm not going to say bug-free, I've 
just had too many total brainos over the last few days ;), but it's 
certainly very easy to make it generate lots of unnecessary phi-nodes with 
the right patterns.

Not _wrong_ phi-nodes, mind you, just unnecessary ones due to not noticing 
that they are the same because the loads got coverted into phi-nodes in 
a less than optimal order.

The most trivial example is a totally made-up-one:


	void fn(int);

	int main(int argc)
	{
		/*
		 * This just makes us have two assignments to argc,
		 * to kick in the "complex" case. Assignment #1 is
		 * the implicit argument value assignment, of course.
		 */
		if (!argc)
			argc++;
		goto end;
	back:
		return argc;
	end:
		fn(argc);
		goto back;
	}

and notice how when we linearize this, we won't notice that the read of 
"argc" in the function call dominates the read of "argc" in the return 
statement (because we convert the function call argument _first_), so we 
will generate two phi-nodes that look exactly the same.

Again, my argument is that CSE takes care of it, and since _usually_ a
load is dominated by a load that was linearized previously, and we get
that case right anyway, my stupid brute-force algorithm is fine. It's
certainly a lot simpler than trying to figure out dominance frontiers and
trying to always put the phi-nodes at the "optimal" point.

At least it's simpler on my poor brain. My phi-replacement really _is_
very simple, since they are always replaced 1:1 with the loads that caused
them (and obviously quite often, I can just nop out the load entirely and
just do a pseudo replacement instead).

The thing that struck me is how often we seem to have the _really_ simple 
case with just a single assignment to a symbol. There's a lot of code like 
that, and then the dominance algorithm doesn't ever even trigger for that 
symbol. I was hitting my head against the wall trying to figure out why I 
couldn't make a bug that I knew about happen, until I noticed that all the 
test-cases I had written to try to catch it all had just a single 
assignment in it, and thus the bug would never trigger ;)

			Linus
-
To unsubscribe from this list: send the line "unsubscribe linux-sparse" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
[prev in list] [next in list] [prev in thread] [next in thread]