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 static void dbg_dumpFlow(pBlock *pb)
  34 {
  35         pCode *pcflow;
  36
  37         for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
  38         pcflow != NULL;
  39         pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
  40
  41                 if(!isPCFL(pcflow))
  42                         fprintf(stderr, "LinkFlow - pcflow is not a flow object ");
  43
  44                 fprintf(stderr, "Flow: 0x%x",pcflow->seq);
  45                 if(PCFL(pcflow) && PCFL(pcflow)->ancestor)
  46                         fprintf(stderr,", ancestor 0x%x\n",
  47                         PCFL(pcflow)->ancestor->pc.seq);
  48                 else {
  49                         pCodeFlowLink *from = (PCFL(pcflow)->from) ? (PCFLINK(setFirstItem(PCFL(pcflow)->from))) : NULL;
  50                         fprintf(stderr," no ancestor");
  51                         while(from) {
  52                                 fprintf(stderr," (0x%x)",from->pcflow->pc.seq);
  53                                 from = setNextItem(PCFL(pcflow)->from);
  54                         }
  55                         fprintf(stderr,"\n");
  56                 }
  57         }
  58
  59 }
  60 #endif
  61
  62 /*-----------------------------------------------------------------*
  63 * void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
  64 *-----------------------------------------------------------------*/
  65
  66 static void BuildFlowSegment(pCodeFlow *pcflow)
  67 {
  68         static int recursion=0;
  69         pCodeFlow *pcflow_other;
  70         set *flowset;
  71
  72         if(!pcflow)
  73                 return;
  74
  75         if(recursion++ > 200) {
  76                 fprintf(stderr, " exceeded recursion\n");
  77                 return;
  78         }
  79
  80         fprintf(stderr,"examining 0x%x\n",pcflow->pc.seq);
  81
  82         if(pcflow->from) {
  83
  84
  85                 flowset = pcflow->from;
  86
  87                 if(flowset && flowset->next == NULL) {
  88
  89                 /*
  90                 There is a flow before this one. In fact, there's
  91                 exactly one flow before this one (because ->next is
  92                 NULL). That means all children of this node pass
  93                 through both this node and the node immediately
  94                 before this one; i.e. they have the same ancestor.
  95                         */
  96
  97                         if( (NULL == (pcflow_other = PCFLINK(flowset->item)->pcflow)) ||
  98                                 (NULL == pcflow_other)) {
  99                                 fprintf(stderr,"2 error in flow link\n");
 100                                 exit(1);
 101                         }
 102                         pcflow->ancestor = pcflow_other->ancestor ;
 103
 104                         fprintf(stderr,"Assigning ancestor 0x%x from flow 0x%x\n",
 105                                 pcflow->ancestor->pc.seq, pcflow_other->pc.seq);
 106
 107                 } else {
 108
 109                         if(flowset == NULL) {
 110
 111                         /* There are no flows before this one.
 112                         * If this is not the first flow object in the pBlock then
 113                                 * there's an error */
 114
 115                                 if(!pcflow->ancestor) {
 116                                         fprintf(stderr,"error in flow link\n");
 117                                         exit(1);
 118
 119                                 }
 120
 121                         } else {
 122
 123                         /* Flow passes to this flow from multiple flows. Let's
 124                         look at just one of these. If the one we look at has
 125                         an ancestor, then that's our ancestor too. If the one
 126                         we look at doesn't have an ancestor, then that means
 127                         we haven't traversed that branch of the call tree
 128                                 yet - but we will */
 129
 130                                 pcflow_other = PCFLINK(flowset->item)->pcflow;
 131                                 if(pcflow_other) {
 132                                         fprintf(stderr, "coming from 0x%x\n",pcflow_other->pc.seq);
 133                                         if( pcflow_other->ancestor)
 134                                                 pcflow->ancestor = pcflow_other->ancestor;
 135                                 }
 136                         }
 137
 138
 139                 }
 140
 141         } else {
 142                 /* there are no nodes before this one */
 143                 if(!pcflow->ancestor)
 144                         fprintf(stderr,"3 Error in flow link\n");
 145         }
 146
 147         /* Now let's recursively expand the call tree */
 148
 149         if(pcflow->ancestor && pcflow->to) {
 150                 flowset = pcflow->to;
 151                 while(flowset) {
 152                         BuildFlowSegment(PCFLINK(flowset->item)->pcflow);
 153                         flowset = flowset->next;
 154                 }
 155         }
 156
 157 }
 158
 159 void BuildFlowTree(pBlock *pb)
 160 {
 161         pCodeFlow *first_pcflow, *pcflow;
 162
 163
 164         //  fprintf(stderr,"BuildFlowTree \n");
 165
 166         first_pcflow = PCFL(findNextpCode(pb->pcHead, PC_FLOW));
 167         if(!first_pcflow)
 168                 return;
 169
 170                 /* The very first node is like Adam, it's its own ancestor (i.e.
 171                 * there are no other flows in this pBlock prior to the first one).
 172         */
 173
 174         first_pcflow->ancestor = first_pcflow;
 175
 176         /* For each flow that has only one predecessor, it's easy to
 177         identify the ancestor */
 178         pcflow = PCFL(findNextpCode(first_pcflow->pc.next, PC_FLOW));
 179
 180         while(pcflow) {
 181                 if(elementsInSet(pcflow->from) == 1) {
 182                         pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));
 183
 184                         pcflow->ancestor = from->pcflow;
 185                         /*
 186                         fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x\n",
 187                         pcflow->ancestor->pc.seq, pcflow->pc.seq);
 188                         */
 189                 }
 190
 191                 pcflow = PCFL(findNextpCode(pcflow->pc.next, PC_FLOW));
 192
 193         }
 194
 195         pcflow = PCFL(findNextpCode(first_pcflow->pc.next, PC_FLOW));
 196
 197         while(pcflow) {
 198                 if(elementsInSet(pcflow->from) > 1) {
 199                         pCodeFlow *min_pcflow;
 200                         pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));
 201
 202                         min_pcflow = from->pcflow;
 203
 204                         while( (from = setNextItem(pcflow->from)) != NULL) {
 205                                 if(from->pcflow->pc.seq < min_pcflow->pc.seq)
 206                                         min_pcflow = from->pcflow;
 207                         }
 208
 209                         pcflow->ancestor = min_pcflow;
 210                         /*
 211                         fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x from multiple\n",
 212                         pcflow->ancestor->pc.seq, pcflow->pc.seq);
 213                         */
 214
 215                 }
 216
 217                 pcflow = PCFL(findNextpCode(pcflow->pc.next, PC_FLOW));
 218
 219         }
 220
 221         //  BuildFlowSegment(pcflow);
 222
 223         //dbg_dumpFlow(pb);
 224
 225 }