path: root/src/pic16/pcodeflow.c

/*-------------------------------------------------------------------------

  pcodeflow.c - post code generation flow analysis

   Written By -  Scott Dattalo scott@dattalo.com
   Ported to PIC16 By -  Martin Dubuc m.dubuc@rogers.com

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version.
   
   This 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 program; if not, write to the Free Software
   Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
   
-------------------------------------------------------------------------*/
/*
  pcodeflow.c

  The purpose of the code in this file is to analyze the flow of the
  pCode.

*/

#include <stdio.h>

#include "common.h"   // Include everything in the SDCC src directory
#include "newalloc.h"
#include "ralloc.h"
#include "device.h"
#include "pcode.h"
#include "pcoderegs.h"
#include "pcodeflow.h"

#if 0

/* 
   In the section that follows, an exhaustive flow "tree" is built.
   It's not a tree that's really built, but instead every possible
   flow path is constructed. 

   This is really overkill...
*/

static set *FlowTree=NULL;

void dbg_dumpFlowTree(set *FlowTree)
{
  set *segment;
  pCodeFlow *pcflow;

  fprintf(stderr,"Flow Tree: \n");

  for(segment = setFirstItem(FlowTree); segment; segment=setNextItem(FlowTree)) {

    fprintf(stderr,"Segment:\n");

    for(pcflow=PCFL(setFirstItem(segment)); pcflow; pcflow=PCFL(setNextItem(segment))) {
      fprintf(stderr, "  0x%03x",pcflow->pc.seq);
    }
    fprintf(stderr,"\n");
  }

}




/*-----------------------------------------------------------------*
 * void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
 *-----------------------------------------------------------------*/
static void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
{

  int nNextFlow=0;
  pCodeFlowLink *pcflowLink=NULL;

  /* Add this flow to the set if it's not in there already */
  if(isinSet(segment, pcflow)) {
    addSetHead(&FlowTree, segment);
    return;
  }

  addSetHead(&segment, pcflow);

  /* Continue to add contiguous flows */

  while( pcflow->to && ((nNextFlow = elementsInSet(pcflow->to)) == 1)) {
    pcflowLink = (pCodeFlowLink *)(setFirstItem(pcflow->to));
    pcflow = pcflowLink->pcflow;

    if(isinSet(segment, pcflow)) {
      addSetIfnotP(&FlowTree, segment);
      return;
    }

    addSetIfnotP(&segment, pcflow);

  }

  /* Branch: for each branch, duplicate the set and recursively call */
  if(pcflow->to && nNextFlow>=2) {
    pCodeFlow *pcflow_to;

    set *branch_segment=NULL;
    
    pcflowLink = (pCodeFlowLink *)(setFirstItem(pcflow->to));
    pcflow_to = pcflowLink->pcflow;

    addSetIfnotP(&segment, pcflow);

    pcflowLink = (pCodeFlowLink *)(setNextItem(pcflow->to));

    while(pcflowLink) {

      branch_segment = setFromSet(segment);
      BuildFlowSegment(setFromSet(segment),pcflowLink->pcflow);
      pcflowLink = (pCodeFlowLink *)(setNextItem(pcflow->to));
    }

    /* add the first branch to this segment */
    BuildFlowSegment(segment,pcflow_to);

  }

  addSetIfnotP(&FlowTree, segment);

  /* done */
}

/*-----------------------------------------------------------------*
 * void pic16_BuildFlowTree(pBlock *pb)
 *-----------------------------------------------------------------*/
void pic16_BuildFlowTree(pBlock *pb)
{
  pCodeFlow *pcflow;
  set *segment;

  FlowTree = newSet();

  /* Start with the first flow object of this pBlock */

  pcflow = PCFL(pic16_findNextpCode(pb->pcHead, PC_FLOW));

  segment = newSet();
  BuildFlowSegment(segment, pcflow);

  pb->FlowTree = FlowTree;

  dbg_dumpFlowTree(FlowTree);
}

static void dbg_dumpFlow(pBlock *pb)
{
  pCode *pcflow;

  for( pcflow = pic16_findNextpCode(pb->pcHead, PC_FLOW); 
       pcflow != NULL;
       pcflow = pic16_findNextpCode(pcflow->next, PC_FLOW) ) {

    if(!isPCFL(pcflow))
      fprintf(stderr, "LinkFlow - pcflow is not a flow object ");

    fprintf(stderr, "Flow: 0x%x",pcflow->seq);
    if(PCFL(pcflow) && PCFL(pcflow)->ancestor)
      fprintf(stderr,", ancestor 0x%x\n",
	      PCFL(pcflow)->ancestor->pc.seq);
    else {
      pCodeFlowLink *from = (PCFL(pcflow)->from) ? (PCFLINK(setFirstItem(PCFL(pcflow)->from))) : NULL;
      fprintf(stderr," no ancestor");
      while(from) {
	fprintf(stderr," (0x%x)",from->pcflow->pc.seq);
	from = setNextItem(PCFL(pcflow)->from);
      }
      fprintf(stderr,"\n");
    }
  }
}
#endif

#if 0
/*-----------------------------------------------------------------*
 * void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
 *-----------------------------------------------------------------*/
static void BuildFlowSegment(pCodeFlow *pcflow)
{
  static int recursion=0;
  pCodeFlow *pcflow_other;
  set *flowset;

  if(!pcflow)
    return;

  if(recursion++ > 200) {
    fprintf(stderr, " exceeded recursion\n");
    return;
  }

  fprintf(stderr,"examining 0x%x\n",pcflow->pc.seq);

  if(pcflow->from) {


    flowset = pcflow->from;

    if(flowset && flowset->next == NULL) {

      /* 
	 There is a flow before this one. In fact, there's
	 exactly one flow before this one (because ->next is
	 NULL). That means all children of this node pass
	 through both this node and the node immediately 
	 before this one; i.e. they have the same ancestor.
      */

      if( (NULL == (pcflow_other = PCFLINK(flowset->item)->pcflow)) ||
	  (NULL == pcflow_other)) {
	fprintf(stderr,"2 error in flow link\n");
	exit(1);
      }
      pcflow->ancestor = pcflow_other->ancestor ;

      fprintf(stderr,"Assigning ancestor 0x%x from flow 0x%x\n",
	      pcflow->ancestor->pc.seq, pcflow_other->pc.seq);

    } else {

      if(flowset == NULL) {

	/* There are no flows before this one.
	 * If this is not the first flow object in the pBlock then 
	 * there's an error */

	if(!pcflow->ancestor) {
	  fprintf(stderr,"error in flow link\n");
	  exit(1);

	} 

      } else {

      	/* Flow passes to this flow from multiple flows. Let's
	   look at just one of these. If the one we look at has
	   an ancestor, then that's our ancestor too. If the one
	   we look at doesn't have an ancestor, then that means
	   we haven't traversed that branch of the call tree 
	   yet - but we will */

	pcflow_other = PCFLINK(flowset->item)->pcflow;
	if(pcflow_other) {
	  fprintf(stderr, "coming from 0x%x\n",pcflow_other->pc.seq);
	  if( pcflow_other->ancestor)
	    pcflow->ancestor = pcflow_other->ancestor;
	}
      }


    }

  } else {
    /* there are no nodes before this one */
    if(!pcflow->ancestor)
      fprintf(stderr,"3 Error in flow link\n");
  }

  /* Now let's recursively expand the call tree */

  if(pcflow->ancestor && pcflow->to) {
    flowset = pcflow->to;
    while(flowset) {
      BuildFlowSegment(PCFLINK(flowset->item)->pcflow);
      flowset = flowset->next;
    }
  }

}
#endif

void pic16_BuildFlowTree(pBlock *pb)
{
  pCodeFlow *first_pcflow, *pcflow;


  //  fprintf(stderr,"pic16_BuildFlowTree \n");

  first_pcflow = PCFL(pic16_findNextpCode(pb->pcHead, PC_FLOW));
  if(!first_pcflow)
    return;

  /* The very first node is like Adam, it's its own ancestor (i.e. 
   * there are no other flows in this pBlock prior to the first one).
   */

  first_pcflow->ancestor = first_pcflow;

  /* For each flow that has only one predecessor, it's easy to 
     identify the ancestor */
  pcflow = PCFL(pic16_findNextpCode(first_pcflow->pc.next, PC_FLOW));

  while(pcflow) {
    if(elementsInSet(pcflow->from) == 1) {
      pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));

      pcflow->ancestor = from->pcflow;
      /*
	fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x\n",
	pcflow->ancestor->pc.seq, pcflow->pc.seq);
      */
    }

    pcflow = PCFL(pic16_findNextpCode(pcflow->pc.next, PC_FLOW));

  }

  pcflow = PCFL(pic16_findNextpCode(first_pcflow->pc.next, PC_FLOW));

  while(pcflow) {
    if(elementsInSet(pcflow->from) > 1) {
      pCodeFlow *min_pcflow;
      pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));

      min_pcflow = from->pcflow;

      while( (from = setNextItem(pcflow->from)) != NULL) {
	if(from->pcflow->pc.seq < min_pcflow->pc.seq)
	  min_pcflow = from->pcflow;
      }

      pcflow->ancestor = min_pcflow;
      /*
	fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x from multiple\n",
	pcflow->ancestor->pc.seq, pcflow->pc.seq);
      */

    }

    pcflow = PCFL(pic16_findNextpCode(pcflow->pc.next, PC_FLOW));

  }
  
  //  BuildFlowSegment(pcflow);

  //dbg_dumpFlow(pb);
  
}