ARM64: Avoid iterating through all unresolved branch infos when many are pending.

src/arm64/assembler-arm64.cc

 // Copyright 2013 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
@@ skipping 527 matching lines @@
       offset = kStartOfLabelLinkChain;
     }
     // The instruction at pc is now the last link in the label's chain.
     label->link_to(pc_offset());
   }
 
   return offset;
 }
 
 
+void Assembler::DeleteUnresolvedBranchInfoForLabelIterate(Label* label) {
+  std::multimap<int, FarBranchInfo>::iterator it_tmp, it;
+  it = unresolved_branches_.begin();
+  while (it != unresolved_branches_.end()) {
+    it_tmp = it++;
+    if (it_tmp->second.label_ == label) {
+      CHECK(it_tmp->first >= pc_offset());
+      unresolved_branches_.erase(it_tmp);
+    }
+  }
+}
+
+
+void Assembler::DeleteUnresolvedBranchInfoForLabelTraverse(Label* label) {
+  ASSERT(label->is_linked());
+  CheckLabelLinkChain(label);
+
+  int link_offset = label->pos();
+  int link_pcoffset;
+  bool end_of_chain = false;
+
+  while (!end_of_chain) {
+    Instruction * link = InstructionAt(link_offset);
+    link_pcoffset = link->ImmPCOffset();
+
+    // ADR instructions are not handled by veneers.
+    if (link->IsImmBranch()) {
+      int max_reachable_pc = InstructionOffset(link) +
+          Instruction::ImmBranchRange(link->BranchType());
+      typedef std::multimap<int, FarBranchInfo>::iterator unresolved_info_it;
+      std::pair<unresolved_info_it, unresolved_info_it> range;
+      range = unresolved_branches_.equal_range(max_reachable_pc);
+      unresolved_info_it it;
+      for (it = range.first; it != range.second; ++it) {
+        if (it->second.pc_offset_ == link_offset) {
+          unresolved_branches_.erase(it);
+          break;
+        }
+      }
+    }
+
+    end_of_chain = (link_pcoffset == 0);
+    link_offset = link_offset + link_pcoffset;
+  }
+}
+
+
 void Assembler::DeleteUnresolvedBranchInfoForLabel(Label* label) {
   if (unresolved_branches_.empty()) {
     ASSERT(next_veneer_pool_check_ == kMaxInt);
     return;
   }
 
   if (label->is_linked()) {
-    // Branches to this label will be resolved when the label is bound below.
-    std::multimap<int, FarBranchInfo>::iterator it_tmp, it;
-    it = unresolved_branches_.begin();
-    while (it != unresolved_branches_.end()) {
-      it_tmp = it++;
-      if (it_tmp->second.label_ == label) {
-        CHECK(it_tmp->first >= pc_offset());
-        unresolved_branches_.erase(it_tmp);
-      }
+    // Branches to this label will be resolved when the label is bound, normally
+    // just after all the associated info has been deleted.
+
+    // If there are too many unresolved branches pending, avoid iterating
+    // through all of them to find the information to delete.
+    static const int kMaxNInfoIterate = 128;
+
+    if (unresolved_branches_.size() < kMaxNInfoIterate) {
+      DeleteUnresolvedBranchInfoForLabelIterate(label);
+    } else {
+      DeleteUnresolvedBranchInfoForLabelTraverse(label);

[ulan, 2014/04/07 13:24:41]

Ignoring ADR instructions, chain length <= unresolved_branches_.size(), right?
Then why not always use this function?

[Alexandre Rames, 2014/04/09 13:22:06]

Yes.
I initially kept it as I was worried that digging through the chain could be
more expensive than a simple iteration. Removed the iterative function to always
traverse the label chain.

     }
   }
   if (unresolved_branches_.empty()) {
     next_veneer_pool_check_ = kMaxInt;
   } else {
     next_veneer_pool_check_ =
       unresolved_branches_first_limit() - kVeneerDistanceCheckMargin;
   }
 }
 
@@ skipping 2309 matching lines @@
     adr(rd, 0);
     MovInt64(scratch, target_offset);
     add(rd, rd, scratch);
   }
 }
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_TARGET_ARCH_ARM64