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

src/arm64/assembler-arm64.cc

Index: src/arm64/assembler-arm64.cc
diff --git a/src/arm64/assembler-arm64.cc b/src/arm64/assembler-arm64.cc
index 5695623afd54e033ca6ec9ebfb349cef159b14c4..43bea9f160f8e0e32ed151fda5517e42be164dd5 100644
--- a/src/arm64/assembler-arm64.cc
+++ b/src/arm64/assembler-arm64.cc
@@ -545,6 +545,53 @@ int Assembler::LinkAndGetByteOffsetTo(Label* label) {
 }
 
 
+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);
@@ -552,15 +599,17 @@ void Assembler::DeleteUnresolvedBranchInfoForLabel(Label* label) {
   }
 
   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()) {