2009-01-20 Sriraman Tallam <tmsriram@google.com>

	* Makefile.am (CCFILES): Add gc.cc.
	(HFILES): Add gc.h.
	* Makefile.in: Regenerate.
	* gold.cc (Gc_runner): New class.
	(queue_initial_tasks): Call garbage collection related tasks
	when corresponding options are invoked.
	(queue_middle_gc_tasks): New function.
	(queue_middle_tasks): Reorder tasks to allow relocs to be read and
	processed early before laying out sections during garbage collection.
	* gold.h (queue_middle_gc_tasks): New function.
	(is_prefix_of): Move from "layout.cc".
	* i386.cc (Target_i386::gc_process_relocs): New function.
	* layout.cc (is_prefix_of): Remove. Move to "gold.h"
	* main.cc (main): Create object of class "Garbage_collection".
	* object.cc (Relobj::copy_symbols_data): New function.
	(Relobj::is_section_name_included): New function.
	(Sized_relobj::do_layout): Allow this function to be called twice
	during garbage collection and defer layout of section during the
	first call.
	* object.h (Relobj::get_symbols_data): New function.
	(Relobj::is_section_name_included): New function.
	(Relobj::copy_symbols_data): New function.
	(Relobj::set_symbols_data): New function.
	(Relobj::get_relocs_data): New function.
	(Relobj::set_relocs_data): New function.
	(Relobj::is_output_section_offset_invalid): New pure virtual function.
	(Relobj::gc_process_relocs): New function.
	(Relobj::do_gc_process_relocs): New pure virtual function.
	(Relobj::sd_): New data member.
	(Sized_relobj::is_output_section_offset_invalid): New function.
	(Sized_relobj::do_gc_process_relocs): New function.
	* options.h (General_options::gc_sections): Modify to not be a no-op.
	(General_options::print_gc_sections): New option.
	* plugin.cc (Plugin_finish::run): Remove function call to
	Plugin_manager::layout_deferred_objects.  Move it to "gold.cc".
	* powerpc.cc (Target_powerpc::gc_process_relocs): New function.
	* reloc.cc (Read_relocs::run): Add task to process relocs and
	determine unreferenced sections when doing garbage collection.
	(Gc_process_relocs): New class.
	(Sized_relobj::do_gc_process_relocs): New function.
	(Sized_relobj::do_scan_relocs): Don't try to scan the relocs for
	sections that are garbage collected.
	* reloc.h (Gc_process_relocs): New class.
	* sparc.cc (Target_sparc::gc_process_relocs): New function.
	* symtab.cc (Symbol::should_add_dynsym_entry): Do not add entries for
	symbols whose corresponding sections are garbage collected.
	(Symbol_table::Symbol_table): Add new parameter for the garbage
	collection object.
	(Symbol_table::gc_mark_undef_symbols): New function.
	(Symbol_table::gc_mark_symbol_for_shlib): New function.
	(Symbol_table::gc_mark_dyn_syms): New function.
	(Symbol_table::resolve): Do not treat symbols seen in dynamic objects
	as garbage.
	(Symbol_table::add_from_object): Likewise.
	(Symbol_table::add_from_relobj): When building shared objects, do not
	treat externally visible symbols as garbage.
	(Symbol_table::sized_finalize_symbol): Do not check dynamic symbol
	table information for static and relocatable links.
	* symtab.h (Symbol_table::set_gc): New function.
	(Symbol_table::gc): New function.
	(Symbol_table::gc_mark_undef_symbols): New function.
	(Symbol_table::gc_mark_symbol_for_shlib): New function.
	(Symbol_table::gc_mark_dyn_syms): New function.
	(Symbol_table::gc_): New data member.
	* target.h (Sized_target::gc_process_relocs): New pure virtual
	function.
	* x86_64.cc (Target_x86_64::gc_process_relocs): New function.
	* testsuite/testfile.cc (Target_test::gc_process_relocs): New function.

23 files changed, 1495 insertions, 138 deletions

diff --git a/gold/ChangeLog b/gold/ChangeLog
index 90af8cb..b8123c4 100644
--- a/gold/ChangeLog
+++ b/gold/ChangeLog
@@ -1,3 +1,74 @@
+2009-01-20  Sriraman Tallam <tmsriram@google.com>
+
+	* Makefile.am (CCFILES): Add gc.cc.
+	(HFILES): Add gc.h.
+	* Makefile.in: Regenerate.
+	* gold.cc (Gc_runner): New class.
+	(queue_initial_tasks): Call garbage collection related tasks
+	when corresponding options are invoked.
+	(queue_middle_gc_tasks): New function.
+	(queue_middle_tasks): Reorder tasks to allow relocs to be read and
+	processed early before laying out sections during garbage collection.
+	* gold.h (queue_middle_gc_tasks): New function.
+	(is_prefix_of): Move from "layout.cc".
+	* i386.cc (Target_i386::gc_process_relocs): New function.
+	* layout.cc (is_prefix_of): Remove. Move to "gold.h"
+	* main.cc (main): Create object of class "Garbage_collection".
+	* object.cc (Relobj::copy_symbols_data): New function.
+	(Relobj::is_section_name_included): New function.
+	(Sized_relobj::do_layout): Allow this function to be called twice 
+	during garbage collection and defer layout of section during the 
+	first call.
+	* object.h (Relobj::get_symbols_data): New function.
+	(Relobj::is_section_name_included): New function.
+	(Relobj::copy_symbols_data): New function.
+	(Relobj::set_symbols_data): New function.
+	(Relobj::get_relocs_data): New function.
+	(Relobj::set_relocs_data): New function.
+	(Relobj::is_output_section_offset_invalid): New pure virtual function.
+	(Relobj::gc_process_relocs): New function.
+	(Relobj::do_gc_process_relocs): New pure virtual function.
+	(Relobj::sd_): New data member.
+	(Sized_relobj::is_output_section_offset_invalid): New function.
+	(Sized_relobj::do_gc_process_relocs): New function.
+	* options.h (General_options::gc_sections): Modify to not be a no-op.
+	(General_options::print_gc_sections): New option.
+	* plugin.cc (Plugin_finish::run): Remove function call to
+	Plugin_manager::layout_deferred_objects.  Move it to "gold.cc".
+	* powerpc.cc (Target_powerpc::gc_process_relocs): New function.
+	* reloc.cc (Read_relocs::run): Add task to process relocs and
+	determine unreferenced sections when doing garbage collection.
+	(Gc_process_relocs): New class.
+	(Sized_relobj::do_gc_process_relocs): New function.
+	(Sized_relobj::do_scan_relocs): Don't try to scan the relocs for
+	sections that are garbage collected.
+	* reloc.h (Gc_process_relocs): New class.
+	* sparc.cc (Target_sparc::gc_process_relocs): New function.
+	* symtab.cc (Symbol::should_add_dynsym_entry): Do not add entries for
+	symbols whose corresponding sections are garbage collected.
+	(Symbol_table::Symbol_table): Add new parameter for the garbage
+	collection object.
+	(Symbol_table::gc_mark_undef_symbols): New function.
+	(Symbol_table::gc_mark_symbol_for_shlib): New function.
+	(Symbol_table::gc_mark_dyn_syms): New function.
+	(Symbol_table::resolve): Do not treat symbols seen in dynamic objects
+	as garbage.
+	(Symbol_table::add_from_object): Likewise.
+	(Symbol_table::add_from_relobj): When building shared objects, do not
+	treat externally visible symbols as garbage.
+	(Symbol_table::sized_finalize_symbol): Do not check dynamic symbol
+	table information for static and relocatable links.
+	* symtab.h (Symbol_table::set_gc): New function.
+	(Symbol_table::gc): New function.
+	(Symbol_table::gc_mark_undef_symbols): New function.
+	(Symbol_table::gc_mark_symbol_for_shlib): New function.
+	(Symbol_table::gc_mark_dyn_syms): New function.
+	(Symbol_table::gc_): New data member.
+	* target.h (Sized_target::gc_process_relocs): New pure virtual 
+	function.
+	* x86_64.cc (Target_x86_64::gc_process_relocs): New function.
+	* testsuite/testfile.cc (Target_test::gc_process_relocs): New function.
+
 2009-01-20  Chris Faylor <me.sourceware@sourceware.org>
 
 	* options.h (General_options::gc_sections): Define as a no-op for now.
diff --git a/gold/Makefile.am b/gold/Makefile.am
index 74db37a..aab1528 100644
--- a/gold/Makefile.am
+++ b/gold/Makefile.am
@@ -48,6 +48,7 @@ CCFILES = \
 	errors.cc \
 	expression.cc \
 	fileread.cc \
+        gc.cc \
 	gold.cc \
 	gold-threads.cc \
 	layout.cc \
@@ -86,6 +87,7 @@ HFILES = \
 	ehframe.h \
 	errors.h \
 	fileread.h \
+        gc.h \
 	gold.h \
 	gold-threads.h \
 	layout.h \
diff --git a/gold/Makefile.in b/gold/Makefile.in
index f6a80d0..a071bcf 100644
--- a/gold/Makefile.in
+++ b/gold/Makefile.in
@@ -79,7 +79,8 @@ am__objects_1 = archive.$(OBJEXT) binary.$(OBJEXT) common.$(OBJEXT) \
 	cref.$(OBJEXT) defstd.$(OBJEXT) descriptors.$(OBJEXT) \
 	dirsearch.$(OBJEXT) dynobj.$(OBJEXT) dwarf_reader.$(OBJEXT) \
 	ehframe.$(OBJEXT) errors.$(OBJEXT) expression.$(OBJEXT) \
-	fileread.$(OBJEXT) gold.$(OBJEXT) gold-threads.$(OBJEXT) \
+	fileread.$(OBJEXT) gc.$(OBJEXT) \
+      gold.$(OBJEXT) gold-threads.$(OBJEXT) \
 	layout.$(OBJEXT) mapfile.$(OBJEXT) merge.$(OBJEXT) \
 	object.$(OBJEXT) options.$(OBJEXT) output.$(OBJEXT) \
 	parameters.$(OBJEXT) plugin.$(OBJEXT) readsyms.$(OBJEXT) \
@@ -330,6 +331,7 @@ CCFILES = \
 	errors.cc \
 	expression.cc \
 	fileread.cc \
+        gc.cc \
 	gold.cc \
 	gold-threads.cc \
 	layout.cc \
@@ -368,6 +370,7 @@ HFILES = \
 	ehframe.h \
 	errors.h \
 	fileread.h \
+        gc.h \
 	gold.h \
 	gold-threads.h \
 	layout.h \
diff --git a/gold/gc.cc b/gold/gc.cc
new file mode 100644
index 0000000..7a594a5
--- /dev/null
+++ b/gold/gc.cc
@@ -0,0 +1,74 @@
+// gc.cc -- garbage collection of unused sections
+
+// Copyright 2009 Free Software Foundation, Inc.
+// Written by Sriraman Tallam <tmsriram@google.com>.
+
+// This file is part of gold.
+
+// This program is free software; you can redistribute it and/or modify
+// it under the terms of the GNU General Public License as published by
+// the Free Software Foundation; either version 3 of the License, or
+// (at your option) any later version.
+
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this program; if not, write to the Free Software
+// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+// MA 02110-1301, USA.
+
+
+#include "gold.h"
+#include "object.h"
+#include "gc.h"
+#include "symtab.h"
+
+namespace gold
+{
+
+// Garbage collection uses a worklist style algorithm to determine the 
+// transitive closure of all referenced sections.
+void 
+Garbage_collection::do_transitive_closure()
+{
+  while (!this->worklist().empty())
+    {
+      // Add elements from the work list to the referenced list
+      // one by one.
+      Section_id entry = this->worklist().front();
+      this->worklist().pop();
+      if (this->referenced_list().find(entry)
+          == this->referenced_list().end()) 
+        {
+          this->referenced_list().insert(entry);
+        }
+      else
+        {
+          continue;
+        }
+      Garbage_collection::Section_ref::iterator find_it = 
+                this->section_reloc_map().find(entry);
+      if (find_it == this->section_reloc_map().end()) 
+          continue;
+      Garbage_collection::Sections_reachable v = find_it->second;
+      // Scan the vector of references for each work_list entry. 
+      for (Garbage_collection::Sections_reachable::iterator it_v = v.begin();
+           it_v != v.end();
+           ++it_v)
+        {
+          // Do not add already processed sections to the work_list. 
+          if (this->referenced_list().find(*it_v)
+              == this->referenced_list().end())
+            {
+              this->worklist().push(*it_v);   
+            }
+        }
+    }
+  this->worklist_ready();
+}
+
+} // End namespace gold.
+
diff --git a/gold/gc.h b/gold/gc.h
new file mode 100644
index 0000000..b7d520f
--- /dev/null
+++ b/gold/gc.h
@@ -0,0 +1,209 @@
+// gc.h -- garbage collection of unused sections
+
+// Copyright 2009 Free Software Foundation, Inc.
+// Written by Sriraman Tallam <tmsriram@google.com>.
+
+// This file is part of gold.
+
+// This program is free software; you can redistribute it and/or modify
+// it under the terms of the GNU General Public License as published by
+// the Free Software Foundation; either version 3 of the License, or
+// (at your option) any later version.
+
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this program; if not, write to the Free Software
+// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
+// MA 02110-1301, USA.
+
+#ifndef GOLD_GC_H
+#define GOLD_GC_H
+
+#include <queue>
+
+#include "elfcpp.h"
+#include "symtab.h"
+
+namespace gold
+{
+
+class Object;
+
+template<int size, bool big_endian>
+class Sized_relobj;
+
+template<int sh_type, int size, bool big_endian>
+class Reloc_types;
+
+class Output_section;
+class General_options;
+class Layout;
+
+typedef std::pair<Object *, unsigned int> Section_id;
+
+class Garbage_collection
+{
+  struct Section_id_hash
+  {
+    size_t operator()(const Section_id& loc) const
+    { return reinterpret_cast<uintptr_t>(loc.first) ^ loc.second; }
+  };
+
+  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;
+
+  public :  
+    Garbage_collection() 
+      :is_worklist_ready_(false)
+    { }
+
+    // Accessor methods for the private members.
+
+    Sections_reachable&
+    referenced_list()
+    { return referenced_list_; }
+
+    Section_ref&
+    section_reloc_map()
+    { return section_reloc_map_; }
+
+    Worklist_type&
+    worklist()
+    { return work_list_; }
+ 
+    bool
+    is_worklist_ready()
+    { return is_worklist_ready_; }
+
+    void
+    worklist_ready()
+    { is_worklist_ready_ = true; }
+
+    void
+    do_transitive_closure();
+
+  private :
+    Worklist_type work_list_;
+    bool is_worklist_ready_;
+    Section_ref section_reloc_map_;
+    Sections_reachable referenced_list_;
+};
+
+// Data to pass between successive invocations of do_layout
+// in object.cc while garbage collecting.  This data structure
+// is filled by using the data from Read_symbols_data.
+
+struct Symbols_data
+{
+  // Section headers.
+  unsigned char* section_headers_data;
+  // Section names.
+  unsigned char* section_names_data;
+  // Size of section name data in bytes.
+  section_size_type section_names_size;
+  // Symbol data.
+  unsigned char* symbols_data;
+  // Size of symbol data in bytes.
+  section_size_type symbols_size;
+  // Offset of external symbols within symbol data.  This structure
+  // sometimes contains only external symbols, in which case this will
+  // be zero.  Sometimes it contains all symbols.
+  section_offset_type external_symbols_offset;
+  // Symbol names.
+  unsigned char* symbol_names_data;
+  // Size of symbol name data in bytes.
+  section_size_type symbol_names_size;
+};
+
+// This function implements the  the generic part of reloc 
+// processing to map a section to all the sections it 
+// references through relocs.  It is used only during garbage 
+// collection.
+
+template<int size, bool big_endian, typename Target_type, int sh_type,
+	 typename Scan>
+inline void
+gc_process_relocs(
+    const General_options& ,
+    Symbol_table* symtab,
+    Layout*,
+    Target_type* ,
+    Sized_relobj<size, big_endian>* object,
+    unsigned int data_shndx,
+    const unsigned char* prelocs,
+    size_t reloc_count,
+    Output_section*,
+    bool ,
+    size_t local_count,
+    const unsigned char* plocal_syms)
+{
+  Object *src_obj, *dst_obj;
+  unsigned int src_indx, dst_indx;
+
+  src_obj = object;
+  src_indx = data_shndx; 
+  
+  typedef typename Reloc_types<sh_type, size, big_endian>::Reloc Reltype;
+  const int reloc_size = Reloc_types<sh_type, size, big_endian>::reloc_size;
+  const int sym_size = elfcpp::Elf_sizes<size>::sym_size;
+
+  for (size_t i = 0; i < reloc_count; ++i, prelocs += reloc_size)
+    {
+      Reltype reloc(prelocs);
+      typename elfcpp::Elf_types<size>::Elf_WXword r_info = reloc.get_r_info();
+      unsigned int r_sym = elfcpp::elf_r_sym<size>(r_info);
+      
+      if (r_sym < local_count)
+        {
+          gold_assert(plocal_syms != NULL);
+          typename elfcpp::Sym<size, big_endian> lsym(plocal_syms
+                                                      + r_sym * sym_size);
+          unsigned int shndx = lsym.get_st_shndx();
+          bool is_ordinary;
+          shndx = object->adjust_sym_shndx(r_sym, shndx, &is_ordinary);
+          if (!is_ordinary) 
+            continue;
+          dst_obj = src_obj;
+          if (shndx == src_indx) 
+            continue;
+          dst_indx = shndx;
+        }
+      else
+        {
+          Symbol* gsym = object->global_symbol(r_sym);
+          gold_assert(gsym != NULL);
+          if (gsym->is_forwarder())
+            gsym = symtab->resolve_forwards(gsym);
+          if (gsym->source() != Symbol::FROM_OBJECT)
+            continue;
+          bool is_ordinary;
+          dst_obj = gsym->object();
+          dst_indx = gsym->shndx(&is_ordinary);
+          if (!is_ordinary)
+            continue;
+        }
+      Section_id p1(src_obj, src_indx);
+      Section_id p2(dst_obj, dst_indx);
+      Garbage_collection::Section_ref::iterator map_it;
+      map_it = symtab->gc()->section_reloc_map().find(p1);
+      if (map_it == symtab->gc()->section_reloc_map().end())
+        {
+          symtab->gc()->section_reloc_map()[p1].insert(p2);
+        }
+      else
+        {
+          Garbage_collection::Sections_reachable& v(map_it->second);
+          v.insert(p2);
+        }
+    }
+  return;
+}
+
+} // End of namespace gold.
+
+#endif
diff --git a/gold/gold.cc b/gold/gold.cc
index 8d86a1b..818a346 100644
--- a/gold/gold.cc
+++ b/gold/gold.cc
@@ -1,6 +1,6 @@
 // gold.cc -- main linker functions
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -122,6 +122,38 @@ Middle_runner::run(Workqueue* workqueue, const Task* task)
 		     this->layout_, workqueue, this->mapfile_);
 }
 
+// This class arranges the tasks to process the relocs for garbage collection.
+
+class Gc_runner : public Task_function_runner 
+{
+  public:
+   Gc_runner(const General_options& options,
+	     const Input_objects* input_objects,
+	     Symbol_table* symtab,
+	     Layout* layout, Mapfile* mapfile)
+    : options_(options), input_objects_(input_objects), symtab_(symtab),
+      layout_(layout), mapfile_(mapfile)
+   { }
+
+  void
+  run(Workqueue*, const Task*);
+
+ private:
+  const General_options& options_;
+  const Input_objects* input_objects_;
+  Symbol_table* symtab_;
+  Layout* layout_;
+  Mapfile* mapfile_;
+};
+
+void
+Gc_runner::run(Workqueue* workqueue, const Task* task)
+{
+  queue_middle_gc_tasks(this->options_, task, this->input_objects_, 
+                        this->symtab_, this->layout_, workqueue, 
+                        this->mapfile_);
+}
+
 // Queue up the initial set of tasks for this link job.
 
 void
@@ -166,13 +198,69 @@ queue_initial_tasks(const General_options& options,
       this_blocker = next_blocker;
     }
 
+  if (parameters->options().relocatable()
+      && parameters->options().gc_sections())
+    gold_error(_("cannot mix -r with garbage collection"));
+
+  if (parameters->options().gc_sections())
+    {
+      workqueue->queue(new Task_function(new Gc_runner(options,
+                                                       input_objects,
+                                                       symtab,
+                                                       layout,
+                                                       mapfile),
+                                         this_blocker,
+                                         "Task_function Gc_runner"));
+    }
+  else
+    {
+      workqueue->queue(new Task_function(new Middle_runner(options,
+                                                           input_objects,
+                                                           symtab,
+                                                           layout,
+                                                           mapfile),
+                                         this_blocker,
+                                         "Task_function Middle_runner"));
+    }
+}
+
+// Queue up a set of tasks to be done before queueing the middle set 
+// of tasks.  This is only necessary when garbage collection 
+// (--gc-sections) of unused sections is desired.  The relocs are read
+// and processed here early to determine the garbage sections before the
+// relocs can be scanned in later tasks.
+
+void
+queue_middle_gc_tasks(const General_options& options,
+		      const Task* ,
+		      const Input_objects* input_objects,
+		      Symbol_table* symtab,
+		      Layout* layout,
+		      Workqueue* workqueue,
+		      Mapfile* mapfile)
+{
+  // Read_relocs for all the objects must be done and processed to find
+  // unused sections before any scanning of the relocs can take place.
+  Task_token* blocker = new Task_token(true);
+  Task_token* symtab_lock = new Task_token(false);
+  for (Input_objects::Relobj_iterator p = input_objects->relobj_begin();
+       p != input_objects->relobj_end();
+       ++p)
+    {
+      // We can read and process the relocations in any order.  
+      blocker->add_blocker();
+      workqueue->queue(new Read_relocs(options, symtab, layout, *p,
+				       symtab_lock, blocker));
+    }
+
+  Task_token* this_blocker = new Task_token(true);
   workqueue->queue(new Task_function(new Middle_runner(options,
-						       input_objects,
-						       symtab,
-						       layout,
-						       mapfile),
-				     this_blocker,
-				     "Task_function Middle_runner"));
+                                                       input_objects,
+                                                       symtab,
+                                                       layout,
+                                                       mapfile),
+                                     this_blocker,
+                                     "Task_function Middle_runner"));
 }
 
 // Queue up the middle set of tasks.  These are the tasks which run
@@ -188,6 +276,70 @@ queue_middle_tasks(const General_options& options,
 		   Workqueue* workqueue,
 		   Mapfile* mapfile)
 {
+  // Add any symbols named with -u options to the symbol table.
+  symtab->add_undefined_symbols_from_command_line();
+
+  // If garbage collection was chosen, relocs have been read and processed
+  // at this point by pre_middle_tasks.  Layout can then be done for all 
+  // objects.
+  if (parameters->options().gc_sections())
+    {
+      // Find the start symbol if any.
+      Symbol* start_sym;
+      if (parameters->options().entry())
+        start_sym = symtab->lookup(parameters->options().entry());
+      else
+        start_sym = symtab->lookup("_start");
+      if (start_sym !=NULL)
+        {
+          bool is_ordinary;
+          unsigned int shndx = start_sym->shndx(&is_ordinary);
+          if (is_ordinary) 
+            {
+              symtab->gc()->worklist().push(
+                Section_id(start_sym->object(), shndx));
+            }
+        }
+      // Symbols named with -u should not be considered garbage.
+      symtab->gc_mark_undef_symbols();
+      gold_assert(symtab->gc() != NULL);
+      // Do a transitive closure on all references to determine the worklist.
+      symtab->gc()->do_transitive_closure();
+      // Call do_layout again to determine the output_sections for all 
+      // referenced input sections.
+      for (Input_objects::Relobj_iterator p = input_objects->relobj_begin();
+           p != input_objects->relobj_end();
+           ++p)
+        {
+          (*p)->layout(symtab, layout, NULL);
+        }
+    }
+  // Layout deferred objects due to plugins.
+  if (parameters->options().has_plugins())
+    {
+      Plugin_manager* plugins = parameters->options().plugins();
+      gold_assert(plugins != NULL);
+      plugins->layout_deferred_objects();
+    }     
+  if (parameters->options().gc_sections())
+    {
+      for (Input_objects::Relobj_iterator p = input_objects->relobj_begin();
+           p != input_objects->relobj_end();
+           ++p)
+        {
+          // Update the value of output_section stored in rd.
+          Read_relocs_data *rd = (*p)->get_relocs_data();
+          for (Read_relocs_data::Relocs_list::iterator q = rd->relocs.begin();
+               q != rd->relocs.end();
+               ++q)
+            {
+              q->output_section = (*p)->output_section(q->data_shndx);
+              q->needs_special_offset_handling = 
+                      (*p)->is_output_section_offset_invalid(q->data_shndx);
+            }
+        }
+    }
+
   // We have to support the case of not seeing any input objects, and
   // generate an empty file.  Existing builds depend on being able to
   // pass an empty archive to the linker and get an empty object file
@@ -240,9 +392,6 @@ queue_middle_tasks(const General_options& options,
   // Define symbols from any linker scripts.
   layout->define_script_symbols(symtab);
 
-  // Add any symbols named with -u options to the symbol table.
-  symtab->add_undefined_symbols_from_command_line();
-
   // Attach sections to segments.
   layout->attach_sections_to_segments();
 
@@ -259,31 +408,48 @@ queue_middle_tasks(const General_options& options,
   // Make sure we have symbols for any required group signatures.
   layout->define_group_signatures(symtab);
 
-  // Read the relocations of the input files.  We do this to find
-  // which symbols are used by relocations which require a GOT and/or
-  // a PLT entry, or a COPY reloc.  When we implement garbage
-  // collection we will do it here by reading the relocations in a
-  // breadth first search by references.
-  //
-  // We could also read the relocations during the first pass, and
-  // mark symbols at that time.  That is how the old GNU linker works.
-  // Doing that is more complex, since we may later decide to discard
-  // some of the sections, and thus change our minds about the types
-  // of references made to the symbols.
   Task_token* blocker = new Task_token(true);
   Task_token* symtab_lock = new Task_token(false);
-  for (Input_objects::Relobj_iterator p = input_objects->relobj_begin();
-       p != input_objects->relobj_end();
-       ++p)
+
+  // If doing garbage collection, the relocations have already been read.
+  // Otherwise, read and scan the relocations.
+  if (parameters->options().gc_sections())
     {
-      // We can read and process the relocations in any order.  But we
-      // only want one task to write to the symbol table at a time.
-      // So we queue up a task for each object to read the
-      // relocations.  That task will in turn queue a task to wait
-      // until it can write to the symbol table.
-      blocker->add_blocker();
-      workqueue->queue(new Read_relocs(options, symtab, layout, *p,
-				       symtab_lock, blocker));
+      for (Input_objects::Relobj_iterator p = input_objects->relobj_begin();
+           p != input_objects->relobj_end();
+           ++p)
+        {
+          blocker->add_blocker();
+          workqueue->queue(new Scan_relocs(options, symtab, layout, *p, 
+                           (*p)->get_relocs_data(),symtab_lock, blocker));
+        }
+    }
+  else
+    {
+      // Read the relocations of the input files.  We do this to find
+      // which symbols are used by relocations which require a GOT and/or
+      // a PLT entry, or a COPY reloc.  When we implement garbage
+      // collection we will do it here by reading the relocations in a
+      // breadth first search by references.
+      //
+      // We could also read the relocations during the first pass, and
+      // mark symbols at that time.  That is how the old GNU linker works.
+      // Doing that is more complex, since we may later decide to discard
+      // some of the sections, and thus change our minds about the types
+      // of references made to the symbols.
+      for (Input_objects::Relobj_iterator p = input_objects->relobj_begin();
+           p != input_objects->relobj_end();
+           ++p)
+        {
+          // We can read and process the relocations in any order.  But we
+          // only want one task to write to the symbol table at a time.
+          // So we queue up a task for each object to read the
+          // relocations.  That task will in turn queue a task to wait
+          // until it can write to the symbol table.
+          blocker->add_blocker();
+          workqueue->queue(new Read_relocs(options, symtab, layout, *p,
+                   symtab_lock, blocker));
+        }
     }
 
   // Allocate common symbols.  This requires write access to the
diff --git a/gold/gold.h b/gold/gold.h
index 63df994..7e38668 100644
--- a/gold/gold.h
+++ b/gold/gold.h
@@ -1,6 +1,6 @@
 // gold.h -- general definitions for gold   -*- C++ -*-
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -259,6 +259,18 @@ queue_initial_tasks(const General_options&,
 		    Layout*,
 		    Mapfile*);
 
+// Queue up the set of tasks to be done before
+// the middle set of tasks.  Only used when garbage
+// collection is to be done. 
+extern void
+queue_middle_gc_tasks(const General_options&,
+                      const Task*,
+                      const Input_objects*,
+                      Symbol_table*,
+                      Layout*,
+                      Workqueue*,
+                      Mapfile*);
+
 // Queue up the middle set of tasks.
 extern void
 queue_middle_tasks(const General_options&,
@@ -278,6 +290,12 @@ queue_final_tasks(const General_options&,
 		  Workqueue*,
 		  Output_file* of);
 
+inline bool
+is_prefix_of(const char* prefix, const char* str)
+{
+  return strncmp(prefix, str, strlen(prefix)) == 0;
+}
+
 } // End namespace gold.
 
 #endif // !defined(GOLD_GOLD_H)
diff --git a/gold/i386.cc b/gold/i386.cc
index 8a5558e..3779d4e 100644
--- a/gold/i386.cc
+++ b/gold/i386.cc
@@ -1,6 +1,6 @@
 // i386.cc -- i386 target support for gold.
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -62,6 +62,22 @@ class Target_i386 : public Sized_target<32, false>
       got_mod_index_offset_(-1U), tls_base_symbol_defined_(false)
   { }
 
+  // Process the relocations to determine unreferenced sections for 
+  // garbage collection.
+  void
+  gc_process_relocs(const General_options& options,
+                    Symbol_table* symtab,
+                    Layout* layout,
+                    Sized_relobj<32, false>* object,
+                    unsigned int data_shndx,
+                    unsigned int sh_type,
+                    const unsigned char* prelocs,
+                    size_t reloc_count,
+                    Output_section* output_section,
+                    bool needs_special_offset_handling,
+                    size_t local_symbol_count,
+                    const unsigned char* plocal_symbols);
+
   // Scan the relocations to look for symbol adjustments.
   void
   scan_relocs(const General_options& options,
@@ -1456,6 +1472,38 @@ Target_i386::Scan::global(const General_options&,
     }
 }
 
+// Process relocations for gc.
+
+void
+Target_i386::gc_process_relocs(const General_options& options,
+                               Symbol_table* symtab,
+                               Layout* layout,
+                               Sized_relobj<32, false>* object,
+                               unsigned int data_shndx,
+                               unsigned int,
+                               const unsigned char* prelocs,
+                               size_t reloc_count,
+                               Output_section* output_section,
+                               bool needs_special_offset_handling,
+                               size_t local_symbol_count,
+                               const unsigned char* plocal_symbols)
+{
+  gold::gc_process_relocs<32, false, Target_i386, elfcpp::SHT_REL,
+		          Target_i386::Scan>(
+    options,
+    symtab,
+    layout,
+    this,
+    object,
+    data_shndx,
+    prelocs,
+    reloc_count,
+    output_section,
+    needs_special_offset_handling,
+    local_symbol_count,
+    plocal_symbols);
+}
+
 // Scan relocations for a section.
 
 void
diff --git a/gold/layout.cc b/gold/layout.cc
index a4f17e5..0977557 100644
--- a/gold/layout.cc
+++ b/gold/layout.cc
@@ -1,6 +1,6 @@
 // layout.cc -- lay out output file sections for gold
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -140,14 +140,6 @@ Layout::Hash_key::operator()(const Layout::Key& k) const
  return k.first + k.second.first + k.second.second;
 }
 
-// Return whether PREFIX is a prefix of STR.
-
-static inline bool
-is_prefix_of(const char* prefix, const char* str)
-{
-  return strncmp(prefix, str, strlen(prefix)) == 0;
-}
-
 // Returns whether the given section is in the list of
 // debug-sections-used-by-some-version-of-gdb.  Currently,
 // we've checked versions of gdb up to and including 6.7.1.
diff --git a/gold/main.cc b/gold/main.cc
index 8e8e8f9..0019863 100644
--- a/gold/main.cc
+++ b/gold/main.cc
@@ -1,6 +1,6 @@
 // main.cc -- gold main function.
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -43,6 +43,7 @@
 #include "symtab.h"
 #include "layout.h"
 #include "plugin.h"
+#include "gc.h"
 
 using namespace gold;
 
@@ -201,6 +202,9 @@ main(int argc, char** argv)
   // The list of input objects.
   Input_objects input_objects;
 
+  // The Garbage Collection Object.
+  Garbage_collection gc;
+
   // The symbol table.  We're going to guess here how many symbols
   // we're going to see based on the number of input files.  Even when
   // this is off, it means at worst we don't quite optimize hashtable
@@ -208,6 +212,9 @@ main(int argc, char** argv)
   Symbol_table symtab(command_line.number_of_input_files() * 1024,
                       command_line.version_script());
 
+  if (parameters->options().gc_sections())
+    symtab.set_gc(&gc);
+
   // The layout object.
   Layout layout(command_line.options(), &command_line.script_options());
 
diff --git a/gold/object.cc b/gold/object.cc
index 6a23a6f..9030abe 100644
--- a/gold/object.cc
+++ b/gold/object.cc
@@ -1,6 +1,6 @@
 // object.cc -- support for an object file for linking in gold
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -28,6 +28,7 @@
 #include "demangle.h"
 #include "libiberty.h"
 
+#include "gc.h"
 #include "target-select.h"
 #include "dwarf_reader.h"
 #include "layout.h"
@@ -232,6 +233,79 @@ Object::handle_gnu_warning_section(const char* name, unsigned int shndx,
   return false;
 }
 
+// Class Relobj
+
+// To copy the symbols data read from the file to a local data structure.
+// This function is called from do_layout only while doing garbage 
+// collection.
+
+void
+Relobj::copy_symbols_data(Symbols_data* gc_sd, Read_symbols_data* sd, 
+                          unsigned int section_header_size)
+{
+  gc_sd->section_headers_data = 
+         new unsigned char[(section_header_size)];
+  memcpy(gc_sd->section_headers_data, sd->section_headers->data(),
+         section_header_size);
+  gc_sd->section_names_data = 
+         new unsigned char[sd->section_names_size];
+  memcpy(gc_sd->section_names_data, sd->section_names->data(),
+         sd->section_names_size);
+  gc_sd->section_names_size = sd->section_names_size;
+  if (sd->symbols != NULL)
+    {
+      gc_sd->symbols_data = 
+             new unsigned char[sd->symbols_size];
+      memcpy(gc_sd->symbols_data, sd->symbols->data(),
+            sd->symbols_size);
+    }
+  else
+    {
+      gc_sd->symbols_data = NULL;
+    }
+  gc_sd->symbols_size = sd->symbols_size;
+  gc_sd->external_symbols_offset = sd->external_symbols_offset;
+  if (sd->symbol_names != NULL)
+    {
+      gc_sd->symbol_names_data =
+             new unsigned char[sd->symbol_names_size];
+      memcpy(gc_sd->symbol_names_data, sd->symbol_names->data(),
+            sd->symbol_names_size);
+    }
+  else
+    {
+      gc_sd->symbol_names_data = NULL;
+    }
+  gc_sd->symbol_names_size = sd->symbol_names_size;
+}
+
+// This function determines if a particular section name must be included
+// in the link.  This is used during garbage collection to determine the
+// roots of the worklist.
+
+bool
+Relobj::is_section_name_included(const char* name)
+{
+  if (is_prefix_of(".ctors", name) 
+      || is_prefix_of(".dtors", name) 
+      || is_prefix_of(".note", name) 
+      || is_prefix_of(".init", name) 
+      || is_prefix_of(".fini", name) 
+      || is_prefix_of(".gcc_except_table", name) 
+      || is_prefix_of(".jcr", name) 
+      || is_prefix_of(".preinit_array", name) 
+      || (is_prefix_of(".text", name) 
+          && strstr(name, "personality")) 
+      || (is_prefix_of(".data", name) 
+          &&  strstr(name, "personality")) 
+      || (is_prefix_of(".gnu.linkonce.d", name) && 
+            strstr(name, "personality")))
+    {
+      return true; 
+    }
+  return false;
+}
+
 // Class Sized_relobj.
 
 template<int size, bool big_endian>
@@ -816,7 +890,15 @@ Sized_relobj<size, big_endian>::layout_section(Layout* layout,
 // Lay out the input sections.  We walk through the sections and check
 // whether they should be included in the link.  If they should, we
 // pass them to the Layout object, which will return an output section
-// and an offset.
+// and an offset.  
+// During garbage collection (gc-sections), this function is called
+// twice.  When it is called the first time, it is for setting up some
+// sections as roots to a work-list and to do comdat processing.  Actual
+// layout happens the second time around after all the relevant sections
+// have been determined.  The first time, is_worklist_ready is false.  
+// It is then set to true after the worklist is processed and the relevant 
+// sections are determined.  Then, this function is called again to 
+// layout the sections.
 
 template<int size, bool big_endian>
 void
@@ -825,15 +907,65 @@ Sized_relobj<size, big_endian>::do_layout(Symbol_table* symtab,
 					  Read_symbols_data* sd)
 {
   const unsigned int shnum = this->shnum();
+  bool is_gc_pass_one = (parameters->options().gc_sections() 
+                         && !symtab->gc()->is_worklist_ready());
+  bool is_gc_pass_two = (parameters->options().gc_sections() 
+                         && symtab->gc()->is_worklist_ready());
   if (shnum == 0)
     return;
+  Symbols_data* gc_sd;
+  if (is_gc_pass_one)
+    {
+      // During garbage collection save the symbols data to use it when 
+      // re-entering this function.   
+      gc_sd = new Symbols_data;
+      this->copy_symbols_data(gc_sd, sd, This::shdr_size * shnum);
+      this->set_symbols_data(gc_sd);
+    }
+  else if (is_gc_pass_two)
+    {
+      gc_sd = this->get_symbols_data();
+    }
+
+  const unsigned char* section_headers_data = NULL;
+  section_size_type section_names_size;
+  const unsigned char* symbols_data = NULL;
+  section_size_type symbols_size;
+  section_offset_type external_symbols_offset;
+  const unsigned char* symbol_names_data = NULL;
+  section_size_type symbol_names_size;
+ 
+  if (parameters->options().gc_sections())
+    {
+      section_headers_data = gc_sd->section_headers_data;
+      section_names_size = gc_sd->section_names_size;
+      symbols_data = gc_sd->symbols_data;
+      symbols_size = gc_sd->symbols_size;
+      external_symbols_offset = gc_sd->external_symbols_offset;
+      symbol_names_data = gc_sd->symbol_names_data;
+      symbol_names_size = gc_sd->symbol_names_size;
+    }
+  else
+    {
+      section_headers_data = sd->section_headers->data();
+      section_names_size = sd->section_names_size;
+      if (sd->symbols != NULL)
+        symbols_data = sd->symbols->data();
+      symbols_size = sd->symbols_size;
+      external_symbols_offset = sd->external_symbols_offset;
+      if (sd->symbol_names != NULL)
+        symbol_names_data = sd->symbol_names->data();
+      symbol_names_size = sd->symbol_names_size;
+    }
 
   // Get the section headers.
-  const unsigned char* shdrs = sd->section_headers->data();
+  const unsigned char* shdrs = section_headers_data;
   const unsigned char* pshdrs;
 
   // Get the section names.
-  const unsigned char* pnamesu = sd->section_names->data();
+  const unsigned char* pnamesu = parameters->options().gc_sections() ?
+                                 gc_sd->section_names_data :
+                                 sd->section_names->data();
   const char* pnames = reinterpret_cast<const char*>(pnamesu);
 
   // If any input files have been claimed by plugins, we need to defer
@@ -882,17 +1014,23 @@ Sized_relobj<size, big_endian>::do_layout(Symbol_table* symtab,
   Output_sections& out_sections(this->output_sections());
   std::vector<Address>& out_section_offsets(this->section_offsets_);
 
-  out_sections.resize(shnum);
-  out_section_offsets.resize(shnum);
+  if (!is_gc_pass_two)
+    {
+      out_sections.resize(shnum);
+      out_section_offsets.resize(shnum);
+    }
 
   // If we are only linking for symbols, then there is nothing else to
   // do here.
   if (this->input_file()->just_symbols())
     {
-      delete sd->section_headers;
-      sd->section_headers = NULL;
-      delete sd->section_names;
-      sd->section_names = NULL;
+      if (!is_gc_pass_two)
+        {
+          delete sd->section_headers;
+          sd->section_headers = NULL;
+          delete sd->section_names;
+          sd->section_names = NULL;
+        }
       return;
     }
 
@@ -925,7 +1063,7 @@ Sized_relobj<size, big_endian>::do_layout(Symbol_table* symtab,
     {
       typename This::Shdr shdr(pshdrs);
 
-      if (shdr.get_sh_name() >= sd->section_names_size)
+      if (shdr.get_sh_name() >= section_names_size)
 	{
 	  this->error(_("bad section name offset for section %u: %lu"),
 		      i, static_cast<unsigned long>(shdr.get_sh_name()));
@@ -934,53 +1072,68 @@ Sized_relobj<size, big_endian>::do_layout(Symbol_table* symtab,
 
       const char* name = pnames + shdr.get_sh_name();
 
-      if (this->handle_gnu_warning_section(name, i, symtab))
-	{
-	  if (!relocatable)
-	    omit[i] = true;
-	}
+      if (!is_gc_pass_two)
+        { 
+          if (this->handle_gnu_warning_section(name, i, symtab))
+            { 
+    	      if (!relocatable)
+	        omit[i] = true;
+	    }
 
-      // The .note.GNU-stack section is special.  It gives the
-      // protection flags that this object file requires for the stack
-      // in memory.
-      if (strcmp(name, ".note.GNU-stack") == 0)
-	{
-	  seen_gnu_stack = true;
-	  gnu_stack_flags |= shdr.get_sh_flags();
-	  omit[i] = true;
-	}
+          // The .note.GNU-stack section is special.  It gives the
+          // protection flags that this object file requires for the stack
+          // in memory.
+          if (strcmp(name, ".note.GNU-stack") == 0)
+            {
+	      seen_gnu_stack = true;
+	      gnu_stack_flags |= shdr.get_sh_flags();
+	      omit[i] = true;
+            }
 
-      bool discard = omit[i];
-      if (!discard)
-	{
-	  if (shdr.get_sh_type() == elfcpp::SHT_GROUP)
-	    {
-	      if (!this->include_section_group(symtab, layout, i, name, shdrs,
-					       pnames, sd->section_names_size,
-					       &omit))
-		discard = true;
-	    }
-          else if ((shdr.get_sh_flags() & elfcpp::SHF_GROUP) == 0
-                   && Layout::is_linkonce(name))
-	    {
-	      if (!this->include_linkonce_section(layout, i, name, shdr))
-		discard = true;
+          bool discard = omit[i];
+          if (!discard)
+            {
+	      if (shdr.get_sh_type() == elfcpp::SHT_GROUP)
+	        {
+	          if (!this->include_section_group(symtab, layout, i, name, 
+                                                   shdrs, pnames, 
+                                                   section_names_size,
+					           &omit))
+		    discard = true;
+	        }
+              else if ((shdr.get_sh_flags() & elfcpp::SHF_GROUP) == 0
+                       && Layout::is_linkonce(name))
+	        {
+	          if (!this->include_linkonce_section(layout, i, name, shdr))
+   		    discard = true;
+	        }
 	    }
-	}
 
-      if (discard)
-	{
-	  // Do not include this section in the link.
-	  out_sections[i] = NULL;
-          out_section_offsets[i] = invalid_address;
-	  continue;
-	}
+          if (discard)
+            {
+	      // Do not include this section in the link.
+	      out_sections[i] = NULL;
+              out_section_offsets[i] = invalid_address;
+	      continue;
+            }
+        }
+ 
+      if (is_gc_pass_one)
+        {
+          if (is_section_name_included(name)
+              || shdr.get_sh_type() == elfcpp::SHT_INIT_ARRAY 
+              || shdr.get_sh_type() == elfcpp::SHT_FINI_ARRAY)
+            {
+              symtab->gc()->worklist().push(Section_id(this, i)); 
+            }
+        }
 
       // When doing a relocatable link we are going to copy input
       // reloc sections into the output.  We only want to copy the
       // ones associated with sections which are not being discarded.
       // However, we don't know that yet for all sections.  So save
-      // reloc sections and process them later.
+      // reloc sections and process them later. Garbage collection is
+      // not triggered when relocatable code is desired.
       if (emit_relocs
 	  && (shdr.get_sh_type() == elfcpp::SHT_REL
 	      || shdr.get_sh_type() == elfcpp::SHT_RELA))
@@ -999,44 +1152,98 @@ Sized_relobj<size, big_endian>::do_layout(Symbol_table* symtab,
       // determine which sections are being discarded, and discard the
       // corresponding information.
       if (!relocatable
-	  && strcmp(name, ".eh_frame") == 0
-	  && this->check_eh_frame_flags(&shdr))
-	{
-	  eh_frame_sections.push_back(i);
-	  continue;
-	}
+          && strcmp(name, ".eh_frame") == 0
+          && this->check_eh_frame_flags(&shdr))
+        {
+          if (is_gc_pass_one)
+            {
+              out_sections[i] = reinterpret_cast<Output_section*>(1);
+              out_section_offsets[i] = invalid_address;
+            }
+          else
+            eh_frame_sections.push_back(i);
+          continue;
+        }
 
+      if (is_gc_pass_two)
+        {
+          // This is executed during the second pass of garbage 
+          // collection. do_layout has been called before and some 
+          // sections have been already discarded. Simply ignore 
+          // such sections this time around.
+          if (out_sections[i] == NULL)
+            {
+              gold_assert(out_section_offsets[i] == invalid_address);
+              continue; 
+            }
+          if ((shdr.get_sh_flags() & elfcpp::SHF_ALLOC) != 0)
+            if (symtab->gc()->referenced_list().find(Section_id(this,i)) 
+                == symtab->gc()->referenced_list().end())
+              {
+                if (parameters->options().print_gc_sections())
+                  gold_info(_("%s: Removing unused section from '%s'" 
+                              " in file '%s"),
+                            program_name, this->section_name(i).c_str(), 
+                            this->name().c_str());
+                out_sections[i] = NULL;
+                out_section_offsets[i] = invalid_address;
+                continue;
+              }
+        }
+      // Defer layout here if input files are claimed by plugins.  When gc
+      // is turned on this function is called twice.  For the second call
+      // should_defer_layout should be false.
       if (should_defer_layout && (shdr.get_sh_flags() & elfcpp::SHF_ALLOC))
         {
-          this->deferred_layout_.push_back(Deferred_layout(i, name, pshdrs,
+          gold_assert(!is_gc_pass_two);
+          this->deferred_layout_.push_back(Deferred_layout(i, name, 
+                                                           pshdrs,
                                                            reloc_shndx[i],
                                                            reloc_type[i]));
-
           // Put dummy values here; real values will be supplied by
           // do_layout_deferred_sections.
+          out_sections[i] = reinterpret_cast<Output_section*>(2);
+          out_section_offsets[i] = invalid_address;
+          continue;
+              }
+      // During gc_pass_two if a section that was previously deferred is
+      // found, do not layout the section as layout_deferred_sections will
+      // do it later from gold.cc.
+      if (is_gc_pass_two 
+          && (out_sections[i] == reinterpret_cast<Output_section*>(2)))
+        continue;
+
+      if (is_gc_pass_one)
+        {
+          // This is during garbage collection. The out_sections are 
+          // assigned in the second call to this function. 
           out_sections[i] = reinterpret_cast<Output_section*>(1);
           out_section_offsets[i] = invalid_address;
         }
       else
         {
+          // When garbage collection is switched on the actual layout
+          // only happens in the second call.
           this->layout_section(layout, i, name, shdr, reloc_shndx[i],
                                reloc_type[i]);
         }
     }
 
-  layout->layout_gnu_stack(seen_gnu_stack, gnu_stack_flags);
+  if (!is_gc_pass_one)
+    layout->layout_gnu_stack(seen_gnu_stack, gnu_stack_flags);
 
   // When doing a relocatable link handle the reloc sections at the
-  // end.
+  // end.  Garbage collection is not turned on for relocatable code. 
   if (emit_relocs)
     this->size_relocatable_relocs();
+  gold_assert(!parameters->options().gc_sections() || reloc_sections.empty());
   for (std::vector<unsigned int>::const_iterator p = reloc_sections.begin();
        p != reloc_sections.end();
        ++p)
     {
       unsigned int i = *p;
       const unsigned char* pshdr;
-      pshdr = sd->section_headers->data() + i * This::shdr_size;
+      pshdr = section_headers_data + i * This::shdr_size;
       typename This::Shdr shdr(pshdr);
 
       unsigned int data_shndx = this->adjust_shndx(shdr.get_sh_info());
@@ -1064,24 +1271,25 @@ Sized_relobj<size, big_endian>::do_layout(Symbol_table* symtab,
     }
 
   // Handle the .eh_frame sections at the end.
+  gold_assert(!is_gc_pass_one || eh_frame_sections.empty());
   for (std::vector<unsigned int>::const_iterator p = eh_frame_sections.begin();
        p != eh_frame_sections.end();
        ++p)
     {
       gold_assert(this->has_eh_frame_);
-      gold_assert(sd->external_symbols_offset != 0);
+      gold_assert(external_symbols_offset != 0);
 
       unsigned int i = *p;
       const unsigned char *pshdr;
-      pshdr = sd->section_headers->data() + i * This::shdr_size;
+      pshdr = section_headers_data + i * This::shdr_size;
       typename This::Shdr shdr(pshdr);
 
       off_t offset;
       Output_section* os = layout->layout_eh_frame(this,
-						   sd->symbols->data(),
-						   sd->symbols_size,
-						   sd->symbol_names->data(),
-						   sd->symbol_names_size,
+						   symbols_data,
+						   symbols_size,
+						   symbol_names_data,
+						   symbol_names_size,
 						   i, shdr,
 						   reloc_shndx[i],
 						   reloc_type[i],
@@ -1099,10 +1307,20 @@ Sized_relobj<size, big_endian>::do_layout(Symbol_table* symtab,
 	this->set_relocs_must_follow_section_writes();
     }
 
-  delete sd->section_headers;
-  sd->section_headers = NULL;
-  delete sd->section_names;
-  sd->section_names = NULL;
+  if (is_gc_pass_two)
+    {
+      delete[] gc_sd->section_headers_data;
+      delete[] gc_sd->section_names_data;
+      delete[] gc_sd->symbols_data;
+      delete[] gc_sd->symbol_names_data;
+    }
+  else
+    {
+      delete sd->section_headers;
+      sd->section_headers = NULL;
+      delete sd->section_names;
+      sd->section_names = NULL;
+    }
 }
 
 // Layout sections whose layout was deferred while waiting for
diff --git a/gold/object.h b/gold/object.h
index 6c8c7a3..614a02e 100644
--- a/gold/object.h
+++ b/gold/object.h
@@ -1,6 +1,6 @@
 // object.h -- support for an object file for linking in gold  -*- C++ -*-
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -46,6 +46,7 @@ class Pluginobj;
 class Dynobj;
 class Object_merge_map;
 class Relocatable_relocs;
+class Symbols_data;
 
 template<typename Stringpool_char>
 class Stringpool_template;
@@ -598,11 +599,52 @@ class Relobj : public Object
       relocs_must_follow_section_writes_(false)
   { }
 
+  // During garbage collection, the Read_symbols_data pass for 
+  // each object is stored as layout needs to be done after 
+  // reloc processing.
+  Symbols_data* 
+  get_symbols_data()
+  { return this->sd_; }
+
+  // Decides which section names have to be included in the worklist
+  // as roots.
+  bool
+  is_section_name_included(const char *name);
+ 
+  void
+  copy_symbols_data(Symbols_data* gc_sd, Read_symbols_data* sd,
+                    unsigned int section_header_size);
+
+  void
+  set_symbols_data(Symbols_data* sd)
+  { this->sd_ = sd; }
+
+  // During garbage collection, the Read_relocs pass for all objects 
+  // is done before scanning the relocs.  In that case, this->rd_ is
+  // used to store the information from Read_relocs for each object.
+  // This data is also used to compute the list of relevant sections.
+  Read_relocs_data*
+  get_relocs_data()
+  { return this->rd_; }
+
+  void
+  set_relocs_data(Read_relocs_data* rd)
+  { this->rd_ = rd; }
+
+  virtual bool
+  is_output_section_offset_invalid(unsigned int shndx) const = 0;
+
   // Read the relocs.
   void
   read_relocs(Read_relocs_data* rd)
   { return this->do_read_relocs(rd); }
 
+  // Process the relocs, during garbage collection only.
+  void
+  gc_process_relocs(const General_options& options, Symbol_table* symtab,
+	            Layout* layout, Read_relocs_data* rd)
+  { return this->do_gc_process_relocs(options, symtab, layout, rd); }
+
   // Scan the relocs and adjust the symbol table.
   void
   scan_relocs(const General_options& options, Symbol_table* symtab,
@@ -728,6 +770,11 @@ class Relobj : public Object
   virtual void
   do_read_relocs(Read_relocs_data*) = 0;
 
+  // Process the relocs--implemented by child class.
+  virtual void
+  do_gc_process_relocs(const General_options&, Symbol_table*, Layout*,
+		 Read_relocs_data*) = 0;
+
   // Scan the relocs--implemented by child class.
   virtual void
   do_scan_relocs(const General_options&, Symbol_table*, Layout*,
@@ -810,6 +857,13 @@ class Relobj : public Object
   // Whether we need to wait for output sections to be written before
   // we can apply relocations.
   bool relocs_must_follow_section_writes_;
+  // Used to store the relocs data computed by the Read_relocs pass. 
+  // Used during garbage collection of unused sections.
+  Read_relocs_data* rd_;
+  // Used to store the symbols data computed by the Read_symbols pass.
+  // Again used during garbage collection when laying out referenced
+  // sections.
+  gold::Symbols_data *sd_;
 };
 
 // This class is used to handle relocations against a section symbol
@@ -1220,6 +1274,12 @@ class Sized_relobj : public Relobj
 
   ~Sized_relobj();
 
+  // Checks if the offset of input section SHNDX within its output
+  // section is invalid. 
+  bool
+  is_output_section_offset_invalid(unsigned int shndx) const
+  { return this->get_output_section_offset(shndx) == invalid_address; }
+
   // Set up the object file based on the ELF header.
   void
   setup(const typename elfcpp::Ehdr<size, big_endian>&);
@@ -1392,6 +1452,12 @@ class Sized_relobj : public Relobj
   void
   do_read_relocs(Read_relocs_data*);
 
+  // Process the relocs to find list of referenced sections. Used only
+  // during garbage collection.
+  void
+  do_gc_process_relocs(const General_options&, Symbol_table*, Layout*,
+		       Read_relocs_data*);
+
   // Scan the relocs and adjust the symbol table.
   void
   do_scan_relocs(const General_options&, Symbol_table*, Layout*,
diff --git a/gold/options.h b/gold/options.h
index ba61d17..b980281 100644
--- a/gold/options.h
+++ b/gold/options.h
@@ -1,6 +1,6 @@
 // options.h -- handle command line options for gold  -*- C++ -*-
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -581,10 +581,6 @@ class General_options
 	      N_("Check segment addresses for overlaps (default)"),
 	      N_("Do not check segment addresses for overlaps"));
 
-  DEFINE_bool(gc_sections, options::TWO_DASHES, '\0', true,
-	      N_("(noop) Garbage collect sections"),
-	      N_("(noop) Do not garbage collect sections"));
-
 #ifdef HAVE_ZLIB_H
   DEFINE_enum(compress_debug_sections, options::TWO_DASHES, '\0', "none",
               N_("Compress .debug_* sections in the output file"),
@@ -772,6 +768,14 @@ class General_options
   DEFINE_special(static, options::ONE_DASH, '\0',
                  N_("Do not link against shared libraries"), NULL);
 
+  DEFINE_bool(gc_sections, options::TWO_DASHES, '\0', false,
+              N_("Remove unused sections"), 
+              N_("Don't remove unused sections (default)"));
+ 
+  DEFINE_bool(print_gc_sections, options::TWO_DASHES, '\0', false,
+              N_("List removed unused sections on stderr"), 
+              N_("Do not list removed unused sections"));
+
   DEFINE_bool(stats, options::TWO_DASHES, '\0', false,
               N_("Print resource usage statistics"), NULL);
 
diff --git a/gold/plugin.cc b/gold/plugin.cc
index 7d5b1b7..aeddcc1 100644
--- a/gold/plugin.cc
+++ b/gold/plugin.cc
@@ -1,4 +1,4 @@
-// plugin.c -- plugin manager for gold      -*- C++ -*-
+// plugin.cc -- plugin manager for gold      -*- C++ -*-
 
 // Copyright 2008, 2009 Free Software Foundation, Inc.
 // Written by Cary Coutant <ccoutant@google.com>.
@@ -795,8 +795,7 @@ Add_plugin_symbols::run(Workqueue*)
 }
 
 // Class Plugin_finish.  This task runs after all replacement files have
-// been added.  It calls Layout::layout for any deferred sections and
-// calls each plugin's cleanup handler.
+// been added.  It calls each plugin's cleanup handler.
 
 class Plugin_finish : public Task
 {
@@ -828,7 +827,6 @@ class Plugin_finish : public Task
   {
     Plugin_manager* plugins = parameters->options().plugins();
     gold_assert(plugins != NULL);
-    plugins->layout_deferred_objects();
     plugins->cleanup();
   }
 
diff --git a/gold/powerpc.cc b/gold/powerpc.cc
index 2d1d984..8eac783 100644
--- a/gold/powerpc.cc
+++ b/gold/powerpc.cc
@@ -1,6 +1,6 @@
 // powerpc.cc -- powerpc target support for gold.
 
-// Copyright 2008 Free Software Foundation, Inc.
+// Copyright 2008, 2009 Free Software Foundation, Inc.
 // Written by David S. Miller <davem@davemloft.net>
 //        and David Edelsohn <edelsohn@gnu.org>
 
@@ -61,6 +61,22 @@ class Target_powerpc : public Sized_target<size, big_endian>
   {
   }
 
+  // Process the relocations to determine unreferenced sections for 
+  // garbage collection.
+  void
+  gc_process_relocs(const General_options& options,
+	            Symbol_table* symtab,
+	            Layout* layout,
+	            Sized_relobj<size, big_endian>* object,
+	            unsigned int data_shndx,
+	            unsigned int sh_type,
+	            const unsigned char* prelocs,
+	            size_t reloc_count,
+	            Output_section* output_section,
+	            bool needs_special_offset_handling,
+	            size_t local_symbol_count,
+	            const unsigned char* plocal_symbols);
+
   // Scan the relocations to look for symbol adjustments.
   void
   scan_relocs(const General_options& options,
@@ -1414,6 +1430,42 @@ Target_powerpc<size, big_endian>::Scan::global(
     }
 }
 
+// Process relocations for gc.
+
+template<int size, bool big_endian>
+void
+Target_powerpc<size, big_endian>::gc_process_relocs(
+			const General_options& options,
+			Symbol_table* symtab,
+			Layout* layout,
+			Sized_relobj<size, big_endian>* object,
+			unsigned int data_shndx,
+			unsigned int,
+			const unsigned char* prelocs,
+			size_t reloc_count,
+			Output_section* output_section,
+			bool needs_special_offset_handling,
+			size_t local_symbol_count,
+			const unsigned char* plocal_symbols)
+{
+  typedef Target_powerpc<size, big_endian> Powerpc;
+  typedef typename Target_powerpc<size, big_endian>::Scan Scan;
+
+  gold::gc_process_relocs<size, big_endian, Powerpc, elfcpp::SHT_RELA, Scan>(
+    options,
+    symtab,
+    layout,
+    this,
+    object,
+    data_shndx,
+    prelocs,
+    reloc_count,
+    output_section,
+    needs_special_offset_handling,
+    local_symbol_count,
+    plocal_symbols);
+}
+
 // Scan relocations for a section.
 
 template<int size, bool big_endian>
diff --git a/gold/reloc.cc b/gold/reloc.cc
index f6bef1d..669d87b 100644
--- a/gold/reloc.cc
+++ b/gold/reloc.cc
@@ -1,6 +1,6 @@
 // reloc.cc -- relocate input files for gold.
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -62,11 +62,28 @@ Read_relocs::run(Workqueue* workqueue)
 {
   Read_relocs_data *rd = new Read_relocs_data;
   this->object_->read_relocs(rd);
+  this->object_->set_relocs_data(rd);
   this->object_->release();
 
-  workqueue->queue_next(new Scan_relocs(this->options_, this->symtab_,
-					this->layout_, this->object_, rd,
-					this->symtab_lock_, this->blocker_));
+  // If garbage collection is desired, we must process the relocs
+  // instead of scanning the relocs as reloc processing is necessary 
+  // to determine unused sections.
+  if (parameters->options().gc_sections())
+    {  
+      workqueue->queue_next(new Gc_process_relocs(this->options_, 
+                                                  this->symtab_,
+                                                  this->layout_, 
+                                                  this->object_, rd,
+                                                  this->symtab_lock_, 
+                                                  this->blocker_));
+    }
+  else
+    {
+      workqueue->queue_next(new Scan_relocs(this->options_, this->symtab_,
+                                            this->layout_, this->object_, rd,
+                                            this->symtab_lock_, 
+                                            this->blocker_));
+    }
 }
 
 // Return a debugging name for the task.
@@ -77,6 +94,43 @@ Read_relocs::get_name() const
   return "Read_relocs " + this->object_->name();
 }
 
+// Gc_process_relocs methods.
+
+// These tasks process the relocations read by Read_relocs and 
+// determine which sections are referenced and which are garbage.
+// This task is done only when --gc-sections is used.
+
+Task_token*
+Gc_process_relocs::is_runnable()
+{
+  if (this->object_->is_locked())
+    return this->object_->token();
+  return NULL;
+}
+
+void
+Gc_process_relocs::locks(Task_locker* tl)
+{
+  tl->add(this, this->object_->token());
+  tl->add(this, this->blocker_);
+}
+
+void
+Gc_process_relocs::run(Workqueue*)
+{
+  this->object_->gc_process_relocs(this->options_, this->symtab_, this->layout_,
+            	     this->rd_);
+  this->object_->release();
+}
+
+// Return a debugging name for the task.
+
+std::string
+Gc_process_relocs::get_name() const
+{
+  return "Gc_process_relocs " + this->object_->name();
+}
+
 // Scan_relocs methods.
 
 // These tasks scan the relocations read by Read_relocs and mark up
@@ -296,6 +350,47 @@ Sized_relobj<size, big_endian>::do_read_relocs(Read_relocs_data* rd)
     }
 }
 
+// Process the relocs to generate mappings from source sections to referenced
+// sections.  This is used during garbage colletion to determine garbage 
+// sections.
+
+template<int size, bool big_endian>
+void
+Sized_relobj<size, big_endian>::do_gc_process_relocs(const General_options& options,
+					       Symbol_table* symtab,
+					       Layout* layout,
+					       Read_relocs_data* rd)
+{  
+  Sized_target<size, big_endian>* target = this->sized_target();
+
+  const unsigned char* local_symbols;
+  if (rd->local_symbols == NULL)
+    local_symbols = NULL;
+  else
+    local_symbols = rd->local_symbols->data();
+
+  for (Read_relocs_data::Relocs_list::iterator p = rd->relocs.begin();
+       p != rd->relocs.end();
+       ++p)
+    {
+      if (!parameters->options().relocatable())
+	  {
+	    // As noted above, when not generating an object file, we
+	    // only scan allocated sections.  We may see a non-allocated
+	    // section here if we are emitting relocs.
+	    if (p->is_data_section_allocated)
+              target->gc_process_relocs(options, symtab, layout, this, 
+                                        p->data_shndx, p->sh_type, 
+                                        p->contents->data(), p->reloc_count, 
+                                        p->output_section,
+                                        p->needs_special_offset_handling,
+                                        this->local_symbol_count_, 
+                                        local_symbols);
+        }
+    }
+}
+
+
 // Scan the relocs and adjust the symbol table.  This looks for
 // relocations which require GOT/PLT/COPY relocations.
 
@@ -318,6 +413,14 @@ Sized_relobj<size, big_endian>::do_scan_relocs(const General_options& options,
        p != rd->relocs.end();
        ++p)
     {
+      // When garbage collection is on, unreferenced sections are not included
+      // in the link that would have been included normally. This is known only
+      // after Read_relocs hence this check has to be done again.
+      if (parameters->options().gc_sections())
+        {
+          if (p->output_section == NULL)
+            continue;
+        }
       if (!parameters->options().relocatable())
 	{
 	  // As noted above, when not generating an object file, we
@@ -1080,6 +1183,42 @@ Sized_relobj<64, true>::do_read_relocs(Read_relocs_data* rd);
 #ifdef HAVE_TARGET_32_LITTLE
 template
 void
+Sized_relobj<32, false>::do_gc_process_relocs(const General_options& options,
+					Symbol_table* symtab,
+					Layout* layout,
+					Read_relocs_data* rd);
+#endif
+
+#ifdef HAVE_TARGET_32_BIG
+template
+void
+Sized_relobj<32, true>::do_gc_process_relocs(const General_options& options,
+				       Symbol_table* symtab,
+				       Layout* layout,
+				       Read_relocs_data* rd);
+#endif
+
+#ifdef HAVE_TARGET_64_LITTLE
+template
+void
+Sized_relobj<64, false>::do_gc_process_relocs(const General_options& options,
+					Symbol_table* symtab,
+					Layout* layout,
+					Read_relocs_data* rd);
+#endif
+
+#ifdef HAVE_TARGET_64_BIG
+template
+void
+Sized_relobj<64, true>::do_gc_process_relocs(const General_options& options,
+				       Symbol_table* symtab,
+				       Layout* layout,
+				       Read_relocs_data* rd);
+#endif
+
+#ifdef HAVE_TARGET_32_LITTLE
+template
+void
 Sized_relobj<32, false>::do_scan_relocs(const General_options& options,
 					Symbol_table* symtab,
 					Layout* layout,
diff --git a/gold/reloc.h b/gold/reloc.h
index 61f05e7..d00578e 100644
--- a/gold/reloc.h
+++ b/gold/reloc.h
@@ -1,6 +1,6 @@
 // reloc.h -- relocate input files for gold   -*- C++ -*-
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -92,6 +92,45 @@ class Read_relocs : public Task
   Task_token* blocker_;
 };
 
+// Process the relocs to figure out which sections are garbage.
+// Very similar to scan relocs.
+
+class Gc_process_relocs : public Task
+{
+ public:
+  // SYMTAB_LOCK is used to lock the symbol table.  BLOCKER should be
+  // unblocked when the task completes.
+  Gc_process_relocs(const General_options& options, Symbol_table* symtab,
+	      Layout* layout, Relobj* object, Read_relocs_data* rd,
+	      Task_token* symtab_lock, Task_token* blocker)
+    : options_(options), symtab_(symtab), layout_(layout), object_(object),
+      rd_(rd), symtab_lock_(symtab_lock), blocker_(blocker)
+  { }
+
+  // The standard Task methods.
+
+  Task_token*
+  is_runnable();
+
+  void
+  locks(Task_locker*);
+
+  void
+  run(Workqueue*);
+
+  std::string
+  get_name() const;
+
+ private:
+  const General_options& options_;
+  Symbol_table* symtab_;
+  Layout* layout_;
+  Relobj* object_;
+  Read_relocs_data* rd_;
+  Task_token* symtab_lock_;
+  Task_token* blocker_;
+};
+
 // Scan the relocations for an object to see if they require any
 // GOT/PLT/COPY relocations.
 
diff --git a/gold/sparc.cc b/gold/sparc.cc
index cca78b7..476aa32 100644
--- a/gold/sparc.cc
+++ b/gold/sparc.cc
@@ -1,6 +1,6 @@
 // sparc.cc -- sparc target support for gold.
 
-// Copyright 2008 Free Software Foundation, Inc.
+// Copyright 2008, 2009 Free Software Foundation, Inc.
 // Written by David S. Miller <davem@davemloft.net>.
 
 // This file is part of gold.
@@ -63,6 +63,22 @@ class Target_sparc : public Sized_target<size, big_endian>
   {
   }
 
+  // Process the relocations to determine unreferenced sections for 
+  // garbage collection.
+  void
+  gc_process_relocs(const General_options& options,
+	            Symbol_table* symtab,
+	            Layout* layout,
+	            Sized_relobj<size, big_endian>* object,
+	            unsigned int data_shndx,
+	            unsigned int sh_type,
+	            const unsigned char* prelocs,
+	            size_t reloc_count,
+	            Output_section* output_section,
+	            bool needs_special_offset_handling,
+	            size_t local_symbol_count,
+	            const unsigned char* plocal_symbols);
+
   // Scan the relocations to look for symbol adjustments.
   void
   scan_relocs(const General_options& options,
@@ -2211,6 +2227,42 @@ Target_sparc<size, big_endian>::Scan::global(
     }
 }
 
+// Process relocations for gc.
+
+template<int size, bool big_endian>
+void
+Target_sparc<size, big_endian>::gc_process_relocs(
+			const General_options& options,
+			Symbol_table* symtab,
+			Layout* layout,
+			Sized_relobj<size, big_endian>* object,
+			unsigned int data_shndx,
+			unsigned int,
+			const unsigned char* prelocs,
+			size_t reloc_count,
+			Output_section* output_section,
+			bool needs_special_offset_handling,
+			size_t local_symbol_count,
+			const unsigned char* plocal_symbols)
+{
+  typedef Target_sparc<size, big_endian> Sparc;
+  typedef typename Target_sparc<size, big_endian>::Scan Scan;
+
+  gold::gc_process_relocs<size, big_endian, Sparc, elfcpp::SHT_RELA, Scan>(
+    options,
+    symtab,
+    layout,
+    this,
+    object,
+    data_shndx,
+    prelocs,
+    reloc_count,
+    output_section,
+    needs_special_offset_handling,
+    local_symbol_count,
+    plocal_symbols);
+}
+
 // Scan relocations for a section.
 
 template<int size, bool big_endian>
diff --git a/gold/symtab.cc b/gold/symtab.cc
index 90ddfae..11feb03 100644
--- a/gold/symtab.cc
+++ b/gold/symtab.cc
@@ -1,6 +1,6 @@
 // symtab.cc -- the gold symbol table
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -30,6 +30,7 @@
 #include <utility>
 #include "demangle.h"
 
+#include "gc.h"
 #include "object.h"
 #include "dwarf_reader.h"
 #include "dynobj.h"
@@ -302,6 +303,22 @@ Symbol::should_add_dynsym_entry() const
   if (this->needs_dynsym_entry())
     return true;
 
+  // If this symbol's section is not added, the symbol need not be added. 
+  // The section may have been GCed.  Note that export_dynamic is being 
+  // overridden here.  This should not be done for shared objects.
+  if (parameters->options().gc_sections() 
+      && !parameters->options().shared()
+      && this->source() == Symbol::FROM_OBJECT
+      && !this->object()->is_dynamic())
+    {
+      Relobj* relobj = static_cast<Relobj*>(this->object());
+      bool is_ordinary;
+      unsigned int shndx = this->shndx(&is_ordinary);
+      if (is_ordinary && shndx != elfcpp::SHN_UNDEF
+          && !relobj->is_section_included(shndx))
+        return false;
+    }
+
   // If the symbol was forced local in a version script, do not add it.
   if (this->is_forced_local())
     return false;
@@ -461,7 +478,7 @@ Symbol_table::Symbol_table(unsigned int count,
                            const Version_script_info& version_script)
   : saw_undefined_(0), offset_(0), table_(count), namepool_(),
     forwarders_(), commons_(), tls_commons_(), forced_locals_(), warnings_(),
-    version_script_(version_script)
+    version_script_(version_script), gc_(NULL)
 {
   namepool_.reserve(count);
 }
@@ -488,6 +505,72 @@ Symbol_table::Symbol_table_eq::operator()(const Symbol_table_key& k1,
   return k1.first == k2.first && k1.second == k2.second;
 }
 
+// For symbols that have been listed with -u option, add them to the
+// work list to avoid gc'ing them.
+
+void 
+Symbol_table::gc_mark_undef_symbols()
+{
+  for (options::String_set::const_iterator p =
+	 parameters->options().undefined_begin();
+       p != parameters->options().undefined_end();
+       ++p)
+    {
+      const char* name = p->c_str();
+      Symbol* sym = this->lookup(name);
+      gold_assert (sym != NULL);
+      if (sym->source() == Symbol::FROM_OBJECT 
+          && !sym->object()->is_dynamic())
+        {
+          Relobj* obj = static_cast<Relobj*>(sym->object());
+          bool is_ordinary;
+          unsigned int shndx = sym->shndx(&is_ordinary);
+          if (is_ordinary)
+            {
+              gold_assert(this->gc_ != NULL);
+              this->gc_->worklist().push(Section_id(obj, shndx));
+            }
+        }
+    }
+}
+
+void
+Symbol_table::gc_mark_symbol_for_shlib(Symbol* sym)
+{
+  if (!sym->is_from_dynobj() 
+      && sym->is_externally_visible())
+    {
+      //Add the object and section to the work list.
+      Relobj* obj = static_cast<Relobj*>(sym->object());
+      bool is_ordinary;
+      unsigned int shndx = sym->shndx(&is_ordinary);
+      if (is_ordinary && shndx != elfcpp::SHN_UNDEF)
+        {
+          gold_assert(this->gc_!= NULL);
+          this->gc_->worklist().push(Section_id(obj, shndx));
+        }
+    }
+}
+
+// When doing garbage collection, keep symbols that have been seen in
+// dynamic objects.
+inline void 
+Symbol_table::gc_mark_dyn_syms(Symbol* sym)
+{
+  if (sym->in_dyn() && sym->source() == Symbol::FROM_OBJECT
+      && !sym->object()->is_dynamic())
+    {
+      Relobj *obj = static_cast<Relobj*>(sym->object()); 
+      bool is_ordinary;
+      unsigned int shndx = sym->shndx(&is_ordinary);
+      if (is_ordinary && shndx != elfcpp::SHN_UNDEF)
+        {
+          gold_assert(this->gc_ != NULL);
+          this->gc_->worklist().push(Section_id(obj, shndx));
+        }
+    }
+}
+
 // Make TO a symbol which forwards to FROM.
 
 void
@@ -561,6 +644,8 @@ Symbol_table::resolve(Sized_symbol<size>* to, const Sized_symbol<size>* from)
     to->set_in_reg();
   if (from->in_dyn())
     to->set_in_dyn();
+  if (parameters->options().gc_sections())
+    this->gc_mark_dyn_syms(to);
 }
 
 // Record that a symbol is forced to be local by a version script.
@@ -732,6 +817,8 @@ Symbol_table::add_from_object(Object* object,
 
       this->resolve(ret, sym, st_shndx, is_ordinary, orig_st_shndx, object,
 		    version);
+      if (parameters->options().gc_sections())
+        this->gc_mark_dyn_syms(ret);
 
       if (def)
 	{
@@ -814,6 +901,8 @@ Symbol_table::add_from_object(Object* object,
 
 	  this->resolve(ret, sym, st_shndx, is_ordinary, orig_st_shndx, object,
 			version);
+          if (parameters->options().gc_sections())
+            this->gc_mark_dyn_syms(ret);
 	  ins.first->second = ret;
 	}
       else
@@ -1019,6 +1108,12 @@ Symbol_table::add_from_relobj(
       res = this->add_from_object(relobj, name, name_key, ver, ver_key,
 				  def, *psym, st_shndx, is_ordinary,
 				  orig_st_shndx);
+      
+      // If building a shared library using garbage collection, do not 
+      // treat externally visible symbols as garbage.
+      if (parameters->options().gc_sections() 
+          && parameters->options().shared())
+        this->gc_mark_symbol_for_shlib(res);
 
       if (local)
 	this->force_local(res);
@@ -2177,7 +2272,10 @@ Symbol_table::sized_finalize_symbol(Symbol* unsized_sym)
 	    if (os == NULL)
 	      {
 		sym->set_symtab_index(-1U);
-		gold_assert(sym->dynsym_index() == -1U);
+                bool static_or_reloc = (parameters->doing_static_link() ||
+                                        parameters->options().relocatable());
+                gold_assert(static_or_reloc || sym->dynsym_index() == -1U);
+
 		return false;
 	      }
 
diff --git a/gold/symtab.h b/gold/symtab.h
index cfd0c73..358dd32 100644
--- a/gold/symtab.h
+++ b/gold/symtab.h
@@ -27,6 +27,7 @@
 #include <utility>
 #include <vector>
 
+#include "gc.h"
 #include "elfcpp.h"
 #include "parameters.h"
 #include "stringpool.h"
@@ -56,6 +57,7 @@ class Output_section;
 class Output_segment;
 class Output_file;
 class Output_symtab_xindex;
+class Garbage_collection;
 
 // The base class of an entry in the symbol table.  The symbol table
 // can have a lot of entries, so we don't want this class to big.
@@ -1140,6 +1142,28 @@ class Symbol_table
 
   ~Symbol_table();
 
+  void
+  set_gc(Garbage_collection* gc)
+  { this->gc_ = gc; }
+
+  Garbage_collection*
+  gc()
+  { return this->gc_; }
+
+  // During garbage collection, this keeps undefined symbols.
+  void
+  gc_mark_undef_symbols(); 
+
+  // During garbage collection, this ensures externally visible symbols
+  // are not treated as garbage while building shared objects.
+  void
+  gc_mark_symbol_for_shlib(Symbol* sym);
+
+  // During garbage collection, this keeps sections that correspond to 
+  // symbols seen in dynamic objects.
+  inline void
+  gc_mark_dyn_syms(Symbol* sym);
+
   // Add COUNT external symbols from the relocatable object RELOBJ to
   // the symbol table.  SYMS is the symbols, SYMNDX_OFFSET is the
   // offset in the symbol table of the first symbol, SYM_NAMES is
@@ -1602,6 +1626,7 @@ class Symbol_table
   Copied_symbol_dynobjs copied_symbol_dynobjs_;
   // Information parsed from the version script, if any.
   const Version_script_info& version_script_;
+  Garbage_collection* gc_;
 };
 
 // We inline get_sized_symbol for efficiency.
diff --git a/gold/target.h b/gold/target.h
index 460ac96..79111ce 100644
--- a/gold/target.h
+++ b/gold/target.h
@@ -1,6 +1,6 @@
 // target.h -- target support for gold   -*- C++ -*-
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -259,6 +259,24 @@ class Sized_target : public Target
 	  const char*)
   { gold_unreachable(); }
 
+  // Process the relocs for a section, and record information of the
+  // mapping from source to destination sections. This mapping is later
+  // used to determine unreferenced garbage sections. This procedure is
+  // only called during garbage collection.
+  virtual void
+  gc_process_relocs(const General_options& options,
+	      Symbol_table* symtab,
+	      Layout* layout,
+	      Sized_relobj<size, big_endian>* object,
+	      unsigned int data_shndx,
+	      unsigned int sh_type,
+	      const unsigned char* prelocs,
+	      size_t reloc_count,
+	      Output_section* output_section,
+	      bool needs_special_offset_handling,
+	      size_t local_symbol_count,
+	      const unsigned char* plocal_symbols) = 0;
+
   // Scan the relocs for a section, and record any information
   // required for the symbol.  OPTIONS is the command line options.
   // SYMTAB is the symbol table.  OBJECT is the object in which the
diff --git a/gold/testsuite/testfile.cc b/gold/testsuite/testfile.cc
index 4551c44..a2a45be 100644
--- a/gold/testsuite/testfile.cc
+++ b/gold/testsuite/testfile.cc
@@ -1,6 +1,6 @@
 // testfile.cc -- Dummy ELF objects for testing purposes.
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -44,6 +44,13 @@ class Target_test : public Sized_target<size, big_endian>
   { }
 
   void
+  gc_process_relocs(const General_options&, Symbol_table*, Layout*,
+                    Sized_relobj<size, big_endian>*, unsigned int,
+                    unsigned int, const unsigned char*, size_t, Output_section*,
+                    bool, size_t, const unsigned char*)
+  { ERROR("call to Target_test::gc_process_relocs"); }
+
+  void
   scan_relocs(const General_options&, Symbol_table*, Layout*,
 	      Sized_relobj<size, big_endian>*, unsigned int,
 	      unsigned int, const unsigned char*, size_t, Output_section*,
diff --git a/gold/x86_64.cc b/gold/x86_64.cc
index 69f76a0..1724624 100644
--- a/gold/x86_64.cc
+++ b/gold/x86_64.cc
@@ -1,6 +1,6 @@
 // x86_64.cc -- x86_64 target support for gold.
 
-// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
+// Copyright 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
 // Written by Ian Lance Taylor <iant@google.com>.
 
 // This file is part of gold.
@@ -68,6 +68,21 @@ class Target_x86_64 : public Sized_target<64, false>
 
   // Scan the relocations to look for symbol adjustments.
   void
+  gc_process_relocs(const General_options& options,
+	            Symbol_table* symtab,
+	            Layout* layout,
+	            Sized_relobj<64, false>* object,
+	            unsigned int data_shndx,
+	            unsigned int sh_type,
+	            const unsigned char* prelocs,
+	            size_t reloc_count,
+	            Output_section* output_section,
+	            bool needs_special_offset_handling,
+	            size_t local_symbol_count,
+	            const unsigned char* plocal_symbols);
+
+  // Scan the relocations to look for symbol adjustments.
+  void
   scan_relocs(const General_options& options,
 	      Symbol_table* symtab,
 	      Layout* layout,
@@ -1544,6 +1559,42 @@ Target_x86_64::Scan::global(const General_options&,
     }
 }
 
+void
+Target_x86_64::gc_process_relocs(const General_options& options,
+                                 Symbol_table* symtab,
+                                 Layout* layout,
+                                 Sized_relobj<64, false>* object,
+                                 unsigned int data_shndx,
+                                 unsigned int sh_type,
+                                 const unsigned char* prelocs,
+                                 size_t reloc_count,
+			         Output_section* output_section,
+			         bool needs_special_offset_handling,
+                                 size_t local_symbol_count,
+                                 const unsigned char* plocal_symbols)
+{
+
+  if (sh_type == elfcpp::SHT_REL)
+    {
+      return;
+    }
+
+   gold::gc_process_relocs<64, false, Target_x86_64, elfcpp::SHT_RELA,
+                           Target_x86_64::Scan>(
+    options,
+    symtab,
+    layout,
+    this,
+    object,
+    data_shndx,
+    prelocs,
+    reloc_count,
+    output_section,
+    needs_special_offset_handling,
+    local_symbol_count,
+    plocal_symbols);
+ 
+}
 // Scan relocations for a section.
 
 void