Use LIFO instead of FIFO to implement gc's transitive closure.

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.

6 files changed, 19 insertions, 9 deletions

diff --git a/gold/ChangeLog b/gold/ChangeLog
index 25b73c0..789ba66 100644
--- a/gold/ChangeLog
+++ b/gold/ChangeLog
@@ -1,3 +1,13 @@
+2015-04-17  Rafael Ávila de Espíndola <rafael.espindola@gmail.com>
+
+	* gc.cc (Garbage_collection::do_transitive_closure): Use back and
+	push_back.
+	* gc.h (Garbage_collection): Use a std::vector instead of a std::queue.
+	* object.cc (Sized_relobj_file::do_layout): Use push_back.
+	* powerpc.cc (process_gc_mark): Use push_back.
+	(Target_powerpc::do_gc_mark_symbol): Use push_back.
+	* symtab.cc (Symbol_table::gc_mark_symbol): Use push_back.
+
 2015-04/16  Han Shen  <shenhan@google.com>
 
     * aarch64.cc (AArch64_insn_utilities): New utility class.
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 8ec8f73..d4f40c8 100644
--- a/gold/symtab.cc
+++ b/gold/symtab.cc
@@ -649,7 +649,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);
 }