Initial commit of OpenSPARC T2 architecture model.

[OpenSPARC-T2-SAM] / sam-t2 / sam / cpus / vonk / ss / api / memsync / src / TsoChecker.cc

// ========== Copyright Header Begin ==========================================
// 
// OpenSPARC T2 Processor File: TsoChecker.cc
// Copyright (c) 2006 Sun Microsystems, Inc.  All Rights Reserved.
// DO NOT ALTER OR REMOVE COPYRIGHT NOTICES.
// 
// The above named program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public
// License version 2 as published by the Free Software Foundation.
// 
// The above named 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 work; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
// 
// ========== Copyright Header End ============================================
/************************************************************************
**  
**  Copyright (C) 2002, Sun Microsystems, Inc.
**
**  Sun considers its source code as an unpublished, proprietary
**  trade secret and it is available only under strict license provisions.
**  This copyright notice is placed here only to protect Sun in the event 
**  the source is deemed a published work. Disassembly, decompilation,
**  or other means of reducing the object code to human readable form
**  is prohibited by the license agreement under which this code is
**  provided to the user or company in possession of this copy."
**
*************************************************************************/
#include "TsoChecker.h"
#include <sstream>
#include <time.h>

using namespace std;
using namespace Tso;

////////////////////////////////////////////////

Tso::TsoChecker::TsoChecker() :
    listSize_(0),
    nodeList_(NULL)
{
  fprintf(stdout, "# msync TsoChecker enabled. To disable, use -sas_run_args=-DNO_TSO_CHECKER\n");
}

////////////////////////////////////////////////

TsoChecker::TsoChecker( const TsoChecker & orig )
{
  maccHist_ = orig.maccHist_; 
}

////////////////////////////////////////////////

TsoChecker::~TsoChecker()
{

}

////////////////////////////////////////////////

const TsoChecker &
TsoChecker::operator=( const TsoChecker & rhs )
{
    return *this;
}

////////////////////////////////////////////////

bool
TsoChecker::operator==( const TsoChecker & rhs ) const
{ 
    return false;
}

////////////////////////////////////////////////

string
TsoChecker::toString() const
{
    ostringstream os;


    return os.str();
}

void 
TsoChecker::init(int nstrands)
{
    listSize_ = nstrands;
  nodeList_ = new list<TsoNode*>[nstrands];
  tmpList_  = new list<TsoNode*>[nstrands];
  lastPoIseq_  = new uint64_t[nstrands];

  for (int i = 0; i < nstrands; i++) {
    lastPoIseq_[i] = 0ull; 
  }
}

TsoNode*
TsoChecker::findNode(TsoCheckerCmd& cmd) 
{
    //MSYNC_DEBUG(8, "TsoChecker::findNode cmd=%s", cmd.toString().c_str());//DBX
    
  list<TsoNode*>::iterator ni;
  uint64_t  mask;

  if (tmpList_[cmd.getThrdId()].empty()) {
      //MSYNC_DEBUG(8, "TsoChecker::findNode tmpList_[%d] empty", cmd.getThrdId());//DBX
    return (NULL); 
  }
  
  mask = ((cmd.getItype() == ITYPE_BLOCK_LOAD) || (cmd.getItype() == ITYPE_BLOCK_STORE)) ? 
    BLK_OP_ADDR_MASK : ((cmd.getItype() == ITYPE_QUAD_LOAD) ? QUAD_OP_ADDR_MASK : FULL_ADDR_MASK);

  //MSYNC_DEBUG(8, "TsoChecker::findNode mask=%#x", mask);//DBX

  ni = tmpList_[cmd.getThrdId()].end(); 
  do {
    ni--;
    //MSYNC_DEBUG(8, "TsoChecker::findNode ni=%s", (*ni)->toString().c_str());//DBX
    if ((*ni)->getIseq() == cmd.getIseq() &&
	(*ni)->getItype() == cmd.getItype() &&
	((*ni)->getAddr() & mask) == (cmd.getAddr()& mask)) {
	//MSYNC_DEBUG(8, "TsoChecker::findNode match=%s", (*ni)->toString().c_str());//DBX
      return (*ni); 
    }
  } while (ni !=  tmpList_[cmd.getThrdId()].begin()); 

//   if (nodeList_[cmd.getThrdId()].empty()) {
//     return (NULL); 
//   }
//   ni = nodeList_[cmd.getThrdId()].end(); 
//   do {
//     ni--;
//     if ((*ni)->getIseq() == cmd.getIseq() &&
// 	(*ni)->getItype() == cmd.getItype() &&
// 	((*ni)->getAddr() & mask) == (cmd.getAddr() & mask)) {
//       MS_ASSERT(false, "Should not find node in the nodeList_"); 
//       return (*ni); 
//     }
//   } while (ni !=  nodeList_[cmd.getThrdId()].begin()); 

  return (NULL); 
}

TsoNode*
TsoChecker::findPrev(enum TSO_NODE_TYPE ntype, uint32_t tid) 
{
  list<TsoNode*>::iterator ni;
  
  if (nodeList_[tid].empty()) {
    return (NULL); 
  }
  
  ni = nodeList_[tid].end(); 
  do {
    ni--;
    switch (ntype) {
    case TSO_LOAD:
      if ((*ni)->isTsoLoad()) { 
	return (*ni); 
      }
      break;
    case TSO_STORE:
      if ((*ni)->isTsoStore()) { 
	return (*ni); 
      }
      break;
    default:
      break;
    }
  } while (ni !=  nodeList_[tid].begin());
  
  return (NULL); 
}

void 
TsoChecker::formDataDependenceEdges(TsoNode *np) 
{
  if (np->isTSO()) {
    if (np->isStoreCommit()) {
      maccHist_.storeCommit(np); 
    } else if (np->isLoadData()) {
      if (np->getDsrc() != DSRC_STB) {
	maccHist_.loadAccess(np);
      }
    } 
  }
}

void
TsoChecker::formProgramOrderEdges(uint32_t tid)
{
  list<TsoNode*>::iterator ni;
  TsoNode                  *np;
  TsoEdge                  edge;

  for (ni = tmpList_[tid].begin(); ni != tmpList_[tid].end(); ni++) {

    MSYNC_DEBUG(8, "tmpList %s", (*ni)->toString().c_str()); 

    if ((*ni)->getIseq() != (lastPoIseq_[tid] + 1)) {
	//MSYNC_DEBUG(8, "TsoChecker iseq not in contiguous sequence, ni=%d, last=%d", (*ni)->getIseq(), (lastPoIseq_[tid] + 1));//DBX
      break;               // not in contiguous sequence
    } else {
      lastPoIseq_[tid]++;
      //MSYNC_DEBUG(8, "TsoChecker lastPoIseq_[%d]=%d", tid, lastPoIseq_[tid]);//DBX
    }
      
    if ((*ni)->isTsoLoad()) {
      if (np = findPrev(TSO_LOAD, tid)) {
	edge.addEdge (ET_PROG, np, (*ni));
	np->setLastLoad(false); 
	(*ni)->setLastLoad(true);
      } else { // This can only possible if this is the 1st tsoLoad, not necessary iseq=1
	(*ni)->setLastLoad(true);
      }
    }
    if ((*ni)->isTsoStore()) {
      if (np = findPrev(TSO_LOAD, tid)) {
	  edge.addEdge (ET_PROG, np, (*ni));
      }
      if (np = findPrev(TSO_STORE, tid)) {
	edge.addEdge (ET_PROG, np, (*ni));
	np->setLastStore(false); 
	(*ni)->setLastStore(true);
      } else {
	(*ni)->setLastStore(true);
      }
    }
    if ((*ni)->isTSO()) { // atomic is both TsoLoad and TsoStore, but contains only one node
      nodeList_[tid].push_back(*ni);
    }
  }
  if (ni != tmpList_[tid].end()) {
      tmpList_[tid].erase(tmpList_[tid].begin(), ni); 
  }
}

void
TsoChecker::input(TsoCheckerCmd& cmd) 
{
  /* create Node */
  TsoNode* node; // = new TsoNode(cmd); 
  TsoNode* node1;
  list<TsoNode*>::iterator ni;
  TsoEdge  edge;
  bool     doProgramOrder;
  bool     newNode;

  uint32_t tid = cmd.getThrdId(); 

  doProgramOrder = false;
  newNode = false;

  setTime(cmd.getTime());

  if (node = findNode(cmd)) {
    /********************************************************************************
     * This path indicates the instruction corresponds to the node consists of 
     * multiple TSO nodes. The algorithm requires some content of the node been
     * updated according to the new cmd, and the old content of node been pushed 
     * to the nodes_ list. Doing so, one instruction can appear as one node in
     * the TSO digraph.
     ********************************************************************************/
    switch (cmd.getItype()) {
      node1 = new TsoNode(*node);
    case ITYPE_ATOMIC:
      // this one must be the store part of the atomic, change content to SC
      if (cmd.getCmd() != MEM_STORE_COMMIT)
      {
        MS_ERROR("Atomic does not follow load-store order. tid=%d  PA=%llx", tid, cmd.getAddr());
        return;
      }
      node->setCommit(cmd.getMacc());
      node->setGobs(cmd.getGobs()); 
      node->setData(cmd.getData()); 
      node->setCmd(cmd.getCmd()); 
      node->setSizeV(cmd.getSizeV()); 
      node->setOld(0); 
      node->nodePush(node1);
      node->incNcnt(); 
      break;
    case ITYPE_QUAD_LOAD:
      node->setCommit(cmd.getMacc());
      node->setData(cmd.getData()); 
      node->setAddr(cmd.getAddr()); 
      node->setSizeV(cmd.getSizeV()); 
      node->nodePush(node1);
      node->incNcnt();     
      break;
    default:
      MS_ERROR("Encountered instruction type that should have only one TSO node. tid=%d  PA=%llx", tid, cmd.getAddr()); 
      return;
    }
  } else { // not atomic or atomic but new 
    node = new TsoNode(cmd); 
    if (cmd.isAtomic()) {
      MSYNC_DEBUG(8, "atomic-node=%s", node->toString().c_str());
      if (cmd.getCmd() != MEM_LOAD_DATA)
      {
        MS_ERROR("Atomic node creation should go with LoadData. tid=%d  PA=%llx", tid, cmd.getAddr()); 
        return;
      }
    }
    newNode = true;
  }
  
//   if ((cmd.isAtomic() && cmd.isStoreCommit()) ||
//       !cmd.isAtomic()) {
  if (node->allEntriesArrive()) {
    doProgramOrder = (node->getIseq() == (lastPoIseq_[tid] + 1)) ? true : false;
  }

  MSYNC_DEBUG(6, "node=%s", node->toString().c_str());

  /* Note that the node's entry type is not valid for atomic instruction
     whose LoadData and StoreCommit share the same node. Therefore, the
     entry type is always LoadData. That is why the MemoryAccessHistory
     action uses cmd.isStoreCommit() and cmd.isLoadData() for conditional
     check. An atomic instruction that has both load and store parts should
     perform both maccHist_.storeCommit() and maccHist_.loadAccess().

     Since an atomic node can be processed in both if-else parts, the
     program order edge may be formed to times. The edge.addEdge() 
     will detect this, and force only one edge is formed.
  */

  /* note that the iseq coming to this function could be out of order */


  /* Form data dependence edges */
  formDataDependenceEdges(node); 

  if (newNode) {
    tmpListInsert (tid, node); 
    MSYNC_DEBUG(6, "tmpList size=%d %s", 
			      tmpList_[tid].size(), node->toString().c_str());    
  }

  /* Form program order edges */
  if (doProgramOrder) {
    if (tmpList_[tid].empty())
    {
      MS_ERROR("tmpList cannot be empty. tid=%d  PA=%llx", tid, cmd.getAddr());
      return;
    }
    formProgramOrderEdges(tid);
  }
        
  /* Cycle check and prun nodes */

  bool removed;
  do {
    removed = false;
    for (ni = nodeList_[tid].begin(); ni != nodeList_[tid].end(); ni++) {
      MSYNC_DEBUG(6, "Check %s", (*ni)->toString().c_str()); 
      if (canRemove(*ni)) {
	if (checkCycle(*ni, *ni)) {
	  MSYNC_DEBUG(0, "Tso Violation: %s", (*ni)->toString().c_str()); 
	  printNodeList(ERROR); 
	  MemorySyncMessage::error("Tso Violation");
	} else { // no TSO violation
	  removeNode(*ni);
	  nodeList_[tid].erase(ni);
	  removed = true;
	  //	  delete(*ni); // need to make sure the node does not appear in other list 
	  break;
	}
      } 
    }
  } while (!nodeList_[tid].empty() && removed); 

}

void
TsoChecker::input(uint32_t tid, uint64_t iseq, enum INSTR_TYPE itype, enum MEM_CMD cmd, 
		  uint64_t addr, uint64_t data, uint8_t sizeV, enum DATA_SRC dsrc, 
		  uint64_t macc, uint64_t gobs, uint64_t time)
{
  TsoCheckerCmd tsocmd;

  tsocmd.setIseq(iseq); 
  tsocmd.setMacc(macc); 
  tsocmd.setGobs(gobs); 
  tsocmd.setThrdId(tid); 
  tsocmd.setItype(itype); 
  tsocmd.setCmd(cmd); 
  tsocmd.setAddr(addr); 
  tsocmd.setData(data); 
  tsocmd.setDsrc(dsrc); 
  tsocmd.setSizeV(sizeV); 
  tsocmd.setTime(time);

  MSYNC_DEBUG(6, "tsocmd=%s", tsocmd.toString().c_str());

  input(tsocmd); 
}

string
TsoChecker::printOutEdges(TsoNode* node) {

  ostringstream os;
  list<TsoEdge*>::iterator ei;

  // os << "nodePtr=" << node << endl;  
  for (ei = node->outBegin(); ei != node->outEnd(); ei++) {
    os << "  " << (char*) node->getNodeName() << " -> " << (char*) (*ei)->getDst()->getNodeName();
    os << " [label=" << '"' << edgeType[(*ei)->getType()] << '"' << "]" << ";" << endl;
  }

  return os.str();
}

void 
TsoChecker::printNodeList() 
{
  printNodeList(NORMAL); 
}

void
TsoChecker::printNodeList(int flag)
{
  list<TsoNode*>::iterator ni;
  TsoNode* nodePtr;
  ofstream out;

  if (flag == ERROR) {
    out.open("TsoViolationDiGraph"); 
  } else {
    out.open("TsoDiGraph"); 
  }
  if (!out) {
    cout << "Cannot Open File" << endl; 
  }
 
  //  cerr << "TsoChecker is printing TsoDiGraph" << endl;

  out << "digraph G {" << endl;
  out << "  center=true;" << endl;
  out << "  size=" << '"' << "7.5, 10" << '"' << ";" << endl;
  //out << "DBX: listSize=" << listSize_ << endl;//DBX
  int i;
  //for (i = 0; i < MAX_STRANDS; i++) {
  for (i = 0; i < listSize_; i++) {
      //out << "DBX: nodeList_[" << i << "]=" << &(nodeList_[i]) << endl;//DBX
      out << "# nodelist " << i << " size=" << nodeList_[i].size() << endl;
  }
  //for (i = 0; i < MAX_STRANDS; i++) {
  for (i = 0; i < listSize_; i++) {
    if (nodeList_[i].size() > 0) {
      out << "  subgraph cluster" << i << " {" << endl;
      out << "    label = " << '"' << "thread " << i << '"' << ";" << endl;
      for (ni = nodeList_[i].begin(); ni != nodeList_[i].end(); ni++) {	
	out << "    " << (char*) (*ni)->getNodeName();
	out << " [label=" << '"' << (*ni)->getIseq() << "," << mmitype[(*ni)->getItype()] << '"' << "];" << endl;
	MSYNC_DEBUG(6, "NodeList %s", (*ni)->toString().c_str()); 
      }
      out << "  }" << endl;
    }
  }
  
  //for (i = 0; i < MAX_STRANDS; i++) {
  for (i = 0; i < listSize_; i++) {
    if (nodeList_[i].size() > 0) {
      for (ni = nodeList_[i].begin(); ni != nodeList_[i].end(); ni++) {
	out << printOutEdges (*ni); 
      }
    }
  }
  
  out << "}" << endl;

}

bool
TsoChecker::checkCycle(TsoNode *np, TsoNode *start_np) 
{
  list<TsoEdge*>::iterator ei;
  TsoEdge                  *ep;
  TsoNode                  *np1;

  if (np->noInEdges()) return false;

  for (ei = np->inBegin(); ei != np->inEnd(); ei++) {
    ep = *ei;
    np1 = ep->getSrc();
    if (np1 == start_np) {
      MSYNC_DEBUG(0, "Tso Violation: %s", np1->toString().c_str()); 
      return true;
    } else {
      if (checkCycle(np1, start_np)) {
	MSYNC_DEBUG(0, "Tso Violation: %s", np1->toString().c_str()); 
	return true;
      }
    }
  }
  return false;
}

bool
TsoChecker::canRemove(TsoNode* np) 
{
//   return false;
//   if (np->getIseq() >= 20) return false;

  bool storeOk = false;
  bool loadOk = false;

  if (np->isStore() && !np->isLastStore() &&
      (np->isAllOld() && (np->getRetire() <= getTime()))) {
    storeOk = true;
  }
  if (np->isLoad() && !np->isLastLoad()) {
    loadOk = true;
  }

  if (np->isAtomic()) {
    return (storeOk && loadOk);
  } else {
    return (storeOk || loadOk); 
  }
}

void
TsoChecker::removeNode(TsoNode* np)
{
  //  MS_ASSERT(np->noInEdges(), "Node that is to be removed has in-edges"); 

  MSYNC_DEBUG(6, "Remove %s", np->toString().c_str());
  if (np->isStore()) {
    maccHist_.removeStoreNode(np);
  }
  np->removeEdges(); 
}

void
TsoChecker::tmpListInsert(uint32_t tid, TsoNode *np)
{
  list<TsoNode*>::iterator ni;
  list<TsoNode*>::iterator posi; // insert position iterator

  if (tmpList_[tid].empty()) {
    tmpList_[tid].push_back(np); 
    return;
  }

  for (ni = tmpList_[tid].begin(); ni != tmpList_[tid].end(); ni++) {
    if ((*ni)->getIseq() > np->getIseq()) {
      tmpList_[tid].insert(ni, np); 
      return; 
    }
  }

  tmpList_[tid].push_back(np); 
  return;
}