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"
33 static void dbg_dumpFlow(pBlock *pb)
37 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
39 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
42 fprintf(stderr, "LinkFlow - pcflow is not a flow object ");
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);
49 pCodeFlowLink *from = (PCFL(pcflow)->from) ? (PCFLINK(setFirstItem(PCFL(pcflow)->from))) : NULL;
50 fprintf(stderr," no ancestor");
52 fprintf(stderr," (0x%x)",from->pcflow->pc.seq);
53 from = setNextItem(PCFL(pcflow)->from);
63 /*-----------------------------------------------------------------*
64 * void BuildFlowSegment(set *segment, pCodeFlow *pcflow)
65 *-----------------------------------------------------------------*/
66 static void BuildFlowSegment(pCodeFlow *pcflow)
68 static int recursion=0;
69 pCodeFlow *pcflow_other;
75 if(recursion++ > 200) {
76 fprintf(stderr, " exceeded recursion\n");
80 fprintf(stderr,"examining 0x%x\n",pcflow->pc.seq);
85 flowset = pcflow->from;
87 if(flowset && flowset->next == NULL) {
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.
97 if( (NULL == (pcflow_other = PCFLINK(flowset->item)->pcflow)) ||
98 (NULL == pcflow_other)) {
99 fprintf(stderr,"2 error in flow link\n");
102 pcflow->ancestor = pcflow_other->ancestor ;
104 fprintf(stderr,"Assigning ancestor 0x%x from flow 0x%x\n",
105 pcflow->ancestor->pc.seq, pcflow_other->pc.seq);
109 if(flowset == NULL) {
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 */
115 if(!pcflow->ancestor) {
116 fprintf(stderr,"error in flow link\n");
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
130 pcflow_other = PCFLINK(flowset->item)->pcflow;
132 fprintf(stderr, "coming from 0x%x\n",pcflow_other->pc.seq);
133 if( pcflow_other->ancestor)
134 pcflow->ancestor = pcflow_other->ancestor;
142 /* there are no nodes before this one */
143 if(!pcflow->ancestor)
144 fprintf(stderr,"3 Error in flow link\n");
147 /* Now let's recursively expand the call tree */
149 if(pcflow->ancestor && pcflow->to) {
150 flowset = pcflow->to;
152 BuildFlowSegment(PCFLINK(flowset->item)->pcflow);
153 flowset = flowset->next;
160 void BuildFlowTree(pBlock *pb)
162 pCodeFlow *first_pcflow, *pcflow;
165 // fprintf(stderr,"BuildFlowTree \n");
167 first_pcflow = PCFL(findNextpCode(pb->pcHead, PC_FLOW));
171 /* The very first node is like Adam, it's its own ancestor (i.e.
172 * there are no other flows in this pBlock prior to the first one).
175 first_pcflow->ancestor = first_pcflow;
177 /* For each flow that has only one predecessor, it's easy to
178 identify the ancestor */
179 pcflow = PCFL(findNextpCode(first_pcflow->pc.next, PC_FLOW));
182 if(elementsInSet(pcflow->from) == 1) {
183 pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));
185 pcflow->ancestor = from->pcflow;
187 fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x\n",
188 pcflow->ancestor->pc.seq, pcflow->pc.seq);
192 pcflow = PCFL(findNextpCode(pcflow->pc.next, PC_FLOW));
196 pcflow = PCFL(findNextpCode(first_pcflow->pc.next, PC_FLOW));
199 if(elementsInSet(pcflow->from) > 1) {
200 pCodeFlow *min_pcflow;
201 pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from));
203 min_pcflow = from->pcflow;
205 while( (from = setNextItem(pcflow->from)) != NULL) {
206 if(from->pcflow->pc.seq < min_pcflow->pc.seq)
207 min_pcflow = from->pcflow;
210 pcflow->ancestor = min_pcflow;
212 fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x from multiple\n",
213 pcflow->ancestor->pc.seq, pcflow->pc.seq);
218 pcflow = PCFL(findNextpCode(pcflow->pc.next, PC_FLOW));
222 // BuildFlowSegment(pcflow);