basic block output order?

basic block output order?

[Christopher Li]

I am playing with the example.c. I am wondering why the parent
basic blocks need to generate first?

The entry point has it's own "entry" instruction now, it should
remain as the first basic block in entry->bbs.

e.g. what is wrong with the following patch?

The reason I ask is because I think I need a few more pass
on the basic block. I try to avoid recursive if it is not necessary.

Thanks

Chris

Index: sparse/flow.c
===================================================================
--- sparse.orig/flow.c	2006-12-12 01:52:06.000000000 -0800
+++ sparse/flow.c	2006-12-12 01:52:40.000000000 -0800
@@ -903,12 +903,10 @@ void vrfy_flow(struct entrypoint *ep)
 	struct basic_block *bb;
 	struct basic_block *entry = ep->entry->bb;
 
+	assert(first_basic_block(ep->bbs) == entry);
 	FOR_EACH_PTR(ep->bbs, bb) {
-		if (bb == entry)
-			entry = NULL;
 		vrfy_bb_flow(bb);
 	} END_FOR_EACH_PTR(bb);
-	assert(!entry);
 }
 
 void pack_basic_blocks(struct entrypoint *ep)
Index: sparse/example.c
===================================================================
--- sparse.orig/example.c	2006-12-12 01:52:06.000000000 -0800
+++ sparse/example.c	2006-12-12 01:52:40.000000000 -0800
@@ -1765,9 +1765,6 @@ static void output_bb(struct basic_block
 
 	bb->generation = generation;
 
-	/* Make sure all parents have been generated first */
-	generate_list(bb->parents, generation);
-
 	state.pos = bb->pos;
 	state.inputs = gather_storage(bb, STOR_IN);
 	state.outputs = gather_storage(bb, STOR_OUT);
@@ -1782,9 +1779,6 @@ static void output_bb(struct basic_block
 
 	free_ptr_list(&state.inputs);
 	free_ptr_list(&state.outputs);
-
-	/* Generate all children... */
-	generate_list(bb->children, generation);
 }
 
 /*
@@ -1920,7 +1914,7 @@ static void output(struct entrypoint *ep
 	arch_set_up_storage(ep);
 
 	/* Show the results ... */
-	output_bb(ep->entry->bb, generation);
+	generate_list(ep->bbs, generation);
 
 	/* Clear the storage hashes for the next function.. */
 	free_storage();

Re: basic block output order?

[Linus Torvalds]

On Tue, 12 Dec 2006, Christopher Li wrote:
>
> I am playing with the example.c. I am wondering why the parent
> basic blocks need to generate first?

They don't have to. But it generated nicer code, iirc, mainly because it 
did the storage allocation the natural way. In particular, if I recall 
correctly, it causes loops to have the storage for the _innermost_ loop to 
be done first.

Notes off the top of my head, without actually looking at the code: 
because when you hit a loop, the "parent" set is actually both the entry 
and the BB that ha the loopback, so you actually end up going to the 
loopback thing, which goes to _its_ parents, etc etc, until you actually 
get back to the _top_ of the loop (and now the "generation" count triggers 
you to break the looping), so you end up doing the actual register 
allocation at tops of loops, but because you do this all recursively, and 
the inner loop will have _its_ parents point to the callback too, you 
generally tend to have started storage allocation at loop-tops.

HOWEVER. There's a reason the thing is called "example.c". The reason is 
simply that it's stupid, idiotic, and not meant to be taken seriously. I 
also ended up just hackign things around randomly to make it output 
something that looked half-way sane, _and_ I ended up changign it to use 
the "unssa" pass by Luc, _and_ I'm border-line psychotic when it comes to 
compilers anyway.

In other words, what I'm trying to say is that you shouldn't take anything 
I say too seriously, and that the "example.c" code wasn't really even 
meant to be serious. I always wanted somebody else to write the back-end, 
and held back as long as I could from writing example.c, and when I wrote 
it, it was more a case of desperately trying to find somebody interested 
in it, and having it as an example of how things _might_ work.

So as far as I am concerned, the whole "example.c" is just total 
throw-away code. Go wild with it.

		Linus

Re: basic block output order?

[Christopher Li]

Thanks for your explain. I see, you want to generate the dominator
first.

Chris

On Tue, Dec 12, 2006 at 08:36:43AM -0800, Linus Torvalds wrote:
> 
> 
> On Tue, 12 Dec 2006, Christopher Li wrote:
> 
> They don't have to. But it generated nicer code, iirc, mainly because it 
> did the storage allocation the natural way. In particular, if I recall 
> correctly, it causes loops to have the storage for the _innermost_ loop to 
> be done first.
> 
> Notes off the top of my head, without actually looking at the code: 
> because when you hit a loop, the "parent" set is actually both the entry 
> and the BB that ha the loopback, so you actually end up going to the 
> loopback thing, which goes to _its_ parents, etc etc, until you actually 
> get back to the _top_ of the loop (and now the "generation" count triggers 
> you to break the looping), so you end up doing the actual register 
> allocation at tops of loops, but because you do this all recursively, and 
> the inner loop will have _its_ parents point to the callback too, you 
> generally tend to have started storage allocation at loop-tops.
> 
> HOWEVER. There's a reason the thing is called "example.c". The reason is 
> simply that it's stupid, idiotic, and not meant to be taken seriously. I 
> also ended up just hackign things around randomly to make it output 
> something that looked half-way sane, _and_ I ended up changign it to use 
> the "unssa" pass by Luc, _and_ I'm border-line psychotic when it comes to 
> compilers anyway.
> 
> In other words, what I'm trying to say is that you shouldn't take anything 
> I say too seriously, and that the "example.c" code wasn't really even 
> meant to be serious. I always wanted somebody else to write the back-end, 
> and held back as long as I could from writing example.c, and when I wrote 
> it, it was more a case of desperately trying to find somebody interested 
> in it, and having it as an example of how things _might_ work.
> 
> So as far as I am concerned, the whole "example.c" is just total 
> throw-away code. Go wild with it.
> 
> 		Linus

Re: basic block output order?

[Linus Torvalds]

On Tue, 12 Dec 2006, Christopher Li wrote:
>
> Thanks for your explain. I see, you want to generate the dominator
> first.

Basically, yes. That way, when we start generating code in any basic 
block, we usually either (a) have the outputs from the dominators or (b) 
we're the top block in a loop and any freedom we can use to pick our 
preferred registers is probably a good thing.

The current "example.c" was very much written with the intent that it 
would not ever do any _smart_ register allocation, but just allocate 
registers on-the-fly. But doing that requires that you set things up so 
that the stupid approach can still get reasonable results.

The way the death-notes work etc was all designed exactly so that the 
register "allocator" never really needed any global visibility at all, it 
could just work on an instruction-per-instruction basis.

That said, the simplicity of it all in example.c still doesn't mean that 
it _works_. It really doesn't, and isn't even really close. But it 
occasionally results in code that looks _almost_ like it could be run ;)

		Linus