git.gag.com Git - fw/sdcc/blob - src/pic/pcodeflow.c

   1 /*-------------------------------------------------------------------------
   2
   3    pcodeflow.c - post code generation flow analysis
   4
   5    Written By -  Scott Dattalo scott@dattalo.com
   6
   7    This program is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by the
   9    Free Software Foundation; either version 2, or (at your option) any
  10    later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program; if not, write to the Free Software
  19    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  20
  21 -------------------------------------------------------------------------*/
  22 /*
  23   pcodeflow.c
  24
  25   The purpose of the code in this file is to analyze the flow of the
  26   pCode.
  27
  28 */
  29
  30 #include <stdio.h>
  31
  32 #include "common.h"   // Include everything in the SDCC src directory
  33 #include "newalloc.h"
  34 #include "ralloc.h"
  35 #include "device.h"
  36 #include "pcode.h"
  37 #include "pcoderegs.h"
  38 #include "pcodeflow.h"
  39
  40 #if 0
  41
  42 /*
  43    In the section that follows, an exhaustive flow "tree" is built.
  44    It's not a tree that's really built, but instead every possible
  45    flow path is constructed.
  46
  47    This is really overkill...
  48 */
  49
  50 static set *FlowTree=NULL;
  51
  52 void dbg_dumpFlowTree(set *FlowTree)
  53 {
  54   set *segment;
  55   pCodeFlow *pcflow;
  56
  57   fprintf(stderr,"Flow Tree: \n");
  58
  59   for(segment = setFirstItem(FlowTree); segment; segment=setNextItem(FlowTree)) {
  60
  61     fprintf(stderr,"Segment:\n");
  62
  63     for(pcflow=PCFL(setFirstItem(segment)); pcflow; pcflow=PCFL(setNextItem(segment))) {
  64       fprintf(stderr, "  0x%03x",pcflow->pc.seq);
  65     }
  66     fprintf(stderr,"\n");
  67   }
  68
  69 }
  70
  71
  72
  73
  74 /*-----------------------------------------------------------------*
  75  * void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
  76  *-----------------------------------------------------------------*/
  77 void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
  78 {
  79
  80   int nNextFlow=0;
  81   pCodeFlowLink *pcflowLink=NULL;
  82
  83   /* Add this flow to the set if it's not in there already */
  84   if(isinSet(segment, pcflow)) {
  85     addSetHead(&FlowTree, segment);
  86     return;
  87   }
  88
  89   addSetHead(&segment, pcflow);
  90
  91   /* Continue to add contiguous flows */
  92
  93   while( pcflow->to && ((nNextFlow = elementsInSet(pcflow->to)) == 1)) {
  94     pcflowLink = (pCodeFlowLink *)(setFirstItem(pcflow->to));
  95     pcflow = pcflowLink->pcflow;
  96
  97     if(isinSet(segment, pcflow)) {
  98       addSetIfnotP(&FlowTree, segment);
  99       return;
 100     }
 101
 102     addSetIfnotP(&segment, pcflow);
 103
 104   }
 105
 106   /* Branch: for each branch, duplicate the set and recursively call */
 107   if(pcflow->to && nNextFlow>=2) {
 108     pCodeFlow *pcflow_to;
 109
 110     set *branch_segment=NULL;
 111
 112     pcflowLink = (pCodeFlowLink *)(setFirstItem(pcflow->to));
 113     pcflow_to = pcflowLink->pcflow;
 114
 115     addSetIfnotP(&segment, pcflow);
 116
 117     pcflowLink = (pCodeFlowLink *)(setNextItem(pcflow->to));
 118
 119     while(pcflowLink) {
 120
 121       branch_segment = setFromSet(segment);
 122       BuildFlowSegment(setFromSet(segment),pcflowLink->pcflow);
 123       pcflowLink = (pCodeFlowLink *)(setNextItem(pcflow->to));
 124     }
 125
 126     /* add the first branch to this segment */
 127     BuildFlowSegment(segment,pcflow_to);
 128
 129   }
 130
 131   addSetIfnotP(&FlowTree, segment);
 132
 133   /* done */
 134 }
 135
 136 /*-----------------------------------------------------------------*
 137  * void BuildFlowTree(pBlock *pb)
 138  *-----------------------------------------------------------------*/
 139 void BuildFlowTree(pBlock *pb)
 140 {
 141   pCodeFlow *pcflow;
 142   set *segment;
 143
 144   FlowTree = newSet();
 145
 146   /* Start with the first flow object of this pBlock */
 147
 148   pcflow = PCFL(findNextpCode(pb->pcHead, PC_FLOW));
 149
 150   segment = newSet();
 151   BuildFlowSegment(segment, pcflow);
 152
 153   pb->FlowTree = FlowTree;
 154
 155   dbg_dumpFlowTree(FlowTree);
 156 }
 157 #endif
 158
 159 void dbg_dumpFlow(pBlock *pb)
 160 {
 161   pCode *pcflow;
 162
 163   for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
 164        pcflow != NULL;
 165        pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
 166
 167     if(!isPCFL(pcflow))
 168       fprintf(stderr, "LinkFlow - pcflow is not a flow object ");
 169
 170     fprintf(stderr, "Flow: 0x%x",pcflow->seq);
 171     if(PCFL(pcflow) && PCFL(pcflow)->ancestor)
 172       fprintf(stderr,", ancestor 0x%x\n",
 173               PCFL(pcflow)->ancestor->pc.seq);
 174     else {
 175       pCodeFlowLink *from = (PCFL(pcflow)->from) ? (PCFLINK(setFirstItem(PCFL(pcflow)->from))) : NULL;
 176       fprintf(stderr," no ancestor");
 177       while(from) {
 178         fprintf(stderr," (0x%x)",from->pcflow->pc.seq);
 179         from = setNextItem(PCFL(pcflow)->from);
 180       }
 181       fprintf(stderr,"\n");
 182     }
 183   }
 184
 185 }
 186 /*-----------------------------------------------------------------*
 187  * void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
 188  *-----------------------------------------------------------------*/
 189
 190 void BuildFlowSegment(pCodeFlow *pcflow)
 191 {
 192   static int recursion=0;
 193   pCodeFlow *pcflow_other;
 194   set *flowset;
 195
 196   if(!pcflow)
 197     return;
 198
 199   if(recursion++ > 200) {
 200     fprintf(stderr, " exceeded recursion\n");
 201     return;
 202   }
 203
 204   fprintf(stderr,"examining 0x%x\n",pcflow->pc.seq);
 205
 206   if(pcflow->from) {
 207
 208
 209     flowset = pcflow->from;
 210
 211     if(flowset && flowset->next == NULL) {
 212
 213       /*
 214          There is a flow before this one. In fact, there's
 215          exactly one flow before this one (because ->next is
 216          NULL). That means all children of this node pass
 217          through both this node and the node immediately
 218          before this one; i.e. they have the same ancestor.
 219       */
 220
 221       if( (NULL == (pcflow_other = PCFLINK(flowset->item)->pcflow)) ||
 222           (NULL == pcflow_other)) {
 223         fprintf(stderr,"2 error in flow link\n");
 224         exit(1);
 225       }
 226       pcflow->ancestor = pcflow_other->ancestor ;
 227
 228       fprintf(stderr,"Assigning ancestor 0x%x from flow 0x%x\n",
 229               pcflow->ancestor->pc.seq, pcflow_other->pc.seq);
 230
 231     } else {
 232
 233       if(flowset == NULL) {
 234
 235         /* There are no flows before this one.
 236          * If this is not the first flow object in the pBlock then
 237          * there's an error */
 238
 239         if(!pcflow->ancestor) {
 240           fprintf(stderr,"error in flow link\n");
 241           exit(1);
 242
 243         }
 244
 245       } else {
 246
 247         /* Flow passes to this flow from multiple flows. Let's
 248            look at just one of these. If the one we look at has
 249            an ancestor, then that's our ancestor too. If the one
 250            we look at doesn't have an ancestor, then that means
 251            we haven't traversed that branch of the call tree
 252            yet - but we will */
 253
 254         pcflow_other = PCFLINK(flowset->item)->pcflow;
 255         if(pcflow_other) {
 256           fprintf(stderr, "coming from 0x%x\n",pcflow_other->pc.seq);
 257           if( pcflow_other->ancestor)
 258             pcflow->ancestor = pcflow_other->ancestor;
 259         }
 260       }
 261
 262
 263     }
 264
 265   } else {
 266     /* there are no nodes before this one */
 267     if(!pcflow->ancestor)
 268       fprintf(stderr,"3 Error in flow link\n");
 269   }
 270
 271   /* Now let's recursively expand the call tree */
 272
 273   if(pcflow->ancestor && pcflow->to) {
 274     flowset = pcflow->to;
 275     while(flowset) {
 276       BuildFlowSegment(PCFLINK(flowset->item)->pcflow);
 277       flowset = flowset->next;
 278     }
 279   }
 280
 281 }
 282
 283 void BuildFlowTree(pBlock *pb)
 284 {
 285   pCodeFlow *first_pcflow, *pcflow;
 286
 287
 288   //  fprintf(stderr,"BuildFlowTree \n");
 289
 290   first_pcflow = PCFL(findNextpCode(pb->pcHead, PC_FLOW));
 291   if(!first_pcflow)
 292     return;
 293
 294   /* The very first node is like Adam, it's its own ancestor (i.e.
 295    * there are no other flows in this pBlock prior to the first one).
 296    */
 297
 298   first_pcflow->ancestor = first_pcflow;
 299
 300   /* For each flow that has only one predecessor, it's easy to
 301      identify the ancestor */
 302   pcflow = PCFL(findNextpCode(first_pcflow->pc.next, PC_FLOW));
 303
 304   while(pcflow) {
 305     if(elementsInSet(pcflow->from) == 1) {
 306       pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));
 307
 308       pcflow->ancestor = from->pcflow;
 309       /*
 310         fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x\n",
 311         pcflow->ancestor->pc.seq, pcflow->pc.seq);
 312       */
 313     }
 314
 315     pcflow = PCFL(findNextpCode(pcflow->pc.next, PC_FLOW));
 316
 317   }
 318
 319   pcflow = PCFL(findNextpCode(first_pcflow->pc.next, PC_FLOW));
 320
 321   while(pcflow) {
 322     if(elementsInSet(pcflow->from) > 1) {
 323       pCodeFlow *min_pcflow;
 324       pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));
 325
 326       min_pcflow = from->pcflow;
 327
 328       while( (from = setNextItem(pcflow->from)) != NULL) {
 329         if(from->pcflow->pc.seq < min_pcflow->pc.seq)
 330           min_pcflow = from->pcflow;
 331       }
 332
 333       pcflow->ancestor = min_pcflow;
 334       /*
 335         fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x from multiple\n",
 336         pcflow->ancestor->pc.seq, pcflow->pc.seq);
 337       */
 338
 339     }
 340
 341     pcflow = PCFL(findNextpCode(pcflow->pc.next, PC_FLOW));
 342
 343   }
 344
 345   //  BuildFlowSegment(pcflow);
 346
 347   //dbg_dumpFlow(pb);
 348
 349 }