Streamline JumpTarget::ComputeEntryFrame by removing the separate loop...

src/jump-target.cc

 // Copyright 2009 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 83 matching lines @@
 
 FrameElement* JumpTarget::Combine(FrameElement* left, FrameElement* right) {
   // Given a pair of non-null frame element pointers, return one of
   // them as an entry frame candidate or null if they are
   // incompatible.
 
   // If either is invalid, the result is.
   if (!left->is_valid()) return left;
   if (!right->is_valid()) return right;
 
-  // If they have the same value, the result is the same.  If either
-  // is unsynced, the result is.
+  // If they have the exact same location, the result is in that
+  // location, otherwise we reallocate.  If either is unsynced, the
+  // result is.  The result static type is the merge of the static
+  // types.  It's safe to set it on one of the frame elements, and
+  // harmless too (because we are only going to merge the reaching
+  // frames and will ensure that the types are coherent, and changing
+  // the static type does not emit code).
 
-  if (left->is_memory() && right->is_memory()) return left;
+  StaticType type = left->static_type().merge(right->static_type());
+  if (left->is_memory() && right->is_memory()) {
+    left->set_static_type(type);
+    return left;
+  }
 
   if (left->is_register() && right->is_register() &&

[Lasse Reichstein, 2009/05/12 14:45:38]

This function looks like a lot of duplicated code. The for conditions are
separate, even though they do almost, or exactly, the same. It's not easy to see
that they are all merely checking whether the two FrameElements are compatible,
and if they are, pick the unsynced one, if any.
When the bodies were simpler, it might not have been a problem, but I do think
it is now.

It seems like it could be simplified (of a sort) by combining the tree
conditions that all have the same body.

Something like: 
 if (... || ... || ...) {
   FrameElement result = left->is_synced ? right : left;
   result->set_static_type(static_type);
   return result;
 }
Perhaps make some utility function for the test, or for parts of the it. The one
at this comment looks like it could be named IsSameRegister.

You can even add the first test as well, since it doesn't seem to matter which
element is used. 

       left->reg().is(right->reg())) {
     if (!left->is_synced()) {
+      left->set_static_type(type);
       return left;
     } else {
+      right->set_static_type(type);
       return right;
     }
   }
 
   if (left->is_constant() &&
       right->is_constant() &&
       left->handle().is_identical_to(right->handle())) {
     if (!left->is_synced()) {
+      left->set_static_type(type);
       return left;
     } else {
+      right->set_static_type(type);
       return right;
     }
   }
 
   if (left->is_copy() &&
       right->is_copy() &&
       left->index() == right->index()) {
     if (!left->is_synced()) {
+      left->set_static_type(type);
       return left;
     } else {
+      right->set_static_type(type);
       return right;
     }
   }
 
   // Otherwise they are incompatible and we will reallocate them.
   return NULL;
 }
 
 
 void JumpTarget::ComputeEntryFrame(int mergable_elements) {
@@ skipping 13 matching lines @@
   // down) to a frame high-water mark (counted from the bottom up).
   // Elements strictly above the high-water index will be mergable in
   // entry frames for bidirectional jump targets.
   int high_water_mark = (mergable_elements == kAllElements)
       ? VirtualFrame::kIllegalIndex  // All frame indices are above this.
       : length - mergable_elements - 1;  // Top index if m_e == 0.
 
   // Initially populate the list of elements based on the initial
   // frame.
   for (int i = 0; i < length; i++) {
     FrameElement element = initial_frame->elements_[i];

[Lasse Reichstein, 2009/05/12 14:45:38]

If we look this element up again later, would it perhaps be easier to store a
pointer instead of making a copy?

-    // We do not allow copies or constants in bidirectional frames.
-    if (direction_ == BIDIRECTIONAL && i > high_water_mark &&
-        (element.is_constant() || element.is_copy())) {
-      elements.Add(NULL);
-    } else {
-      elements.Add(&initial_frame->elements_[i]);
+    // We do not allow copies or constants in bidirectional frames.  All
+    // elements above the water mark on bidirectional frames have
+    // unknown static types.
+    if (direction_ == BIDIRECTIONAL && i > high_water_mark) {
+      if (element.is_constant() || element.is_copy()) {
+        elements.Add(NULL);
+        continue;
+      }
+      // It's safe to change the static type on the initial frame
+      // element, see comment in JumpTarget::Combine.
+      initial_frame->elements_[i].set_static_type(StaticType::unknown());
     }
+    elements.Add(&initial_frame->elements_[i]);
   }
 
   // Compute elements based on the other reaching frames.
   if (reaching_frames_.length() > 1) {
     for (int i = 0; i < length; i++) {
       for (int j = 1; j < reaching_frames_.length(); j++) {
         FrameElement* element = elements[i];
 
         // Element computation is monotonic: new information will not
         // change our decision about undetermined or invalid elements.
         if (element == NULL || !element->is_valid()) break;
 
         elements[i] = Combine(element, &reaching_frames_[j]->elements_[i]);

[Lasse Reichstein, 2009/05/12 14:45:38]

Why do we read the element on each round of the inner loop, instead of reading
it before entering the loop, updating only the variable during the loop, and
then setting it back after the loop?

       }
     }
   }
 
   // Build the new frame.  A freshly allocated frame has memory elements
   // for the parameters and some platform-dependent elements (e.g.,
   // return address).  Replace those first.
   entry_frame_ = new VirtualFrame(cgen_);
   int index = 0;
   for (; index < entry_frame_->elements_.length(); index++) {
@@ skipping 24 matching lines @@
       } else if (elements[index]->is_copy()) {
         entry_frame_->elements_[elements[index]->index()].set_copied();
       }
     }
   }
 
   // Allocate any still-undetermined frame elements to registers or
   // memory, from the top down.
   for (int i = length - 1; i >= 0; i--) {
     if (elements[i] == NULL) {
+      // Loop over all the reaching frames to check whether the element
+      // is synced on all frames, to count the registers it occupies,
+      // and to compute a merged static type.
+      bool is_synced = true;
+      RegisterFile candidate_registers;
+      int best_count = kMinInt;
+      int best_reg_code = no_reg.code_;
+
+      StaticType type;  // Initially invalid.
+      if (direction_ != BIDIRECTIONAL || i < high_water_mark) {
+        type = reaching_frames_[0]->elements_[i].static_type();
+      }
+
+      for (int j = 0; j < reaching_frames_.length(); j++) {
+        FrameElement element = reaching_frames_[j]->elements_[i];
+        is_synced = is_synced && element.is_synced();
+        if (element.is_register() && !entry_frame_->is_used(element.reg())) {
+          // Count the register occurrence and remember it if better
+          // than the previous best.
+          candidate_registers.Use(element.reg());
+          if (candidate_registers.count(element.reg()) > best_count) {
+            best_count = candidate_registers.count(element.reg());
+            best_reg_code = element.reg().code();
+          }
+        }
+        type = type.merge(element.static_type());
+      }
+
       // If the value is synced on all frames, put it in memory.  This
       // costs nothing at the merge code but will incur a
       // memory-to-register move when the value is needed later.
-      bool is_synced = true;
-      for (int j = 0; is_synced && j < reaching_frames_.length(); j++) {
-        is_synced = reaching_frames_[j]->elements_[i].is_synced();
+      if (is_synced) {
+        // Already recorded as a memory element.
+        entry_frame_->elements_[i].set_static_type(type);
+        continue;
       }
 
-      // There is nothing to be done if the elements are all synced.
-      // It is already recorded as a memory element.
-      if (is_synced) continue;
-
-      // Choose an available register.  Prefer ones that the element
-      // is already occupying on some reaching frame.
-      RegisterFile candidate_registers;
-      int max_count = kMinInt;
-      int best_reg_code = no_reg.code_;
-
-      for (int j = 0; j < reaching_frames_.length(); j++) {
-        FrameElement element = reaching_frames_[j]->elements_[i];
-        if (element.is_register() &&
-            !entry_frame_->is_used(element.reg())) {
-          candidate_registers.Use(element.reg());
-          if (candidate_registers.count(element.reg()) > max_count) {
-            max_count = candidate_registers.count(element.reg());
-            best_reg_code = element.reg().code();
-          }
-        }
-      }
-      // If there was no preferred choice consider any free register.
+      // Try to put it in a register.  If there was no best choice
+      // consider any free register.
       if (best_reg_code == no_reg.code_) {
         for (int j = 0; j < kNumRegisters; j++) {
           if (!entry_frame_->is_used(j) && !RegisterAllocator::IsReserved(j)) {
             best_reg_code = j;
             break;
           }
         }
       }
 
-      if (best_reg_code != no_reg.code_) {
+      if (best_reg_code == no_reg.code_) {
+        // If there was no register found, the element is already
+        // recorded as in memory.
+        entry_frame_->elements_[i].set_static_type(type);
+      } else {
         // If there was a register choice, use it.  Preserve the copied
-        // flag on the element.
+        // flag on the element.  Set the static type as computed.
         bool is_copied = entry_frame_->elements_[i].is_copied();
         Register reg = { best_reg_code };
         entry_frame_->elements_[i] =
             FrameElement::RegisterElement(reg,
                                           FrameElement::NOT_SYNCED);
         if (is_copied) entry_frame_->elements_[i].set_copied();
+        entry_frame_->elements_[i].set_static_type(type);
         entry_frame_->register_locations_[best_reg_code] = i;
       }
-      // If there was no register found, the element is already
-      // recorded as in memory.
-    }
-  }
-
-  // Set the static type of frame elements.
-  for (int i = 0; i < length; i++) {
-    FrameElement* current = &entry_frame_->elements_[i];
-    if (direction_ == BIDIRECTIONAL && i >= high_water_mark) {
-      current->set_static_type(StaticType::unknown());
-    } else {
-      StaticType merged_type = reaching_frames_[0]->elements_[i].static_type();
-      for (int j = 1, n = reaching_frames_.length();
-           !merged_type.is_unknown() && j < n;
-           j++) {
-        merged_type =
-            merged_type.merge(reaching_frames_[j]->elements_[i].static_type());
-      }
-      current->set_static_type(merged_type);
     }
   }
 
   // Fill in the other fields of the entry frame.
   entry_frame_->local_count_ = initial_frame->local_count_;
   entry_frame_->frame_pointer_ = initial_frame->frame_pointer_;
 
   // The stack pointer is at the highest synced element or the base of
   // the expression stack.
   int stack_pointer = length - 1;
@@ skipping 419 matching lines @@
   temp.CopyTo(this);
   temp.Reset();  // So the destructor does not deallocate virtual frames.
 
 #ifdef DEBUG
   is_shadowing_ = false;
 #endif
 }
 
 
 } }  // namespace v8::internal