1 /*-------------------------------------------------------------------------
3 pcodeflow.c - post code generation flow analysis
5 Written By - Scott Dattalo scott@dattalo.com
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
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.
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.
21 -------------------------------------------------------------------------*/
25 The purpose of the code in this file is to analyze the flow of the
32 #include "common.h" // Include everything in the SDCC src directory
37 #include "pcoderegs.h"
38 #include "pcodeflow.h"
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.
47 This is really overkill...
50 static set *FlowTree=NULL;
52 void dbg_dumpFlowTree(set *FlowTree)
57 fprintf(stderr,"Flow Tree: \n");
59 for(segment = setFirstItem(FlowTree); segment; segment=setNextItem(FlowTree)) {
61 fprintf(stderr,"Segment:\n");
63 for(pcflow=PCFL(setFirstItem(segment)); pcflow; pcflow=PCFL(setNextItem(segment))) {
64 fprintf(stderr, " 0x%03x",pcflow->pc.seq);
74 /*-----------------------------------------------------------------*
75 * void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
76 *-----------------------------------------------------------------*/
77 void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
81 pCodeFlowLink *pcflowLink=NULL;
83 /* Add this flow to the set if it's not in there already */
84 if(isinSet(segment, pcflow)) {
85 addSetHead(&FlowTree, segment);
89 addSetHead(&segment, pcflow);
91 /* Continue to add contiguous flows */
93 while( pcflow->to && ((nNextFlow = elementsInSet(pcflow->to)) == 1)) {
94 pcflowLink = (pCodeFlowLink *)(setFirstItem(pcflow->to));
95 pcflow = pcflowLink->pcflow;
97 if(isinSet(segment, pcflow)) {
98 addSetIfnotP(&FlowTree, segment);
102 addSetIfnotP(&segment, pcflow);
106 /* Branch: for each branch, duplicate the set and recursively call */
107 if(pcflow->to && nNextFlow>=2) {
108 pCodeFlow *pcflow_to;
110 set *branch_segment=NULL;
112 pcflowLink = (pCodeFlowLink *)(setFirstItem(pcflow->to));
113 pcflow_to = pcflowLink->pcflow;
115 addSetIfnotP(&segment, pcflow);
117 pcflowLink = (pCodeFlowLink *)(setNextItem(pcflow->to));
121 branch_segment = setFromSet(segment);
122 BuildFlowSegment(setFromSet(segment),pcflowLink->pcflow);
123 pcflowLink = (pCodeFlowLink *)(setNextItem(pcflow->to));
126 /* add the first branch to this segment */
127 BuildFlowSegment(segment,pcflow_to);
131 addSetIfnotP(&FlowTree, segment);
136 /*-----------------------------------------------------------------*
137 * void BuildFlowTree(pBlock *pb)
138 *-----------------------------------------------------------------*/
139 void BuildFlowTree(pBlock *pb)
146 /* Start with the first flow object of this pBlock */
148 pcflow = PCFL(findNextpCode(pb->pcHead, PC_FLOW));
151 BuildFlowSegment(segment, pcflow);
153 pb->FlowTree = FlowTree;
155 dbg_dumpFlowTree(FlowTree);
159 void dbg_dumpFlow(pBlock *pb)
163 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
165 pcflow = 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");
186 /*-----------------------------------------------------------------*
187 * void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
188 *-----------------------------------------------------------------*/
190 void BuildFlowSegment(pCodeFlow *pcflow)
192 static int recursion=0;
193 pCodeFlow *pcflow_other;
199 if(recursion++ > 200) {
200 fprintf(stderr, " exceeded recursion\n");
204 fprintf(stderr,"examining 0x%x\n",pcflow->pc.seq);
209 flowset = pcflow->from;
211 if(flowset && flowset->next == NULL) {
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.
221 if( (NULL == (pcflow_other = PCFLINK(flowset->item)->pcflow)) ||
222 (NULL == pcflow_other)) {
223 fprintf(stderr,"2 error in flow link\n");
226 pcflow->ancestor = pcflow_other->ancestor ;
228 fprintf(stderr,"Assigning ancestor 0x%x from flow 0x%x\n",
229 pcflow->ancestor->pc.seq, pcflow_other->pc.seq);
233 if(flowset == NULL) {
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 */
239 if(!pcflow->ancestor) {
240 fprintf(stderr,"error in flow link\n");
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
254 pcflow_other = PCFLINK(flowset->item)->pcflow;
256 fprintf(stderr, "coming from 0x%x\n",pcflow_other->pc.seq);
257 if( pcflow_other->ancestor)
258 pcflow->ancestor = pcflow_other->ancestor;
266 /* there are no nodes before this one */
267 if(!pcflow->ancestor)
268 fprintf(stderr,"3 Error in flow link\n");
271 /* Now let's recursively expand the call tree */
273 if(pcflow->ancestor && pcflow->to) {
274 flowset = pcflow->to;
276 BuildFlowSegment(PCFLINK(flowset->item)->pcflow);
277 flowset = flowset->next;
283 void BuildFlowTree(pBlock *pb)
285 pCodeFlow *first_pcflow, *pcflow;
288 // fprintf(stderr,"BuildFlowTree \n");
290 first_pcflow = PCFL(findNextpCode(pb->pcHead, PC_FLOW));
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).
298 first_pcflow->ancestor = first_pcflow;
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));
305 if(elementsInSet(pcflow->from) == 1) {
306 pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));
308 pcflow->ancestor = from->pcflow;
310 fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x\n",
311 pcflow->ancestor->pc.seq, pcflow->pc.seq);
315 pcflow = PCFL(findNextpCode(pcflow->pc.next, PC_FLOW));
319 pcflow = PCFL(findNextpCode(first_pcflow->pc.next, PC_FLOW));
322 if(elementsInSet(pcflow->from) > 1) {
323 pCodeFlow *min_pcflow;
324 pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));
326 min_pcflow = from->pcflow;
328 while( (from = setNextItem(pcflow->from)) != NULL) {
329 if(from->pcflow->pc.seq < min_pcflow->pc.seq)
330 min_pcflow = from->pcflow;
333 pcflow->ancestor = min_pcflow;
335 fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x from multiple\n",
336 pcflow->ancestor->pc.seq, pcflow->pc.seq);
341 pcflow = PCFL(findNextpCode(pcflow->pc.next, PC_FLOW));
345 // BuildFlowSegment(pcflow);