//===- MipsGOT.h ----------------------------------------------------------===//
//
//                     The MCLinker Project
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
#ifndef TARGET_MIPS_MIPSGOT_H
#define TARGET_MIPS_MIPSGOT_H
#include <map>
#include <vector>


#include <mcld/ADT/SizeTraits.h>
#include <mcld/Target/GOT.h>
#include <mcld/Fragment/Relocation.h>
#include <mcld/Support/MemoryRegion.h>
#include <llvm/ADT/DenseMap.h>
#include <llvm/ADT/DenseSet.h>
#include <set>

namespace mcld {

class Input;
class LDSection;
class LDSymbol;
class OutputRelocSection;

/** \class MipsGOT
 *  \brief Mips Global Offset Table.
 */
class MipsGOT : public GOT
{
public:
  MipsGOT(LDSection& pSection);

  /// Assign value to the GOT entry.
  virtual void setEntryValue(Fragment* entry, uint64_t pValue) = 0;

  /// Emit the global offset table.
  virtual uint64_t emit(MemoryRegion& pRegion) = 0;

  /// Address of _gp_disp symbol.
  uint64_t getGPDispAddress() const;

  void initializeScan(const Input& pInput);
  void finalizeScan(const Input& pInput);

  bool reserveLocalEntry(ResolveInfo& pInfo, int reloc,
                         Relocation::DWord pAddend);
  bool reserveGlobalEntry(ResolveInfo& pInfo);

  size_t getLocalNum() const;   ///< number of local symbols in primary GOT
  size_t getGlobalNum() const;  ///< total number of global symbols

  bool isPrimaryGOTConsumed();

  Fragment* consumeLocal();
  Fragment* consumeGlobal();

  uint64_t getGPAddr(const Input& pInput) const;
  uint64_t getGPRelOffset(const Input& pInput, const Fragment& pEntry) const;

  void recordGlobalEntry(const ResolveInfo* pInfo, Fragment* pEntry);
  Fragment* lookupGlobalEntry(const ResolveInfo* pInfo);

  void recordLocalEntry(const ResolveInfo* pInfo,
                        Relocation::DWord pAddend,
                        Fragment* pEntry);
  Fragment* lookupLocalEntry(const ResolveInfo* pInfo,
                             Relocation::DWord pAddend);

  /// hasGOT1 - return if this got section has any GOT1 entry
  bool hasGOT1() const;

  bool hasMultipleGOT() const;

  /// Create GOT entries and reserve dynrel entries.
  void finalizeScanning(OutputRelocSection& pRelDyn);

  /// Compare two symbols to define order in the .dynsym.
  bool dynSymOrderCompare(const LDSymbol* pX, const LDSymbol* pY) const;

protected:
  /// Create GOT entry.
  virtual Fragment* createEntry(uint64_t pValue, SectionData* pParent) = 0;

  /// Size of GOT entry.
  virtual size_t getEntrySize() const = 0;

  /// Reserve GOT header entries.
  virtual void reserveHeader() = 0;

private:
  /** \class GOTMultipart
   *  \brief GOTMultipart counts local and global entries in the GOT.
   */
  struct GOTMultipart
  {
    GOTMultipart(size_t local = 0, size_t global = 0);

    typedef llvm::DenseSet<const Input*> InputSetType;

    size_t m_LocalNum;  ///< number of reserved local entries
    size_t m_GlobalNum; ///< number of reserved global entries

    size_t m_ConsumedLocal;       ///< consumed local entries
    size_t m_ConsumedGlobal;      ///< consumed global entries

    Fragment* m_pLastLocal;   ///< the last consumed local entry
    Fragment* m_pLastGlobal;  ///< the last consumed global entry

    InputSetType m_Inputs;

    bool isConsumed() const;

    void consumeLocal();
    void consumeGlobal();
  };

  /** \class LocalEntry
   *  \brief LocalEntry local GOT entry descriptor.
   */
  struct LocalEntry
  {
    const ResolveInfo* m_pInfo;
    Relocation::DWord  m_Addend;
    bool               m_IsGot16;

    LocalEntry(const ResolveInfo* pInfo,
               Relocation::DWord addend, bool isGot16);

    bool operator<(const LocalEntry &O) const;
  };

  typedef std::vector<GOTMultipart> MultipartListType;

  // Set of global symbols.
  typedef llvm::DenseSet<const ResolveInfo*> SymbolSetType;
  // Map of symbols. If value is true, the symbol is referenced
  // in the current input only. If value is false, the symbol
  // is referenced in the other modules merged to the current GOT.
  typedef llvm::DenseMap<const ResolveInfo*, bool> SymbolUniqueMapType;

  // Set of local symbols.
  typedef std::set<LocalEntry> LocalSymbolSetType;

  MultipartListType m_MultipartList;  ///< list of GOT's descriptors
  const Input* m_pInput;              ///< current input

  // Global symbols merged to the current GOT
  // except symbols from the current input.
  SymbolSetType m_MergedGlobalSymbols;
  // Global symbols from the current input.
  SymbolUniqueMapType m_InputGlobalSymbols;
  // Local symbols merged to the current GOT
  // except symbols from the current input.
  LocalSymbolSetType m_MergedLocalSymbols;
  // Local symbols from the current input.
  LocalSymbolSetType m_InputLocalSymbols;

  size_t m_CurrentGOTPart;

  typedef llvm::DenseMap<const LDSymbol*, unsigned> SymbolOrderMapType;
  SymbolOrderMapType m_SymbolOrderMap;

  void initGOTList();

  void changeInput();
  bool isGOTFull() const;
  void split();
  void reserve(size_t pNum);

private:
  struct GotEntryKey
  {
    size_t m_GOTPage;
    const ResolveInfo* m_pInfo;
    Relocation::DWord m_Addend;

    bool operator<(const GotEntryKey& key) const
    {
      if (m_GOTPage != key.m_GOTPage)
        return m_GOTPage < key.m_GOTPage;

      if (m_pInfo != key.m_pInfo)
        return m_pInfo < key.m_pInfo;

      return m_Addend < key.m_Addend;
    }
  };

  typedef std::map<GotEntryKey, Fragment*> GotEntryMapType;
  GotEntryMapType m_GotLocalEntriesMap;
  GotEntryMapType m_GotGlobalEntriesMap;
};

/** \class Mips32GOT
 *  \brief Mips 32-bit Global Offset Table.
 */
class Mips32GOT : public MipsGOT
{
public:
  Mips32GOT(LDSection& pSection);

private:
  typedef GOT::Entry<4> Mips32GOTEntry;

  // MipsGOT
  virtual void setEntryValue(Fragment* entry, uint64_t pValue);
  virtual uint64_t emit(MemoryRegion& pRegion);
  virtual Fragment* createEntry(uint64_t pValue, SectionData* pParent);
  virtual size_t getEntrySize() const;
  virtual void reserveHeader();
};

/** \class Mips64GOT
 *  \brief Mips 64-bit Global Offset Table.
 */
class Mips64GOT : public MipsGOT
{
public:
  Mips64GOT(LDSection& pSection);

private:
  typedef GOT::Entry<8> Mips64GOTEntry;

  // MipsGOT
  virtual void setEntryValue(Fragment* entry, uint64_t pValue);
  virtual uint64_t emit(MemoryRegion& pRegion);
  virtual Fragment* createEntry(uint64_t pValue, SectionData* pParent);
  virtual size_t getEntrySize() const;
  virtual void reserveHeader();
};

} // namespace of mcld

#endif