TraceCache.cc

#include <iostream>
#include "TraceCache.h"
#include "def.h"


using namespace std;


/***************************************************************************
 *                              Cache Methods                              *
 ***************************************************************************/
Cache::Cache( unsigned size, rep_policy_t rep_policy, unsigned assoc ){
  _size       = size;
  _assoc      = assoc;
  _rep_policy = rep_policy;
  _lines      = _size / _assoc;
}


bool Cache::exists( unsigned addr ){
  unsigned tag   = addr / _lines;
  unsigned index = addr % _lines;
  if ( _cache.find( index ) != _cache.end() ){
    return ( _cache[index]->exists( tag ));
  }
  return false;
}


Trace Cache::read( unsigned addr ){
  assert( this->exists( addr ));
  unsigned tag   = addr / _lines;
  unsigned index = addr % _lines;
  return _cache[index]->read( tag );
}


void Cache::updateCount( unsigned addr ){
  assert( this->exists( addr ));
  unsigned tag   = addr / _lines;
  unsigned index = addr % _lines;
  _cache[index]->updateCount( tag );
}


void Cache::write( Trace trace ){
  assert( _cache.size() <= _lines );
  unsigned addr  = trace.getFetchAddr();
  unsigned tag   = addr / _lines;
  unsigned index = addr % _lines;
  if ( _cache.find( index ) == _cache.end() ){
    if ( DBG_TCACHE ) std::cout << "    TCACHE: Creating new line #" << index << std::endl;
    _cache[index] = new CacheLine( _assoc, _rep_policy );
  }
  _cache[index]->write( tag, trace );
}



/***************************************************************************
 *                            CacheLine Methods                            *
 ***************************************************************************/
CacheLine::CacheLine( unsigned assoc, rep_policy_t rep_policy ){
  _assoc      = assoc;
  _rep_policy = rep_policy;
}


bool CacheLine::exists( unsigned tag ){
  return ( _cache_line.find( tag ) != _cache_line.end() );
}


Trace CacheLine::read( unsigned tag ){
  assert( exists( tag ));
  return *(_cache_line[tag].trace);
}


void CacheLine::updateCount( unsigned tag ){
  assert( exists( tag ));

  if ( LRU == _rep_policy || MRU == _rep_policy ){
    for( CacheLine_t::iterator it = _cache_line.begin(), it_last = _cache_line.end(); it != it_last; ++it )
      if ( it->second.frecency < _cache_line[tag].frecency ) ++(it->second.frecency);
    _cache_line[tag].frecency = 1;
  }else if ( LFU == _rep_policy || MFU == _rep_policy ){
    ++_cache_line[tag].frecency;
  }else{
    std::cout << "    TCLINE: Unknown replacement policy" << std::endl;
    assert(0);
  }
}


void CacheLine::write( unsigned tag, Trace trace ){
  if ( this->isFull() ) this->evict();
  assert( !this->isFull() );

  if ( LRU == _rep_policy || MRU == _rep_policy )
    for( CacheLine_t::iterator it = _cache_line.begin(), it_last = _cache_line.end(); it != it_last; ++it )
      ++(it->second.frecency);
  CacheBlock_t block;
  block.trace = new Trace(2, 1);
  *block.trace = trace;
  block.frecency = 1;

  _cache_line[tag] = block;
}


void CacheLine::evict(){
  assert( _cache_line.size() == _assoc );

  CacheLine_t::iterator it_evicted_trace;

  if ( LRU == _rep_policy || MFU == _rep_policy ){
    it_evicted_trace = max();
  }else if ( MRU == _rep_policy || LFU == _rep_policy ){
    it_evicted_trace = min();
  }else{
    std::cout << "    TCLINE: Unknown replacement policy" << std::endl;
    assert(0);
  }

  if ( LRU == _rep_policy ) assert( it_evicted_trace->second.frecency == _assoc );
  if ( MRU == _rep_policy ) assert( it_evicted_trace->second.frecency == 1 );
  _cache_line.erase( it_evicted_trace );
}


CacheLine_t::iterator CacheLine::min(){
  unsigned frecency_min = _cache_line.begin()->second.frecency;
  CacheLine_t::iterator it_min = _cache_line.begin();

  for( CacheLine_t::iterator it = _cache_line.begin(), it_last = _cache_line.end(); it != it_last; ++it ){
    if ( it->second.frecency < frecency_min ) it_min = it;
  }
  return it_min;
}


CacheLine_t::iterator CacheLine::max(){
  unsigned frecency_max = _cache_line.begin()->second.frecency;
  CacheLine_t::iterator it_max = _cache_line.begin();

  for( CacheLine_t::iterator it = _cache_line.begin(), it_last = _cache_line.end(); it != it_last; ++it ){
    if ( it->second.frecency > frecency_max ) it_max = it;
  }
  return it_max;
}



/***************************************************************************
 *                              Trace Methods                              *
 ***************************************************************************/
Trace::Trace( unsigned max_insns, unsigned max_branches ){
  assert( max_insns > 0 );
  assert( max_branches > 0 );
  assert( max_insns >= max_branches );

  _max_insns = max_insns;
  _max_branches = max_branches;
}


unsigned Trace::getFetchAddr(){
  return _insn_seq[0].pc;
}


void Trace::grow_insn( insn_packet_t insn_packet ){
  _insn_seq.push_back( insn_packet );
  _trace_fallthru = insn_packet.next_pc;
}


void Trace::grow_br( insn_packet_t insn_packet, unsigned trace_fallthru, unsigned trace_target ){
  _insn_seq.push_back( insn_packet );
  _br_mask = ( _br_mask << 1 ) + 1;

  // Note: _br_flags is modified for all branches. This is incorrect if the trace ends in a branch
  // This has to be checked and corrected just before the trace is used
  _br_flags <<= 1;
  if ( insn_packet.next_pc != insn_packet.pc + 8 )
    _br_flags += 1;

  _trace_target   = trace_target;
  _trace_fallthru = trace_fallthru;
}


bool Trace::isFull(){
  return (( this->getSize() == _max_insns ) | ( _br_mask == ( 2 << _max_branches - 1)));
}