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;
}