[patch][gold] Use LIFO instead of FIFO to implement gc's transitive closure

[Rafael EspÃndola <rafael dot espindola at gmail dot com>]

Hi Cary,

FIFO is harder to implement and has less locality than LIFO. It is
also not necessary to implement a transitive closure, a LIFO works
just as well.

The attached patch then switches the structure used for GC. It
produces identical binaries for chromium and the linking time goes
from 6.216024688 to 6.177238463 seconds.

Cheers,
Rafael

diff --git a/gold/gc.cc b/gold/gc.cc
index 16bdb19..08a2bba 100644
--- a/gold/gc.cc
+++ b/gold/gc.cc
@@ -38,8 +38,8 @@ Garbage_collection::do_transitive_closure()
     {
       // Add elements from the work list to the referenced list
       // one by one.
-      Section_id entry = this->worklist().front();
-      this->worklist().pop();
+      Section_id entry = this->worklist().back();
+      this->worklist().pop_back();
       if (!this->referenced_list().insert(entry).second)
         continue;
       Garbage_collection::Section_ref::iterator find_it = 
@@ -57,7 +57,7 @@ Garbage_collection::do_transitive_closure()
           if (this->referenced_list().find(*it_v)
               == this->referenced_list().end())
             {
-              this->worklist().push(*it_v);   
+              this->worklist().push_back(*it_v);
             }
         }
     }
diff --git a/gold/gc.h b/gold/gc.h
index be4a63c..bf4023d 100644
--- a/gold/gc.h
+++ b/gold/gc.h
@@ -23,7 +23,6 @@
 #ifndef GOLD_GC_H
 #define GOLD_GC_H
 
-#include <queue>
 #include <vector>
 
 #include "elfcpp.h"
@@ -52,7 +51,7 @@ class Garbage_collection
 
   typedef Unordered_set<Section_id, Section_id_hash> Sections_reachable;
   typedef std::map<Section_id, Sections_reachable> Section_ref;
-  typedef std::queue<Section_id> Worklist_type;
+  typedef std::vector<Section_id> Worklist_type;
   // This maps the name of the section which can be represented as a C
   // identifier (cident) to the list of sections that have that name.
   // Different object files can have cident sections with the same name.
diff --git a/gold/object.cc b/gold/object.cc
index f28305b..18c6670 100644
--- a/gold/object.cc
+++ b/gold/object.cc
@@ -1602,7 +1602,7 @@ Sized_relobj_file<size, big_endian>::do_layout(Symbol_table* symtab,
 	      || shdr.get_sh_type() == elfcpp::SHT_INIT_ARRAY
 	      || shdr.get_sh_type() == elfcpp::SHT_FINI_ARRAY)
 	    {
-	      symtab->gc()->worklist().push(Section_id(this, i));
+	      symtab->gc()->worklist().push_back(Section_id(this, i));
 	    }
 	  // If the section name XXX can be represented as a C identifier
 	  // it cannot be discarded if there are references to
diff --git a/gold/powerpc.cc b/gold/powerpc.cc
index 47bdc13..fddf3fa 100644
--- a/gold/powerpc.cc
+++ b/gold/powerpc.cc
@@ -238,7 +238,7 @@ public:
       if (this->opd_ent_[i].gc_mark)
 	{
 	  unsigned int shndx = this->opd_ent_[i].shndx;
-	  symtab->gc()->worklist().push(Section_id(this, shndx));
+	  symtab->gc()->worklist().push_back(Section_id(this, shndx));
 	}
   }
 
@@ -6434,7 +6434,8 @@ Target_powerpc<size, big_endian>::do_gc_mark_symbol(
 	  if (ppc_object->opd_valid())
 	    {
 	      unsigned int dst_indx = ppc_object->get_opd_ent(dst_off);
-	      symtab->gc()->worklist().push(Section_id(ppc_object, dst_indx));
+	      symtab->gc()->worklist().push_back(Section_id(ppc_object,
+                                                            dst_indx));
 	    }
 	  else
 	    ppc_object->add_gc_mark(dst_off);
diff --git a/gold/symtab.cc b/gold/symtab.cc
index 045327a..6a74b49 100644
--- a/gold/symtab.cc
+++ b/gold/symtab.cc
@@ -646,7 +646,7 @@ Symbol_table::gc_mark_symbol(Symbol* sym)
   if (is_ordinary && shndx != elfcpp::SHN_UNDEF)
     {
       gold_assert(this->gc_!= NULL);
-      this->gc_->worklist().push(Section_id(sym->object(), shndx));
+      this->gc_->worklist().push_back(Section_id(sym->object(), shndx));
     }
   parameters->target().gc_mark_symbol(this, sym);
 }