path: root/lib/Bitcode/NaCl/Writer/NaClValueEnumerator.cpp

//===-- NaClValueEnumerator.cpp ------------------------------------------===//
//     Number values and types for bitcode writer
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the NaClValueEnumerator class.
//
//===----------------------------------------------------------------------===//

#include "NaClValueEnumerator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/ValueSymbolTable.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <set>

using namespace llvm;

static bool isIntOrIntVectorValue(const std::pair<const Value*, unsigned> &V) {
  return V.first->getType()->isIntOrIntVectorTy();
}

/// NaClValueEnumerator - Enumerate module-level information.
NaClValueEnumerator::NaClValueEnumerator(const Module *M, uint32_t PNaClVersion)
    : PNaClVersion(PNaClVersion) {
  // Create map for counting frequency of types, and set field
  // TypeCountMap accordingly.  Note: Pointer field TypeCountMap is
  // used to deal with the fact that types are added through various
  // method calls in this routine. Rather than pass it as an argument,
  // we use a field. The field is a pointer so that the memory
  // footprint of count_map can be garbage collected when this
  // constructor completes.
  TypeCountMapType count_map;
  TypeCountMap = &count_map;

  IntPtrType = IntegerType::get(M->getContext(), PNaClIntPtrTypeBitSize);

  // Enumerate the functions. Note: We do this before global
  // variables, so that global variable initializations can refer to
  // the functions without a forward reference.
  for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I) {
    EnumerateValue(I);
  }

  // Enumerate the global variables.
  FirstGlobalVarID = Values.size();
  for (Module::const_global_iterator I = M->global_begin(),
         E = M->global_end(); I != E; ++I)
    EnumerateValue(I);
  NumGlobalVarIDs = Values.size() - FirstGlobalVarID;

  // Enumerate the aliases.
  for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
       I != E; ++I)
    EnumerateValue(I);

  // Remember what is the cutoff between globalvalue's and other constants.
  unsigned FirstConstant = Values.size();

  // Skip global variable initializers since they are handled within
  // WriteGlobalVars of file NaClBitcodeWriter.cpp.

  // Enumerate the aliasees.
  for (Module::const_alias_iterator I = M->alias_begin(), E = M->alias_end();
       I != E; ++I)
    EnumerateValue(I->getAliasee());

  // Insert constants that are named at module level into the slot
  // pool so that the module symbol table can refer to them...
  EnumerateValueSymbolTable(M->getValueSymbolTable());

  // Enumerate types used by function bodies and argument lists.
  for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {

    for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
         I != E; ++I)
      EnumerateType(I->getType());

    for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
      for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E;++I){
        // Don't generate types for elided pointer casts!
        if (IsElidedCast(I))
          continue;

        if (const SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
          // Handle switch instruction specially, so that we don't
          // write out unnecessary vector/array types used to model case
          // selectors.
          EnumerateOperandType(SI->getCondition());
        } else {
          for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
               OI != E; ++OI) {
            EnumerateOperandType(*OI);
          }
        }
        EnumerateType(I->getType());
      }
  }

  // Optimized type indicies to put "common" expected types in with small
  // indices.
  OptimizeTypes(M);
  TypeCountMap = NULL;

  // Optimize constant ordering.
  OptimizeConstants(FirstConstant, Values.size());
}

void NaClValueEnumerator::OptimizeTypes(const Module *M) {

  // Sort types by count, so that we can index them based on
  // frequency. Use indices of built TypeMap, so that order of
  // construction is repeatable.
  std::set<unsigned> type_counts;
  typedef std::set<unsigned> TypeSetType;
  std::map<unsigned, TypeSetType> usage_count_map;
  TypeList IdType(Types);

  for (TypeCountMapType::iterator iter = TypeCountMap->begin();
       iter != TypeCountMap->end(); ++ iter) {
    type_counts.insert(iter->second);
    usage_count_map[iter->second].insert(TypeMap[iter->first]-1);
  }

  // Reset type tracking maps, so that we can re-enter based
  // on fequency ordering.
  TypeCountMap = NULL;
  Types.clear();
  TypeMap.clear();

  // Reinsert types, based on frequency.
  for (std::set<unsigned>::reverse_iterator count_iter = type_counts.rbegin();
       count_iter != type_counts.rend(); ++count_iter) {
    TypeSetType& count_types = usage_count_map[*count_iter];
    for (TypeSetType::iterator type_iter = count_types.begin();
         type_iter != count_types.end(); ++type_iter)
      EnumerateType((IdType[*type_iter]), true);
  }
}

unsigned NaClValueEnumerator::getInstructionID(const Instruction *Inst) const {
  InstructionMapType::const_iterator I = InstructionMap.find(Inst);
  assert(I != InstructionMap.end() && "Instruction is not mapped!");
  return I->second;
}

void NaClValueEnumerator::setInstructionID(const Instruction *I) {
  InstructionMap[I] = InstructionCount++;
}

unsigned NaClValueEnumerator::getValueID(const Value *V) const {
  ValueMapType::const_iterator I = ValueMap.find(V);
  assert(I != ValueMap.end() && "Value not in slotcalculator!");
  return I->second-1;
}

void NaClValueEnumerator::dump() const {
  print(dbgs(), ValueMap, "Default");
  dbgs() << '\n';
}

void NaClValueEnumerator::print(raw_ostream &OS, const ValueMapType &Map,
                            const char *Name) const {

  OS << "Map Name: " << Name << "\n";
  OS << "Size: " << Map.size() << "\n";
  for (ValueMapType::const_iterator I = Map.begin(),
         E = Map.end(); I != E; ++I) {

    const Value *V = I->first;
    if (V->hasName())
      OS << "Value: " << V->getName();
    else
      OS << "Value: [null]\n";
    V->dump();

    OS << " Uses(" << std::distance(V->use_begin(),V->use_end()) << "):";
    for (Value::const_use_iterator UI = V->use_begin(), UE = V->use_end();
         UI != UE; ++UI) {
      if (UI != V->use_begin())
        OS << ",";
      if((*UI)->hasName())
        OS << " " << (*UI)->getName();
      else
        OS << " [null]";

    }
    OS <<  "\n\n";
  }
}

// Optimize constant ordering.
namespace {
  struct CstSortPredicate {
    NaClValueEnumerator &