<commit_before>/*
 * This file is part of the MIAMI framework. For copyright information, see
 * the LICENSE file in the MIAMI root folder.  
 */
/* 
 * File: CFG.C
 * Author: <NAME>, <EMAIL>
 *
 * Implements the Control Flow Graph (CFG) for a routine. It extends the 
 * common PrivateCFG class implementation with functionality specifically 
 * needed for a CFG profiler.
 */

#include "miami_types.h"
#include <math.h>

// standard headers

#ifdef NO_STD_CHEADERS
# include <stdlib.h>
# include <string.h>
# include <assert.h>
# include <stdarg.h>
#else
# include <cstdlib>
# include <cstring>
# include <cassert>
using namespace std; // For compatibility with non-std C headers
#endif

#include <iostream>
#include <fstream>
#include <iomanip>

#include "fast_hashmap.h"

using std::ostream;
using std::endl;
using std::cout;
using std::cerr;
using std::setw;

#include "CFG.h"
#include "routine.h"
#include "debug_miami.h"

using namespace MIAMI;

//--------------------------------------------------------------------------------------------------------------------

CFG::CFG (Routine* _r, const std::string& func_name)
      : PrivateCFG(_r, func_name)
{
  // create a node that will act as the cfg entry node
  cfg_entry = MakeNode(0, 0, MIAMI_CFG_BLOCK);
  cfg_entry->setNodeFlags(NODE_IS_CFG_ENTRY);
  PrivateCFG::add(cfg_entry);
  // and a node that will act as the cfg exit node
  cfg_exit = MakeNode(0, 0, MIAMI_CFG_BLOCK);
  cfg_exit->setNodeFlags(NODE_IS_CFG_EXIT);
  PrivateCFG::add(cfg_exit);
}

//--------------------------------------------------------------------------------------------------------------------
CFG::~CFG()
{
}

//--------------------------------------------------------------------------------------------------------------------
void 
CFG::add (DGraph::Edge* de)
{
   setCfgFlags(CFG_GRAPH_IS_MODIFIED);
   DGraph::add(de);
   Edge *e = static_cast<Edge*>(de);
   if (e->getType()==MIAMI_DIRECT_BRANCH_EDGE || e->getType()==MIAMI_INDIRECT_BRANCH_EDGE)
      e->setCounterEdge();
}
//--------------------------------------------------------------------------------------------------------------------

void 
CFG::saveToFile(FILE *fd, addrtype base_addr, LoadModule *myimg, 
                  const MIAMI_CFG::count_type *thr_counters, 
                  MIAMI_CFG::MiamiCfgStats &stats)
{
   // traverse prospectiveEdges first and check for any indirect branches that
   // have counts. If they are still in prospectiveEdges, it means they were
   // interprocedural jumps, so add a call surrogate node for each such edge
   // and then a return edge from the call surrogate to the cfg exit node.
   // Save the target address in the call surrogate node in case I use it later.
   // I can also have direct jumps to another routine, so do not limit the test
   // only to indirect jumps
   // gmarin, 04/13/2012: News flash: I can also have a fall-through edge which was
   // even taken, but not recorded. This happens in optimized libraries where you fall
   // through from one routine to another. The fall-through edge is added without a 
   // counter. We need to preserve any FALL_THROUGH edges that go to the cfg_exit node.
   // gmarin, 05/15/2012: I add explicit return edges from each call surrogate block.
   // Do not keep prospective fall-through edges that originate at call surrogate blocks. 
   // gmarin, 2013/10/16: Due to bad routine boundaries from PIN, sometimes I add
   // a fall-thru edge to the cfg exit node because that is the reported routine end, 
   // but then I get a trace that crosses that boundary, so I create a new fall-thru
   // edge. Do not keep fall-thru edges to cfg-exit if the source node has another
   // fall-thru edge.
   EdgeMap::iterator eit = prospectiveEdges.begin();
   for ( ; eit!=prospectiveEdges.end() ; )
   {
      EdgeMap::iterator tmp =  eit;
      Edge *e = static_cast<Edge*>(eit->second);
      if ( (e->type==MIAMI_INDIRECT_BRANCH_EDGE || e->type==MIAMI_DIRECT_BRANCH_EDGE) && 
           (eit->first<in_routine->Start() || eit->first>=in_routine->End()) )
      {
         // it is an indirect jump outside of current routine; create a call surogate node 
         // as sink
         addrtype eaddr = e->source()->getEndAddress();
         Node *n = MakeNode(eaddr, eaddr, MIAMI_CALL_SITE);
         setCfgFlags(CFG_GRAPH_IS_MODIFIED);
         DGraph::add(n);
         
         n->setTarget(eit->first);
         e->sink()->incoming_edges.remove(e);
         n->incoming_edges.push_back(e);
         e->ChangeSink(n);
         e->setProspectiveEdge(false);
      } else
      if (e->type==MIAMI_FALLTHRU_EDGE && e->source()->isCallSurrogate())
      {
         // I should not remove prospective edges when dealing with multi-threaded 
         // programs. Other threads are still running and may still use these
         // prospective edges.
         assert (e->isProspectiveEdge());
         // remove(e); 
         // delete (e);
      }
      ++eit;
      if (! e->isProspectiveEdge())
         prospectiveEdges.erase(tmp);
   }

   // write number of nodes first (not including cfg_entry and cfg_exit)
   uint32_t nNodes = node_set.size() - 2;
   fwrite(&nNodes, 4, 1, fd);
   if (nNodes == 0) return;
   fwrite(&cfgFlags, 4, 1, fd);
   
   NodesIterator nit(*this);
   uint32_t actualNodes = 0;
   while ((bool)nit)
   {
      Node *nn = nit;
      if (nn->isCodeNode())
      {
         fwrite(&nn->id, 4, 1, fd);
         char type = (char)nn->type;
         fwrite(&type, 1, 1, fd);
         fwrite(&nn->flags, 4, 1, fd);
         addrtype temp_addr = nn->start_addr - base_addr;
         fwrite(&temp_addr, sizeof(addrtype), 1, fd);
         if (type == MIAMI_CALL_SITE)
            temp_addr = nn->target - base_addr;
         else
            temp_addr = nn->end_addr - base_addr;
         fwrite(&temp_addr, sizeof(addrtype), 1, fd);
         ++ actualNodes;
      }
      ++ nit;
   }
   if (nNodes != actualNodes)
   {
      fprintf(stderr, "Routine %s, wrote out %u nodes instead of the expected %u. Check this out.\n",
           routine_name.c_str(), actualNodes, nNodes);
      assert(nNodes == actualNodes);
   }
   
   EdgesIterator egit(*this);
   while ((bool)egit)
   {
      Edge *ee = egit;
      // some edges may be NULL after dynamic_cast from iterator because they are
      // CFG edges of type PrivateCFG::Edge (only happens if Top Nodes are computed,
      // like when a CFG is drawn)
      if (ee && ee->type!=MIAMI_CFG_EDGE && !ee->isProspectiveEdge() &&
            (ee->sink()!=cfg_exit || ee->type==MIAMI_RETURN_EDGE || ee->type==MIAMI_FALLTHRU_EDGE)
         )
      {
         if (ee->sink()==cfg_exit && ee->type==MIAMI_FALLTHRU_EDGE)  
         {
            // check if we have other fall-thru edges from the same source node
            bool has_fall_thru = false;
            OutgoingEdgesIterator ogit(ee->source());
            while ((bool)ogit)
            {
               Edge *oe = ogit;
               if (oe->type==MIAMI_FALLTHRU_EDGE && oe->sink()!=cfg_exit) // different fall-thru
               {
                  has_fall_thru = true;
                  break;
               }
               ++ ogit;
            }
            if (has_fall_thru)
            {
               ++ egit;
               continue;
            }
         }
         // no need to save the id, we will not use it later
         //fwrite(&ee->id, 4, 1, fd);<commit_msg>Preserve fall-thru edges from non-call blocks to cfg_exit<commit_after>/*
 * This file is part of the MIAMI framework. For copyright information, see
 * the LICENSE file in the MIAMI root folder.  
 */
/* 
 * File: CFG.C
 * Author: <NAME>, <EMAIL>
 *
 * Implements the Control Flow Graph (CFG) for a routine. It extends the 
 * common PrivateCFG class implementation with functionality specifically 
 * needed for a CFG profiler.
 */

#include "miami_types.h"
#include <math.h>

// standard headers

#ifdef NO_STD_CHEADERS
# include <stdlib.h>
# include <string.h>
# include <assert.h>
# include <stdarg.h>
#else
# include <cstdlib>
# include <cstring>
# include <cassert>
using namespace std; // For compatibility with non-std C headers
#endif

#include <iostream>
#include <fstream>
#include <iomanip>

#include "fast_hashmap.h"

using std::ostream;
using std::endl;
using std::cout;
using std::cerr;
using std::setw;

#include "CFG.h"
#include "routine.h"
#include "debug_miami.h"

using namespace MIAMI;

//--------------------------------------------------------------------------------------------------------------------

CFG::CFG (Routine* _r, const std::string& func_name)
      : PrivateCFG(_r, func_name)
{
  // create a node that will act as the cfg entry node
  cfg_entry = MakeNode(0, 0, MIAMI_CFG_BLOCK);
  cfg_entry->setNodeFlags(NODE_IS_CFG_ENTRY);
  PrivateCFG::add(cfg_entry);
  // and a node that will act as the cfg exit node
  cfg_exit = MakeNode(0, 0, MIAMI_CFG_BLOCK);
  cfg_exit->setNodeFlags(NODE_IS_CFG_EXIT);
  PrivateCFG::add(cfg_exit);
}

//--------------------------------------------------------------------------------------------------------------------
CFG::~CFG()
{
}

//--------------------------------------------------------------------------------------------------------------------
void 
CFG::add (DGraph::Edge* de)
{
   setCfgFlags(CFG_GRAPH_IS_MODIFIED);
   DGraph::add(de);
   Edge *e = static_cast<Edge*>(de);
   if (e->getType()==MIAMI_DIRECT_BRANCH_EDGE || e->getType()==MIAMI_INDIRECT_BRANCH_EDGE)
      e->setCounterEdge();
}
//--------------------------------------------------------------------------------------------------------------------

void 
CFG::saveToFile(FILE *fd, addrtype base_addr, LoadModule *myimg, 
                  const MIAMI_CFG::count_type *thr_counters, 
                  MIAMI_CFG::MiamiCfgStats &stats)
{
   // traverse prospectiveEdges first and check for any indirect branches that
   // have counts. If they are still in prospectiveEdges, it means they were
   // interprocedural jumps, so add a call surrogate node for each such edge
   // and then a return edge from the call surrogate to the cfg exit node.
   // Save the target address in the call surrogate node in case I use it later.
   // I can also have direct jumps to another routine, so do not limit the test
   // only to indirect jumps
   // gmarin, 04/13/2012: News flash: I can also have a fall-through edge which was
   // even taken, but not recorded. This happens in optimized libraries where you fall
   // through from one routine to another. The fall-through edge is added without a 
   // counter. We need to preserve any FALL_THROUGH edges that go to the cfg_exit node.
   // gmarin, 05/15/2012: I add explicit return edges from each call surrogate block.
   // Do not keep prospective fall-through edges that originate at call surrogate blocks. 
   // gmarin, 2013/10/16: Due to bad routine boundaries from PIN, sometimes I add
   // a fall-thru edge to the cfg exit node because that is the reported routine end, 
   // but then I get a trace that crosses that boundary, so I create a new fall-thru
   // edge. Do not keep fall-thru edges to cfg-exit if the source node has another
   // fall-thru edge.
   EdgeMap::iterator eit = prospectiveEdges.begin();
   for ( ; eit!=prospectiveEdges.end() ; )
   {
      EdgeMap::iterator tmp =  eit;
      Edge *e = static_cast<Edge*>(eit->second);
      if ( (e->type==MIAMI_INDIRECT_BRANCH_EDGE || e->type==MIAMI_DIRECT_BRANCH_EDGE) && 
           (eit->first<in_routine->Start() || eit->first>=in_routine->End()) )
      {
         // it is an indirect jump outside of current routine; create a call surogate node 
         // as sink
         addrtype eaddr = e->source()->getEndAddress();
         Node *n = MakeNode(eaddr, eaddr, MIAMI_CALL_SITE);
         setCfgFlags(CFG_GRAPH_IS_MODIFIED);
         DGraph::add(n);
         
         n->setTarget(eit->first);
         e->sink()->incoming_edges.remove(e);
         n->incoming_edges.push_back(e);
         e->ChangeSink(n);
         e->setProspectiveEdge(false);
      } else
      if (e->type==MIAMI_FALLTHRU_EDGE && e->source()->isCallSurrogate())
      {
         // I should not remove prospective edges when dealing with multi-threaded 
         // programs. Other threads are still running and may still use these
         // prospective edges.
         assert (e->isProspectiveEdge());
         // remove(e); 
         // delete (e);
      }
      ++eit;
      if (! e->isProspectiveEdge())
         prospectiveEdges.erase(tmp);
   }

   // write number of nodes first (not including cfg_entry and cfg_exit)
   uint32_t nNodes = node_set.size() - 2;
   fwrite(&nNodes, 4, 1, fd);
   if (nNodes == 0) return;
   fwrite(&cfgFlags, 4, 1, fd);
   
   NodesIterator nit(*this);
   uint32_t actualNodes = 0;
   while ((bool)nit)
   {
      Node *nn = nit;
      if (nn->isCodeNode())
      {
         fwrite(&nn->id, 4, 1, fd);
         char type = (char)nn->type;
         fwrite(&type, 1, 1, fd);
         fwrite(&nn->flags, 4, 1, fd);
         addrtype temp_addr = nn->start_addr - base_addr;
         fwrite(&temp_addr, sizeof(addrtype), 1, fd);
         if (type == MIAMI_CALL_SITE)
            temp_addr = nn->target - base_addr;
         else
            temp_addr = nn->end_addr - base_addr;
         fwrite(&temp_addr, sizeof(addrtype), 1, fd);
         ++ actualNodes;
      }
      ++ nit;
   }
   if (nNodes != actualNodes)
   {
      fprintf(stderr, "Routine %s, wrote out %u nodes instead of the expected %u. Check this out.\n",
           routine_name.c_str(), actualNodes, nNodes);
      assert(nNodes == actualNodes);
   }
   
   EdgesIterator egit(*this);
   while ((bool)egit)
   {
      Edge *ee = egit;
      // some edges may be NULL after dynamic_cast from iterator because they are
      // CFG edges of type PrivateCFG::Edge (only happens if Top Nodes are computed,
      // like when a CFG is drawn)
      if (ee && ee->type!=MIAMI_CFG_EDGE && 
              (!ee->isProspectiveEdge() || 
                    (!ee->source()->isCallSurrogate() && ee->type==MIAMI_FALLTHRU_EDGE)) &&
              (ee->sink()!=cfg_exit || ee->type==MIAMI_RETURN_EDGE || ee->type==MIAMI_FALLTHRU_EDGE)
         )
      {
         if (ee->sink()==cfg_exit && ee->type==MIAMI_FALLTHRU_EDGE)  
         {
            // check if we have other fall-thru edges from the same source node
            bool has_fall_thru = false;
            OutgoingEdgesIterator ogit(ee->source());
            while ((bool)ogit)
            {
               Edge *oe = ogit;
               if (oe->type==MIAMI_FALLTHRU_EDGE && oe->sink()!=cfg_exit) // different fall-thru
               {
                  has_fall_thru = true;
                  break;
               }
               ++ ogit;
            }
            if (has_fall_thru)
            {
               ++ egit;
               continue;
            }
         }
         // no need to save the id, we will not use it later
         //fwrite(&ee->id, 4, 1, fd);
{'fraction_non_alphanumeric': 0.17188438689006075, 'fraction_numerical': 0.006541619384553768, 'mean_word_length': 1.998198919351611, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 126, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4180685', 'n_tokens_mistral': 4688, 'n_tokens_neox': 4510, 'n_words': 1362}