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 }