From 4277535cdc6ce6998cdc273bbe454f9ca2c23037 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Rafael=20=C3=81vila=20de=20Esp=C3=ADndola?= Date: Fri, 17 Apr 2015 11:51:36 -0400 Subject: [PATCH] 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. --- gold/ChangeLog | 10 ++++++++++ gold/gc.cc | 6 +++--- gold/gc.h | 3 +-- gold/object.cc | 2 +- gold/powerpc.cc | 5 +++-- gold/symtab.cc | 2 +- 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 + + * 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 * 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 #include #include "elfcpp.h" @@ -52,7 +51,7 @@ class Garbage_collection typedef Unordered_set Sections_reachable; typedef std::map Section_ref; - typedef std::queue Worklist_type; + typedef std::vector 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::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::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); } -- 2.7.4