X-Git-Url: https://git.gag.com/?a=blobdiff_plain;f=src%2Fpic%2Fpcodeflow.c;h=2a4207194863ee8a5ee45542e2f5abaf366bccb0;hb=661651374d7b67aca713b215c01b13b2782c4b37;hp=3cce0d5b13d68e0613f5baee8a317ff10039e34a;hpb=35eb2a4c6915040928b5911827135685aa94a0a1;p=fw%2Fsdcc diff --git a/src/pic/pcodeflow.c b/src/pic/pcodeflow.c index 3cce0d5b..2a420719 100644 --- a/src/pic/pcodeflow.c +++ b/src/pic/pcodeflow.c @@ -40,137 +40,310 @@ #if 0 /* - In the section that follows, an exhaustive flow "tree" is built. - It's not a tree that's really built, but instead every possible - flow path is constructed. +In the section that follows, an exhaustive flow "tree" is built. +It's not a tree that's really built, but instead every possible +flow path is constructed. - This is really overkill... + This is really overkill... */ static set *FlowTree=NULL; void dbg_dumpFlowTree(set *FlowTree) { - set *segment; - pCodeFlow *pcflow; - - fprintf(stderr,"Flow Tree: \n"); - - for(segment = setFirstItem(FlowTree); segment; segment=setNextItem(FlowTree)) { - - fprintf(stderr,"Segment:\n"); - - for(pcflow=PCFL(setFirstItem(segment)); pcflow; pcflow=PCFL(setNextItem(segment))) { - fprintf(stderr, " 0x%03x",pcflow->pc.seq); - } - fprintf(stderr,"\n"); - } - + set *segment; + pCodeFlow *pcflow; + + fprintf(stderr,"Flow Tree: \n"); + + for(segment = setFirstItem(FlowTree); segment; segment=setNextItem(FlowTree)) { + + fprintf(stderr,"Segment:\n"); + + for(pcflow=PCFL(setFirstItem(segment)); pcflow; pcflow=PCFL(setNextItem(segment))) { + fprintf(stderr, " 0x%03x",pcflow->pc.seq); + } + fprintf(stderr,"\n"); + } + } /*-----------------------------------------------------------------* - * void BuildFlowSegment(set *segment, pCodeFlow *pcflow) - *-----------------------------------------------------------------*/ +* void BuildFlowSegment(set *segment, pCodeFlow *pcflow) +*-----------------------------------------------------------------*/ void BuildFlowSegment(set *segment, pCodeFlow *pcflow) { - - int nNextFlow=0; - pCodeFlowLink *pcflowLink=NULL; - - /* Add this flow to the set if it's not in there already */ - if(isinSet(segment, pcflow)) { - addSetHead(&FlowTree, segment); - return; - } - - addSetHead(&segment, pcflow); - - /* Continue to add contiguous flows */ - - while( pcflow->to && ((nNextFlow = elementsInSet(pcflow->to)) == 1)) { - pcflowLink = (pCodeFlowLink *)(setFirstItem(pcflow->to)); - pcflow = pcflowLink->pcflow; - - if(isinSet(segment, pcflow)) { - addSetIfnotP(&FlowTree, segment); - return; - } - - addSetIfnotP(&segment, pcflow); - - } - - /* Branch: for each branch, duplicate the set and recursively call */ - if(pcflow->to && nNextFlow>=2) { - pCodeFlow *pcflow_to; - - set *branch_segment=NULL; - - pcflowLink = (pCodeFlowLink *)(setFirstItem(pcflow->to)); - pcflow_to = pcflowLink->pcflow; - - addSetIfnotP(&segment, pcflow); - - pcflowLink = (pCodeFlowLink *)(setNextItem(pcflow->to)); - - while(pcflowLink) { - - branch_segment = setFromSet(segment); - BuildFlowSegment(setFromSet(segment),pcflowLink->pcflow); - pcflowLink = (pCodeFlowLink *)(setNextItem(pcflow->to)); - } - - /* add the first branch to this segment */ - BuildFlowSegment(segment,pcflow_to); - - } - - addSetIfnotP(&FlowTree, segment); - - /* done */ + + int nNextFlow=0; + pCodeFlowLink *pcflowLink=NULL; + + /* Add this flow to the set if it's not in there already */ + if(isinSet(segment, pcflow)) { + addSetHead(&FlowTree, segment); + return; + } + + addSetHead(&segment, pcflow); + + /* Continue to add contiguous flows */ + + while( pcflow->to && ((nNextFlow = elementsInSet(pcflow->to)) == 1)) { + pcflowLink = (pCodeFlowLink *)(setFirstItem(pcflow->to)); + pcflow = pcflowLink->pcflow; + + if(isinSet(segment, pcflow)) { + addSetIfnotP(&FlowTree, segment); + return; + } + + addSetIfnotP(&segment, pcflow); + + } + + /* Branch: for each branch, duplicate the set and recursively call */ + if(pcflow->to && nNextFlow>=2) { + pCodeFlow *pcflow_to; + + set *branch_segment=NULL; + + pcflowLink = (pCodeFlowLink *)(setFirstItem(pcflow->to)); + pcflow_to = pcflowLink->pcflow; + + addSetIfnotP(&segment, pcflow); + + pcflowLink = (pCodeFlowLink *)(setNextItem(pcflow->to)); + + while(pcflowLink) { + + branch_segment = setFromSet(segment); + BuildFlowSegment(setFromSet(segment),pcflowLink->pcflow); + pcflowLink = (pCodeFlowLink *)(setNextItem(pcflow->to)); + } + + /* add the first branch to this segment */ + BuildFlowSegment(segment,pcflow_to); + + } + + addSetIfnotP(&FlowTree, segment); + + /* done */ } /*-----------------------------------------------------------------* - * void BuildFlowTree(pBlock *pb) - *-----------------------------------------------------------------*/ +* void BuildFlowTree(pBlock *pb) +*-----------------------------------------------------------------*/ void BuildFlowTree(pBlock *pb) { - pCodeFlow *pcflow; - set *segment; - - FlowTree = newSet(); - - /* Start with the first flow object of this pBlock */ - - pcflow = PCFL(findNextpCode(pb->pcHead, PC_FLOW)); - - segment = newSet(); - BuildFlowSegment(segment, pcflow); - - pb->FlowTree = FlowTree; - - dbg_dumpFlowTree(FlowTree); + pCodeFlow *pcflow; + set *segment; + + FlowTree = newSet(); + + /* Start with the first flow object of this pBlock */ + + pcflow = PCFL(findNextpCode(pb->pcHead, PC_FLOW)); + + segment = newSet(); + BuildFlowSegment(segment, pcflow); + + pb->FlowTree = FlowTree; + + dbg_dumpFlowTree(FlowTree); } #endif -void BuildFlowAncestry(pBlock *pb) +void dbg_dumpFlow(pBlock *pb) { - pCode *pc=NULL; - pCode *pcflow; - pCode *pct; - - //fprintf(stderr,"linkflow \n"); - - for( pcflow = findNextpCode(pb->pcHead, PC_FLOW); - pcflow != NULL; - pcflow = findNextpCode(pcflow->next, PC_FLOW) ) { - - if(!isPCFL(pcflow)) - fprintf(stderr, "LinkFlow - pcflow is not a flow object "); + pCode *pcflow; + + for( pcflow = findNextpCode(pb->pcHead, PC_FLOW); + pcflow != NULL; + pcflow = findNextpCode(pcflow->next, PC_FLOW) ) { + + if(!isPCFL(pcflow)) + fprintf(stderr, "LinkFlow - pcflow is not a flow object "); + + fprintf(stderr, "Flow: 0x%x",pcflow->seq); + if(PCFL(pcflow) && PCFL(pcflow)->ancestor) + fprintf(stderr,", ancestor 0x%x\n", + PCFL(pcflow)->ancestor->pc.seq); + else { + pCodeFlowLink *from = (PCFL(pcflow)->from) ? (PCFLINK(setFirstItem(PCFL(pcflow)->from))) : NULL; + fprintf(stderr," no ancestor"); + while(from) { + fprintf(stderr," (0x%x)",from->pcflow->pc.seq); + from = setNextItem(PCFL(pcflow)->from); + } + fprintf(stderr,"\n"); + } + } + +} +/*-----------------------------------------------------------------* +* void BuildFlowSegment(set *segment, pCodeFlow *pcflow) +*-----------------------------------------------------------------*/ +void BuildFlowSegment(pCodeFlow *pcflow) +{ + static int recursion=0; + pCodeFlow *pcflow_other; + set *flowset; + + if(!pcflow) + return; + + if(recursion++ > 200) { + fprintf(stderr, " exceeded recursion\n"); + return; + } + + fprintf(stderr,"examining 0x%x\n",pcflow->pc.seq); + + if(pcflow->from) { + + + flowset = pcflow->from; + + if(flowset && flowset->next == NULL) { + + /* + There is a flow before this one. In fact, there's + exactly one flow before this one (because ->next is + NULL). That means all children of this node pass + through both this node and the node immediately + before this one; i.e. they have the same ancestor. + */ + + if( (NULL == (pcflow_other = PCFLINK(flowset->item)->pcflow)) || + (NULL == pcflow_other)) { + fprintf(stderr,"2 error in flow link\n"); + exit(1); + } + pcflow->ancestor = pcflow_other->ancestor ; + + fprintf(stderr,"Assigning ancestor 0x%x from flow 0x%x\n", + pcflow->ancestor->pc.seq, pcflow_other->pc.seq); + + } else { + + if(flowset == NULL) { + + /* There are no flows before this one. + * If this is not the first flow object in the pBlock then + * there's an error */ + + if(!pcflow->ancestor) { + fprintf(stderr,"error in flow link\n"); + exit(1); + + } + + } else { + + /* Flow passes to this flow from multiple flows. Let's + look at just one of these. If the one we look at has + an ancestor, then that's our ancestor too. If the one + we look at doesn't have an ancestor, then that means + we haven't traversed that branch of the call tree + yet - but we will */ + + pcflow_other = PCFLINK(flowset->item)->pcflow; + if(pcflow_other) { + fprintf(stderr, "coming from 0x%x\n",pcflow_other->pc.seq); + if( pcflow_other->ancestor) + pcflow->ancestor = pcflow_other->ancestor; + } + } + + + } + + } else { + /* there are no nodes before this one */ + if(!pcflow->ancestor) + fprintf(stderr,"3 Error in flow link\n"); + } + + /* Now let's recursively expand the call tree */ + + if(pcflow->ancestor && pcflow->to) { + flowset = pcflow->to; + while(flowset) { + BuildFlowSegment(PCFLINK(flowset->item)->pcflow); + flowset = flowset->next; + } + } + +} - } +void BuildFlowTree(pBlock *pb) +{ + pCodeFlow *first_pcflow, *pcflow; + + + // fprintf(stderr,"BuildFlowTree \n"); + + first_pcflow = PCFL(findNextpCode(pb->pcHead, PC_FLOW)); + if(!first_pcflow) + return; + + /* The very first node is like Adam, it's its own ancestor (i.e. + * there are no other flows in this pBlock prior to the first one). + */ + + first_pcflow->ancestor = first_pcflow; + + /* For each flow that has only one predecessor, it's easy to + identify the ancestor */ + pcflow = PCFL(findNextpCode(first_pcflow->pc.next, PC_FLOW)); + + while(pcflow) { + if(elementsInSet(pcflow->from) == 1) { + pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from)); + + pcflow->ancestor = from->pcflow; + /* + fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x\n", + pcflow->ancestor->pc.seq, pcflow->pc.seq); + */ + } + + pcflow = PCFL(findNextpCode(pcflow->pc.next, PC_FLOW)); + + } + + pcflow = PCFL(findNextpCode(first_pcflow->pc.next, PC_FLOW)); + + while(pcflow) { + if(elementsInSet(pcflow->from) > 1) { + pCodeFlow *min_pcflow; + pCodeFlowLink *from = PCFLINK(setFirstItem(pcflow->from)); + + min_pcflow = from->pcflow; + + while( (from = setNextItem(pcflow->from)) != NULL) { + if(from->pcflow->pc.seq < min_pcflow->pc.seq) + min_pcflow = from->pcflow; + } + + pcflow->ancestor = min_pcflow; + /* + fprintf(stderr,"Assigning ancestor 0x%x to flow 0x%x from multiple\n", + pcflow->ancestor->pc.seq, pcflow->pc.seq); + */ + + } + + pcflow = PCFL(findNextpCode(pcflow->pc.next, PC_FLOW)); + + } + + // BuildFlowSegment(pcflow); + + //dbg_dumpFlow(pb); + }