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
30 #include "pcodeflow.h"
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.
39 This is really overkill...
42 static set *FlowTree=NULL;
44 static void dbg_dumpFlowTree(set *FlowTree)
49 fprintf(stderr,"Flow Tree: \n");
51 for(segment = setFirstItem(FlowTree); segment; segment=setNextItem(FlowTree)) {
53 fprintf(stderr,"Segment:\n");
55 for(pcflow=PCFL(setFirstItem(segment)); pcflow; pcflow=PCFL(setNextItem(segment))) {
56 fprintf(stderr, " 0x%03x",pcflow->pc.seq);
66 /*-----------------------------------------------------------------*
67 * void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
68 *-----------------------------------------------------------------*/
69 static void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
73 pCodeFlowLink *pcflowLink=NULL;
75 /* Add this flow to the set if it's not in there already */
76 if(isinSet(segment, pcflow)) {
77 addSetHead(&FlowTree, segment);
81 addSetHead(&segment, pcflow);
83 /* Continue to add contiguous flows */
85 while( pcflow->to && ((nNextFlow = elementsInSet(pcflow->to)) == 1)) {
86 pcflowLink = (pCodeFlowLink *)(setFirstItem(pcflow->to));
87 pcflow = pcflowLink->pcflow;
89 if(isinSet(segment, pcflow)) {
90 addSetIfnotP(&FlowTree, segment);
94 addSetIfnotP(&segment, pcflow);
98 /* Branch: for each branch, duplicate the set and recursively call */
99 if(pcflow->to && nNextFlow>=2) {
100 pCodeFlow *pcflow_to;
102 set *branch_segment=NULL;
104 pcflowLink = (pCodeFlowLink *)(setFirstItem(pcflow->to));
105 pcflow_to = pcflowLink->pcflow;
107 addSetIfnotP(&segment, pcflow);
109 pcflowLink = (pCodeFlowLink *)(setNextItem(pcflow->to));
113 branch_segment = setFromSet(segment);
114 BuildFlowSegment(setFromSet(segment),pcflowLink->pcflow);
115 pcflowLink = (pCodeFlowLink *)(setNextItem(pcflow->to));
118 /* add the first branch to this segment */
119 BuildFlowSegment(segment,pcflow_to);
123 addSetIfnotP(&FlowTree, segment);
128 /*-----------------------------------------------------------------*
129 * void BuildFlowTree(pBlock *pb)
130 *-----------------------------------------------------------------*/
131 void BuildFlowTree(pBlock *pb)
138 /* Start with the first flow object of this pBlock */
140 pcflow = PCFL(findNextpCode(pb->pcHead, PC_FLOW));
143 BuildFlowSegment(segment, pcflow);
145 pb->FlowTree = FlowTree;
147 dbg_dumpFlowTree(FlowTree);
152 static void dbg_dumpFlow(pBlock *pb)
156 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
158 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
161 fprintf(stderr, "LinkFlow - pcflow is not a flow object ");
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);
168 pCodeFlowLink *from = (PCFL(pcflow)->from) ? (PCFLINK(setFirstItem(PCFL(pcflow)->from))) : NULL;
169 fprintf(stderr," no ancestor");
171 fprintf(stderr," (0x%x)",from->pcflow->pc.seq);
172 from = setNextItem(PCFL(pcflow)->from);
174 fprintf(stderr,"\n");
181 /*-----------------------------------------------------------------*
182 * void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
183 *-----------------------------------------------------------------*/
185 static void BuildFlowSegment(pCodeFlow *pcflow)
187 static int recursion=0;
188 pCodeFlow *pcflow_other;
194 if(recursion++ > 200) {
195 fprintf(stderr, " exceeded recursion\n");
199 fprintf(stderr,"examining 0x%x\n",pcflow->pc.seq);
204 flowset = pcflow->from;
206 if(flowset && flowset->next == NULL) {
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.
216 if( (NULL == (pcflow_other = PCFLINK(flowset->item)->pcflow)) ||
217 (NULL == pcflow_other)) {
218 fprintf(stderr,"2 error in flow link\n");
221 pcflow->ancestor = pcflow_other->ancestor ;
223 fprintf(stderr,"Assigning ancestor 0x%x from flow 0x%x\n",
224 pcflow->ancestor->pc.seq, pcflow_other->pc.seq);
228 if(flowset == NULL) {
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 */
234 if(!pcflow->ancestor) {
235 fprintf(stderr,"error in flow link\n");
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
249 pcflow_other = PCFLINK(flowset->item)->pcflow;
251 fprintf(stderr, "coming from 0x%x\n",pcflow_other->pc.seq);
252 if( pcflow_other->ancestor)
253 pcflow->ancestor = pcflow_other->ancestor;
261 /* there are no nodes before this one */
262 if(!pcflow->ancestor)
263 fprintf(stderr,"3 Error in flow link\n");
266 /* Now let's recursively expand the call tree */
268 if(pcflow->ancestor && pcflow->to) {
269 flowset = pcflow->to;
271 BuildFlowSegment(PCFLINK(flowset->item)->pcflow);
272 flowset = flowset->next;
278 void BuildFlowTree(pBlock *pb)
280 pCodeFlow *first_pcflow, *pcflow;
283 // fprintf(stderr,"BuildFlowTree \n");
285 first_pcflow = PCFL(findNextpCode(pb->pcHead, PC_FLOW));
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).
293 first_pcflow->ancestor = first_pcflow;
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));
300 if(elementsInSet(pcflow->from) == 1) {
301 pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));
303 pcflow->ancestor = from->pcflow;
305 fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x\n",
306 pcflow->ancestor->pc.seq, pcflow->pc.seq);
310 pcflow = PCFL(findNextpCode(pcflow->pc.next, PC_FLOW));
314 pcflow = PCFL(findNextpCode(first_pcflow->pc.next, PC_FLOW));
317 if(elementsInSet(pcflow->from) > 1) {
318 pCodeFlow *min_pcflow;
319 pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));
321 min_pcflow = from->pcflow;
323 while( (from = setNextItem(pcflow->from)) != NULL) {
324 if(from->pcflow->pc.seq < min_pcflow->pc.seq)
325 min_pcflow = from->pcflow;
328 pcflow->ancestor = min_pcflow;
330 fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x from multiple\n",
331 pcflow->ancestor->pc.seq, pcflow->pc.seq);
336 pcflow = PCFL(findNextpCode(pcflow->pc.next, PC_FLOW));
340 // BuildFlowSegment(pcflow);