// icf.h --  Identical Code Folding

// Copyright 2009, 2010 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_ICF_H
#define GOLD_ICF_H

#include <vector>

#include "elfcpp.h"
#include "symtab.h"
#include "object.h"

namespace gold
{

class Object;
class Input_objects;
class Symbol_table;

class Icf
{
 public:
  typedef std::vector<Section_id> Sections_reachable_list;
  typedef std::vector<Symbol*> Symbol_info;
  typedef std::vector<std::pair<long long, long long> > Addend_info;
  typedef Unordered_map<Section_id,
                        Sections_reachable_list,
                        Section_id_hash> Section_list;
  typedef Unordered_map<Section_id, Symbol_info, Section_id_hash> Symbol_list;
  typedef Unordered_map<Section_id, Addend_info, Section_id_hash> Addend_list;
  typedef Unordered_map<Section_id,
                        unsigned int,
                        Section_id_hash> Uniq_secn_id_map;
  typedef Unordered_set<Section_id, Section_id_hash> Secn_fptr_taken_set;

  Icf()
  : id_section_(), section_id_(), kept_section_id_(),
    fptr_section_id_(),
    num_tracked_relocs(NULL), icf_ready_(false),
    section_reloc_list_(), symbol_reloc_list_(),
    addend_reloc_list_()
  { }

  // Returns the kept folded identical section corresponding to
  // dup_obj and dup_shndx.
  Section_id
  get_folded_section(Object* dup_obj, unsigned int dup_shndx);

  // Forms groups of identical sections where the first member
  // of each group is the kept section during folding.
  void
  find_identical_sections(const Input_objects* input_objects,
                          Symbol_table* symtab);

  // This is set when ICF has been run and the groups of
  // identical sections have been formed.
  void
  icf_ready()
  { this->icf_ready_ = true; }

  // Returns true if ICF has been run.
  bool
  is_icf_ready()
  { return this->icf_ready_; }

  // Unfolds the section denoted by OBJ and SHNDX if folded.
  void
  unfold_section(Object* obj, unsigned int shndx);

  // Returns the kept section corresponding to the 
  // given section.
  bool
  is_section_folded(Object* obj, unsigned int shndx);

  // Given an object and a section index, this returns true if the
  // pointer of the function defined in this section is taken.
  bool
  section_has_function_pointers(Object *obj, unsigned int shndx)
  {
    return (this->fptr_section_id_.find(Section_id(obj, shndx))
            != this->fptr_section_id_.end());
  }

  // Records that a pointer of the function defined in this section
  // is taken.
  void
  set_section_has_function_pointers(Object *obj, unsigned int shndx)
  {
    this->fptr_section_id_.insert(Section_id(obj, shndx));
  }

  // Checks if the section_name should be searched for relocs
  // corresponding to taken function pointers.  Ignores eh_frame
  // and vtable sections.
  inline bool
  check_section_for_function_pointers(std::string section_name,
                                      Target* target)
  {
    return (parameters->options().icf_safe_folding()
	    && target->can_check_for_function_pointers()
            && !is_prefix_of(".rodata._ZTV", section_name.c_str())
            && !is_prefix_of(".eh_frame", section_name.c_str()));
  }

  // Returns a map of a section to a list of all sections referenced
  // by its relocations.
  Section_list&
  section_reloc_list()
  { return this->section_reloc_list_; }

  // Returns a map of  a section to a list of all symbols referenced
  // by its relocations.
  Symbol_list&
  symbol_reloc_list()
  { return this->symbol_reloc_list_; }

  // Returns a maps of a section to a list of symbol values and addends
  // of its relocations.
  Addend_list&
  addend_reloc_list()
  { return this->addend_reloc_list_; }
  
  // Returns a mapping of each section to a unique integer.
  Uniq_secn_id_map&
  section_to_int_map()
  { return this->section_id_; }

 private:

  // Maps integers to sections.
  std::vector<Section_id> id_section_;
  // Does the reverse.
  Uniq_secn_id_map section_id_;
  // Given a section id, this maps it to the id of the kept
  // section.  If the id's are the same then this section is
  // not folded.
  std::vector<unsigned int> kept_section_id_;
  // Given a section id, this says if the pointer to this
  // function is taken in which case it is dangerous to fold
  // this function.
  Secn_fptr_taken_set fptr_section_id_;
  unsigned int* num_tracked_relocs;
  // Flag to indicate if ICF has been run.
  bool icf_ready_;

  // These lists are populated by gc_process_relocs in gc.h.
  Section_list section_reloc_list_;
  Symbol_list symbol_reloc_list_;
  Addend_list addend_reloc_list_;
};

// This function returns true if this section corresponds to a function that
// should be considered by icf as a possible candidate for folding.  Some
// earlier gcc versions, like 4.0.3, put constructors and destructors in
// .gnu.linkonce.t sections and hence should be included too.
inline bool
is_section_foldable_candidate(const char* section_name)
{
  return (is_prefix_of(".text", section_name)
          || is_prefix_of(".gnu.linkonce.t", section_name));
}

} // End of namespace gold.

#endif