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

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