Update copyright to LGPL on all files
[dyninst.git] / testsuite / src / dyninst / test1_33.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 // $Id: test1_33.C,v 1.1 2008/10/30 19:19:07 legendre Exp $
33 /*
34  * #Name: test1_33 
35  * #Desc: Control Flow Graphs
36  * #Dep: 
37  * #Arch:
38  * #Notes:
39  */
40
41 #include "BPatch.h"
42 #include "BPatch_Vector.h"
43 #include "BPatch_thread.h"
44 #include "BPatch_snippet.h"
45
46 #include "test_lib.h"
47 #include "dyninst_comp.h"
48
49 class test1_33_Mutator : public DyninstMutator {
50         virtual test_results_t executeTest();
51 };
52
53 extern "C" DLLEXPORT  TestMutator *test1_33_factory() 
54 {
55         return new test1_33_Mutator();
56 }
57
58 //
59 // Start Test Case #33 - (control flow graphs)
60 //
61
62 static bool hasBackEdge(BPatch_basicBlock *bb, BPatch_Set<int> visited)
63 {
64         if (visited.contains(bb->getBlockNumber()))
65                 return true;
66
67         visited.insert(bb->getBlockNumber());
68
69         BPatch_Vector<BPatch_basicBlock*> targets;
70         bb->getTargets(targets);
71
72         unsigned int i;
73         for (i = 0; i < targets.size(); i++) 
74         {
75                 if (hasBackEdge(targets[i], visited))
76                         return true;
77         }
78
79         return false;
80 }
81
82 test_results_t test1_33_Mutator::executeTest() 
83 {
84         int pvalue;
85         unsigned int i;
86
87         if (isMutateeFortran(appImage)) 
88         {
89                 return SKIPPED;
90         }
91
92         BPatch_Vector<BPatch_function *> bpfv;
93         char *fn = "test1_33_func2";
94         if (NULL == appImage->findFunction(fn, bpfv) || !bpfv.size()
95                         || NULL == bpfv[0])
96         {
97                 logerror("**Failed** test #33 (control flow graphs)\n");
98                 logerror("    Unable to find function %s\n", fn);
99                 return FAILED;
100         }
101
102         BPatch_function *func2 = bpfv[0];
103
104         BPatch_flowGraph *cfg = func2->getCFG();
105         if (cfg == NULL) 
106         {
107                 logerror("**Failed** test #33 (control flow graphs)\n");
108                 logerror("  Unable to get control flow graph of %s\n", fn);
109                 return FAILED;
110         }
111
112         /*
113          * Test for consistency of entry basic blocks.
114          */
115
116         BPatch_Vector<BPatch_basicBlock*> entry_blocks;
117         cfg->getEntryBasicBlock(entry_blocks);
118
119         if (entry_blocks.size() != 1) 
120         {
121                 logerror("**Failed** test #33 (control flow graphs)\n");
122                 logerror("  Detected %d entry basic blocks in %s, should have been one.\n", entry_blocks.size(), fn);
123                 return FAILED;
124         }
125
126         for (i = 0; i < entry_blocks.size(); i++) 
127         {
128                 BPatch_Vector<BPatch_basicBlock*> sources;
129                 entry_blocks[i]->getSources(sources);
130
131                 if (sources.size() > 0) 
132                 {
133                         logerror("**Failed** test #33 (control flow graphs)\n");
134                         logerror("  An entry basic block has incoming edges in the control flow graph\n");
135                         return FAILED;
136                 }
137
138                 BPatch_Vector<BPatch_basicBlock*> targets;
139                 entry_blocks[i]->getTargets(targets);
140
141                 if (targets.size() < 1) 
142                 {
143                         logerror("**Failed** test #33 (control flow graphs\n");
144                         logerror("  An entry basic block has no outgoing edges in the control flow graph\n");
145                         return FAILED;
146                 }
147         }
148
149         /*
150          * Test for consistency of exit basic blocks.
151          */
152
153         BPatch_Vector<BPatch_basicBlock*> exit_blocks;
154         cfg->getExitBasicBlock(exit_blocks);
155
156         if (exit_blocks.size() != 1) 
157         {
158                 logerror("**Failed** test #33 (control flow graphs)\n");
159                 logerror("  Detected %d exit basic blocks in %s, should have been one.\n", exit_blocks.size(), fn);
160                 return FAILED;
161         }
162
163         for (i = 0; i < exit_blocks.size(); i++) 
164         {
165                 BPatch_Vector<BPatch_basicBlock*> sources;
166                 exit_blocks[i]->getSources(sources);
167
168                 if (sources.size() < 1) 
169                 {
170                         logerror("**Failed** test #33 (control flow graphs)\n");
171                         logerror("  An exit basic block has no incoming edges in the control flow graph\n");
172                         return FAILED;
173                 }
174
175                 BPatch_Vector<BPatch_basicBlock*> targets;
176                 exit_blocks[i]->getTargets(targets);
177
178                 if (targets.size() > 0) 
179                 {
180                         logerror("**Failed** test #33 (control flow graphs)\n");
181                         logerror("  An exit basic block has outgoing edges in the control flow graph\n");
182                         return FAILED;
183                 }
184         }
185
186         /*
187          * Check structure of control flow graph.
188          */
189
190         BPatch_Set<BPatch_basicBlock*> blocks;
191         cfg->getAllBasicBlocks(blocks);
192
193         if (blocks.size() < 4) 
194         {
195                 logerror("**Failed** test #33 (control flow graphs)\n");
196                 logerror("  Detected %d basic blocks in %s, should be at least four.\n", blocks.size(), fn);
197                 return FAILED;
198         }
199
200         BPatch_basicBlock **block_elements = new BPatch_basicBlock*[blocks.size()];
201         blocks.elements(block_elements);
202
203         bool foundOutDegreeTwo = false;
204         bool foundInDegreeTwo = false;
205         int blocksNoIn = 0, blocksNoOut = 0;
206
207         for (i = 0; i < (unsigned int) blocks.size(); i++) 
208         {
209                 BPatch_Vector<BPatch_basicBlock*> in;
210                 BPatch_Vector<BPatch_basicBlock*> out;
211
212                 block_elements[i]->getSources(in);
213                 block_elements[i]->getTargets(out);
214
215                 if (in.size() == 0)
216                         blocksNoIn++;
217
218                 if (out.size() == 0)
219                         blocksNoOut++;
220
221                 if (in.size() > 2 || out.size() > 2) 
222                 {
223                         logerror("**Failed** test #33 (control flow graphs)\n");
224                         logerror("  Detected a basic block in %s with %d incoming edges and %d\n", fn, in.size(), out.size());
225                         logerror("  outgoing edges - neither should be greater than two.\n");
226                         return FAILED;
227                 } 
228                 else if (in.size() > 1 && out.size() > 1) 
229                 {
230                         logerror("**Failed** test #33 (control flow graphs)\n");
231                         logerror("  Detected a basic block in %s with %d incoming edges and %d\n", fn, in.size(), out.size());
232                         logerror("  outgoing edges - only one should be greater than one.\n");
233                         return FAILED;
234                 } 
235                 else if (in.size() == 0 && out.size() == 0) 
236                 {
237                         logerror("**Failed** test #33 (control flow graphs)\n");
238                         logerror("  Detected a basic block in %s with no incoming or outgoing edges.\n", fn);
239                         return FAILED;
240                 } 
241                 else if (in.size() == 2) 
242                 {
243                         assert(out.size() <= 1);
244
245                         if (foundInDegreeTwo) 
246                         {
247                                 logerror("**Failed** test #33 (control flow graphs)\n");
248                                 logerror("  Detected two basic blocks in %s with in degree two, there should only\n", fn);
249                                 logerror("  be one.\n");
250                                 return FAILED;
251                         }
252                         foundInDegreeTwo = true;
253
254                         if (in[0]->getBlockNumber() == in[1]->getBlockNumber()) 
255                         {
256                                 logerror("**Failed** test #33 (control flow graphs)\n");
257                                 logerror("  Two edges go to the same block (number %d).\n", in[0]->getBlockNumber());
258                                 return FAILED;
259                         }
260                 } 
261                 else if (out.size() == 2) 
262                 {
263                         assert(in.size() <= 1);
264
265                         if (foundOutDegreeTwo) 
266                         {
267                                 logerror("**Failed** test #33 (control flow graphs)\n");
268                                 logerror("  Detected two basic blocks in %s with out degree two, there should only\n", fn);
269                                 logerror("  be one.\n");
270                                 return FAILED;
271                         }
272                         foundOutDegreeTwo = true;
273
274                         if (out[0]->getBlockNumber() == out[1]->getBlockNumber()) 
275                         {
276                                 logerror("**Failed** test #33 (control flow graphs)\n");
277                                 logerror("  Two edges go to the same block (number %d).\n", out[0]->getBlockNumber());
278                                 return FAILED;
279                         }
280                 } 
281                 else if (in.size() > 1 || out.size() > 1) 
282                 {
283                         /* Shouldn't be able to get here. */
284                         logerror("**Failed** test #33 (control flow graphs)\n");
285                         logerror("  Detected a basic block in %s with %d incoming edges and %d\n", fn, in.size(), out.size());
286                         logerror("  outgoing edges.\n");
287                         return FAILED;
288                 }
289         }
290
291         delete [] block_elements;
292
293         if (blocksNoIn > 1) 
294         {
295                 logerror("**Failed** test #33 (control flow graphs)\n");
296                 logerror("  Detected more than one block in %s with no incoming edges.\n", fn);
297                 return FAILED;
298         }
299
300         if (blocksNoOut > 1) 
301         {
302                 logerror("**Failed** test #33 (control flow graphs)\n");
303                 logerror("  Detected more than block in %s with no outgoing edges.\n", fn);
304                 return FAILED;
305         }
306
307         if (!foundOutDegreeTwo) 
308         {
309                 logerror("**Failed** test #33 (control flow graphs)\n");
310                 logerror("  Did not detect the \"if\" statement in %s.\n", fn);
311                 return FAILED;
312         }
313
314         /*
315          * Check for loops (there aren't any in the function we're looking at).
316          */
317
318         BPatch_Set<int> empty;
319
320         if (hasBackEdge(entry_blocks[0], empty)) 
321         {
322                 logerror("**Failed** test #33 (control flow graphs)\n");
323                 logerror("  Detected a loop in %s, there should not be one.\n", fn);
324                 return FAILED;
325         }
326
327         /*
328          * Now check a function with a switch statement.
329          */
330         bpfv.clear();
331         char *fn2 = "test1_33_func3";
332
333         // Bernat, 8JUN05 -- include uninstrumentable here...
334
335         if (NULL == appImage->findFunction(fn2, bpfv, false, false, true) || !bpfv.size()
336                         || NULL == bpfv[0])
337         {
338                 logerror("**Failed** test #33 (control flow graphs)\n");
339                 logerror("    Unable to find function %s\n", fn2);
340                 return FAILED;
341         }
342
343         BPatch_function *func3 = bpfv[0];
344         BPatch_flowGraph *cfg3 = func3->getCFG();
345
346         if (cfg3 == NULL) 
347         {
348                 logerror("**Failed** test #33 (control flow graphs)\n");
349                 logerror("  Unable to get control flow graph of %s\n", fn2);
350                 return FAILED;
351         }
352
353         BPatch_Set<BPatch_basicBlock*> blocks3;
354         cfg3->getAllBasicBlocks(blocks3);
355
356         if (blocks3.size() < 10) 
357         {
358                 logerror("**Failed** test #33 (control flow graphs)\n");
359                 logerror("  Detected %d basic blocks in %s, should be at least ten.\n", blocks3.size(), fn2);
360                 return FAILED;
361         }
362
363         block_elements = new BPatch_basicBlock*[blocks3.size()];
364         blocks3.elements(block_elements);
365
366         bool foundSwitchIn = false;
367         bool foundSwitchOut = false;
368         bool foundRangeCheck = false;
369
370         for (i = 0; i < (unsigned int)blocks3.size(); i++) 
371         {
372                 BPatch_Vector<BPatch_basicBlock*> in;
373                 BPatch_Vector<BPatch_basicBlock*> out;
374
375                 block_elements[i]->getSources(in);
376                 block_elements[i]->getTargets(out);
377
378                 if (!foundSwitchOut && out.size() >= 10 && in.size() <= 1) 
379                 {
380                         foundSwitchOut = true;
381                 } 
382                 else if (!foundSwitchIn && in.size() >= 10 && out.size() <= 1) 
383                 {
384                         foundSwitchIn = true;
385                 } 
386                 else if (!foundRangeCheck && out.size() == 2 && in.size() <= 1) 
387                 {
388                         foundRangeCheck = true;
389                 } 
390                 else if (in.size() > 1 && out.size() > 1) 
391                 {
392                         logerror("**Failed** test #33 (control flow graphs)\n");
393                         logerror("  Found basic block in %s with unexpected number of edges.\n", fn2);
394                         logerror("  %d incoming edges, %d outgoing edges.\n",
395                                         in.size(), out.size());
396                         return FAILED;
397                 }
398         }
399
400         if (!foundSwitchIn || !foundSwitchOut) 
401         {
402                 logerror("**Failed** test #33 (control flow graphs)\n");
403                 if (!foundSwitchIn)
404                         logerror("  Did not find \"switch\" statement in %s.\n", fn2);
405                 if (!foundSwitchOut)
406                         logerror("  Did not find block after \"switch\" statement.\n");
407                 return FAILED;
408         }
409
410         /* Check dominator info. */
411         BPatch_Vector<BPatch_basicBlock*> entry3;
412         cfg3->getEntryBasicBlock(entry3);
413
414         if (entry3.size() != 1) 
415         {
416                 logerror("**Failed** test #33 (control flow graphs)\n");
417                 logerror("  Detected %d entry basic blocks in %s, should have been one.\n", entry_blocks.size(), fn2);
418                 return FAILED;
419         }
420
421         for (i = 0; i < (unsigned int) blocks3.size(); i++) 
422         {
423                 if (!entry3[0]->dominates(block_elements[i])) 
424                 {
425                         logerror("**Failed** test #33 (control flow graphs)\n");
426                         logerror("  Entry block does not dominate all blocks in %s\n", fn2);
427                         return FAILED;
428                 }
429         }
430
431         BPatch_Vector<BPatch_basicBlock*> exit3;
432         cfg3->getExitBasicBlock(exit3);
433
434         if (exit3.size() != 1) 
435         {
436                 logerror("**Failed** test #33 (control flow graphs)\n");
437                 logerror("  Detected %d exit basic blocks in  %s, should have been one.\n", exit3.size(), fn2);
438                 return FAILED;
439         }
440
441         for (i = 0; i < (unsigned int) exit3.size(); i++) 
442         {
443                 if (!exit3[i]->postdominates(entry3[0])) 
444                 {
445                         logerror("**Failed** test #33 (control flow graphs)\n");
446                         logerror("  Exit block %d does not postdominate all entry blocks in %s\n", i, fn2);
447                         return FAILED;
448                 }
449         }
450
451         BPatch_variableExpr *expr33_1 = 
452                 appImage->findVariable("test1_33_globalVariable1");
453         if (expr33_1 == NULL) 
454         {
455                 logerror("**Failed** test #33 (control flow graphs)\n");
456                 logerror("    Unable to locate test1_33_globalVariable1\n");
457                 return FAILED;
458         } 
459
460         pvalue = 1;
461         expr33_1->writeValue(&pvalue);
462
463         delete [] block_elements;
464
465         return PASSED;
466 }