#include "interface.h"  // Do NOT edit interface .h
#include "sample_prefetcher.h"

MyStream *pref1;   // This is the L1 prefetcher
MyStream *pref2;   // Thss is the L2 prefetcher

using namespace std;

INT32 AddrOperation::GetLog2(ADDRINT blocksize) {
  UINT32 i = 0;
  if( (blocksize & (blocksize-1)) != 0)
    return -1;
  while(blocksize != 0) {
    blocksize >>= 1;
    i++;
  }
  return i-1;
}

///////////////////////////////////////////////////////////////////////////////
// Methods of Class MyStream
///////////////////////////////////////////////////////////////////////////////


/*************************************************************************************
 * MSHR::AddEntry
 *
 * Insert an entry to MSHR, replace LRU if necessary
 *
 ************************************************************************************/
MSHR::Node* MSHR::AddEntry(ADDRINT addr) {
  Node *node = Find(addr);

  if(node != NULL) {
    return node;
  }
  else {
    node = mListTail;
    MSHREntry* entry = &(node->_item);

    DelFrmMSHRlist(entry->addr);

    entry->addr = addr;
    AddToMSHRlist(entry->addr, node);

    BringsToHead(node);
    return node;
  }
}

/*************************************************************************************
 * MSHR::AddEntry
 *
 * Delete an entry 
 *
 ************************************************************************************/
void MSHR::DelEntry(ADDRINT addr) {
  Node *node = Find(addr);

  if(node != NULL) {
    MSHREntry* entry = &(node->_item);

    DelFrmMSHRlist(entry->addr);

    entry->addr = 0;
    BringsToTail(node);
  }
  else {
    return;
  }
}

/*************************************************************************************
 * MSHR::Find, AddToMSHRlist, DelFrmMSHRlist
 *
 * Address indexing operations
 *
 ************************************************************************************/
MSHR::Node* MSHR::Find( ADDRINT addr )
{
  ADDRINT baddr = AddrOperation::GetCacheBlockAddr(addr, blocksize);
  iter = mshrlist.find(baddr);
  if( iter != mshrlist.end() ) 
    {
      return iter->second;
    }

  return NULL;
}

void MSHR::AddToMSHRlist( ADDRINT addr, Node *tmp ) 
{
  ADDRINT baddr = AddrOperation::GetCacheBlockAddr(addr, blocksize);
  mshrlist[ baddr  ] = tmp;
}

void MSHR::DelFrmMSHRlist( ADDRINT addr ) 
{
  ADDRINT baddr = AddrOperation::GetCacheBlockAddr(addr, blocksize);
  mshrlist.erase( baddr );
}

void MSHR::ShowMSHR(stringstream& ss) {
  Node *node = mListHead;
  ss << "ShowMSHR:";
  while(node != NULL) {
    MSHREntry *entry = &(node->_item);
    ss << hex << "(" << entry->addr << ")";
    node = node->_next;
  } 
}

///////////////////////////////////////////////////////////////////////////////
// Methods of Class MyStream
///////////////////////////////////////////////////////////////////////////////

/*************************************************************************************
 * MyStream::OnMiss
 *
 * Miss handing:
 * 1.Look for the stream entry which monitors the miss, if found, go to 2
 *   if not found, use the not MSHR filtered miss to train new stream;
 * 2.Use the miss (MSHR filtered or not) to revise/detect constant stride
 * 3.Issue prefetch requests:
 *   If the miss is regarded as a late prefetch (prefetched, but not in cache now, detect in AccessTrainedEntry function), 
 *    then ignore it, no prefetches made
 *   Otherwise, do normal prefetch requests
 *
 ************************************************************************************/
void MyStream::OnMiss(stringstream& ss,
		      PrefetchData_t& prefdata, 
		      vector<CacheAddr_t>& requests,
		      COUNTER cycle,
		      bool isfiltered)
{
  ADDRINT miss_baddr;  // block address of the miss
  MyStreamEntry *entry = NULL;

  //ignore the first cycle
  if(prefdata.LastRequestCycle == 0)
    return;

  //clear the result first
  requests.clear();

  //update the prefetch table
  miss_baddr = GetBlockFromAddr(prefdata.DataAddr);
  bool islatepref;
  if(!isfiltered)
    entry = _stream_table->AccessTrainedEntry(miss_baddr, islatepref, cycle);

  if( entry == NULL ) {
    /****** if not found in streams, train it in training table *****/
    if(!isfiltered) {
      // train stream in the training table:
      MyTrainingTable::Node *tnode = _training_table->AccessEntry(0, miss_baddr, cycle);

      // if the training succeeds, then move the entry to stream table:
      if( (tnode != NULL) && tnode->_item.trained ) {
	MyStreamEntry sentry;
	// copy data:
	MoveFromTrainingToStream(tnode->_item, sentry);
	// add a stream entry to stream table:
	_stream_table->AddEntry(sentry, cycle);
	_stream_table->ShowAll();
	// clear up the training entry
	tnode->_item.Clear();
	_training_table->BringsToTail(tnode);
      }
    }
    return;
  }

  ConstantStrideRevise(entry, prefdata.DataAddr);
  // detect for constant stride
  ConstantStrideDetect(entry, prefdata.DataAddr);
  // update the original access is is repeating stream
  if(entry->isrepeat) {
    entry->original_baddr = GetBAddrFromAddr(prefdata.DataAddr);
    entry->isrepeat = false;
  }
  // update the last access
  _stream_table->SetLastAccessAddressToDist(*entry, prefdata.DataAddr);

  if(!isfiltered) {
    if(!islatepref)
      MyIssuePrefetches(ss, entry, cycle);
  }
}

/*************************************************************************************
 * MyStream::OnHit
 *
 * Hit handing:
 * 1.Look for the stream entry which monitors the hit address, if found, go to 2
 * 2.Use the hit to revise/detect constant stride
 * 3.If it's a repeat stream and the first time hit, set the original-addr with the hit address
 * 4.Issue prefetch requests:
 *   If the hit is regarded as a early prefetch (hit, but fall behind the stream's region, detect in AccessTrainedEntry function), 
 *    then ignore it, no prefetches made
 *   Otherwise, do normal prefetch requests
 *
 ************************************************************************************/
void MyStream::OnHit(stringstream& ss,
		   PrefetchData_t& prefdata, 
		   vector<CacheAddr_t>& requests,
		   COUNTER cycle)
{
  ADDRINT hit_baddr;  // block address of the miss

  //ignore the first cycle
  if(prefdata.LastRequestCycle == 0)
    return;

  //clear the result first
  requests.clear();

  //update the prefetch table
  bool islatepref;
  hit_baddr = GetBlockFromAddr(prefdata.DataAddr);
  MyStreamEntry *entry = _stream_table->AccessTrainedEntry(hit_baddr, islatepref, cycle);

  ss << "on hit,";
  if(entry == NULL) {
    return;
  }

  ConstantStrideRevise(entry, prefdata.DataAddr);
  // detect for constant stride
  ConstantStrideDetect(entry, prefdata.DataAddr);
  // update the original access is is repeating stream
  if(entry->isrepeat) {
    entry->original_baddr = GetBAddrFromAddr(prefdata.DataAddr);
    entry->isrepeat = false;
  }
  // update the last access
  _stream_table->SetLastAccessAddressToDist(*entry, prefdata.DataAddr);
  // issue prefetch requests
  if(!islatepref)
    MyIssuePrefetches(ss, entry, cycle);
}


/*************************************************************************************
 * MyStream::MyIssuePrefetches
 * 1. Get prefetch candidates;
 *    If there's a more than 1 block stride confirmed, then prefetch p+s, p+2s, p+d*s, where d is the prefetch degree (4)
 *    otherwise prefetch p+64, p+2*64, ..p+d*64, where 64 is the block size
 * 2. Issue prefetch requests;
 *    By calling IssueL2Prefetch() function, it makes prefetches. Stop when the function return the flag of queue full.
 * 3. Forward the monitored region;
 * 4. Check for repeated stream. If found, trigger early prefetches
 *    Detail of check is in LookForRepeatStream function.
 *
 ************************************************************************************/
void MyStream::MyIssuePrefetches(stringstream& ss, MyStreamEntry *entry, COUNTER cycle) 
{
  if(entry == NULL)
    return;

  vector<CacheAddr_t> requests;

  //1. Get prefetch candidates;
  GetPrefetchCandidates(ss, entry, requests, cycle);

  //2. Issue prefetch requests:
  int prefmade = 0;
  for(unsigned int j = 0; j < requests.size(); j++) {
    if(j==0)
      ss << " ---> prefetch ";

    bool queuefull = IssueL2Prefetch(cycle, requests[j]);
    if(queuefull) {
      ss << "q full,";
      break;
    }
    else {
      ss << hex << requests[j] << ",";
      prefmade ++;
      IncPrefnum();
      if(_enable_stream_merge) {
	SetPrefetchBit(1, requests[j]);
      }
    }
  }  

  //3. forward the monitored region 
  _stream_table->ForwardTrackingRegion(entry, _stream_prefetch_distance, prefmade);
  _stream_table->ShowMyStreamEntry(*entry);  

  //4. check for possible stream repeat and early prefetches
  if(_enable_stream_repeat) {
    vector<CacheAddr_t> new_requests;
    MyStreamEntry *repeat_entry = _stream_table->LookForRepeatStream(new_requests, *entry);

    unsigned int j;
    for( j = 0; j < new_requests.size(); j++) {
      if(j==0)
	ss << " ---> repeat prefetch ";

      bool queuefull = IssueL2Prefetch(cycle, new_requests[j]);
      if(queuefull) {
	ss << "q full,";
	break;
      }
      else {
	ss << hex << new_requests[j] << ",";
	IncPrefnum();
      }
    }  
    if(j >0) {
      ADDRINT region_start_baddr = _stream_table->GetRegionStartBAddrFromBDist(*repeat_entry);
      ADDRINT last_access_addr = _stream_table->GetLastAccessAddressFromDist(*repeat_entry);
      repeat_entry->region_end_addr = new_requests[j-1];
      _stream_table->SetRegionStartBAddrToBDist(*repeat_entry, region_start_baddr);
      _stream_table->SetLastAccessAddressToDist(*repeat_entry, last_access_addr);
      repeat_entry->isrepeat = true;
      cout << "repeat stream:";
      _stream_table->ShowMyStreamEntry(*repeat_entry);  
    }
  }
}

/*************************************************************************************
 * MyStream::GetPrefetchCandidates
 *    If there's a more than 1 block stride confirmed, then prefetch p+s, p+2s, p+d*s, where d is the prefetch degree (4)
 *    otherwise prefetch p+64, p+2*64, ..p+d*64, where 64 is the block size
 *
 ************************************************************************************/
void MyStream::GetPrefetchCandidates(stringstream& ss, MyStreamEntry *entry, vector<CacheAddr_t>& requests, COUNTER cycle)
{
  UINT32 j;
  ADDRINT stride;
  ADDRINT last_access_addr;
  ADDRINT last_prefetch_addr;

  if(entry == NULL)
    return;

  requests.clear();

  ss << " recommend ";
  //prefetch for "pref_degree" of next addresses
  stride = (entry->stride_confirm)?entry->stride:_blocksize; // >= 1 block
  last_access_addr = _stream_table->GetLastAccessAddressFromDist(*entry);

  if(entry->ascending) {
    ADDRINT maxaddr = ( GetAddrFromBAddr(GetBAddrFromAddr(entry->region_end_addr)+1) ) - 1;
    ADDRINT num_stride = (maxaddr - last_access_addr)/stride;
    last_prefetch_addr = last_access_addr + (num_stride * stride);
  }
  else {
    ADDRINT minaddr = GetAddrFromBAddr( GetBAddrFromAddr(entry->region_end_addr) );
    ADDRINT num_stride = (last_access_addr - minaddr)/stride;
    last_prefetch_addr = last_access_addr - (num_stride * stride);
  }

  ADDRINT pref_addr;
  for(j = 1; j <= _pref_degree; j++) {
    if(entry->ascending)
      pref_addr = (last_prefetch_addr + j*stride);
    else
      pref_addr = (last_prefetch_addr - j*stride);

    ss << hex << pref_addr << ",";
    //entry->prefmade ++;
    requests.push_back( pref_addr );
  }
}

/*************************************************************************************
 * MyStream::ClearConstantStride
 *    Reset the constant stride related bits
 *
 ************************************************************************************/
void MyStream::ClearConstantStride(MyStreamEntry *entry) {
  entry->stride_confirm = false;
  entry->csd1 = false;
  entry->csd2 = false;
  entry->stride = _blocksize;
}

/*************************************************************************************
 * MyStream::ConstantStrideRevise
 *  Check for any hit/miss which may violate the constant stride.
 *  If so, reset the stride to 1 block and keep detecting for constant stride
 *
 ************************************************************************************/
void MyStream::ConstantStrideRevise(MyStreamEntry* entry, ADDRINT addr) {
  if(!_enable_constant_stride)
    return;

  ADDRINT stride = (entry->stride_confirm)?entry->stride:_blocksize; // >= 1 block

  if(entry->ascending) {
    if( entry->stride_confirm && (entry->stride>_blocksize) && (addr <= entry->region_end_addr) ) {
      if( ((entry->region_end_addr - addr) % stride) != 0 ) {
	ClearConstantStride(entry);
      }
    }
  }
  else {
    if( entry->stride_confirm && (entry->stride>_blocksize) && (addr >= entry->region_end_addr) ) {
      if( ((addr - entry->region_end_addr) % stride) != 0 ) {
	ClearConstantStride(entry);
      }
    }
  }
}

/*************************************************************************************
 * MyStream::ConstantStrideDetect
 *  Use the last 3 accesses (hit/miss) to detect a constant stride.
 *  If two stride are identical, then turn on the stride_confirm bit. 
 *  In case the stride is less than 1 block, set it to 1 block; otherwise keep the detected stride
 *  If no two consecutive identical strides found, keep looking for.
 *
 ************************************************************************************/
void MyStream::ConstantStrideDetect(MyStreamEntry* entry, ADDRINT addr)
{
  if(!_enable_constant_stride)
    return;

  if(entry == NULL)
    return;

  if(entry->stride_confirm && (entry->stride > _blocksize) )
    return;

  _stream_table->ShowMyStreamEntry(*entry);

  ADDRINT old_last_access_addr = _stream_table->GetLastAccessAddressFromDist(*entry);
  signed long long diff = (signed long long)addr - (signed long long)old_last_access_addr;
  ADDRINT udiff = (diff>0)?diff:-diff;
  
  if( !entry->csd1 ) {
    _stream_table->SetLastAccessAddressToDist(*entry, addr);
    entry->csd1 = true;
  }
  else if( entry->csd1 && !entry->csd2 ) {
    // if the stride is opposite to the direction, then quit stride detection, use 1 block as stride
    if( (entry->ascending && (diff<=0)) || (!entry->ascending && (diff>=0)) ) {
      entry->stride_confirm = false;
      entry->stride = _blocksize;
    }
    else {
      entry->stride = udiff;
      entry->csd2 = true;
    }
  }
  else {
    if( (entry->ascending && (diff<=0)) || (!entry->ascending && (diff>=0)) 
	|| (udiff != entry->stride) ) {
      entry->stride_confirm = false;
      entry->stride = _blocksize;
      entry->csd2 = false;
    }
    else {
      //found a constant stride in byte address: if the stride <= 1 block, set it as 1 block.
      entry->stride_confirm = true;
      if(udiff>_blocksize) {
	entry->stride = udiff;
	//cout << "found constant stride " << dec << udiff << ",";
      }
      else {
	//cout << "found constant stride " << dec << udiff << ",";
	entry->stride = _blocksize;
      }
    }  
  }

  _stream_table->SetLastAccessAddressToDist(*entry, addr);

  _stream_table->ShowMyStreamEntry(*entry);
}

/*************************************************************************************
 * MyStream::OnPrefetchHit
 *
 * Prefetch Hit handing:
 *   For statistics purpose only
 *
 ************************************************************************************/
void MyStream::OnPrefetchHit(stringstream& ss,
			   PrefetchData_t& prefdata, 
			   vector<CacheAddr_t>& requests,
			   COUNTER cycle)
{
  //ignore the first cycle
  if(prefdata.LastRequestCycle == 0)
    return;

  //clear the result first
  requests.clear();

  //increment the counter
}

/*************************************************************************************
 * MyStream::MoveFromTrainingToStream
 *
 * After a stream is trained, move it from training table to stream table;
 * Set the region end address of the stream as end_addr + (distance between end_addr and second_addr)
 *
 ************************************************************************************/
void MyStream::MoveFromTrainingToStream(MyTrainingEntry& tent, MyStreamEntry& sent)
{
  if(!tent.trained)
    return;

  sent.Clear();
  sent.original_baddr = tent.start_baddr;
  ADDRINT region_end_baddr = tent.start_baddr + tent.end_baddr_dist + (tent.end_baddr_dist - tent.second_baddr_dist);
  sent.region_end_addr = GetAddrFromBAddr(region_end_baddr);

  sent.ascending = tent.ascending;

  _stream_table->SetRegionStartBAddrToBDist(sent, sent.original_baddr);   
  _stream_table->SetLastAccessAddressToDist(sent, sent.region_end_addr);
}


///////////////////////////////////////////////////////////////////////////////
// Methods of Class MyTrainingTable
///////////////////////////////////////////////////////////////////////////////



/*************************************************************************************
 * MyTrainingTable::RenewEntry
 *
 * Reclaim the failed training entry:
 * Shift out start_addr, use the second and end address as the new start and second address
 * If the distance of the second and end address exceeds the 16 blocks, only set the start addr
 * 
 ************************************************************************************/
void MyTrainingTable::RenewEntry(MyTrainingEntry& entry, COUNTER cycle) {
  INT32 end_second_dist = entry.end_baddr_dist - entry.second_baddr_dist;
  ADDRINT second_baddr = entry.GetSecondBAddr();
  ADDRINT end_baddr = entry.GetEndBAddr();
  
  entry.Clear();
  if( (end_baddr >= second_baddr - Common::STREAM_MAX_NEIGHBOR_DISTANCE) &&
      (end_baddr <= second_baddr + Common::STREAM_MAX_NEIGHBOR_DISTANCE) ) {
    entry.start_baddr = second_baddr;
    entry.second_baddr_dist = end_second_dist;
  }
  else {
    entry.start_baddr = end_baddr;    
  }
}

/*************************************************************************************
 * MyTrainingTable::AccessEntry
 *
 * Train the stream:
 * 1.Look for the entry into which the new miss falls into its training window (+/- 16 blocks),
 *   if none found, create a new entry;
 * 2.If it’s the second address, stores it in the second_addr field;
 * 3.If it’s the third address, check whether the three misses are in same direction. 
 *       If so, create a stream entry, set the ascending bit and release the training entry.
 *       Otherwise, go to 3;
 * 4 If the address distance between the start_addr and second_addr is +/- 1, 
 *       turn on the noise flag, ignore the second address, 
 *       and use the third one as the second to continue training.
 *
 ************************************************************************************/
MyTrainingTable::Node * MyTrainingTable::AccessEntry(UINT32 threadId, ADDRINT baddr, COUNTER cycle)
{
  if(baddr == 0)
    return NULL;

  /* 1.Look for the entry into which the new miss falls into its training window (+/- 16 blocks), */
  Node* node = mListHead;
  while (node != NULL) {
    MyTrainingEntry* ent = &(node->_item);
    // end of search if start_addr =0
    if(ent->start_baddr == 0) {
      node = NULL;
      break;
    }
    
    // check whether it falles into +/- 16 blocks of start_addr, to get trained
    if( (baddr >= ent->start_baddr - Common::STREAM_MAX_NEIGHBOR_DISTANCE) &&
	(baddr <= ent->start_baddr + Common::STREAM_MAX_NEIGHBOR_DISTANCE) ) {
      break;
    }
    
    node=node->_next;
  }

  MyTrainingEntry* entry;
  // If none found, allocate an entry for it to train
  if ( node == NULL ) { 
    /// Replace tail
    node = mListTail;

    entry = &(node->_item);

    // create a new entry
    entry->Clear();
    entry->start_baddr = baddr;
    ShowEntry(*entry);
  }
  // If found one entry existing, train the stream
  else {
    entry = &(node->_item);

    // proceed only when the addr not equal to start_addr and second_addr, but within +/- 16 blocks
    if( (baddr != entry->start_baddr) && (baddr != entry->GetSecondBAddr())
	&& ( baddr >= entry->start_baddr - Common::STREAM_MAX_NEIGHBOR_DISTANCE )
	&& ( baddr <= entry->start_baddr + Common::STREAM_MAX_NEIGHBOR_DISTANCE ) ) {

      /* 2.If it’s the second address, stores it in the second_addr field; */
      if( entry->second_baddr_dist == 0) {
	entry->second_baddr_dist = entry->GetBAddrDist(baddr);
	entry->noise_flag = 0;
      }
      /* 3 */
      else {
	entry->end_baddr_dist = entry->GetBAddrDist(baddr);

	INT32 end_second_dist = entry->end_baddr_dist - entry->second_baddr_dist;

	// Case 1:
	if(entry->second_baddr_dist > 1) {
	  if(end_second_dist >= 1) {
	    entry->trained = true;
	    entry->ascending = true; //trained
	  }
	  else if (end_second_dist < -1) {
	    RenewEntry(*entry, cycle);
	  }
	  else if(end_second_dist == -1) {
	    if(entry->noise_flag) {
	    }
	    else {
	      RenewEntry(*entry, cycle);
	    }
	  }
	}
	// Case 2:
	else if(entry->second_baddr_dist == 1) {
	  if(end_second_dist >= 1) {
	    entry->trained = true; //trained
	    entry->ascending = true;
	  }
	  else if(end_second_dist < 0) {
	    if(_enable_noise_removal) {
	      /* 4. turn on the noise flag, ignore the second address */
	      entry->second_baddr_dist += end_second_dist;
	      entry->noise_flag = true;
	    }
	    else {
	      RenewEntry(*entry, cycle);
	    }
	  }	  
	}
	// Case 3:
	else if(entry->second_baddr_dist == -1) {
	  if(end_second_dist <= -1) {
	    entry->trained = true; //trained
	    entry->ascending = false;
	  }
	  else if(end_second_dist > 0) {
	    if(_enable_noise_removal) {
	      /* 4. turn on the noise flag, ignore the second address */
	      entry->second_baddr_dist += end_second_dist;
	      entry->noise_flag = true;
	    }
	    else {
	      RenewEntry(*entry, cycle);
	    }
	  }	  
	}
	// Case 4:
	else if(entry->second_baddr_dist < -1) {
	  if(end_second_dist <= -1) {
	    entry->trained = true; //trained
	    entry->ascending = false;
	  }
	  else if (end_second_dist > 1) {
	    RenewEntry(*entry, cycle);
	  }
	  else if(end_second_dist == 1) {
	    if(entry->noise_flag) {
	    }
	    else {
	      RenewEntry(*entry, cycle);
	    }
	  }
	}
  
      }

    }
    else {
      /* NA */
    }
  }

  ShowEntry(*entry);
  BringsToHead(node);
  return node;
}

void MyTrainingTable::ShowEntry(MyTrainingEntry& entry) 
{
  return;
  cout << hex 
       << (entry.start_baddr << _blockbitnum) << "," 
       << dec
       << entry.second_baddr_dist << "," 
       << entry.end_baddr_dist << "," 
       << dec << entry.trained << "," 
       << entry.ascending << ",";
    
  cout << endl;
}

void MyTrainingTable::ShowTable() {
  return;
  Node *node = mListHead;
  cout << "StreamTrainingTable:" << endl;
  while(node != NULL) {
    if(node->_item.start_baddr == 0)
      break;
    ShowEntry(node->_item);
    node = node->_next;
  }
}

//////////////////////////////////////////////////////////////////////////////////////
// Methods of class MyStreamPrefetchTable, the stream table 
//
// Provides functions to make prefetch requests
//////////////////////////////////////////////////////////////////////////////////////




/*************************************************************************************
 * MyTrainingTable::AddEntry
 *
 * Add a new trained entry into stream table, replacing the LRU, and move to MRU
 *
 ************************************************************************************/
void MyStreamPrefetchTable::AddEntry(MyStreamEntry& newentry, COUNTER cycle) {
  /// Replace tail
  Node *node = mListTail;

  // clone the new entry
  node->_item = newentry;

  BringsToHead(node);
}


/*************************************************************************************
 * MyStreamPrefetchTable::AccessTrainedEntry
 *
 * Look for a stream entry that monitors the access, returns if found
 * To handle with the hit/miss that falls behind the prefetch region,
 *
 * one extra window with size of prefetch degree is given to collect the possible 
 * late prefetches (miss, behind the region) or early prefetches (hit, behind the region)
 * These special miss/hit will be used in constant stride detection/revise, but not trigger prefetches
 *
 ************************************************************************************/
MyStreamEntry* MyStreamPrefetchTable::AccessTrainedEntry(ADDRINT baddr, bool& islatepref, COUNTER cycle)
{
  if(baddr == 0)
    return NULL;

  islatepref = false;

  Node* node = mListHead;
  while (node != NULL) {
    MyStreamEntry* ent = &(node->_item);
    // end of search if start_addr =0
    if(ent->original_baddr == 0) {
      return NULL;
    }
    
    ADDRINT region_start_baddr = GetRegionStartBAddrFromBDist(*ent);
    ADDRINT region_end_baddr = GetBAddrFromAddr(ent->region_end_addr);
    ADDRINT stride = (ent->stride_confirm)?ent->stride:_blocksize; // >= 1 block

    if(ent->ascending) {
      if( (baddr >= region_start_baddr) && (baddr <= region_end_baddr) ) {
	BringsToHead(node);
	return ent;
      }
      else if( (baddr < region_start_baddr) && (baddr > region_start_baddr - GetBAddrFromAddr(_pref_degree * stride)) ) {
	islatepref = true;
	return ent;
      }
    }
    else {
      if( (baddr <= region_start_baddr) && (baddr >= region_end_baddr) ) {
	BringsToHead(node);
	return ent;
      }
      else if( (baddr > region_start_baddr) && (baddr < region_start_baddr + GetBAddrFromAddr(_pref_degree * stride)) ) {
	islatepref = true;
	return ent;
      }
    }

    node=node->_next;
  }  

  return NULL;
}

/*************************************************************************************
 * MyStreamPrefetchTable::FindPrefetchStream
 *
 * Look for the stream which may have issues prefetch for the given addr.
 * This is done by checking the boundary of original_baddr and region_end_addr
 * If the given addr falls on the region, it would have been prefetched by the stream.
 * This function is used in statistics.
 *
 ************************************************************************************/
MyStreamPrefetchTable::Node * MyStreamPrefetchTable::FindPrefetchStream(ADDRINT baddr)
{
  if(baddr == 0)
    return NULL;

  Node* node = mListHead;
  while (node != NULL) {
    MyStreamEntry* ent = &(node->_item);
    // end of search if start_addr =0
    if(ent->original_baddr == 0) {
      return NULL;
    }

    if(ent->ascending) {
      // the second_addr of trained stream is the last block which is NOT prefetched
      //if((baddr > ent->second_addr) && (baddr <= ent->end_addr)) {
      if((baddr > ent->original_baddr) && (baddr <= GetBAddrFromAddr(ent->region_end_addr)) ) {
	return node;
      }
    }
    else {
      if((baddr < ent->original_baddr) && (baddr >= GetBAddrFromAddr(ent->region_end_addr)) ) {
	return node;
      }
    }
    node=node->_next;
  }  

  return NULL;
}

/*************************************************************************************
 * MyStreamPrefetchTable::ForwardTrackingRegion
 *
 * After prefetches have been made, move forward the stream's monitored region.
 * How many blocks to move depends on the number of prefetches made and the stride of the stream.
 * For example, 8 prefetches are made and stride is 3 blocks, then move the region by 24 blocks
 * When startup, the region size may be less than the prefetch distance (64*stride), in this case, only the region_end_addr
 * increases/decreases. Until the region size becomes more or equal to 64*stride, move both boundaries to keep the region size 64*stride.
 *
 ************************************************************************************/
void MyStreamPrefetchTable::ForwardTrackingRegion(MyStreamEntry* entry, UINT32 prefdistance, UINT32 prefdegree) 
{
  ADDRINT stride;
  ADDRINT last_prefetch_addr;
  ADDRINT region_start_baddr;
  ADDRINT last_access_addr;

  if(entry == NULL)
    return;

  stride = (entry->stride_confirm)?entry->stride:_blocksize; // >= 1 block
  last_access_addr = GetLastAccessAddressFromDist(*entry);
  region_start_baddr = GetRegionStartBAddrFromBDist(*entry);

  if(entry->ascending) {
    ADDRINT maxaddr = ( GetAddrFromBAddr(GetBAddrFromAddr(entry->region_end_addr)+1) ) - 1;
    ADDRINT num_stride = (maxaddr - last_access_addr)/stride;
    last_prefetch_addr = last_access_addr + (num_stride * stride);
    entry->region_end_addr = last_prefetch_addr + prefdegree*stride;
  }
  else {
    ADDRINT minaddr = GetAddrFromBAddr( GetBAddrFromAddr(entry->region_end_addr) );
    ADDRINT num_stride = (last_access_addr - minaddr)/stride;
    last_prefetch_addr = last_access_addr - (num_stride * stride);
    entry->region_end_addr = last_prefetch_addr - prefdegree*stride;
  }

  SetLastAccessAddressToDist(*entry, last_access_addr);

  if(entry->ascending) {
    //keep prefdistance the max distance 
    ADDRINT num_stride = ( entry->region_end_addr - GetAddrFromBAddr(region_start_baddr) )/stride;
    if(num_stride > prefdistance) {
      region_start_baddr = GetBAddrFromAddr(entry->region_end_addr - prefdistance*stride);
    }
    SetRegionStartBAddrToBDist(*entry, region_start_baddr);
  }
  else {
    //keep prefdistance the max distance 
    ADDRINT num_stride = ( GetAddrFromBAddr(region_start_baddr) - entry->region_end_addr )/stride;
    if(num_stride > prefdistance) {
      region_start_baddr = GetBAddrFromAddr(entry->region_end_addr + prefdistance*stride);
    }
    SetRegionStartBAddrToBDist(*entry, region_start_baddr);
  }

  ShowMyStreamEntry(*entry);
}

/*************************************************************************************
 * MyStreamPrefetchTable::ShowAll, ShowMyStreamEntry
 *
 *  Output the stream table on screen.
 *
 ************************************************************************************/
void MyStreamPrefetchTable::ShowMyStreamEntry(MyStreamEntry& entry) 
{
  return;
  cout << hex 
       << (entry.original_baddr << _blockbitnum) << "," 
       << dec << entry.region_start_baddr_dist << "," 
       << hex << entry.region_end_addr << "," 
       << GetLastAccessAddressFromDist(entry) << ","
       << dec
       << entry.stride << ","    
       << entry.ascending << ","
       << entry.stride_confirm << ","
       << endl;
}

void MyStreamPrefetchTable::ShowAll() {
  return;
  Node *node = mListHead;
  cout << "StreamPrefetchTable:" << endl;
  while(node != NULL) {
    if(node->_item.original_baddr == 0)
      break;
    ShowMyStreamEntry(node->_item);
    node = node->_next;
  }
}

/*************************************************************************************
 * MyStreamPrefetchTable::LookForRepeatStream
 *
 *  Detect a repeated stream and trigger early prefetches of the starting area of the stream
 *  After one stream moves forward by prefetch degree, it checks for another stream which
 *  has almost the same orginal_addr and almost the same last access address, 
 *  also both entries are longer than a threshold ( 2*prefetch_distance in this prefetcher).
 *  If such a stream is found, then the current stream can be regarded as repetition of the old stream.
 *  Thus at this point, begins to prefetch the starting area of the current stream.
 *
 ************************************************************************************/
MyStreamEntry * MyStreamPrefetchTable::LookForRepeatStream(vector<CacheAddr_t>& requests, MyStreamEntry& newentry) {
  Node *node = mListHead;
  //ADDRINT new_region_start_baddr = GetRegionStartBAddrFromBDist(newentry);
  ADDRINT new_region_end_baddr = GetBAddrFromAddr(newentry.region_end_addr);
  ADDRINT new_original_baddr = newentry.original_baddr;
  ADDRINT new_last_access_baddr = GetBAddrFromAddr( GetLastAccessAddressFromDist(newentry) );
  ADDRINT new_length = (newentry.ascending)?(new_region_end_baddr - new_original_baddr):(new_original_baddr - new_region_end_baddr );

  while(node != NULL) {
    MyStreamEntry & entry = node->_item;
    //ADDRINT region_start_baddr = GetRegionStartBAddrFromBDist(entry);
    //ADDRINT region_end_baddr = GetBAddrFromAddr(entry.region_end_addr);
    ADDRINT original_baddr = entry.original_baddr;
    ADDRINT last_access_baddr = GetBAddrFromAddr( GetLastAccessAddressFromDist(entry) );
    //ADDRINT length = (entry.ascending)?(region_end_baddr - original_baddr):(original_baddr - region_end_baddr );

    if(entry.original_baddr == 0)
      break;

    if( &newentry == &entry) {
      node = node->_next;
      continue;
    }

    if( (newentry.ascending && entry.ascending) || 
	(!newentry.ascending && !entry.ascending) ) {
      if( (new_last_access_baddr <= (last_access_baddr + Common::STREAM_MAX_NEIGHBOR_DISTANCE) ) &&
	  (new_last_access_baddr >= (last_access_baddr - Common::STREAM_MAX_NEIGHBOR_DISTANCE) ) &&
	  (new_original_baddr <= (original_baddr + Common::STREAM_MAX_NEIGHBOR_DISTANCE) ) &&
	  (new_original_baddr >= (original_baddr - Common::STREAM_MAX_NEIGHBOR_DISTANCE) ) &&
	  (new_length > 2*_stream_prefetch_distance) ) {
	
	cout << "repeat stream ";
	ShowMyStreamEntry(newentry);
	ShowMyStreamEntry(entry);

	entry.original_baddr = (new_original_baddr < original_baddr)?new_original_baddr:original_baddr;
	entry.region_end_addr = GetAddrFromBAddr(entry.original_baddr);
	entry.region_start_baddr_dist = 0;
	entry.stride_confirm = false;
	entry.csd1 = false;
	entry.csd2 = false;
	entry.last_access_addr_dist = 0;

	for(unsigned int j = 0; j < _stream_prefetch_distance/2; j++) {
	  if(entry.ascending)
	    requests.push_back( GetAddrFromBAddr(entry.original_baddr +j) );
	  else
	    requests.push_back( GetAddrFromBAddr(entry.original_baddr -j) );
	}  
	

	ShowMyStreamEntry(entry);	

	BringsToHead(node);
	return(&entry);
	//break;
      }
    }

    node = node->_next;
  }
  return NULL;
}

void MyStream::GetSpecificStatistics() {
  /* Show the customized statistics */
}




//
//  Function to initialize the prefetchers.  DO NOT change the prototype of this
//  function.  You can change the body of the function by calling your necessary
//  initialization functions.
//
// Only have L2 prefetcher!!!
void InitPrefetchers() // DO NOT CHANGE THE PROTOTYPE
{
  pref2 = new MyStream();

  if(pref2 != NULL) {
    map<string, int>::iterator it;
    cout << pref2->GetPrefName() << " parameters: ";
    for( it=pref2->params.begin(); it!= pref2->params.end(); it++)
      cout << it->first << " = " << it->second << ", ";
    cout << endl;
  }
}


//
//  Function that is called every cycle to issue prefetches should the
//  prefetcher want to.  The arguments to the function are the current cycle,
//  the demand requests to L1 and L2 cache.  Again, DO NOT change the prototype of this
//  function.  You can change the body of the function by calling your necessary
//  routines to invoke your prefetcher.
//

// DO NOT CHANGE THE PROTOTYPE
void IssuePrefetches( COUNTER cycle, PrefetchData_t *L1Data, PrefetchData_t * L2Data )
{    

    // INSERT YOUR CHANGES IN HERE
    //unsigned int i, j;
    stringstream ss,ss1;

   // Issue L1 prefetches: no l1 prefetcher here!!!
    /*if(pref1 != NULL) {
      for(i = 0; i < 4; i++) {
        if((cycle == L1Data[i].LastRequestCycle) && (L1Data[i].hit == 0)) {
	  vector<CacheAddr_t> prefl1_requests;
	  pref1->OnMiss(ss, L1Data[i], prefl1_requests, cycle, false);
	  for(j=0; j<prefl1_requests.size(); j++) {
	    IssueL1Prefetch(cycle, prefl1_requests[j]);
	  }
	}
      }
      }*/

    // Update MSHR : check for each entry in MSHR, if it's in cache, remove it
    if( pref2->IsMSHREnabled() ) {
      MSHR::Node *mshrnode = pref2->GetMSHR()->mListHead;
      while(mshrnode != NULL) {
	ADDRINT testaddr = mshrnode->_item.addr;
	if(testaddr == 0)
	    break;
	if( GetPrefetchBit(1, testaddr) != -1 ) { // in cache now
	  pref2->DelMSHREntry(testaddr);
	}
	mshrnode = mshrnode->_next;
      }     
    }

    vector<CacheAddr_t> prefl2_requests;
    if( pref2 != NULL ) {
      if((cycle == L2Data->LastRequestCycle) && (L2Data->LastRequestAddr != 0) ) {
	if(L2Data->hit == 0) {
	  //Only when there's no matching entry in MSHR, the miss is a real miss:
	  bool isfiltered = false;
	  if( pref2->IsMSHREnabled() ) {
	    isfiltered = pref2->LookupMSHR(L2Data->DataAddr);
	  }

	  // OnMiss handling: make prefetch requests, or train stream
	  pref2->OnMiss(ss, *L2Data, prefl2_requests,cycle, isfiltered);
	}
	else {
	  // OnHit handling:  make prefetch requests
	  pref2->OnHit(ss, *L2Data, prefl2_requests, cycle);
	}
      
	if(L2Data->hit == 1) {
	  //hit info will also cause MSHR entry deletion:
	  pref2->DelMSHREntry(L2Data->DataAddr);

	  if( GetPrefetchBit(1, L2Data->DataAddr) == 1 ) {
	    pref2->IncPrefhit();
	    UnSetPrefetchBit(1, L2Data->DataAddr);
	    ss << "hit prefetch,";
	    // OnPrefetchHit handling:
	    pref2->OnPrefetchHit(ss, *L2Data, prefl2_requests, cycle);
	  }
	}

      }
    }
}