1 /*-------------------------------------------------------------------------
3 pcodeflow.c - post code generation flow analysis
5 Written By - Scott Dattalo scott@dattalo.com
6 Ported to PIC16 By - Martin Dubuc m.dubuc@rogers.com
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
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.
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.
22 -------------------------------------------------------------------------*/
26 The purpose of the code in this file is to analyze the flow of the
33 #include "common.h" // Include everything in the SDCC src directory
38 #include "pcoderegs.h"
39 #include "pcodeflow.h"
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.
48 This is really overkill...
51 static set *FlowTree=NULL;
53 void dbg_dumpFlowTree(set *FlowTree)
58 fprintf(stderr,"Flow Tree: \n");
60 for(segment = setFirstItem(FlowTree); segment; segment=setNextItem(FlowTree)) {
62 fprintf(stderr,"Segment:\n");
64 for(pcflow=PCFL(setFirstItem(segment)); pcflow; pcflow=PCFL(setNextItem(segment))) {
65 fprintf(stderr, " 0x%03x",pcflow->pc.seq);
75 /*-----------------------------------------------------------------*
76 * void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
77 *-----------------------------------------------------------------*/
78 static void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
82 pCodeFlowLink *pcflowLink=NULL;
84 /* Add this flow to the set if it's not in there already */
85 if(isinSet(segment, pcflow)) {
86 addSetHead(&FlowTree, segment);
90 addSetHead(&segment, pcflow);
92 /* Continue to add contiguous flows */
94 while( pcflow->to && ((nNextFlow = elementsInSet(pcflow->to)) == 1)) {
95 pcflowLink = (pCodeFlowLink *)(setFirstItem(pcflow->to));
96 pcflow = pcflowLink->pcflow;
98 if(isinSet(segment, pcflow)) {
99 addSetIfnotP(&FlowTree, segment);
103 addSetIfnotP(&segment, pcflow);
107 /* Branch: for each branch, duplicate the set and recursively call */
108 if(pcflow->to && nNextFlow>=2) {
109 pCodeFlow *pcflow_to;
111 set *branch_segment=NULL;
113 pcflowLink = (pCodeFlowLink *)(setFirstItem(pcflow->to));
114 pcflow_to = pcflowLink->pcflow;
116 addSetIfnotP(&segment, pcflow);
118 pcflowLink = (pCodeFlowLink *)(setNextItem(pcflow->to));
122 branch_segment = setFromSet(segment);
123 BuildFlowSegment(setFromSet(segment),pcflowLink->pcflow);
124 pcflowLink = (pCodeFlowLink *)(setNextItem(pcflow->to));
127 /* add the first branch to this segment */
128 BuildFlowSegment(segment,pcflow_to);
132 addSetIfnotP(&FlowTree, segment);
137 /*-----------------------------------------------------------------*
138 * void pic16_BuildFlowTree(pBlock *pb)
139 *-----------------------------------------------------------------*/
140 void pic16_BuildFlowTree(pBlock *pb)
147 /* Start with the first flow object of this pBlock */
149 pcflow = PCFL(pic16_findNextpCode(pb->pcHead, PC_FLOW));
152 BuildFlowSegment(segment, pcflow);
154 pb->FlowTree = FlowTree;
156 dbg_dumpFlowTree(FlowTree);
159 static void dbg_dumpFlow(pBlock *pb)
163 for( pcflow = pic16_findNextpCode(pb->pcHead, PC_FLOW);
165 pcflow = pic16_findNextpCode(pcflow->next, PC_FLOW) ) {
168 fprintf(stderr, "LinkFlow - pcflow is not a flow object ");
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);
175 pCodeFlowLink *from = (PCFL(pcflow)->from) ? (PCFLINK(setFirstItem(PCFL(pcflow)->from))) : NULL;
176 fprintf(stderr," no ancestor");
178 fprintf(stderr," (0x%x)",from->pcflow->pc.seq);
179 from = setNextItem(PCFL(pcflow)->from);
181 fprintf(stderr,"\n");
187 /*-----------------------------------------------------------------*
188 * void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
189 *-----------------------------------------------------------------*/
191 static void BuildFlowSegment(pCodeFlow *pcflow)
193 static int recursion=0;
194 pCodeFlow *pcflow_other;
200 if(recursion++ > 200) {
201 fprintf(stderr, " exceeded recursion\n");
205 fprintf(stderr,"examining 0x%x\n",pcflow->pc.seq);
210 flowset = pcflow->from;
212 if(flowset && flowset->next == NULL) {
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.
222 if( (NULL == (pcflow_other = PCFLINK(flowset->item)->pcflow)) ||
223 (NULL == pcflow_other)) {
224 fprintf(stderr,"2 error in flow link\n");
227 pcflow->ancestor = pcflow_other->ancestor ;
229 fprintf(stderr,"Assigning ancestor 0x%x from flow 0x%x\n",
230 pcflow->ancestor->pc.seq, pcflow_other->pc.seq);
234 if(flowset == NULL) {
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 */
240 if(!pcflow->ancestor) {
241 fprintf(stderr,"error in flow link\n");
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
255 pcflow_other = PCFLINK(flowset->item)->pcflow;
257 fprintf(stderr, "coming from 0x%x\n",pcflow_other->pc.seq);
258 if( pcflow_other->ancestor)
259 pcflow->ancestor = pcflow_other->ancestor;
267 /* there are no nodes before this one */
268 if(!pcflow->ancestor)
269 fprintf(stderr,"3 Error in flow link\n");
272 /* Now let's recursively expand the call tree */
274 if(pcflow->ancestor && pcflow->to) {
275 flowset = pcflow->to;
277 BuildFlowSegment(PCFLINK(flowset->item)->pcflow);
278 flowset = flowset->next;
284 void pic16_BuildFlowTree(pBlock *pb)
286 pCodeFlow *first_pcflow, *pcflow;
289 // fprintf(stderr,"pic16_BuildFlowTree \n");
291 first_pcflow = PCFL(pic16_findNextpCode(pb->pcHead, PC_FLOW));
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).
299 first_pcflow->ancestor = first_pcflow;
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));
306 if(elementsInSet(pcflow->from) == 1) {
307 pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));
309 pcflow->ancestor = from->pcflow;
311 fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x\n",
312 pcflow->ancestor->pc.seq, pcflow->pc.seq);
316 pcflow = PCFL(pic16_findNextpCode(pcflow->pc.next, PC_FLOW));
320 pcflow = PCFL(pic16_findNextpCode(first_pcflow->pc.next, PC_FLOW));
323 if(elementsInSet(pcflow->from) > 1) {
324 pCodeFlow *min_pcflow;
325 pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));
327 min_pcflow = from->pcflow;
329 while( (from = setNextItem(pcflow->from)) != NULL) {
330 if(from->pcflow->pc.seq < min_pcflow->pc.seq)
331 min_pcflow = from->pcflow;
334 pcflow->ancestor = min_pcflow;
336 fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x from multiple\n",
337 pcflow->ancestor->pc.seq, pcflow->pc.seq);
342 pcflow = PCFL(pic16_findNextpCode(pcflow->pc.next, PC_FLOW));
346 // BuildFlowSegment(pcflow);