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