Update copyright to LGPL on all files
[dyninst.git] / dyninstAPI / src / BPatch_basicBlockLoop.C
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #define BPATCH_FILE
33
34 #include <stdio.h>
35 #include <string.h>
36 #include <iostream>
37 #include "common/h/std_namesp.h"
38 #include "BPatch_basicBlockLoop.h"
39
40 #include "BPatch_edge.h"
41
42 //constructors
43 //internal use only
44
45
46 BPatch_basicBlockLoop::BPatch_basicBlockLoop(BPatch_flowGraph *fg)
47     : flowGraph(fg), parent(NULL) {}
48
49 BPatch_basicBlockLoop::BPatch_basicBlockLoop(BPatch_edge *be, 
50                                              BPatch_flowGraph *fg) 
51     : backEdge(be), flowGraph(fg), parent(NULL) {}
52
53 bool BPatch_basicBlockLoop::containsAddressInt(unsigned long addr)
54 {
55     BPatch_Vector<BPatch_basicBlock*> blks;
56     getLoopBasicBlocksExclusive(blks);
57
58     for(unsigned i = 0; i < blks.size(); i++) {
59         if (addr >= blks[i]->getStartAddress() &&
60             addr < blks[i]->getStartAddress() + blks[i]->size() ) 
61             return true;
62     }
63
64     return false;
65 }
66
67 bool BPatch_basicBlockLoop::containsAddressInclusiveInt(unsigned long addr)
68 {
69     BPatch_Vector<BPatch_basicBlock*> blks;
70     getLoopBasicBlocks(blks);
71
72     for(unsigned i = 0; i < blks.size(); i++) {
73         if (addr >= blks[i]->getStartAddress() &&
74             addr < blks[i]->getStartAddress() + blks[i]->size() ) 
75             return true;
76     }
77
78     return false;
79 }
80
81 BPatch_edge *BPatch_basicBlockLoop::getBackEdgeInt()
82 {
83   return backEdge;
84 }
85
86 bool 
87 BPatch_basicBlockLoop::hasAncestorInt(BPatch_basicBlockLoop* l) {
88     // walk up this loop's chain of parents looking for l
89     BPatch_basicBlockLoop* p = parent;
90     while (p != NULL) {
91         //        fprintf(stderr,"hasAncestor 0x%x 0x%x\n", p, p->parent);
92         if (p==l) return true;
93         p = p->parent;
94     }
95     return false;
96 }
97
98
99 bool
100 BPatch_basicBlockLoop::getLoops(BPatch_Vector<BPatch_basicBlockLoop*>& nls, 
101                                 bool outerMostOnly) const
102 {
103     BPatch_basicBlockLoop** elements = 
104         new BPatch_basicBlockLoop* [containedLoops.size()];
105
106     containedLoops.elements(elements);
107
108     for(unsigned i=0; i < containedLoops.size(); i++) {
109         // only return a contained loop if this loop is its parent
110         if (outerMostOnly) {
111             if (this == elements[i]->parent) {
112                 nls.push_back(elements[i]);
113             }
114         }
115         else {
116             nls.push_back(elements[i]);
117         }
118     }
119
120     delete[] elements;
121     return true;
122 }
123
124 //method that returns the nested loops inside the loop. It returns a set
125 //of basicBlockLoop that are contained. It might be useful to add nest 
126 //as a field of this class but it seems it is not necessary at this point
127 bool
128 BPatch_basicBlockLoop::getContainedLoopsInt(BPatch_Vector<BPatch_basicBlockLoop*>& nls)
129 {
130   return getLoops(nls, false);
131 }
132
133 // get the outermost loops nested under this loop
134 bool 
135 BPatch_basicBlockLoop::getOuterLoopsInt(BPatch_Vector<BPatch_basicBlockLoop*>& nls)
136 {
137   return getLoops(nls, true);
138 }
139
140 //returns the basic blocks in the loop
141 bool BPatch_basicBlockLoop::getLoopBasicBlocksInt(BPatch_Vector<BPatch_basicBlock*>& bbs) {
142   BPatch_basicBlock** elements = 
143     new BPatch_basicBlock*[basicBlocks.size()];
144   basicBlocks.elements(elements);
145   for(unsigned i=0;i<basicBlocks.size();i++)
146     bbs.push_back(elements[i]);
147   delete[] elements;
148   return true;
149 }
150
151
152 // returns the basic blocks in this loop, not those of its inner loops
153 bool BPatch_basicBlockLoop::getLoopBasicBlocksExclusiveInt(BPatch_Vector<BPatch_basicBlock*>& bbs) {
154     // start with a copy of all this loops basic blocks
155     BPatch_Set<BPatch_basicBlock*> allBlocks(basicBlocks);
156
157     // remove the blocks in each contained loop
158     BPatch_Vector<BPatch_basicBlockLoop*> contLoops;
159     getContainedLoops(contLoops);
160
161     for (unsigned int i = 0; i < contLoops.size(); i++) {
162         allBlocks -= contLoops[i]->basicBlocks;
163     }
164
165     BPatch_basicBlock** elements = new BPatch_basicBlock*[allBlocks.size()];
166     allBlocks.elements(elements);
167
168     for (unsigned int j = 0; j < allBlocks.size(); j++)
169         bbs.push_back(elements[j]);
170
171     delete[] elements;
172     return true;
173 }
174
175
176
177 bool BPatch_basicBlockLoop::hasBlockInt(BPatch_basicBlock*block) 
178 {
179     BPatch_Vector<BPatch_basicBlock*> blks;
180     getLoopBasicBlocks(blks);
181
182     for(unsigned i = 0; i < basicBlocks.size(); i++)
183         if (blks[i]->getBlockNumber() == block->getBlockNumber())
184             return true;
185     return false;
186 }
187
188
189 bool BPatch_basicBlockLoop::hasBlockExclusiveInt(BPatch_basicBlock*block) 
190 {
191     BPatch_Vector<BPatch_basicBlock*> blks;
192     getLoopBasicBlocksExclusive(blks);
193
194     for(unsigned i = 0; i < basicBlocks.size(); i++)
195         if (blks[i]->getBlockNumber() == block->getBlockNumber())
196             return true;
197     return false;
198 }
199
200
201 //method that returns the head of the loop. Which is also
202 //head of the back edge which defines the natural loop
203 BPatch_basicBlock* BPatch_basicBlockLoop::getLoopHeadInt()
204 {
205     assert(backEdge != NULL);
206     return backEdge->target;
207 }
208
209
210 BPatch_flowGraph* BPatch_basicBlockLoop::getFlowGraphInt() 
211 {
212     return flowGraph;
213 }
214
215
216 //we did not implement this method yet. It needs some deeper
217 //analysis and some sort of uniform dataflow framework. It is a method
218 //that returns the iterator of the loop. To find it we have to do 
219 //invariant code analysis which needs reaching definition information
220 //live variable analysis etc. Since these algorithms are not
221 //machine independent and needs more inner level machine dependent
222 //functions and we do not need at this moment for our project we did not 
223 //implement the function. It returns NULL for now.
224 BPatch_Set<BPatch_variableExpr*>* BPatch_basicBlockLoop::getLoopIteratorsInt(){
225         cerr<<"WARNING : BPatch_basicBlockLoop::getLoopIterators is not";
226         cerr<<" implemented yet\n";
227         return NULL;
228 }
229