Reimplemented HGraph::Postorder and HGraph::PostorderLoopBlocks iteratively to avoid stack overflow…

Reimplemented HGraph::Postorder and HGraph::PostorderLoopBlocks iteratively to avoid stack overflows.

BUG=
TEST=

Committed: https://code.google.com/p/v8/source/detail?r=11843

[Jakob Kummerow, 2012-06-14 17:24:14]

LGTM with a bunch of comments, but nothing major.

I'm still not a fan of this recursion algorithm, but I suppose it has served us
well so far.

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:755: // At a _very_ high level the algorithm looks like this:
Remove the "_very_". Just "high level". It's cleaner.

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:762: //     SuccessorsOfLoopHeaderCycle(block, loop_header);
This only needs "block" as input, right? That's the case where "block" is
actually passed in as the new outer_loop_header to recursive calls.

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:769: // LoopMembersCycle(block) {
This needs a second argument "outer_loop_header".

Also, how about renaming all of these methods from <Foo>Cycle to Visit<Foo>?

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:771: //     SuccessorsOfLoopMemberCycle(b);
This call must pass on the outer_loop_header.

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:776: // SuccessorsOfLoopMemberCycle(block, loop_header) {
I'd rename the second argument to outer_loop_header.

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:781: //   foreach (block b in block successors) Postorder(b, b)
Shouldn't this pass (b, block) instead?

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:784: // PostorderCycle(block, loop_header) {
I don't feel strongly about this, but wouldn't s/Postorder/Successors/ (=>
"VisitSuccessors") match the other method names better?

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:795: class PostorderProcessor : ZoneObject {
"...: public ZoneObject" please

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:797: // Back list link (towards the stack bottom)
nit: "Backward", and a missing full stop at the end.

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:798: PostorderProcessor* father() {return father_; }
nit: s/father/parent/? ;-)

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:799: // Forward list link (towards the stack top)
nit: missing full stop at the end.

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:839: if ((block == NULL || visited->Contains(block->block_id()))
||
nit: you can remove one pair of ().

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:840: (block->parent_loop_header() != loop_header)) {
can remove the outer (...) here too

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:933: ASSERT(false);
nit: we have UNREACHABLE() for this.
Even better: remove the "default:" case, you've handled all cases anyway and
without "default:" the compiler will tell you if you've forgotten one.

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:942: PostorderProcessor* father = Pop(zone, visited, order);
Again, s/father/parent/.

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:993: default:
Again, please remove the default case.

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:1011: } else {
nit: You could remove the "else" and just "return NULL" on the top level. I
don't care much, your choice. (There are a few more occurrences of this
pattern.)

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:1032: explicit PostorderProcessor(PostorderProcessor* father)
Please put the constructor first (within the "private:" section).

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:1041: int loop_index;
nit: trailing _ please (again below, twice).

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:1068: void HGraph::PostorderLoopBlocks(HLoopInformation* loop,
I think you can remove this method and the next. They should be dead code now.

[Massi, 2012-06-18 11:21:30]

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc
File src/hydrogen.cc (right):

https://chromiumcodereview.appspot.com/10543138/diff/1/src/hydrogen.cc#newcod...
src/hydrogen.cc:993: default:
On 2012/06/14 17:24:14, Jakob wrote:
> Again, please remove the default case.

If I remove it I cannot compile, likewise if I remove the "return NULL;" at the
end...