* Bugfix: InstrucIter no longer used for int_function iteration.
[dyninst.git] / dyninstAPI / src / BPatch_function.C
1 /*
2  * Copyright (c) 1996-2004 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  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 // $Id: BPatch_function.C,v 1.96 2007/12/11 20:22:05 bill Exp $
43
44 #define BPATCH_FILE
45
46 #include <string.h>
47 #include "symtab.h"
48 #include "process.h"
49 #include "instPoint.h"
50 #include "ast.h"
51
52 #include "BPatch.h"
53 #include "BPatch_function.h"
54 #include "BPatch_type.h"
55 #include "BPatch_collections.h"
56 #include "BPatch_Vector.h"
57 #include "BPatch_flowGraph.h"
58 #include "BPatch_libInfo.h"
59 #include "BPatch_memoryAccess_NP.h"
60 #include "BPatch_basicBlock.h"
61 #include "BPatch_statement.h"
62
63 #include "symtabAPI/h/LineInformation.h"
64 #include "common/h/Types.h"
65 #include "InstrucIter-Function.h"
66
67 #if defined(cap_slicing)
68 // #include "BPatch_dependenceGraphNode.h"
69 #include "BPatch_dependenceGraphEdge.h"
70 #include "common/h/Annotatable.h"
71 #endif
72
73 /**************************************************************************
74  * BPatch_function
75  *************************************************************************/
76 /*
77  * BPatch_function::BPatch_function
78  *
79  * Constructor that creates a BPatch_function.
80  *
81  */
82
83 int bpatch_function_count = 0;
84
85 BPatch_function::BPatch_function(BPatch_addressSpace *_addSpace, int_function *_func,
86         BPatch_module *_mod) :
87         addSpace(_addSpace), mod(_mod), cfg(NULL), cfgCreated(false), liveInit(false), func(_func)
88 {
89 #if defined(ROUGH_MEMORY_PROFILE)
90     bpatch_function_count++;
91     if ((bpatch_function_count % 10) == 0)
92         fprintf(stderr, "bpatch_function_count: %d (%d)\n",
93                 bpatch_function_count, bpatch_function_count*sizeof(BPatch_function));
94 #endif
95
96   // there should be at most one BPatch_func for each int_function per process
97     //  assert( proc && !proc->func_map->defines(func) );
98     assert( addSpace && !addSpace->func_map->defines(func) );
99   _srcType = BPatch_sourceFunction;
100
101   localVariables = new BPatch_localVarCollection;
102   funcParameters = new BPatch_localVarCollection;
103   retType = NULL;
104
105   addSpace->func_map->add(_func, this);
106   if (mod) {
107       // Track for deletion
108       mod->all_funcs.push_back(this);
109   }
110 };
111
112 /*
113  * BPatch_function::BPatch_function
114  *
115  * Constructor that creates the BPatch_function with return type.
116  *
117  */
118 BPatch_function::BPatch_function(BPatch_addressSpace *_addSpace, int_function *_func,
119                                  BPatch_type * _retType, BPatch_module *_mod) :
120         addSpace(_addSpace), mod(_mod), cfg(NULL), cfgCreated(false), liveInit(false), func(_func)
121 {
122   //assert(proc && !proc->func_map->defines(_func));
123   assert(addSpace && !addSpace->func_map->defines(_func));
124
125   _srcType = BPatch_sourceFunction;
126
127   localVariables = new BPatch_localVarCollection;
128   funcParameters = new BPatch_localVarCollection;
129   retType = _retType;
130
131   //proc->func_map->add(_func, this);
132   addSpace->func_map->add(_func,this);
133   if (mod) {
134       // Track for deletion
135       mod->all_funcs.push_back(this);
136   }
137 };
138
139
140 BPatch_function::~BPatch_function()
141 {
142     if (localVariables) delete localVariables;
143     if (funcParameters) delete funcParameters;
144
145     if (cfg) delete cfg;
146
147     // Remove us from the proc map...
148     //if (proc && proc->func_map)
149     //  proc->func_map->undefine(lowlevel_func());
150
151     if (addSpace && addSpace->func_map)
152         addSpace->func_map->undefine(lowlevel_func());
153 }
154
155 /* 
156  * BPatch_function::getSourceObj()
157  *
158  * Return the contained source objects (e.g. statements).
159  *    This is not currently supported.
160  *
161  */
162 bool BPatch_function::getSourceObj(BPatch_Vector<BPatch_sourceObj *> &children)
163 {
164     // init and empty vector
165     BPatch_Vector<BPatch_sourceObj *> dummy;
166
167     children = dummy;
168     return false;
169 }
170
171
172 BPatch_process * BPatch_function::getProc() const
173 {
174   assert(addSpace->getType() == TRADITIONAL_PROCESS); 
175   return dynamic_cast<BPatch_process *>(addSpace); 
176 }
177
178
179 /*
180  * BPatch_function::getObjParent()
181  *
182  * Return the parent of the function (i.e. the module)
183  *
184  */
185 BPatch_sourceObj *BPatch_function::getObjParent()
186 {
187     return (BPatch_sourceObj *) mod;
188 }
189
190 /*
191  * BPatch_function::getName
192  *
193  * Copies the name of the function into a buffer, up to a given maximum
194  * length.  Returns a pointer to the beginning of the buffer that was
195  * passed in.
196  *
197  * s            The buffer into which the name will be copied.
198  * len          The size of the buffer.
199  */
200 char *BPatch_function::getNameBuffer(char *s, int len)
201 {
202     assert(func);
203     string name = func->prettyName();
204     strncpy(s, name.c_str(), len);
205     return s;
206 }
207
208 #ifdef IBM_BPATCH_COMPAT
209 const char *BPatch_function::getNameDPCL()
210 {
211     assert(func);
212     return func->prettyName().c_str();
213 }
214 #endif
215
216 /*
217  * BPatch_function::getMangledName
218  *
219  * Copies the mangled name of the function into a buffer, up to a given maximum
220  * length.  Returns a pointer to the beginning of the buffer that was
221  * passed in.
222  *
223  * s            The buffer into which the name will be copied.
224  * len          The size of the buffer.
225  */
226 char *BPatch_function::getMangledNameInt(char *s, int len)
227 {
228   assert(func);
229   string mangledname = func->symTabName();
230   strncpy(s, mangledname.c_str(), len);
231   return s;
232 }
233
234 /*
235  * BPatch_function::getTypedName
236  *
237  * Copies the mangled name of the function into a buffer, up to a given maximum
238  * length.  Returns a pointer to the beginning of the buffer that was
239  * passed in.
240  *
241  * s            The buffer into which the name will be copied.
242  * len          The size of the buffer.
243  */
244 char *BPatch_function::getTypedNameInt(char *s, int len)
245 {
246   assert(func);
247   string typedname = func->typedName();
248   strncpy(s, typedname.c_str(), len);
249   return s;
250 }
251
252
253 /*
254  * BPatch_function::getNames
255  *
256  * Copies all names of the function into the provided BPatch_Vector.
257  * Names are represented as const char *s and are
258  * allocated/deallocated by Dyninst.
259  *
260  * names           BPatch_Vector reference
261  */
262
263 bool BPatch_function::getNamesInt(BPatch_Vector<const char *> &names)
264 {
265     assert(func);
266     unsigned pre_size = names.size();
267
268     for (unsigned i = 0; i < func->prettyNameVector().size(); i++) {
269         names.push_back(func->prettyNameVector()[i].c_str());
270     }
271
272     return names.size() > pre_size;
273 }
274
275 /*
276  * BPatch_function::getMangledNames
277  *
278  * Copies all mangled names of the function into the provided
279  * BPatch_Vector.  Names are represented as const char *s and are
280  * allocated/deallocated by Dyninst.
281  *
282  * names           BPatch_Vector reference
283  */
284
285 bool BPatch_function::getMangledNamesInt(BPatch_Vector<const char *> &names)
286 {
287     assert(func);
288     unsigned pre_size = names.size();
289
290     for (unsigned i = 0; i < func->symTabNameVector().size(); i++) {
291         names.push_back(func->symTabNameVector()[i].c_str());
292     }
293
294     return names.size() > pre_size;
295 }
296
297
298
299 /*
300  * BPatch_function::getBaseAddr
301  *
302  * Returns the starting address of the function.
303  */
304 void *BPatch_function::getBaseAddrInt()
305 {
306   return (void *)func->getAddress();
307 }
308
309 /*
310  * BPatch_function::getSize
311  *
312  * Returns the size of the function in bytes.
313  */
314 unsigned int BPatch_function::getSizeInt() 
315 {
316     return func->getSize_NP();
317 }
318
319 /*
320  * BPatch_function::getReturnType
321  *
322  * Returns the return type of the function.
323  */
324 BPatch_type *BPatch_function::getReturnTypeInt()
325 {
326     mod->parseTypesIfNecessary();
327     return retType;
328 }
329
330 /*
331  * BPatch_function::getModule
332  *
333  * Returns the BPatch_module to which this function belongs.
334  */
335 BPatch_module *BPatch_function::getModuleInt()
336 {
337   return mod;
338 }
339
340 //  BPatch_function::getParams
341 //  Returns a vector of BPatch_localVar, representing this function's parameters
342
343 BPatch_Vector<BPatch_localVar *> * BPatch_function::getParamsInt()
344 {
345     if (!mod->isValid()) return NULL;
346     mod->parseTypesIfNecessary();
347     return funcParameters->getAllVars();
348 }
349
350
351
352
353 /*
354  * BPatch_function::findPoint
355  *
356  * Returns a vector of the instrumentation points from a procedure that is
357  * identified by the parameters, or returns NULL upon failure.
358  * (Points are sorted by address in the vector returned.)
359  *
360  * loc          The points within the procedure to return.  The following
361  *              values are valid for this parameter:
362  *                BPatch_entry         The function's entry point.
363  *                BPatch_exit          The function's exit point(s).
364  *                BPatch_subroutine    The points at which the procedure calls
365  *                                     other procedures.
366  *                BPatch_longJump      The points at which the procedure make
367  *                                     long jump calls.
368  *                BPatch_allLocations  All of the points described above.
369  */
370 BPatch_Vector<BPatch_point*> *BPatch_function::findPointInt(
371         const BPatch_procedureLocation loc)
372 {
373     // function does not exist!
374     if (func == NULL) return NULL;
375
376     if (!mod->isValid()) return NULL;
377
378     // if the function is not instrumentable, we won't find the point
379     if (!isInstrumentable())
380        return NULL;
381
382     // function is generally uninstrumentable (with current technology)
383     if (func->funcEntries().size() == 0) return NULL;
384
385     BPatch_Vector<BPatch_point*> *result = new BPatch_Vector<BPatch_point *>;
386
387     if (loc == BPatch_entry || loc == BPatch_allLocations) {
388         const pdvector<instPoint *> entries = func->funcEntries();
389         for (unsigned foo = 0; foo < entries.size(); foo++)
390             result->push_back(addSpace->findOrCreateBPPoint(this, 
391                                                         entries[foo], 
392                                                         BPatch_entry));
393     }
394     switch (loc) {
395       case BPatch_entry: // already done
396           break;
397       case BPatch_allLocations:
398         {
399           const pdvector<instPoint *> &Rpoints = func->funcExits();
400           const pdvector<instPoint *> &Cpoints = func->funcCalls();
401           unsigned int c=0, r=0;
402           Address cAddr, rAddr;
403           while (c < Cpoints.size() || r < Rpoints.size()) {
404               if (c < Cpoints.size()) cAddr = Cpoints[c]->addr();
405               else                    cAddr = (Address)(-1);
406               if (r < Rpoints.size()) rAddr = Rpoints[r]->addr();
407               else                    rAddr = (Address)(-1);
408               if (cAddr <= rAddr) {
409                   result->push_back(addSpace->findOrCreateBPPoint(
410                                                               this, Cpoints[c], BPatch_subroutine));
411               c++;
412             } else {
413                  result->push_back(addSpace->findOrCreateBPPoint(
414                                    this, Rpoints[r], BPatch_exit));
415                  r++;
416             }
417           }
418           break;
419         }
420       case BPatch_exit:
421         {
422           const pdvector<instPoint *> &points = func->funcExits();
423           for (unsigned i = 0; i < points.size(); i++) {
424              result->push_back(addSpace->findOrCreateBPPoint(
425                                              this, points[i], BPatch_exit));
426           }
427           break;
428         }
429       case BPatch_subroutine:
430         {
431           const pdvector<instPoint *> &points = func->funcCalls();
432           for (unsigned i = 0; i < points.size(); i++) {
433              result->push_back(addSpace->findOrCreateBPPoint(
434                                           this, points[i], BPatch_subroutine));
435           }
436           break;
437         }
438       case BPatch_longJump:
439         /* XXX Not yet implemented */
440       default:
441         assert( 0 );
442     }
443
444     return result;
445 }
446
447 /*
448  * BPatch_function::findPoint (VG 09/05/01)
449  *
450  * Returns a vector of the instrumentation points from a procedure that is
451  * identified by the parameters, or returns NULL upon failure.
452  * (Points are sorted by address in the vector returned.)
453  *
454  * ops          The points within the procedure to return. A set of op codes
455  *              defined in BPatch_opCode (BPatch_point.h)
456  */
457 BPatch_Vector<BPatch_point*> *BPatch_function::findPointByOp(
458         const BPatch_Set<BPatch_opCode>& ops)
459 {
460   // function does not exist!
461   if (func == NULL) return NULL;
462
463     if (!mod->isValid()) return NULL;
464
465   // function is generally uninstrumentable (with current technology)
466   if (func->funcEntries().size() == 0) return NULL;
467   
468   // Use an instruction iterator
469   InstrucIterFunction ii(func);
470     
471   return BPatch_point::getPoints(ops, ii, this);
472 }
473
474 /*
475  * BPatch_function::addParam()
476  *
477  * This function adds a function parameter to the BPatch_function parameter
478  * vector.
479  */
480 void BPatch_function::addParam(const char * _name, BPatch_type *_type,
481                                int _linenum, long _frameOffset, int _reg,
482                                BPatch_storageClass _sc)
483 {
484   BPatch_localVar * param = new BPatch_localVar(_name, _type, _linenum,
485                                                 _frameOffset, _reg, _sc);
486
487   // Add parameter to list of parameters
488   params.push_back(param);
489 }
490
491 /*
492  * BPatch_function::findLocalVarInt()
493  *
494  * This function searchs for a local variable in the BPatch_function's
495  * local variable collection.
496  */
497 BPatch_localVar * BPatch_function::findLocalVarInt(const char * name)
498 {
499     if (!mod->isValid()) return NULL;
500     mod->parseTypesIfNecessary();
501     BPatch_localVar * var = localVariables->findLocalVar(name);
502     return (var);
503 }
504
505 /*
506  * BPatch_function::findLocalParam()
507  *
508  * This function searchs for a function parameter in the BPatch_function's
509  * parameter collection.
510  */
511 BPatch_localVar * BPatch_function::findLocalParamInt(const char * name)
512 {
513     if (!mod->isValid()) return NULL;
514     mod->parseTypesIfNecessary();
515     BPatch_localVar * var = funcParameters->findLocalVar(name);
516     return (var);
517 }
518
519 BPatch_flowGraph* BPatch_function::getCFGInt()
520 {
521     if (!mod->isValid()) return NULL;
522     if (cfg)
523         return cfg;
524     bool valid = false;
525     cfg = new BPatch_flowGraph(this, valid);
526     if (!valid) {
527         delete cfg;
528         cfg = NULL;
529         fprintf(stderr, "CFG is NULL in %s\n", lowlevel_func()->symTabName().c_str());
530         return NULL;
531     }
532     return cfg;
533 }
534
535
536 BPatch_Vector<BPatch_localVar *> *BPatch_function::getVarsInt() 
537 {
538     if (!mod->isValid()) return NULL;
539     mod->parseTypesIfNecessary();
540     return localVariables->getAllVars(); 
541 }
542
543 BPatch_Vector<BPatch_variableExpr *> *BPatch_function::findVariableInt(
544         const char *name)
545 {
546     if (!mod->isValid()) return NULL;
547    getModule()->parseTypesIfNecessary();
548    BPatch_Vector<BPatch_variableExpr *> *ret;
549    BPatch_localVar *lv = findLocalVar(name);
550    if (!lv) {
551       // look for it in the parameter scope now
552       lv = findLocalParam(name);
553    }
554    if (lv) {
555       // create a local expr with the correct frame offset or absolute
556       //   address if that is what is needed
557       ret = new BPatch_Vector<BPatch_variableExpr *>;
558       BPatch_Vector<BPatch_point*> *points = findPoint(BPatch_entry);
559       assert(points->size() == 1);
560       BPatch_image *imgPtr = (BPatch_image *) mod->getObjParent();
561
562       ret->push_back(new BPatch_variableExpr(imgPtr->getAddressSpace(),
563                                              (void *) lv->getFrameOffset(), 
564                                              lv->getRegister(), lv->getType(), 
565                                              lv->getStorageClass(), 
566                                              (*points)[0]));
567       return ret;
568    } else {
569       // finally check the global scope.
570       BPatch_image *imgPtr = (BPatch_image *) mod->getObjParent();
571       
572       if (!imgPtr) return NULL;
573       
574       BPatch_variableExpr *vars = imgPtr->findVariable(name);
575       if (!vars) return NULL;
576       
577       ret = new BPatch_Vector<BPatch_variableExpr *>;
578       ret->push_back(vars);
579       return ret;
580    }
581 }
582
583 bool BPatch_function::getVariablesInt(BPatch_Vector<BPatch_variableExpr *> &/*vect*/)
584 {
585         return false;
586 }
587
588 char *BPatch_function::getModuleNameInt(char *name, int maxLen) {
589     return getModule()->getName(name, maxLen);
590 }
591
592 BPatch_variableExpr *BPatch_function::getFunctionRefInt() 
593 {
594   Address remoteAddress = (Address)getBaseAddrInt();
595    char *fname = const_cast<char *>(func->prettyName().c_str());
596
597    //  Need to figure out the type for this effective function pointer,
598    //  of the form <return type> (*)(<arg1 type>, ... , <argn type>)
599
600    //  Note:  getParamsInt allocates the vector
601    assert(retType);
602    char typestr[1024];
603    sprintf(typestr, "%s (*)(", retType->getName());
604
605    BPatch_Vector<BPatch_localVar *> *params = getParamsInt();
606    assert(params);
607
608    for (unsigned int i = 0; i < params->size(); ++i) {
609      if (i >= (params->size() -1)) {
610         //  no comma after last parameter
611         sprintf(typestr, "%s %s", typestr, (*params)[i]->getName());
612      } else 
613         sprintf(typestr, "%s %s,", typestr, (*params)[i]->getName());
614    }
615    sprintf(typestr, "%s)", typestr);
616
617    BPatch_type *type = addSpace->image->findType(typestr);
618    if (!type) {
619      fprintf(stderr, "%s[%d]:  cannot find type '%s'\n", FILE__, __LINE__, typestr);
620    }
621    assert(type);
622
623    //  only the vector was newly allocated, not the parameters themselves
624    delete [] params;
625
626 #if defined( arch_ia64 )
627    // IA-64 function pointers actually point to structures.  We insert such
628    // a structure in the mutatee so that instrumentation can use it. */
629    Address entryPoint = (Address)getBaseAddr();
630    
631    //RUTAR, need to change this over when we start to support IA64
632    assert(addSpace->getType() == TRADITIONAL_PROCESS);
633    BPatch_process * proc = dynamic_cast<BPatch_process *>(addSpace);
634    Address gp = proc->llproc->getTOCoffsetInfo( entryPoint );
635
636    remoteAddress = proc->llproc->inferiorMalloc( sizeof( Address ) * 2 );
637    assert( remoteAddress != (Address)NULL );
638
639    if (!proc->llproc->writeDataSpace( (void *)remoteAddress, sizeof( Address ), & entryPoint ))
640           fprintf(stderr, "%s[%d]:  writeDataSpace failed\n", FILE__, __LINE__);
641    if (!proc->llproc->writeDataSpace( (void *)(remoteAddress + sizeof( Address )), 
642                                            sizeof( Address ), & gp ))
643    fprintf(stderr, "%s[%d]:  writeDataSpace failed\n", FILE__, __LINE__);
644
645    
646    AstNodePtr *wrapper = new AstNodePtr(AstNode::operandNode(AstNode::Constant, (void *) remoteAddress));
647    // variableExpr owns the AST
648    return new BPatch_variableExpr(fname, proc, wrapper, type, (void *) remoteAddress);
649         //return (BPatch_function::voidVoidFunctionPointer)remoteAddress;
650
651 #else
652    //  For other platforms, the baseAddr of the function should be sufficient.
653
654    //  In truth it would make more sense for this to be a BPatch_constExpr,
655    //  But since we are adding this as part of the DPCL compatibility process
656    //  we use the IBM API, to eliminate one API difference.
657
658    AstNodePtr *ast = new AstNodePtr(AstNode::operandNode(AstNode::Constant, (void *) remoteAddress));
659    
660    // the variableExpr owns the ast now.
661    return new BPatch_variableExpr(fname, addSpace, ast, type, (void *) remoteAddress);
662    
663 #endif
664
665 } /* end getFunctionRef() */
666
667 #ifdef IBM_BPATCH_COMPAT
668
669 bool BPatch_function::getLineNumbersInt(unsigned int &start, unsigned int &end) {
670   char name[256];
671   unsigned int length = 255;
672   return getLineAndFileInt(start, end, name, length);
673 }
674
675 void *BPatch_function::getAddressInt() { return getBaseAddr(); }
676     
677 bool BPatch_function::getAddressRangeInt(void * &start, void * &end) {
678         start = getBaseAddr();
679         unsigned long temp = (unsigned long) start;
680         end = (void *) (temp + getSize());
681
682         return true;
683 }
684
685 //BPatch_type *BPatch_function::returnType() { return retType; }
686 void BPatch_function::getIncPointsInt(BPatch_Vector<BPatch_point *> &vect) 
687 {
688     BPatch_Vector<BPatch_point *> *v1 = findPoint(BPatch_allLocations);
689     if (v1) {
690         for (unsigned int i=0; i < v1->size(); i++) {
691             vect.push_back((*v1)[i]);
692         }
693     }
694 }
695
696 int     BPatch_function::getMangledNameLenInt() { return 1024; }
697
698 void BPatch_function::getExcPointsInt(BPatch_Vector<BPatch_point*> &points) {
699   points.clear();
700   abort();
701   return;
702 };
703
704
705 #endif
706
707 /*
708  * BPatch_function::isInstrumentable
709  *
710  * Returns true if the function is instrumentable, false otherwise.
711  */
712 bool BPatch_function::isInstrumentableInt()
713 {
714      return ((int_function *)func)->isInstrumentable();
715 }
716
717 // Return TRUE if the function resides in a shared lib, FALSE otherwise
718
719 bool BPatch_function::isSharedLibInt(){
720   return mod->isSharedLib();
721
722
723 void BPatch_function::fixupUnknown(BPatch_module *module) {
724    if (retType != NULL && retType->getDataClass() == BPatch_dataUnknownType) 
725       retType = module->getModuleTypes()->findType(retType->getID());
726
727    for (unsigned int i = 0; i < params.size(); i++)
728       params[i]->fixupUnknown(module);
729    if (localVariables != NULL) {
730       BPatch_Vector<BPatch_localVar *> *vars = localVariables->getAllVars();
731       for (unsigned int i = 0; i < vars->size(); i++)
732          (*vars)[i]->fixupUnknown(module);
733       delete vars;
734    }
735 }
736
737 bool BPatch_function::containsSharedBlocks() {
738     return func->containsSharedBlocks();
739 }
740
741 // isPrimary: function will now use this name as a primary output name
742 // isMangled: this is the "mangled" name rather than demangled (pretty)
743 const char *BPatch_function::addNameInt(const char *name,
744                                         bool isPrimary, /* = true */
745                                         bool isMangled) { /* = false */
746     // Add to the internal function object
747     //    Add to the container mapped_object name mappings
748     //    Add to the proc-independent function object
749     //       Add to the container image class
750
751     if (isMangled) {
752         func->addSymTabName(pdstring(name),
753                             isPrimary);
754     }
755     else {
756         func->addPrettyName(pdstring(name),
757                               isPrimary);
758     }
759     return name;
760 }
761
762 /* This function should be deprecated. */
763 bool BPatch_function::getLineAndFileInt( unsigned int & start, 
764                                          unsigned int & end, 
765                                          char * filename, 
766                                          unsigned int max ) 
767 {
768    Address startAddress = func->getAddress();
769    Address endAddress = startAddress + func->getSize_NP();
770         
771    BPatch_Vector<BPatch_statement> startLines;
772    if ( ! mod->getSourceLines( startAddress, startLines ) ) { return false; }
773    if ( startLines.size() == 0 ) { return false; }
774    start = startLines[0].lineNumber();
775         
776    /* Arbitrarily... */
777    strncpy( filename, startLines[0].fileName(), max );
778         
779    BPatch_Vector<BPatch_statement> endLines;
780    if ( ! mod->getSourceLines( endAddress, endLines ) ) { return false; }
781    if ( endLines.size() == 0 ) { return false; }
782    end = endLines[0].lineNumber();
783
784 return true;
785 } /* end getLineAndFile() */
786
787 /* This function should be deprecated. */
788 bool BPatch_function::getLineToAddrInt( unsigned short lineNo, BPatch_Vector< unsigned long > & buffer, bool /* exactMatch */ ) {
789         std::vector< std::pair< unsigned long, unsigned long > > ranges;
790         if( ! mod->getAddressRanges( NULL, lineNo, ranges ) ) { return false; }
791         
792         for( unsigned int i = 0; i < ranges.size(); ++i ) {
793                 buffer.push_back( ranges[i].first );
794                 }
795         
796         return true;
797         } /* end getLineToAddr() */
798
799 unsigned int BPatch_function::getContiguousSizeInt() {
800    Address start, end;
801    start = func->getAddress();
802    end = start + func->getSize_NP();
803     
804     bblInstance* block = func->findBlockInstanceByAddr(start);
805     while (block != NULL) {
806        end = block->firstInsnAddr() + block->getSize();
807        block = func->findBlockInstanceByAddr(end);
808     }
809     return end - start;
810 }
811
812 bool BPatch_function::findOverlappingInt(BPatch_Vector<BPatch_function *> &funcs) {
813     assert(func);
814     assert(addSpace);
815
816     pdvector<int_function *> overlappingIntFuncs;
817     if (!func->getOverlappingFuncs(overlappingIntFuncs)) {
818         // No overlapping functions
819         return false;
820     }
821
822     // We now need to map from int_functions to BPatch_functions
823     for (unsigned i = 0; i < overlappingIntFuncs.size(); i++) {
824         funcs.push_back(addSpace->findOrCreateBPFunc(overlappingIntFuncs[i],
825                                                  mod));
826     }
827
828     return true;
829 }
830
831 #if defined(cap_slicing)
832 /* The following structures are used in the creation of Program/Data/Control Dependence Graphs */
833 /* used to store keep track of the node where a register with number 'reg' is updated */ 
834 typedef struct RegisterUpdate{
835   int reg;
836   BPatch_dependenceGraphNode* node;
837 } regUpdate;
838
839 /* used to store which instruction last modified a given memory location */
840 typedef struct MemoryUpdate{
841   long immediate;
842   int reg0;
843   int reg1;
844   int scale;
845   BPatch_dependenceGraphNode* node;
846 } memUpdate;
847
848 #if defined(interprocedural)
849
850 /* should probably included from another file*/
851 #if defined(arch_x86)
852 #define EAX 0
853 #define ESP 4
854 #define EBP 5
855 #endif
856
857 /* The following type defs are useful for code reuse in interprocedural slicing*/
858 #if defined(sparc_sun_solaris2_4)
859 typedef regUpdate ParameterType;
860 typedef regUpdate ReturnParameterType;
861 #elif defined(arch_x86)
862 typedef memUpdate ParameterType;
863 typedef regUpdate ReturnParameterType;
864 #endif
865
866 #endif
867
868
869
870 /* as you traverse instructions in a basic block, keep which registers/mem locations are last modified by which instruction */
871 typedef struct VectorEntry{
872   BPatch_basicBlock * basicBlock;
873   BPatch_Vector<regUpdate*>* registers;
874   BPatch_Vector<memUpdate*>* memLocs;
875 #if defined(interprocedural)
876   BPatch_Vector<BPatch_dependenceGraphNode*>* prevCalls;
877 #endif
878 } entry;
879
880 /* stores a list of basic blocks which are predecessors of this 'basicBlock'*/
881 typedef struct CDGVectorEntry{
882   BPatch_basicBlock * basicBlock;
883   BPatch_Vector<BPatch_basicBlock*> depends;
884 } CDGentry;
885
886 ////////////////////////////////////////////    INTERPROCEDURAL      ///////////////////////////
887 #if defined(interprocedural)
888 typedef struct ParameterWithFuncAddress{
889   void* address;
890   union {
891     BPatch_Vector<ParameterType*>* parameters;
892     BPatch_Vector<ReturnParameterType*>*returnVals;
893   } v; // v for vector
894 } annotation;
895
896 /* returns true if a given actual parameter p1 matches a given formal parameter p2  */
897 bool match(ParameterType* p1, ParameterType* p2) {
898 #if defined(sparc_sun_solaris2_4)
899   return p1->reg+16 == p2->reg? true: false;
900 #elif defined(arch_x86)
901   if(p1->reg0 == ESP && p2->reg0 == EBP &&
902      p1->scale == p2->scale && p1->immediate+8 == p2->immediate )
903     // The difference between immediate values is 8, since prev base pointer and return address are also pushed onto stack after the parameters
904     return true;
905   return false;
906 #endif
907 }
908
909 /* returns true if a given actual return value p1 matches a given formal return value p2 */
910 bool returnMatch(ReturnParameterType* p1, ReturnParameterType* p2) {
911 #if defined(sparc_sun_solaris2_4)
912   return p1->reg+16 == p2->reg? true: false;
913 #elif defined(arch_x86)
914   return (p1->reg == p2->reg && p1->reg == EAX)? true: false;
915 #endif
916 }
917
918
919 /*
920  * Locates the dependencies between a set of formal parameters and a set of actual parameters
921  */
922 void identifyParamDependencies(BPatch_function* thisFunc, BPatch_function* callee, void* calleeAddress) {
923   BPatch_Vector<ParameterType*>* parameters = (BPatch_Vector<ParameterType*>*)callee->getAnnotation("formalParams");
924   
925   BPatch_Vector<ParameterType*>* outParams = NULL;
926   unsigned ctr;
927   for(ctr=0; true; ctr++) {
928     annotation* ann = (annotation*)thisFunc->getAnnotation("actualParams",ctr);
929     if(ann == NULL) break;
930     if(ann->address == calleeAddress) {
931       outParams = ann->v.parameters;
932       unsigned i,j;
933       ParameterType* p1;
934       fprintf(stderr,"1. Size: %d\t2. Size %d\n",outParams->size(),parameters->size());
935       for(i=0; i<outParams->size(); i++) {
936         p1 = (*outParams)[i];
937         for(j=0; j<parameters->size(); j++) {
938           ParameterType* p2 = (*parameters)[j];
939           if(match(p1,p2)) {
940             fprintf(stderr,"\n\nDepends\n\n");
941             // TODO: check this line
942             p2->node->inter->push_back(new BPatch_dependenceGraphEdge(p2->node,p1->node));
943           }
944         }
945       }   
946     }
947   }
948   if(outParams == NULL) {
949     fprintf(stderr,"No such Annotation!!\n");
950     return;
951   }
952   
953 }
954
955 /*
956  * Locates the dependencies between a set of formal returns and a set of actual returns
957  */
958 void identifyReturnDependencies(BPatch_function* thisFunc, BPatch_function* callee, void* calleeAddress) {
959   BPatch_Vector<ReturnParameterType*>* returnVals = (BPatch_Vector<ReturnParameterType*>*)callee->getAnnotation("returnVals");
960
961   BPatch_Vector<ReturnParameterType*>* returned = NULL;
962   unsigned ctr;
963   for(ctr=0; true; ctr++) {
964     annotation* ann = (annotation*)thisFunc->getAnnotation("returned",ctr);
965     if(ann == NULL) break;
966     if(ann->address == calleeAddress) {
967       returned = ann->v.returnVals;
968       //      returnedNodes = ann->nodes;
969       //      break;
970       unsigned i,j;
971       ReturnParameterType* r1;
972       fprintf(stderr,"Ret - 1. Size: %d\t2. Size %d\n",returned->size(),returnVals->size());
973       for(i=0; i<returned->size(); i++) {
974         r1 = (*returned)[i];
975         for(j=0; j<returnVals->size(); j++) {
976           ReturnParameterType* r2 = (*returnVals)[j];
977           if(returnMatch(r1,r2)) { // r1+16 == (*returnVals)[j]->reg) {
978             fprintf(stderr,"\nReturn Depends\n\n");
979             r1->node->inter->push_back(new BPatch_dependenceGraphEdge(r1->node,r2->node));
980           }
981         }
982       }
983     }
984   }
985   if(returned == NULL) {
986     fprintf(stderr,"No such Annotation!!\n");
987     return;
988   }
989 }
990
991 /*
992  * Locates dependencies between two functions (this and callee) that are results of parameter passing
993  */
994 void BPatch_function::identifyDependencies(BPatch_function* callee, void* calleeAddress) {
995   identifyParamDependencies(this, callee,  calleeAddress);
996   identifyReturnDependencies(this, callee, calleeAddress);
997 }
998
999 /* Used to copy from one function call vector to another */
1000 void copyFuncCallVector(BPatch_Vector<BPatch_dependenceGraphNode*>* original,BPatch_Vector<BPatch_dependenceGraphNode*>* copy) {
1001   unsigned int i;
1002   for(i=0; i<original->size(); i++) {
1003     copy->push_back((*original)[i]);
1004   }
1005 }
1006 #endif
1007
1008 /* If we come across a basic block more than once, check if we need to re-visit it
1009    Returns true if register lists or memory lists do not have the same contents */ // TODO: add prevCalls
1010 bool needsVisiting(BPatch_Vector<regUpdate*>* firstRegs,BPatch_Vector<memUpdate*>* firstMems, BPatch_Vector<regUpdate*>* secondRegs, BPatch_Vector<memUpdate*>* secondMems) {
1011   // is there a better method than O(m*n)? Do we know the limits of reg id's?
1012   unsigned int i, j, numMatching;
1013   numMatching=0;
1014
1015   for(i=0; i<firstRegs->size(); i++) {
1016     bool match = false;
1017     for(j=0; j<secondRegs->size(); j++) {
1018       // if this reg has a matching reg in secondRegs
1019       regUpdate* first = (*firstRegs)[i];
1020       regUpdate* second = (*secondRegs)[j];
1021       if(first->reg == second->reg && first->node->getBPInstruction()->getAddress() == second->node->getBPInstruction()->getAddress() ) {
1022         numMatching++;
1023         match=true;
1024         break;
1025       }
1026     }
1027     // if there isn't any matching reg in secondRegs, we need to visit this basic block
1028     if(match == false) {
1029       return true;
1030     }
1031   }
1032   if(numMatching != secondRegs->size()) {
1033     return true;
1034   }
1035
1036   numMatching=0;
1037   for(i=0; i<firstMems->size(); i++) {
1038     bool match = false;
1039     for(j=0; j<secondMems->size(); j++) {
1040       // if this reg has a matching reg in secondRegs
1041       memUpdate* first = (*firstMems)[i];
1042       memUpdate* second = (*secondMems)[j];
1043       if(first->reg0 == second->reg0 && first->reg1 == second->reg1 && first->scale == second->scale && first->immediate == second->immediate && 
1044       first->node->getBPInstruction()->getAddress() == second->node->getBPInstruction()->getAddress() ) {
1045         numMatching++;
1046         match=true;
1047         break;
1048       }
1049     }
1050     // if there isn't any matching reg in secondRegs, we need to visit this basic block
1051     if(match == false) {
1052       return true;
1053     }
1054   }
1055   if(numMatching != secondMems->size()) {
1056     return true;
1057   }
1058
1059   return false;
1060 }
1061
1062 /* Used to copy from one regUpdate vector to another */
1063 void copyRegisterVector(BPatch_Vector<regUpdate*>* original,BPatch_Vector<regUpdate*>* copy) {
1064   unsigned int i;
1065   for(i=0; i<original->size(); i++) {
1066     regUpdate* temp = (*original)[i];
1067     regUpdate * entry = (regUpdate*)malloc(sizeof(regUpdate));
1068     entry->reg = temp->reg;
1069     entry->node = temp->node;
1070     copy->push_back(entry);
1071   }
1072 }
1073
1074 /* Used to copy from one memUpdate vector to another */
1075 void copyMemLocVector(BPatch_Vector<memUpdate*>* original,BPatch_Vector<memUpdate*>* copy) {
1076   unsigned int i;
1077   for(i=0; i<original->size(); i++) {
1078     fflush(stdout);
1079     memUpdate* temp = (*original)[i];
1080     memUpdate * entry = (memUpdate*)malloc(sizeof(memUpdate));
1081     entry->reg0 = temp->reg0;
1082     entry->reg1 = temp->reg1;
1083     entry->scale = temp->scale;
1084     entry->immediate = temp->immediate;
1085     entry->node = temp->node;
1086     copy->push_back(entry);
1087   }
1088 }
1089
1090 int* initialize_array(int* array, int size,int num) {
1091   int i;
1092   for(i=0;i<size;i++)
1093     array[i] = num;
1094   return array;
1095 }
1096
1097 /*
1098  * print a given graph (Control dependence graph, program dependence graph, etc) in tabular format
1099  */
1100 void outputGraph(BPatch_Vector<BPatch_dependenceGraphNode*>* graph) {
1101   unsigned i,j;
1102   printf("Output the results. Total Node Num: %d\n", graph->size());
1103   fflush(stdout);
1104   for(i=0; i<graph->size(); i++) {
1105     printf("\nAddress: %ld\t Dominates: ",((*graph)[i]->getBPInstruction())==NULL?0:(long)((*graph)[i]->getBPInstruction()->getAddress()));
1106     BPatch_Vector<BPatch_dependenceGraphEdge*>* list = new BPatch_Vector<BPatch_dependenceGraphEdge*>();
1107     (*graph)[i]->getIncomingEdges(*list);
1108     for(j=0; j<list->size(); j++) {
1109       printf("%ld ",((*list)[j]->source->getBPInstruction())==NULL?0:(long)((*list)[j]->source->getBPInstruction()->getAddress()) );
1110     }
1111   }
1112 }
1113
1114 /* merge two graphs
1115  * for each BPatch_dependenceGraphNode in graph2, insert its predecessors to the predecessor list of the corresponding BPatch_dependenceGraphNode in graph1
1116  * Assumption: each instance of BPatch_dependenceGraphNode in graph 2 should have a matching BPatch_dependenceGraphNode object in graph1
1117  */
1118 bool mergeGraphs(BPatch_Vector<BPatch_dependenceGraphNode*>* graph1, BPatch_Vector<BPatch_dependenceGraphNode*>* graph2) {
1119   unsigned int i,j,k;
1120   int ins_ind=0;
1121   for(i=0; i<graph2->size(); i++) {
1122     BPatch_Vector<BPatch_dependenceGraphEdge*>* preds1 = new BPatch_Vector<BPatch_dependenceGraphEdge*>();
1123     BPatch_Vector<BPatch_dependenceGraphEdge*>* preds2 = new BPatch_Vector<BPatch_dependenceGraphEdge*>();
1124     (*graph2)[i]->getIncomingEdges(*preds2);
1125     // general case. ith element of both graphs should be related to the same instruction.
1126     if(i < graph1->size() && (*graph1)[i]->getBPInstruction() == (*graph2)[i]->getBPInstruction() ) { // should always evaluate to true in current situation
1127       (*graph1)[i]->getIncomingEdges(*preds1);
1128     }
1129     else { // search for the instruction in case previous if clause fails for some reason.
1130       bool found = false;
1131       for(j=0; j<graph1->size(); j++) {
1132         if((*graph1)[j]->getBPInstruction()!= NULL && (*graph2)[i]->getBPInstruction()!= NULL && 
1133            (*graph1)[j]->getBPInstruction()->getAddress() == (*graph2)[i]->getBPInstruction()->getAddress()) {
1134           found = true;
1135           (*graph1)[j]->getIncomingEdges(*preds1);
1136           ins_ind = j;
1137           break;
1138         }
1139       }
1140       // if not found in the first list, there is a mismatch between instructions! Not tolerable at this time.
1141       if(!found)
1142         return false;
1143     }
1144     // iterate through both lists and update first list if there are some objects in list 2 which are not matched in list 1.
1145     for(j=0; j<preds2->size(); j++) {
1146       bool found=false;
1147       for(k=0; k<preds1->size(); k++) {
1148         if((*preds2)[j]->source->getBPInstruction()->getAddress() == (*preds1)[k]->source->getBPInstruction()->getAddress()) {
1149           found=true;
1150           break;
1151         }
1152       }
1153       if(!found) {
1154         (*graph1)[ins_ind]->addToIncoming((*preds2)[j]->source);
1155       }
1156     }
1157     delete preds1;
1158     delete preds2;
1159   }
1160
1161   return true;
1162 }
1163
1164
1165 /* Used to copy the dependence graph of any kind.
1166  * Before calling mergeGraphs, I copy the first one since it will get modified by the mergeGraphs method.
1167  */
1168 BPatch_Vector<BPatch_dependenceGraphNode*>* copyDependenceGraph(BPatch_Vector<BPatch_dependenceGraphNode*>* graph) {
1169   if(graph == NULL) {
1170     fprintf(stderr,"Graph is empty (NULL)");
1171     return NULL;
1172   }
1173   BPatch_Vector<BPatch_dependenceGraphNode*>* copy = new BPatch_Vector<BPatch_dependenceGraphNode*>();
1174   unsigned i,j,k;
1175   BPatch_Vector<BPatch_dependenceGraphEdge*>* preds; //successors;
1176
1177   for(i=0; i<graph->size(); i++) {
1178     BPatch_dependenceGraphNode* newInst = new BPatch_dependenceGraphNode((*graph)[i]->getBPInstruction(),new BPatch_Vector<BPatch_dependenceGraphEdge*>(),new BPatch_Vector<BPatch_dependenceGraphEdge*>());
1179     copy->push_back(newInst);
1180   }
1181   for(i=0; i<graph->size(); i++) {
1182     preds = new BPatch_Vector<BPatch_dependenceGraphEdge*>();
1183     (*graph)[i]->getIncomingEdges(*preds);
1184     for(j=0; j<preds->size(); j++) {
1185       bool found=false;
1186       for(k=0; k<copy->size(); k++) {
1187         if(((*copy)[k]->getBPInstruction() == NULL && (*preds)[j]->source->getBPInstruction()==NULL) || 
1188            ((*copy)[k]->getBPInstruction() != NULL && (*preds)[j]->source->getBPInstruction()!=NULL && (*copy)[k]->getBPInstruction()->getAddress() == (*preds)[j]->source->getBPInstruction()->getAddress())) {
1189           // add to predecessor list of i'th obj.
1190           (*copy)[i]->addToIncoming((*copy)[k]);
1191           // add to successor list of k'th object
1192           (*copy)[k]->addToOutgoing((*copy)[i]);
1193           found=true;
1194           break;
1195         }
1196       }
1197       assert(found);
1198     }
1199   }
1200   return copy;
1201 }
1202
1203 /*
1204  * Given an instruction inst, find the backward slice of the program from that instruction.
1205  * This assumes that the variable/register that is in the slicing criteria is modified at this instruction
1206  * This function builds the extended program dependence graph if not built before, then searched for the given instruction in that graph 
1207  */
1208 BPatch_dependenceGraphNode* BPatch_function::getSliceInt(BPatch_instruction* inst) {
1209   if(inst == NULL)
1210     return NULL;
1211   unsigned i;
1212   createExtendedProgramDependenceGraph();
1213   BPatch_Vector<BPatch_dependenceGraphNode*>* extendedProgramDependenceGraph = (BPatch_Vector<BPatch_dependenceGraphNode*>*)getAnnotation("ExtendedProgramDependenceGraph");
1214   for(i=0; i<extendedProgramDependenceGraph->size(); i++) {
1215     if((*extendedProgramDependenceGraph)[i]->getBPInstruction() != NULL && (*extendedProgramDependenceGraph)[i]->getBPInstruction()->getAddress() == inst->getAddress()) {
1216       return (*extendedProgramDependenceGraph)[i];
1217     }
1218   }
1219   return NULL;
1220 }
1221
1222 /*
1223  * Creates extended program dependence graph (program dependence graph + another graph which I call helper graph for now)
1224  */
1225 void BPatch_function::createExtendedProgramDependenceGraph() {
1226   if(getAnnotation("ExtendedProgramDependenceGraph") == NULL) {
1227     if(getAnnotation("ProgramDependenceGraph") == NULL)
1228       createProgramDependenceGraph();
1229     BPatch_Vector<BPatch_dependenceGraphNode*>* extendedProgramDependenceGraph = copyDependenceGraph((BPatch_Vector<BPatch_dependenceGraphNode*>*)getAnnotation("ProgramDependenceGraph"));
1230     // now add the unconditional jump and return instructions.
1231     mergeGraphs(extendedProgramDependenceGraph,(BPatch_Vector<BPatch_dependenceGraphNode*>*)getAnnotation("HelperGraph"));
1232     setAnnotation(getAnnotationType("ExtendedProgramDependenceGraph"), new Annotation(extendedProgramDependenceGraph));
1233   }
1234 }
1235
1236 /*
1237  * Creates program dependence graph (Control dependence Graph + data dependence graph)
1238  */
1239 void BPatch_function::createProgramDependenceGraph(/*BPatch_flowGraph* cfg*/) {
1240   if(getAnnotation("ProgramDependenceGraph") == NULL) {
1241     if(getAnnotation("ControlDependenceGraph") == NULL) {
1242       // updates the global controlDependenceGraph variable
1243       createControlDependenceGraph();
1244     }
1245     if(getAnnotation("DataDependenceGraph") == NULL) {
1246       // updates the global dataDependenceGraph variable
1247       createDataDependenceGraph();
1248     }
1249     BPatch_Vector<BPatch_dependenceGraphNode*>* programDependenceGraph = copyDependenceGraph((BPatch_Vector<BPatch_dependenceGraphNode*>*)getAnnotation("ControlDependenceGraph"));
1250     mergeGraphs(programDependenceGraph,(BPatch_Vector<BPatch_dependenceGraphNode*>*)getAnnotation("DataDependenceGraph")); // updates programDependenceGraph
1251     setAnnotation(getAnnotationType("ProgramDependenceGraph"), new Annotation(programDependenceGraph));
1252   } 
1253
1254 #ifdef print_graphs
1255   BPatch_Vector<BPatch_dependenceGraphNode*> * allNodes = (BPatch_Vector<BPatch_dependenceGraphNode*>*)getAnnotation("ProgramDependenceGraph");
1256   printf("Progam Dependence Graph. Total Node Num: %d\n", allNodes->size());
1257   outputGraph(allNodes);
1258 #endif
1259 }
1260 /*
1261  * BPatch_function::getProgramDependenceGraph
1262  *
1263  * given a BPatch_instruction object, returns the corresponding BPatch_dependenceGraphNode object
1264  * which enables accessing the predecessors and successors of this instruction
1265  */
1266 BPatch_dependenceGraphNode* BPatch_function::getProgramDependenceGraphInt(BPatch_instruction* inst) {
1267   unsigned int i;
1268   if(getAnnotation("ProgramDependenceGraph") == NULL) {
1269     createProgramDependenceGraph();
1270   }
1271   BPatch_Vector<BPatch_dependenceGraphNode*>* programDependenceGraph = (BPatch_Vector<BPatch_dependenceGraphNode*>*)getAnnotation("ProgramDependenceGraph");
1272   for(i=0; i<programDependenceGraph->size(); i++) {
1273     if((*programDependenceGraph)[i]->getBPInstruction() != NULL && (*programDependenceGraph)[i]->getBPInstruction()->getAddress() == inst->getAddress()) {
1274       return (*programDependenceGraph)[i];
1275     }
1276   }
1277   return NULL;
1278 }
1279
1280 /*
1281  * BPatch_function::getControlDependenceGraph
1282  * 
1283  * given a BPatch_instruction object, returns the corresponding BPatch_dependenceGraphNode object
1284  * that has information about which instructions dominate/are dominated by this instruction in the
1285  * control dependence graph
1286  */
1287 BPatch_dependenceGraphNode* BPatch_function::getControlDependenceGraphInt(BPatch_instruction* inst) {
1288   unsigned int i;
1289   if(getAnnotation("ControlDependenceGraph") == NULL) {
1290     createControlDependenceGraph();
1291   }
1292   BPatch_Vector<BPatch_dependenceGraphNode*>* controlDependenceGraph = (BPatch_Vector<BPatch_dependenceGraphNode*>*)getAnnotation("ControlDependenceGraph");
1293   for(i=0; i<controlDependenceGraph->size(); i++) {
1294     if((*controlDependenceGraph)[i]->getBPInstruction() != NULL && (*controlDependenceGraph)[i]->getBPInstruction()->getAddress() == inst->getAddress()) {
1295       return (*controlDependenceGraph)[i];
1296     }
1297   }
1298   return NULL;
1299 }
1300
1301 /*
1302  * BPatch_function::getDataDependenceGraph
1303  * 
1304  * given a BPatch_instruction object, returns the corresponding BPatch_dependenceGraphNode object
1305  * that has information about which instructions dominate/are dominated by this instruction in the
1306  * data dependence graph
1307  */
1308 BPatch_dependenceGraphNode* BPatch_function::getDataDependenceGraphInt(BPatch_instruction* inst) {
1309   unsigned int i;
1310   if(getAnnotation("DataDependenceGraph") == NULL) {
1311     createDataDependenceGraph();
1312   }
1313   BPatch_Vector<BPatch_dependenceGraphNode*>* dataDependenceGraph = (BPatch_Vector<BPatch_dependenceGraphNode*>*)getAnnotation("DataDependenceGraph");
1314   for(i=0; i<dataDependenceGraph->size(); i++) {
1315     if((*dataDependenceGraph)[i]->getBPInstruction()->getAddress() == inst->getAddress()) {
1316       return (*dataDependenceGraph)[i];
1317     }
1318   }
1319   return NULL;
1320 }
1321
1322 /*
1323  * Using post-dominator information, marks the control dependencies between basic blocks
1324  */
1325 BPatch_Vector<BPatch_basicBlock*>** createBlockDependency(int num_blocks, BPatch_basicBlock** blocks) {
1326   unsigned j;
1327   int i;
1328   BPatch_Vector<BPatch_basicBlock*>** dependencies = (BPatch_Vector<BPatch_basicBlock*>**)malloc(sizeof(BPatch_Vector<BPatch_basicBlock*>*)*num_blocks);//new BPatch_Vector<BPatch_basicBlock*>[num_blocks];
1329   for(i=0; i<num_blocks; i++) {
1330     dependencies[i] = new BPatch_Vector<BPatch_basicBlock*>();
1331   }
1332   BPatch_Vector<BPatch_basicBlock*>* out;
1333   int* parent_check = initialize_array(new int[num_blocks],num_blocks,-1);
1334   for(i=0; i<num_blocks; i++) {
1335     out = new BPatch_Vector<BPatch_basicBlock*>();
1336     (blocks[i])->getTargets(*out);
1337     for(j=0; j<out->size(); j++) {
1338       if( ! ((*out)[j]->postdominates(blocks[i])) ) {
1339         // Work on this edge right now;
1340         // mark all parents of blocks[i]
1341         BPatch_basicBlock* temp = blocks[i];
1342         // According to Ferrante et al. page 325, marking only this node and its parent is enough
1343         parent_check[ temp->getBlockNumber() ] = 1;
1344         temp = temp->getImmediatePostDominator();
1345         if(temp!=NULL) {
1346           parent_check[ temp->getBlockNumber() ] = 1;
1347         }
1348         // traverse from out[j] to one of the parents marked in the previous step
1349         temp = (*out)[j];
1350         while(temp!=NULL && parent_check[ temp->getBlockNumber() ] != 1) {
1351           // mark them as control dependent to blocks[i]
1352           dependencies[ temp->getBlockNumber() ]->push_back(blocks[i]);
1353           temp = temp->getImmediatePostDominator();
1354         }
1355           }
1356     }
1357     delete out;
1358   }
1359   free(parent_check);
1360   return dependencies;
1361 }
1362
1363 void determineReturnBranchDependencies(BPatch_Vector<BPatch_dependenceGraphNode*>* controlDependenceGraph, BPatch_Vector<BPatch_dependenceGraphNode*>* helperGraph, BPatch_Vector<BPatch_basicBlock*>** dependencies,
1364                                        BPatch_Vector<BPatch_basicBlock*>* blockNumbers, BPatch_basicBlock** blocks, int num_blocks,BPatch_dependenceGraphNode** last_inst_in_block,BPatch_dependenceGraphNode** last_inst_helper) {
1365   unsigned i,j;
1366   for(i=0; i<(unsigned)num_blocks; i++) {
1367     BPatch_basicBlock * blck = blocks[i];
1368     InstrucIter* iter;
1369     for(iter = new InstrucIter(blck); iter->hasMore(); (*iter)++) {
1370       BPatch_dependenceGraphNode* bpdom = new BPatch_dependenceGraphNode(iter->getBPInstruction(),new BPatch_Vector<BPatch_dependenceGraphEdge*>(),new BPatch_Vector<BPatch_dependenceGraphEdge*>());
1371       // printf("in block %d\n",blck->getBlockNumber()/*bpdom->getBPInstruction()->getParent()->getBlockNumber()*/); fflush(stdout);
1372       controlDependenceGraph->push_back(bpdom);
1373       helperGraph->push_back(new BPatch_dependenceGraphNode(iter->getBPInstruction(),
1374                             new BPatch_Vector<BPatch_dependenceGraphEdge*>(),new BPatch_Vector<BPatch_dependenceGraphEdge*>()));
1375       blockNumbers->push_back(blck);
1376     }
1377     last_inst_in_block[blck->getBlockNumber()] = (*controlDependenceGraph)[ controlDependenceGraph->size()-1 ];
1378     (*iter)--;
1379     if(iter->hasMore() && (iter->isAReturnInstruction() || iter->isAJumpInstruction()) )
1380       last_inst_helper[blck->getBlockNumber()] = (*helperGraph)[ helperGraph->size()-1 ];
1381     else
1382       last_inst_helper[blck->getBlockNumber()] = NULL;
1383   }
1384
1385   for(i=0; i<controlDependenceGraph->size(); i++) {
1386     int blockNum = (*blockNumbers)[i]->getBlockNumber();//(*controlDependenceGraph)[i]->getBPInstruction()->getParent()->getBlockNumber();
1387     BPatch_dependenceGraphNode* instDom = (*controlDependenceGraph)[i];
1388     for(j=0; j< dependencies[blockNum]->size(); j++) {
1389       instDom->addToIncoming(last_inst_in_block[(*dependencies[blockNum])[j]->getBlockNumber() ]);
1390       last_inst_in_block[(*dependencies[blockNum])[j]->getBlockNumber() ]->addToOutgoing(instDom);
1391     }
1392     if(last_inst_helper[blockNum] != NULL) {
1393       (*helperGraph)[i]->addToIncoming(last_inst_helper[blockNum]);
1394       last_inst_helper[blockNum]->addToOutgoing((*helperGraph)[i]);
1395     }
1396   }
1397 }
1398
1399 /*
1400  * Used to create the control dependence graph from the binary.
1401  * Called only once for each function
1402  */
1403 void BPatch_function::createControlDependenceGraph() {
1404   unsigned num_blocks;
1405   BPatch_flowGraph* cfg = getCFG();
1406   
1407   // if we already calculated graph, return immediately
1408   if(getAnnotation("ControlDependenceGraph") != NULL)
1409     return;
1410   // if we are here, annotation type for helper graph must be missing. So, create it:
1411   createAnnotationType("HelperGraph");
1412   
1413   // get the dominators
1414   // already there! No need to do anything real
1415   
1416   // calculate dependency relation in terms of basic blocks
1417
1418   BPatch_Set<BPatch_basicBlock*> all_b_b;
1419
1420   cfg->getAllBasicBlocks(all_b_b); //getBasicBlocks(cfg, all_b_b);
1421   num_blocks = all_b_b.size();
1422
1423   BPatch_basicBlock** blocks = new BPatch_basicBlock*[num_blocks];
1424   all_b_b.elements(blocks);
1425
1426   // create the dependencies between blocks.
1427   BPatch_Vector<BPatch_basicBlock*>** dependencies = createBlockDependency(num_blocks, blocks);
1428
1429   BPatch_Vector<BPatch_basicBlock*>* blockNumbers = new BPatch_Vector<BPatch_basicBlock*>();
1430   BPatch_Vector<BPatch_dependenceGraphNode*>* controlDependenceGraph = new BPatch_Vector<BPatch_dependenceGraphNode*>();
1431   BPatch_Vector<BPatch_dependenceGraphNode*>* helperGraph = new BPatch_Vector<BPatch_dependenceGraphNode*>();
1432
1433   // use dependency relation to figure out which instruction depends on which instruction
1434   BPatch_dependenceGraphNode** last_inst_in_block = (BPatch_dependenceGraphNode**)malloc(sizeof(BPatch_dependenceGraphNode*)*num_blocks);
1435   BPatch_dependenceGraphNode** last_inst_helper = (BPatch_dependenceGraphNode**)malloc(sizeof(BPatch_dependenceGraphNode*)*num_blocks);
1436   determineReturnBranchDependencies(controlDependenceGraph, helperGraph, dependencies, blockNumbers, blocks, num_blocks,last_inst_in_block,last_inst_helper);
1437
1438 #ifdef print_graphs
1439   printf("\nControlDependenceGraph\n");
1440   outputGraph(controlDependenceGraph);
1441
1442   printf("\nHelperGraph\n");
1443   outputGraph(helperGraph);
1444 #endif
1445   setAnnotation(getAnnotationType("ControlDependenceGraph"), new Annotation(controlDependenceGraph));
1446   setAnnotation(getAnnotationType("HelperGraph"), new Annotation(helperGraph));
1447 } // end of createControlDependenceGraph
1448
1449
1450 /* find out which instruction last modified the register specified with reg_num 
1451  * and add that instruction to predecessor list of this node,
1452  * and add this node to successor list of that instruction
1453 */
1454 void register_check(int reg_num, BPatch_Vector<regUpdate*>* registers, BPatch_dependenceGraphNode* node) {
1455   unsigned k, l;
1456   bool found = false;
1457   //if(reg_num != -1) {
1458   for(k=0; k<registers->size(); k++) {
1459     if(reg_num == (*(registers))[k]->reg) {
1460       found = true;
1461       BPatch_Vector<BPatch_dependenceGraphEdge*>* predPtr = new BPatch_Vector<BPatch_dependenceGraphEdge*>();
1462       node->getIncomingEdges(*predPtr);
1463       bool alreadyInList = false;
1464       void* successor_addr = (*(registers))[k]->node->getBPInstruction()->getAddress();
1465       for(l=0; l<predPtr->size(); l++) {
1466         if((*predPtr)[l]->source->getBPInstruction()->getAddress() == successor_addr) {
1467           alreadyInList = true;
1468           break;
1469         }
1470       }
1471       if(alreadyInList == false) {
1472         node->addToIncoming((*(registers))[k]->node);
1473         (*(registers))[k]->node->addToOutgoing(node);
1474       }
1475     }
1476   }
1477   // if not found in the registers list, uninitialized!! Do whatever you want.. Report?
1478   if(found == false) {
1479     // printf("\nUninitialized %d!!",reg_num);  
1480   }
1481 }
1482
1483 /*
1484  * Find the entry blocks for this function, and put them into the workload after wrapping them with some data structures
1485  */
1486 void pushEntryBlocks(BPatch_Vector<entry*>& blocks, BPatch_flowGraph* cfg) {
1487   // get a handle to entry block(s)
1488   unsigned i;
1489   BPatch_Vector<BPatch_basicBlock*>* entryBlocks =new BPatch_Vector<BPatch_basicBlock*>();
1490   cfg->getEntryBasicBlock(*entryBlocks);
1491
1492   // start with entry blocks, so copy them to the front
1493   for(i=0; i<entryBlocks->size(); i++) {
1494     entry* entryBlEntry = (entry *)malloc(sizeof(entry));
1495     entryBlEntry->registers =new BPatch_Vector<regUpdate*>();
1496     entryBlEntry->memLocs =new BPatch_Vector<memUpdate*>();
1497     entryBlEntry->basicBlock = (*entryBlocks)[i];
1498 #if defined(interprocedural)
1499     entryBlEntry->prevCalls = new BPatch_Vector<BPatch_dependenceGraphNode*>();
1500 #endif
1501     blocks.push_back(entryBlEntry);
1502   }
1503   delete entryBlocks;
1504 }
1505
1506 /*
1507  * find the node of a graph that contains the given BPatch_instruction
1508  */
1509 BPatch_dependenceGraphNode* getNode(BPatch_Vector<BPatch_dependenceGraphNode*>* allNodes, BPatch_instruction* bpins) {
1510   unsigned j;
1511   BPatch_dependenceGraphNode * node;
1512   bool nodeAvailable = false;
1513   for(j=0; j<allNodes->size(); j++) {
1514     if((*allNodes)[j]->getBPInstruction()->getAddress() == bpins->getAddress()) {
1515       nodeAvailable=true;
1516       break;
1517     }
1518   }
1519   // if available, it is at j'th position
1520   if(nodeAvailable == true)
1521     node = (*allNodes)[j];
1522   else {
1523     node = new BPatch_dependenceGraphNode(bpins,new BPatch_Vector<BPatch_dependenceGraphEdge*>(),new BPatch_Vector<BPatch_dependenceGraphEdge*>());
1524     allNodes->push_back(node);
1525   }
1526   return node;
1527 }
1528
1529 void handleCondBranch(BPatch_dependenceGraphNode* node, InstrucIter* iter, BPatch_Vector<BPatch_dependenceGraphNode*>* allNodes) {
1530   unsigned i;
1531   if(iter->hasPrev()) {
1532     void* pred_addr = (void*)iter->peekPrev();
1533     BPatch_dependenceGraphNode* prevNode = NULL;
1534     // the previous instruction should be in the previous index. Check anyway...
1535     if(allNodes->size() >= 2 && (*allNodes)[allNodes->size()-2]->getBPInstruction()->getAddress() == pred_addr) {
1536       prevNode = (*allNodes)[allNodes->size()-2];
1537     }
1538     else {
1539       for(i=0; i<allNodes->size(); i++) {
1540         if((*allNodes)[i]->getBPInstruction()->getAddress() == pred_addr) {
1541           prevNode = (*allNodes)[i];
1542           break;
1543         }
1544       }
1545       if(prevNode == NULL) {
1546         fprintf(stderr,"Control should have never reached here. (No previous instruction). Exiting...");
1547         exit(1);
1548       }
1549     }
1550     
1551     BPatch_Vector<BPatch_dependenceGraphEdge*>* predPtr = new BPatch_Vector<BPatch_dependenceGraphEdge*>();
1552     node->getIncomingEdges(*predPtr);
1553     bool alreadyInList = false;
1554     for(i=0; i<predPtr->size(); i++) {
1555       if((*predPtr)[i]->source->getBPInstruction()->getAddress() == pred_addr ) {
1556         alreadyInList = true;
1557         break;
1558       }
1559     }
1560     if(alreadyInList == false) {
1561       node->addToIncoming(prevNode);
1562       prevNode->addToOutgoing(node);
1563     }
1564   }
1565 }
1566
1567 /*
1568  * If an instruction accesses a memory location, find out which registers/memory locations are affected
1569  */
1570 void handleMemoryAccess(BPatch_dependenceGraphNode* node, BPatch_instruction* bpins, BPatch_Vector<regUpdate*>* copy_regs, 
1571                         BPatch_Vector<memUpdate*>* copy_mems, const BPatch_addrSpec_NP* addrSpec
1572 #if defined(arch_x86)
1573 #else
1574                         , InstrucIter* iter, int reg_offset
1575 #endif
1576                         ) {
1577   unsigned k, l;
1578   if(addrSpec->getReg(0) == 0 && addrSpec->getReg(1) == 0 && addrSpec->getImm() == 0 && addrSpec->getScale() == 0 ) {
1579     return;
1580   }
1581   
1582   int reg0 = addrSpec->getReg(0);
1583   int reg1 = addrSpec->getReg(1);
1584 #if defined(arch_x86)
1585 #else
1586   if(reg0 != -1)
1587     reg0 = iter->adjustRegNumbers(reg0,reg_offset);
1588   if(reg1 != -1)
1589     reg1 = iter->adjustRegNumbers(reg1,reg_offset);
1590 #endif
1591   
1592   // first, check whether the registers that are used in address computation are already in the copy_regs list!!
1593   if(reg0 != -1)
1594     register_check(reg0,copy_regs,node);
1595   if(reg1 != -1)
1596     register_check(reg1,copy_regs,node);
1597   
1598   bool found = false;
1599   for(k=0; k<copy_mems->size(); k++) {
1600     // if this is the one we're looking for
1601     if(reg0 == (*(copy_mems))[k]->reg0 && reg1 == (*(copy_mems))[k]->reg1 &&
1602        addrSpec->getScale() == (*(copy_mems))[k]->scale && addrSpec->getImm() == (*(copy_mems))[k]->immediate ) {
1603       
1604       if(bpins->isALoad()) { // reading from memory
1605         // Update dominates list of the node where this reg was last written
1606         BPatch_Vector<BPatch_dependenceGraphEdge*>* predPtr = new BPatch_Vector<BPatch_dependenceGraphEdge*>();
1607         node->getIncomingEdges(*predPtr);//(*(copy_mems))[k]->node->getSuccessors();
1608         bool alreadyInList = false;
1609         void* predecessor_addr = (*(copy_mems))[k]->node->getBPInstruction()->getAddress();
1610         for(l=0; l<predPtr->size(); l++) {
1611           if((*predPtr)[l]->source->getBPInstruction()->getAddress() == predecessor_addr ) {
1612             alreadyInList = true;
1613             break;
1614           }
1615         }
1616         if(alreadyInList == false) {
1617           node->addToIncoming((*(copy_mems))[k]->node);
1618           (*(copy_mems))[k]->node->addToOutgoing(node);
1619         }
1620       }
1621       if(bpins->isAStore()) {
1622         // update the memory entry so that it stores this node as the last location this reg was written
1623         (*(copy_mems))[k]->node = node;
1624       }
1625       found = true;
1626       break;
1627     }
1628   }
1629   // if(found == false && bpins->isALoad()) // do nothing
1630   // if a register is written which is not in the out list, we add this register and node to the list
1631   if(found == false && bpins->isAStore()) {
1632     memUpdate* cell = (memUpdate*)malloc(sizeof(memUpdate));
1633     cell->reg0 = reg0;
1634     cell->reg1 = reg1;
1635     cell->scale = addrSpec->getScale();
1636     cell->immediate = addrSpec->getImm();
1637     cell->node = node;
1638     // add this to the list...
1639     copy_mems->push_back(cell);
1640   }
1641   else if(found == false) { // && bpins->isALoad() => trivially true
1642     // Uninitialized
1643   }
1644 }
1645
1646 /*
1647  * add new blocks to the workload after one is processed. The blocks that are directly reachable from block blck are added
1648  */
1649 void addBlocksToWorkload(BPatch_Vector<entry*>& blocks, BPatch_basicBlock* blck, int* visitedBlocks,
1650                          BPatch_Vector<regUpdate*>* copy_regs, BPatch_Vector<memUpdate*>* copy_mems
1651 #if defined(interprocedural)
1652                          , BPatch_Vector<BPatch_dependenceGraphNode*>* funcCalls
1653 #endif
1654                          ) {
1655   unsigned j;
1656   // get the basic blocks which has en edge towards this basic block
1657   //BPatch_Vector<BPatch_edge*>* outgoing = new BPatch_Vector<BPatch_edge*>();
1658   BPatch_Vector<BPatch_basicBlock*> outgoing;
1659   //      BPatch_Vector<BPatch_edge*> incoming = *incomingPtr;
1660   //      blck->getOutgoingEdges(*outgoing);
1661   blck->getTargets(outgoing);
1662   
1663   for(j=0; j<outgoing.size(); j++) {
1664     int blockLocation;
1665     BPatch_basicBlock* outBlck = outgoing[j];//->target;
1666     blockLocation = visitedBlocks[outBlck->getBlockNumber()];
1667     if(blockLocation == -1 || needsVisiting(copy_regs, copy_mems, blocks[blockLocation]->registers, blocks[blockLocation]->memLocs)) {
1668       
1669       entry * ptr = (entry*)malloc(sizeof(entry));
1670       ptr->basicBlock = outBlck;
1671       
1672       BPatch_Vector<regUpdate*>* newCopy = new BPatch_Vector<regUpdate*>();
1673       copyRegisterVector(copy_regs, newCopy);
1674       
1675       BPatch_Vector<memUpdate*>* new_mems = new BPatch_Vector<memUpdate*>();
1676       copyMemLocVector(copy_mems, new_mems);
1677       
1678 #if defined(interprocedural)
1679       BPatch_Vector<BPatch_dependenceGraphNode*>* newCalls = new BPatch_Vector<BPatch_dependenceGraphNode*>();
1680       copyFuncCallVector(funcCalls, newCalls);
1681       ptr->prevCalls = newCalls;
1682 #endif
1683       
1684       ptr->registers = newCopy;
1685       ptr->memLocs = new_mems;
1686
1687       blocks.push_back(ptr);      
1688     }
1689   }
1690 }
1691
1692 /* if a register is written by an instruction, store this info since future reads will depend on this write */
1693 void handleWrittenRegister(BPatch_dependenceGraphNode* node, int rn, BPatch_Vector<regUpdate*>* copy_regs) {
1694   bool found = false;
1695   unsigned k;
1696   for(k=0; k<copy_regs->size(); k++) {
1697     // if a reg in out list is written by this instruction
1698     if(rn == (*(copy_regs))[k]->reg) {
1699       // update the register entry so that it stores this node as the last location this reg was written     
1700       (*(copy_regs))[k]->node = node;
1701       found = true;
1702     }
1703   }
1704   // if a register is written which is not in the out list, we add this register and node to the list
1705   if(found == false) {
1706     regUpdate* reg = (regUpdate*)malloc(sizeof(regUpdate));
1707     reg->reg = rn;
1708     reg->node = node;
1709     // add this to the list...
1710     copy_regs->push_back(reg);
1711   }
1712 }
1713
1714 #if defined(interprocedural)
1715  bool isWrittenBefore(int reg_num, BPatch_Vector<regUpdate*>* registers) {
1716    unsigned i;
1717    for(i=0;i<registers->size();i++) {
1718      if(reg_num == (*(registers))[i]->reg) {
1719        return true;
1720      }
1721    }
1722    return false;
1723  }
1724  
1725  bool isReturnedValue(int r) {
1726 #if defined(sparc_sun_solaris2_4)
1727    if(r >= 8 && r < 14) {
1728      return true;
1729    }
1730 #elif defined(arch_x86)
1731    if(r == EAX)
1732      return true;
1733 #endif
1734    return false;
1735  }
1736
1737  bool isReturnValue(int r) {
1738 #if defined(sparc_sun_solaris2_4)
1739    if(r >= 24 && r < 30) {
1740      return true;
1741    }
1742 #elif defined(arch_x86)
1743    if(r == EAX)
1744      return true;
1745 #endif
1746    return false;
1747  }
1748 #endif
1749
1750 /*
1751  * Used to create the data dependence graph from the binary.
1752  * Called only once for each function
1753  */
1754 void BPatch_function::createDataDependenceGraph() {
1755   unsigned i,j;
1756   BPatch_flowGraph* cfg = getCFG();
1757
1758 #if defined(arch_x86)
1759   unsigned num_regs=3;
1760 #else
1761   unsigned num_regs=8;
1762   int reg_offset = 0;
1763 #endif
1764   int * writeArr = (int *) malloc(sizeof(int)*num_regs);
1765   int * readArr = (int *) malloc(sizeof(int)*num_regs);
1766   // ******************** Initializations and collecting required objects **************************
1767   if(getAnnotation("DataDependenceGraph") != NULL)
1768     return;
1769
1770 #if defined(interprocedural)
1771   BPatch_Vector<ParameterType*>* parameters = new BPatch_Vector<ParameterType*>();
1772   setAnnotation(createAnnotationType("formalParams"), new Annotation(parameters));  
1773
1774   BPatch_Vector<ParameterType*>* actualParams = new BPatch_Vector<ParameterType*>();
1775   BPatch_Vector<ReturnParameterType*>* returned = new BPatch_Vector<ReturnParameterType*>();
1776
1777   /*
1778   BPatch_Vector<void*>* production = new BPatch_Vector<void*>();
1779   setAnnotation(createAnnotationType("production"), new Annotation(production));  
1780   */
1781 #endif
1782
1783
1784   BPatch_Vector<BPatch_dependenceGraphNode*>* dataDependenceGraph = new BPatch_Vector<BPatch_dependenceGraphNode*>();
1785   BPatch_Vector<entry *> blocks;// = *blocksPtr;
1786
1787   BPatch_Set<BPatch_basicBlock*> all_b_b;
1788   cfg->getAllBasicBlocks(all_b_b); // getBasicBlocks(cfg, all_b_b);
1789
1790   // an array to store whether a basic block is visited, parallel to the blocks
1791   int* visitedBlocks = initialize_array(new int[all_b_b.size()], all_b_b.size(), -1);
1792
1793   /// ****************** start with entry blocks ************************************************
1794   pushEntryBlocks(blocks, cfg);
1795 // ***************************** Iterate through all blocks ***********************************
1796 #if defined(logging)
1797   FILE* logFile = fopen("log.txt","w");
1798 #endif
1799   // iterate as long as there are blocks in the list
1800   for(i=0; i<blocks.size(); i++) {
1801     BPatch_basicBlock * blck = blocks[i]->basicBlock;
1802     int blockNum = blck->getBlockNumber(); // the block number of this basic block
1803     int blockLoc = visitedBlocks[blockNum]; // the location of this block in the blocks list
1804 #if defined(logging)
1805     fprintf(logFile,"Block Num: %d\n",blockNum);
1806 #endif
1807     //    printf("Block Num %d\n",blockNum);
1808     // in case a block is visited after being checked, double-check if it is visited
1809     // May not be enough when there is a loop in CFG, so also check before pushing into the list
1810
1811     // if not visited, visit now
1812     // perhaps the register list is different, check
1813     if(blockLoc == -1 || needsVisiting(blocks[i]->registers, blocks[i]->memLocs, blocks[blockLoc]->registers, blocks[blockLoc]->memLocs)) {
1814       visitedBlocks[blockNum] = i; // update the block location
1815
1816 #if defined(logging)
1817     fprintf(logFile,"Block Num: %d Being visited\n",blockNum);
1818 #endif
1819       // create an iterator
1820       InstrucIter* iter;// = new InstrucIter(blck);
1821       InstrucIter* prevIter;
1822       // create a copy of the register vector
1823       BPatch_Vector<regUpdate*>* copy_regs = new BPatch_Vector<regUpdate*>();
1824       copyRegisterVector(blocks[i]->registers, copy_regs);
1825
1826       BPatch_Vector<memUpdate*>* copy_mems = new BPatch_Vector<memUpdate*>();
1827       copyMemLocVector(blocks[i]->memLocs, copy_mems);
1828
1829 #if defined(interprocedural)
1830       BPatch_Vector<BPatch_dependenceGraphNode*>* copy_calls = new BPatch_Vector<BPatch_dependenceGraphNode*>();
1831       copyFuncCallVector(blocks[i]->prevCalls, copy_calls);
1832
1833       //      BPatch_Vector<BPatch_instruction *> * insts = blck->getInstructions();
1834 #endif
1835       // prevIter initally does not point to previous instruction, but it is OK.
1836       for(iter = new InstrucIter(blck), prevIter = new InstrucIter(blck); iter->hasMore(); (*iter)++) {
1837         instruction ins = iter->getInstruction();
1838         BPatch_instruction* bpins = iter->getBPInstruction();
1839         // check whether a memory operation is performed
1840         BPatch_memoryAccess * memAcc = iter->isLoadOrStore();
1841         // create a node for this instruction in case we did not create yet
1842         BPatch_dependenceGraphNode * node = getNode(dataDependenceGraph, bpins);
1843 #if defined(arch_x86)
1844         // if this instruction is a conditional branch instruction, it depends on the previous compare instruction
1845         if(iter->isACondBranchInstruction()) {
1846           handleCondBranch(node, iter, dataDependenceGraph);
1847         } // end checking whether this is conditional instruction
1848 #endif
1849         // initialize read/write arrays
1850         for (j = 0; j < num_regs; j++) {
1851           writeArr[j] = readArr[j] = -1;
1852         }
1853         iter->readWriteRegisters(readArr,writeArr);
1854 #if defined(logging)
1855         // ins.print();
1856     fprintf(logFile,"Read Registers ");
1857     int rg;
1858     for(rg=0; rg<num_regs; rg++)
1859       fprintf(logFile,"%d ", readArr[rg]);
1860     fprintf(logFile,"Write Registers ");
1861     for(rg=0; rg<num_regs; rg++)
1862       fprintf(logFile,"%d ", writeArr[rg]);
1863     if(memAcc != BPatch_memoryAccess::none) {
1864       const BPatch_addrSpec_NP* spec = memAcc->getStartAddr(0);
1865       fprintf(logFile,"Mem: %d %d %d %d",spec->getReg(0),spec->getReg(1),spec->getScale(),spec->getImm());
1866     }
1867     fprintf(logFile,"\n");
1868 #endif
1869
1870 #if defined(interprocedural)
1871
1872 #if defined(arch_x86)
1873         if(iter->isACallInstruction()) {
1874           int k = 0;
1875           for(; k<num_regs && writeArr[k] != -1; k++);
1876           if(k<num_regs)
1877             writeArr[k] = EAX;
1878           // TODO: if k>= reg_num
1879           // TODO: if void func!
1880         }
1881
1882         // handle memory operations
1883         if(bpins->isALoad() && memAcc != BPatch_memoryAccess::none) {
1884           // Iterate list for the memory locations that are read at this line
1885           for(j=0; j<BPatch_instruction::nmaxacc_NP; j++) {
1886             const BPatch_addrSpec_NP* addrSpec = memAcc->getStartAddr(j);
1887             if((addrSpec->getReg(0) == EBP || addrSpec->getReg(1) == EBP) && addrSpec->getImm() >=0 ) {
1888               bool found = false;
1889               unsigned k;
1890               for(k=0; k<copy_mems->size(); k++) {
1891                 // if this location is already written, this is not a parameter
1892                 if(addrSpec->getReg(0) == (*(copy_mems))[k]->reg0 && addrSpec->getReg(1) == (*(copy_mems))[k]->reg1 &&
1893                    addrSpec->getScale() == (*(copy_mems))[k]->scale && addrSpec->getImm() == (*(copy_mems))[k]->immediate ) {
1894                   found = true;
1895                 }
1896               }
1897               if(! found) {
1898                 memUpdate* cell = (memUpdate*)malloc(sizeof(memUpdate));
1899                 cell->reg0 = addrSpec->getReg(0);
1900                 cell->reg1 = addrSpec->getReg(1);
1901                 cell->scale = addrSpec->getScale();
1902                 cell->immediate = addrSpec->getImm();
1903                 cell->node = node;
1904                 // add this to the list...
1905                 parameters->push_back(cell);
1906               }
1907             }
1908           }
1909         }
1910 #endif
1911
1912         for(j=0; j<num_regs && readArr[j] != -1; j++) {
1913 #if defined(sparc_sun_solaris2_4)
1914           //  if(readArr[j] < 16 && readArr[j] >= 8)
1915           if(readArr[j] >= 24 && readArr[j] < 30) {
1916
1917               // if not overwritten by this function before
1918               if(! isWrittenBefore(readArr[j], copy_regs)) {
1919                 ParameterType* param = (ParameterType*)malloc(sizeof(ParameterType));
1920                 param->reg = readArr[j];
1921                 param->node = node;
1922                 parameters->push_back(param);
1923               }
1924           }
1925 #endif
1926           if(isReturnedValue(readArr[j])) { //readArr[j] >= 8 && readArr[j] < 14) {
1927 #if defined(arch_x86)
1928             bool found = false;
1929             int k;
1930             for(k=0; k< copy_regs->size(); k++) {
1931               regUpdate* r = (*copy_regs)[k];
1932               if(r->reg == EAX && r->node->getBPInstruction()->insn()->isCall())
1933                 found = true;
1934             }
1935             if(! found)
1936               continue;
1937 #endif
1938             //        if(! isWrittenBefore(readArr[j], copy_regs)) {
1939             ReturnParameterType* rt = (ReturnParameterType*)malloc(sizeof(ReturnParameterType));
1940             rt->reg = readArr[j];
1941             rt->node = node;
1942             returned->push_back(rt);
1943             //        }
1944           }
1945         }
1946
1947         bool retInst = iter->isAReturnInstruction();
1948         bool callInst = iter->isACallInstruction();
1949         if(retInst || callInst){
1950           unsigned count;
1951           for(count=0; count<copy_calls->size(); count++) {
1952             // for the return value of the previous call instruction
1953             annotation* ann = (annotation*)malloc(sizeof(annotation));
1954             ann->v.returnVals = returned;
1955             ann->address = (*copy_calls)[count]->getBPInstruction()->getAddress();
1956             setAnnotation(createAnnotationType("returned"), new Annotation(ann));
1957             returned = new BPatch_Vector<ReturnParameterType*>();
1958           }
1959           if(callInst) {
1960             unsigned mynum;
1961 #if defined(sparc_sun_solaris2_4)
1962             //      fprintf(stderr,"marking regs among %d regs that are written:",copy_regs->size());
1963             for(mynum=0; mynum < copy_regs->size(); mynum++) {
1964               int r = (*copy_regs)[mynum]->reg - WIN_SIZE*(MAX_SETS - reg_offset);
1965               // fprintf(stderr,"%d-%d ",r,(*copy_regs)[mynum]->reg);
1966               if(r >= 8 && r < 14) {
1967                 ParameterType* pt = (ParameterType*)malloc(sizeof(ParameterType));
1968                 pt->reg = r;
1969                 pt->node = (*copy_regs)[mynum]->node;
1970                 actualParams->push_back(pt);
1971               }
1972             }
1973 #else
1974             for(mynum=0; mynum < copy_mems->size(); mynum++) {
1975               memUpdate* m = (*copy_mems)[mynum];
1976               // fprintf(stderr,"%d-%d ",r,(*copy_regs)[mynum]->reg);
1977               if(m->immediate >= 0 && (m->reg0 == ESP || m->reg1 == ESP)) {
1978                 /*
1979                   ParameterType* pt = (ParameterType*)malloc(sizeof(ParameterType));
1980                 pt->reg = r;
1981                 pt->node = (*copy_regs)[mynum]->node;
1982                 */
1983                 actualParams->push_back(m);
1984               }
1985             }
1986 #endif
1987             annotation* an = (annotation*)malloc(sizeof(annotation));
1988             
1989             void* addr = bpins->getAddress();
1990             an->address = addr;
1991
1992             // TODO
1993             // production->push_back(addr);
1994             
1995             an->v.parameters = actualParams;
1996             setAnnotation(createAnnotationType("actualParams"), new Annotation(an));
1997
1998             actualParams = new BPatch_Vector<ParameterType*>();
1999
2000             copy_calls->clear();
2001             copy_calls->push_back(node);
2002           }
2003           else if(retInst) {
2004             BPatch_Vector<ReturnParameterType*>* returnVals = new BPatch_Vector<ReturnParameterType*>();
2005             unsigned mynum;
2006             //fprintf(stderr,"Return: marking regs among %d regs that are written:",copy_regs->size());
2007             for(mynum=0; mynum < copy_regs->size(); mynum++) {
2008 #if defined(sparc_sun_solaris2_4)
2009               int r = (*copy_regs)[mynum]->reg - WIN_SIZE*(MAX_SETS - reg_offset);
2010 #elif defined(arch_x86)
2011               int r = (*copy_regs)[mynum]->reg;
2012 #endif        //fprintf(stderr,"%d-%d ",r,(*copy_regs)[mynum]->reg);
2013               if(isReturnValue(r)) {
2014                 ReturnParameterType* rt = (ReturnParameterType*)malloc(sizeof(ReturnParameterType));
2015                 rt->reg = r;
2016                 rt->node = (*copy_regs)[mynum]->node;
2017                 returnVals->push_back(rt);
2018               }
2019             }
2020             //fprintf(stderr," Marked %d\n",returnVals->size());
2021             setAnnotation(createAnnotationType("returnVals"), new Annotation(returnVals));
2022           }
2023         }
2024 #endif
2025 #if defined(arch_x86)
2026 #else
2027         iter->adjustRegNumbers(readArr,writeArr,reg_offset);
2028         if(iter->isASaveInstruction())
2029           reg_offset++;
2030         else if(iter->isARestoreInstruction())
2031           reg_offset--;
2032 #endif
2033
2034         // printf("Read\t");
2035         // Iterate list for the registers that are read at this line
2036         for(j=0; j<num_regs && readArr[j] != -1; j++) { // are we sure that the registers are gonna fill the start of array
2037           // printf("Reg %d\t",readArr[j]);
2038           register_check(readArr[j],copy_regs,node);
2039         }
2040         // printf("\n\n");
2041         
2042         // handle memory operations
2043         if(memAcc != BPatch_memoryAccess::none) {
2044           // Iterate list for the memory locations that are read at this line
2045           for(j=0; j<BPatch_instruction::nmaxacc_NP; j++) {
2046             const BPatch_addrSpec_NP* addrSpec = memAcc->getStartAddr(j);
2047 #if defined(arch_x86)
2048             handleMemoryAccess(node, bpins, copy_regs, copy_mems, addrSpec);
2049 #else
2050             handleMemoryAccess(node, bpins, copy_regs, copy_mems, addrSpec, iter, reg_offset);
2051 #endif
2052           }
2053         }
2054         delete memAcc;
2055         //      printf("Write\t");
2056         // Reading the registers that are written at this instruction
2057         for(j=0; j<num_regs && writeArr[j] != -1; j++) { // are we sure that the registers are gonna fill the start of array
2058           // printf("Reg %d\t",writeArr[j]);
2059           handleWrittenRegister(node, writeArr[j], copy_regs);
2060         }
2061         //      printf("\n\n");
2062         // Finally, update prevIter...
2063         prevIter = iter;
2064
2065
2066       } // end of loop that scans instructions in this block
2067
2068       delete iter;
2069       addBlocksToWorkload(blocks, blck, visitedBlocks, copy_regs, copy_mems
2070 #if defined(interprocedural)
2071                           , copy_calls
2072 #endif
2073                           );
2074     }
2075   }
2076
2077   free(writeArr);
2078   free(readArr);
2079   delete visitedBlocks;
2080   //  delete blocksPtr;
2081
2082 #ifdef print_graphs
2083   printf("\nAll\n");
2084   outputGraph(dataDependenceGraph);
2085 #endif
2086
2087 #if defined(logging)
2088   fclose(logFile);
2089 #endif
2090   
2091   setAnnotation(getAnnotationType("DataDependenceGraph"), new Annotation(dataDependenceGraph));  
2092 }
2093 #else
2094 BPatch_dependenceGraphNode* BPatch_function::getSliceInt(BPatch_instruction*)
2095 {
2096    return NULL;
2097 }
2098
2099 BPatch_dependenceGraphNode* BPatch_function::getProgramDependenceGraphInt(BPatch_instruction*)
2100 {
2101    return NULL;
2102 }
2103
2104 BPatch_dependenceGraphNode* BPatch_function::getControlDependenceGraphInt(BPatch_instruction*)
2105 {
2106    return NULL;
2107 }
2108
2109 BPatch_dependenceGraphNode* BPatch_function::getDataDependenceGraphInt(BPatch_instruction *)
2110 {
2111    return NULL;
2112 }
2113
2114 #endif