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

src/hydrogen.cc

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 730 matching lines @@
   for (int i = 0; i < blocks()->length(); ++i) {
     HInstruction* instr = blocks()->at(i)->first();
     while (instr != NULL) {
       HValue* value = instr->Canonicalize();
       if (value != instr) instr->DeleteAndReplaceWith(value);
       instr = instr->next();
     }
   }
 }
 
+// Block ordering was implemented with two mutually recursive methods,
+// HGraph::Postorder and HGraph::PostorderLoopBlocks.
+// The recursion could lead to stack overflow so the algorithm has been
+// implemented iteratively.
+// At a _very_ high level the algorithm looks like this:

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

Remove the "_very_". Just "high level". It's cleaner.

+//
+// Postorder(block, loop_header) : {
+//   if (block has already been visited or is of another loop) return;
+//   mark block as visited;
+//   if (block is a loop header) {
+//     LoopMembersCycle(block, loop_header);
+//     SuccessorsOfLoopHeaderCycle(block, loop_header);

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

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.

+//   } else {
+//     PostorderCycle(block)
+//   }
+//   put block in result list;
+// }
+//
+// LoopMembersCycle(block) {

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

This needs a second argument "outer_loop_header".

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

+//   foreach (block b in block loop members) {
+//     SuccessorsOfLoopMemberCycle(b);

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

This call must pass on the outer_loop_header.

+//     if (b is loop header) LoopMembersCycle(b);
+//   }
+// }
+//
+// SuccessorsOfLoopMemberCycle(block, loop_header) {

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

I'd rename the second argument to outer_loop_header.

+//   foreach (block b in block successors) Postorder(b, loop_header)
+// }
+//
+// SuccessorsOfLoopHeaderCycle(block) {
+//   foreach (block b in block successors) Postorder(b, b)

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

Shouldn't this pass (b, block) instead?

+// }
+//
+// PostorderCycle(block, loop_header) {

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

I don't feel strongly about this, but wouldn't s/Postorder/Successors/ (=>
"VisitSuccessors") match the other method names better?

+//   foreach (block b in block successors) Postorder(b, loop_header)
+// }
+//
+// The ordering is started calling Postorder(entry, NULL).
+//
+// Each instance of PostorderProcessor represents the "stack frame" of the
+// recursion, and particularly keeps the state of one of the cycles.
+// To recycle memory we keep all the frames in a double linked list but
+// this means that we cannot use constructors to initialize the frames.
+//
+class PostorderProcessor : ZoneObject {

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

"...: public ZoneObject" please

+ public:
+  // Back list link (towards the stack bottom)

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

nit: "Backward", and a missing full stop at the end.

+  PostorderProcessor* father() {return father_; }

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

nit: s/father/parent/? ;-)

+  // Forward list link (towards the stack top)

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

nit: missing full stop at the end.

+  PostorderProcessor* child() {return child_; }
+  HBasicBlock* block() { return block_; }
+  HLoopInformation* loop() { return loop_; }
+  HBasicBlock* loop_header() { return loop_header_; }
+
+  static PostorderProcessor* CreateEntryProcessor(Zone* zone,
+                                                  HBasicBlock* block,
+                                                  BitVector* visited) {
+    PostorderProcessor* result = new(zone) PostorderProcessor(NULL);
+    return result->SetupSuccessors(zone, block, NULL, visited);
+  }
+
+  PostorderProcessor* PerformStep(Zone* zone,
+                                  BitVector* visited,
+                                  ZoneList<HBasicBlock*>* order) {
+    PostorderProcessor* next =
+        PerformNonBacktrackingStep(zone, visited, order);
+    if (next != NULL) {
+      return next;
+    } else {
+      return Backtrack(zone, visited, order);
+    }
+  }
+
+ private:
+  // Each enum value states the cycle whose state is kept by this instance.
+  enum LoopKind {
+    NONE,
+    SUCCESSORS,
+    SUCCESSORS_OF_LOOP_HEADER,
+    LOOP_MEMBERS,
+    SUCCESSORS_OF_LOOP_MEMBER
+  };
+
+  // Each "Setup..." method is like a constructor for a cycle state.
+  PostorderProcessor* SetupSuccessors(Zone* zone,
+                                      HBasicBlock* block,
+                                      HBasicBlock* loop_header,
+                                      BitVector* visited) {
+    if ((block == NULL || visited->Contains(block->block_id())) ||

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

nit: you can remove one pair of ().

+        (block->parent_loop_header() != loop_header)) {

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

can remove the outer (...) here too

+      kind_ = NONE;
+      block_ = NULL;
+      loop_ = NULL;
+      loop_header_ = NULL;
+      return this;
+    } else {
+      block_ = block;
+      loop_ = NULL;
+      visited->Add(block->block_id());
+
+      if (block->IsLoopHeader()) {
+        kind_ = SUCCESSORS_OF_LOOP_HEADER;
+        loop_header_ = block;
+        InitializeSuccessors();
+        PostorderProcessor* result = Push(zone);
+        return result->SetupLoopMembers(zone, block, block->loop_information(),
+                                        loop_header);
+      } else {
+        ASSERT(block->IsFinished());
+        kind_ = SUCCESSORS;
+        loop_header_ = loop_header;
+        InitializeSuccessors();
+        return this;
+      }
+    }
+  }
+
+  PostorderProcessor* SetupLoopMembers(Zone* zone,
+                                       HBasicBlock* block,
+                                       HLoopInformation* loop,
+                                       HBasicBlock* loop_header) {
+    kind_ = LOOP_MEMBERS;
+    block_ = block;
+    loop_ = loop;
+    loop_header_ = loop_header;
+    InitializeLoopMembers();
+    return this;
+  }
+
+  PostorderProcessor* SetupSuccessorsOfLoopMember(
+      HBasicBlock* block,
+      HLoopInformation* loop,
+      HBasicBlock* loop_header) {
+    kind_ = SUCCESSORS_OF_LOOP_MEMBER;
+    block_ = block;
+    loop_ = loop;
+    loop_header_ = loop_header;
+    InitializeSuccessors();
+    return this;
+  }
+
+  // This method "allocates" a new stack frame.
+  PostorderProcessor* Push(Zone* zone) {
+    if (child_ == NULL) {
+      child_ = new(zone) PostorderProcessor(this);
+    }
+    return child_;
+  }
+
+  void ClosePostorder(ZoneList<HBasicBlock*>* order) {
+    ASSERT(block_->end()->FirstSuccessor() == NULL ||
+           order->Contains(block_->end()->FirstSuccessor()) ||
+           block_->end()->FirstSuccessor()->IsLoopHeader());
+    ASSERT(block_->end()->SecondSuccessor() == NULL ||
+           order->Contains(block_->end()->SecondSuccessor()) ||
+           block_->end()->SecondSuccessor()->IsLoopHeader());
+    order->Add(block_);
+  }
+
+  // This method is the basic block to walk up the stack.
+  PostorderProcessor* Pop(Zone* zone,
+                          BitVector* visited,
+                          ZoneList<HBasicBlock*>* order) {
+    switch (kind_) {
+      case SUCCESSORS:
+      case SUCCESSORS_OF_LOOP_HEADER:
+        ClosePostorder(order);
+        return father_;
+      case LOOP_MEMBERS:
+        return father_;
+      case SUCCESSORS_OF_LOOP_MEMBER:
+        if (block()->IsLoopHeader() && block() != loop_->loop_header()) {
+          // In this case we need to perform a LOOP_MEMBERS cycle so we
+          // initialize it and return this instead of father.
+          return SetupLoopMembers(zone, block(),
+                                  block()->loop_information(), loop_header_);
+        } else {
+          return father_;
+        }
+      case NONE:
+        return father_;
+      default:
+        ASSERT(false);

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

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.

+        return NULL;
+    }
+  }
+
+  // Walks up the stack.
+  PostorderProcessor* Backtrack(Zone* zone,
+                                BitVector* visited,
+                                ZoneList<HBasicBlock*>* order) {
+    PostorderProcessor* father = Pop(zone, visited, order);

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

Again, s/father/parent/.

+    while (father != NULL) {
+      PostorderProcessor* next =
+          father->PerformNonBacktrackingStep(zone, visited, order);
+      if (next != NULL) {
+        return next;
+      } else {
+        father = father->Pop(zone, visited, order);
+      }
+    }
+    return NULL;
+  }
+
+  PostorderProcessor* PerformNonBacktrackingStep(
+      Zone* zone,
+      BitVector* visited,
+      ZoneList<HBasicBlock*>* order) {
+    HBasicBlock* next_block;
+    switch (kind_) {
+      case SUCCESSORS:
+        next_block = AdvanceSuccessors();
+        if (next_block != NULL) {
+          PostorderProcessor* result = Push(zone);
+          return result->SetupSuccessors(zone, next_block,
+                                         loop_header_, visited);
+        }
+        break;
+      case SUCCESSORS_OF_LOOP_HEADER:
+        next_block = AdvanceSuccessors();
+        if (next_block != NULL) {
+          PostorderProcessor* result = Push(zone);
+          return result->SetupSuccessors(zone, next_block,
+                                         block(), visited);
+        }
+        break;
+      case LOOP_MEMBERS:
+        next_block = AdvanceLoopMembers();
+        if (next_block != NULL) {
+          PostorderProcessor* result = Push(zone);
+          return result->SetupSuccessorsOfLoopMember(next_block,
+                                                     loop_, loop_header_);
+        }
+        break;
+      case SUCCESSORS_OF_LOOP_MEMBER:
+        next_block = AdvanceSuccessors();
+        if (next_block != NULL) {
+          PostorderProcessor* result = Push(zone);
+          return result->SetupSuccessors(zone, next_block,
+                                         loop_header_, visited);
+        }
+        break;
+      default:

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

Again, please remove the default case.

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

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

+        return NULL;
+    }
+    return NULL;
+  }
+
+  // The following two methods implement a "foreach b in successors" cycle.
+  void InitializeSuccessors() {
+    loop_index = 0;
+    loop_length = 0;
+    successor_iterator = HSuccessorIterator(block_->end());
+  }
+
+  HBasicBlock* AdvanceSuccessors() {
+    if (!successor_iterator.Done()) {
+      HBasicBlock* result = successor_iterator.Current();
+      successor_iterator.Advance();
+      return result;
+    } else {

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

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.)

+      return NULL;
+    }
+  }
+
+  // The following two methods implement a "foreach b in loop members" cycle.
+  void InitializeLoopMembers() {
+    loop_index = 0;
+    loop_length = loop_->blocks()->length();
+  }
+
+  HBasicBlock* AdvanceLoopMembers() {
+    if (loop_index < loop_length) {
+      HBasicBlock* result = loop_->blocks()->at(loop_index);
+      loop_index++;
+      return result;
+    } else {
+      return NULL;
+    }
+  }
+
+  explicit PostorderProcessor(PostorderProcessor* father)

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

Please put the constructor first (within the "private:" section).

+      : father_(father), child_(NULL), successor_iterator(NULL) { }
+
+  LoopKind kind_;
+  PostorderProcessor* father_;
+  PostorderProcessor* child_;
+  HLoopInformation* loop_;
+  HBasicBlock* block_;
+  HBasicBlock* loop_header_;
+  int loop_index;

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

nit: trailing _ please (again below, twice).

+  int loop_length;
+  HSuccessorIterator successor_iterator;
+};
+
 
 void HGraph::OrderBlocks() {
   HPhase phase("H_Block ordering");
   BitVector visited(blocks_.length(), zone());
 
   ZoneList<HBasicBlock*> reverse_result(8);
   HBasicBlock* start = blocks_[0];
-  Postorder(start, &visited, &reverse_result, NULL);
-
+  PostorderProcessor* postorder =
+      PostorderProcessor::CreateEntryProcessor(zone(), start, &visited);
+  while (postorder != NULL) {
+    postorder = postorder->PerformStep(zone(), &visited, &reverse_result);
+  }
   blocks_.Rewind(0);
   int index = 0;
   for (int i = reverse_result.length() - 1; i >= 0; --i) {
     HBasicBlock* b = reverse_result[i];
     blocks_.Add(b);
     b->set_block_id(index++);
   }
 }
 
 
 void HGraph::PostorderLoopBlocks(HLoopInformation* loop,

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

I think you can remove this method and the next. They should be dead code now.

                                  BitVector* visited,
                                  ZoneList<HBasicBlock*>* order,
                                  HBasicBlock* loop_header) {
   for (int i = 0; i < loop->blocks()->length(); ++i) {
     HBasicBlock* b = loop->blocks()->at(i);
     for (HSuccessorIterator it(b->end()); !it.Done(); it.Advance()) {
       Postorder(it.Current(), visited, order, loop_header);
     }
     if (b->IsLoopHeader() && b != loop->loop_header()) {
       PostorderLoopBlocks(b->loop_information(), visited, order, loop_header);
@@ skipping 8213 matching lines @@
     }
   }
 
 #ifdef DEBUG
   if (graph_ != NULL) graph_->Verify(false);  // No full verify.
   if (allocator_ != NULL) allocator_->Verify();
 #endif
 }
 
 } }  // namespace v8::internal