"ancestor" flow logic was implemented. Applied optimization patches from Frieder...

[fw/sdcc] / src / pic / pcodeflow.c

diff --git a/src/pic/pcodeflow.c b/src/pic/pcodeflow.c
index e3e47e0d4fc1035208010779c0f9d42b139b5c4c..7bc043861e71a2fb74a8333fd3c715b6bbc306e7 100644 (file)
--- a/src/pic/pcodeflow.c
+++ b/src/pic/pcodeflow.c
@@ -156,13 +156,9 @@ void BuildFlowTree(pBlock *pb)
 }
 #endif
 
-void BuildFlowTree(pBlock *pb)
+void dbg_dumpFlow(pBlock *pb)
 {
-  pCode *pc=NULL;
   pCode *pcflow;
-  pCode *pct;
-
-  //fprintf(stderr,"linkflow \n");
 
   for( pcflow = findNextpCode(pb->pcHead, PC_FLOW); 
        pcflow != NULL;
@@ -171,6 +167,183 @@ void BuildFlowTree(pBlock *pb)
     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");
+    }
+  }
+
+}
+/*-----------------------------------------------------------------*
+ * void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
+ *-----------------------------------------------------------------*/
+
+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;
+    }
+  }
+
+}
+
+void BuildFlowTree(pBlock *pb)
+{
+  pCodeFlow *first_pcflow, *pcflow;
+
+
+  //  fprintf(stderr,"BuildFlowTree \n");
+
+  first_pcflow = PCFL(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(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(findNextpCode(pcflow->pc.next, PC_FLOW));
 
   }
+
+  pcflow = PCFL(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(findNextpCode(pcflow->pc.next, PC_FLOW));
+
+  }
+  
+  //  BuildFlowSegment(pcflow);
+
+  //dbg_dumpFlow(pb);
+  
 }