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 /*-----------------------------------------------------------------*
 188  * void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
 189  *-----------------------------------------------------------------*/
 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
 284 void pic16_BuildFlowTree(pBlock *pb)
 285 {
 286   pCodeFlow *first_pcflow, *pcflow;
 287
 288
 289   //  fprintf(stderr,"pic16_BuildFlowTree \n");
 290
 291   first_pcflow = PCFL(pic16_findNextpCode(pb->pcHead, PC_FLOW));
 292   if(!first_pcflow)
 293     return;
 294
 295   /* The very first node is like Adam, it's its own ancestor (i.e.
 296    * there are no other flows in this pBlock prior to the first one).
 297    */
 298
 299   first_pcflow->ancestor = first_pcflow;
 300
 301   /* For each flow that has only one predecessor, it's easy to
 302      identify the ancestor */
 303   pcflow = PCFL(pic16_findNextpCode(first_pcflow->pc.next, PC_FLOW));
 304
 305   while(pcflow) {
 306     if(elementsInSet(pcflow->from) == 1) {
 307       pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));
 308
 309       pcflow->ancestor = from->pcflow;
 310       /*
 311         fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x\n",
 312         pcflow->ancestor->pc.seq, pcflow->pc.seq);
 313       */
 314     }
 315
 316     pcflow = PCFL(pic16_findNextpCode(pcflow->pc.next, PC_FLOW));
 317
 318   }
 319
 320   pcflow = PCFL(pic16_findNextpCode(first_pcflow->pc.next, PC_FLOW));
 321
 322   while(pcflow) {
 323     if(elementsInSet(pcflow->from) > 1) {
 324       pCodeFlow *min_pcflow;
 325       pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));
 326
 327       min_pcflow = from->pcflow;
 328
 329       while( (from = setNextItem(pcflow->from)) != NULL) {
 330         if(from->pcflow->pc.seq < min_pcflow->pc.seq)
 331           min_pcflow = from->pcflow;
 332       }
 333
 334       pcflow->ancestor = min_pcflow;
 335       /*
 336         fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x from multiple\n",
 337         pcflow->ancestor->pc.seq, pcflow->pc.seq);
 338       */
 339
 340     }
 341
 342     pcflow = PCFL(pic16_findNextpCode(pcflow->pc.next, PC_FLOW));
 343
 344   }
 345
 346   //  BuildFlowSegment(pcflow);
 347
 348   //dbg_dumpFlow(pb);
 349
 350 }