ROSE  0.9.6a
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DistributedMemoryAnalysisImplementation.h
Go to the documentation of this file.
1 // Distributed memory traversal implementation.
2 // Author: Gergo Barany
3 // $Id: DistributedMemoryAnalysisTemplateDefs.C,v 1.1 2008/01/08 02:55:52 dquinlan Exp $
4 
5 // DQ (9/28/2007): Comment by Gergo to explain nesting problem:
6 // The current implementation of DistributedMemoryAnalysisPreTraversal has an issue within
7 // AST node types that may be nested within constructs of the same type (basic blocks within
8 // basic blocks, function definitions within function definitions etc.). When entering the
9 // first scope in the top-down traversal, it is recorded at the end of the funcDecls list.
10 // The bottom-up pass (in the destroyInheritedValue function) must check that the node it
11 // is invoked with is actually that last element of funcDecls -- only then can the inFunc
12 // flag be unset and the number of nodes recorded.
13 // (In case this doesn't work, complain to gergo@llnl.gov.)
14 
15 
16 #ifndef DISTRIBUTED_MEMORY_ANALYSIS_IMPLEMENTATION_H
17 #define DISTRIBUTED_MEMORY_ANALYSIS_IMPLEMENTATION_H
18 
19 //#include <mpi.h>
20 #include <math.h>
21 
22 #define DIS_DEBUG_OUTPUT false
23 #define RUN_STD true
24 #define RUN_DECLARATION false
25 #define ALLGATHER_MPI false
26 
27 // --------------------------------------------------------------------------
28 // class DistributedMemoryAnalysisBase -- version by Gergo (based on nodes weight)
29 // --------------------------------------------------------------------------
30 
31 template <class InheritedAttributeType>
32 std::pair<int, int>
33 DistributedMemoryAnalysisBase<InheritedAttributeType>::
34 computeFunctionIndices(
35  SgNode *root,
36  InheritedAttributeType rootInheritedValue,
37  AstTopDownProcessing<InheritedAttributeType> *preTraversal)
38 {
39  // This function load balances the work assigned to processors. Work is currently
40  // assigned to processors on the basis SgFunctionDeclaration (if it is a defining declaration).
41 
42  DistributedMemoryAnalysisPreTraversal<InheritedAttributeType> nodeCounter(preTraversal);
43 #if DIS_DEBUG_OUTPUT
44  std::cout << " >>> >>>>>>>>>>>>> starting traversal of nodeCounter (preTraversal)" << std::endl;
45 #endif
46  nodeCounter.traverse(root, rootInheritedValue);
47 
48  funcDecls = nodeCounter.get_funcDecls();
49  initialInheritedValues = nodeCounter.get_initialInheritedValues();
50  std::vector<size_t> &nodeCounts = nodeCounter.get_nodeCounts();
51  std::vector<size_t> &funcWeights = nodeCounter.get_funcWeights();
52  ROSE_ASSERT(funcDecls.size() == initialInheritedValues.size());
53  ROSE_ASSERT(funcDecls.size() == nodeCounts.size());
54  ROSE_ASSERT(funcDecls.size() == funcWeights.size());
55 
56 #if DIS_DEBUG_OUTPUT
57  std::cout << " >>> nr of funcs: " << funcDecls.size() << " inheritedValues:" << initialInheritedValues.size()
58  << " nodeCounts: " << nodeCounts.size() << std::endl;
59  if (funcDecls.size()>0)
60  std::cout << " >>> example entry 0: funcs[0] " << funcDecls.back() << " inheritedValues[0]:"
61  << initialInheritedValues.back() << " nodeCounts[0]: " << nodeCounts.back() << std::endl;
62  std::cout << " >>> >>>>>>>>>>>>> done traversal of nodeCounter (preTraversal) \n\n\n" << std::endl;
63 #endif
64 
65  std::vector<size_t>::const_iterator itr;
66  size_t totalNodes = 0;
67  size_t totalWeight = 0;
68  for (itr = nodeCounts.begin(); itr != nodeCounts.end(); ++itr)
69  totalNodes += *itr;
70  for (itr = funcWeights.begin(); itr != funcWeights.end(); ++itr)
71  totalWeight += *itr;
72  myNodeCounts = nodeCounts;
73  myFuncWeights = funcWeights;
74 
75  if (DistributedMemoryAnalysisBase<InheritedAttributeType>::myID() == 0)
76  {
77  nrOfNodes = totalNodes;
78 
79 //#if DIS_DEBUG_OUTPUT
80  std::cout << "ROOT - splitting functions: " << funcDecls.size() << ", total nodes: " << totalNodes
81  << " totalWeight: " << totalWeight << std::endl;
82 //#endif
83  }
84 
85 
86  // load balance!!
87  size_t lo, hi = 0;
88  size_t nodesSoFar = 0, nodesOfPredecessors = 0;
89  size_t my_lo, my_hi;
90  functionsPerProcess.clear();
91  for (int rank = 0; rank < processes; rank++)
92  {
93  const size_t myNodesHigh = (totalNodes / processes + 1) * (rank + 1);
94  // set lower limit
95  lo = hi;
96  nodesOfPredecessors = nodesSoFar;
97  size_t myNodes = nodesOfPredecessors + nodeCounts[hi];
98 #if DIS_DEBUG_OUTPUT
99  std::cout << "SPLITTING - rank : " << rank << " myNodesHigh " << myNodesHigh << " myNodes: " << myNodes
100  << " lo: " << lo << " hi: " << hi << std::endl;
101 #endif
102  // find upper limit
103  for (hi = lo + 1; hi < funcDecls.size(); hi++)
104  {
105 #if DIS_DEBUG_OUTPUT
106  std::cout << " SPLITTING - func-hi : " << hi << " myNodes: " << myNodes << std::endl;
107  std::cout << " SPLITTING - mynodes > mynodesHigh : " << myNodes << " > " << myNodesHigh << std::endl;
108  std::cout << " SPLITTING - mynodesHigh - myNodes < nodeCounts["<<hi<<"]/2 : " << (myNodesHigh-myNodes)
109  << " < " << (nodeCounts[hi]/2) << std::endl;
110 #endif
111  if (myNodes > myNodesHigh)
112  break;
113  else if (myNodesHigh - myNodes < nodeCounts[hi] / 2)
114  break;
115 #if DIS_DEBUG_OUTPUT
116  std::cout << " hi++" << std::endl;
117 #endif
118  myNodes += nodeCounts[hi];
119  }
120  nodesSoFar = myNodes;
121  functionsPerProcess.push_back(hi - lo);
122 
123  // make sure all files have been assigned to some process
124  if (rank == processes - 1)
125  {
126  if (hi != funcDecls.size())
127  {
128  std::cout << "hi: " << hi << ", funcDecls.size(): " << funcDecls.size() << std::endl;
129  std::cout << "It looks like you asked me to analyze too few functions in too many processes."
130  << std::endl << " Please give me fewer processes or a larger program to work on." << std::endl;
131  }
132  ROSE_ASSERT(hi == funcDecls.size());
133  }
134 
135  if (rank == my_rank)
136  {
137  my_lo = lo;
138  my_hi = hi;
139 #if DIS_DEBUG_OUTPUT
140  std::cout << "process " << rank << ": functions [" << lo << "," << hi
141  << "[ for a total of "
142  << myNodes - nodesOfPredecessors
143  << " nodes" << std::endl;
144 #endif
145  }
146  }
147 
148  return std::make_pair(my_lo, my_hi);
149 }
150 
151 //compare function for std sort
152 struct SortDescending : public std::binary_function<std::pair<double, size_t>,std::pair<double, size_t>,bool>
153 {
154  bool operator()(const std::pair<double, size_t>& s1, const std::pair<double, size_t>& s2) const
155  {
156  return (s1.first > s2.first);
157  }
158 };
159 
160 template <class InheritedAttributeType>
161 void
162 DistributedMemoryAnalysisBase<InheritedAttributeType>::
163 sortFunctions(std::vector<SgFunctionDeclaration*>& funcDecls, std::vector<InheritedAttributeType>& inheritedValues,
164  std::vector<size_t>& nodeCounts, std::vector<size_t>& funcWeights)
165 {
166 
167  std::vector<SgFunctionDeclaration*> funcDecls_temp(funcDecls.size());
168  std::vector<InheritedAttributeType> inheritedValues_temp(funcDecls.size());
169  std::vector<size_t> nodeCounts_temp(funcDecls.size());
170  std::vector<size_t> funcWeights_temp(funcDecls.size());
171 
172  // std::cout << "Sorting all functions according to weight..." << std::endl;
173  // sort all the vectors
174  std::vector<std::pair<double, size_t> > weights(funcDecls.size());
175  for (int i=0; i< (int) funcDecls.size(); i++) {
176  double currentWeight = (((double)nodeCounts[i]*funcWeights[i])/(double)funcDecls.size()/100);
177  weights[i].first = currentWeight;
178  weights[i].second = i;
179  }
180  std::sort(weights.begin(), weights.end(), SortDescending());
181  for (int i=0; i< (int) funcDecls.size(); i++) {
182  funcDecls_temp[i]=funcDecls[weights[i].second];
183  inheritedValues_temp[i]=inheritedValues[weights[i].second];
184  nodeCounts_temp[i]=nodeCounts[weights[i].second];
185  funcWeights_temp[i]=funcWeights[weights[i].second];
186  if (my_rank==0)
187  if (DIS_DEBUG_OUTPUT)
188  std::cout << " function : " << funcDecls_temp[i]->get_qualified_name().str()
189  << " weight_mul : " << (weights[i].first) << " nodes: " << nodeCounts_temp[i]
190  << " weight : " << funcWeights_temp[i] << std::endl;
191  }
192  funcDecls.swap(funcDecls_temp);
193  inheritedValues.swap(inheritedValues_temp);
194  nodeCounts.swap(nodeCounts_temp);
195  funcWeights.swap(funcWeights_temp);
196 }
197 
198 
199 
200 // --------------------------------------------------------------------------
201 // class DistributedMemoryAnalysisBase -- version by tps (based on computation weight -- dynamic algorithm)
202 // --------------------------------------------------------------------------
203 template <class InheritedAttributeType>
204 void
205 DistributedMemoryAnalysisBase<InheritedAttributeType>::
206 computeFunctionIndicesPerNode(
207  SgNode *root, std::vector<int>& functionToProcessor,
208  InheritedAttributeType rootInheritedValue,
209  AstTopDownProcessing<InheritedAttributeType> *preTraversal)
210 {
211  // This function load balances the work assigned to processors. Work is currently
212  // assigned to processors on the basis SgFunctionDeclaration (if it is a defining declaration).
213 
214  DistributedMemoryAnalysisPreTraversal<InheritedAttributeType> nodeCounter(preTraversal);
215 #if DIS_DEBUG_OUTPUT
216  std::cout << " >>> >>>>>>>>>>>>> starting traversal of nodeCounter (preTraversal)" << std::endl;
217 #endif
218  nodeCounter.traverse(root, rootInheritedValue);
219 
220  funcDecls = nodeCounter.get_funcDecls();
221  initialInheritedValues = nodeCounter.get_initialInheritedValues();
222  std::vector<size_t> &nodeCounts = nodeCounter.get_nodeCounts();
223  std::vector<size_t> &funcWeights = nodeCounter.get_funcWeights();
224  ROSE_ASSERT(funcDecls.size() == initialInheritedValues.size());
225  ROSE_ASSERT(funcDecls.size() == nodeCounts.size());
226  ROSE_ASSERT(funcDecls.size() == funcWeights.size());
227 
228  sortFunctions(funcDecls, initialInheritedValues, nodeCounts, funcWeights);
229 
230 #if DIS_DEBUG_OUTPUT
231  std::cout << " >>> nr of funcs: " << funcDecls.size() << " inheritedValues:" << initialInheritedValues.size()
232  << " nodeCounts: " << nodeCounts.size() << std::endl;
233  if (funcDecls.size()>0)
234  std::cout << " >>> example entry 0: funcs[0] " << funcDecls.back() << " inheritedValues[0]:"
235  << initialInheritedValues.back() << " nodeCounts[0]: " << nodeCounts.back() << std::endl;
236  std::cout << " >>> >>>>>>>>>>>>> done traversal of nodeCounter (preTraversal) \n\n\n" << std::endl;
237 #endif
238 
239  std::vector<size_t>::const_iterator itr, itr2;
240  size_t totalNodes = 0;
241  double totalWeight = 0;
242  for (itr = nodeCounts.begin(), itr2 = funcWeights.begin(); itr != nodeCounts.end(); ++itr, ++itr2) {
243  totalNodes += *itr;
244  double currentWeight = (((double)(*itr)*(*itr2))/(double)funcDecls.size()/100);
245  totalWeight += currentWeight;
246  }
247  myNodeCounts = nodeCounts;
248  myFuncWeights = funcWeights;
249 
250  if (DistributedMemoryAnalysisBase<InheritedAttributeType>::myID() == 0)
251  {
252  nrOfNodes = totalNodes;
253 
254 //#if DIS_DEBUG_OUTPUT
255  std::cout << "ROOT - splitting functions: " << funcDecls.size() << ", total nodes: " << totalNodes
256  << " totalWeight: " << totalWeight << std::endl;
257 //#endif
258  }
259 
260  // changed this so it can be used for defuse for all processors
261  // int start_rank=1;
262  int start_rank=0;
263  // std::cerr << " *********** processes : " << processes << std::endl;
264  // if only one processor is defined then processor 0 does NOT have to do communication
265  // and can hence perform the analysis
266  if (processes==1)
267  start_rank=0;
268  // std::vector<int> functionToProcessor;
269  double processorWeight[processes];
270  int nrOfFunctions[processes];
271  for (int rank = 0; rank < processes; rank++) {
272  processorWeight[rank] = 0;
273  nrOfFunctions[rank]=0;
274  }
275  for (unsigned int i=0; i< funcDecls.size(); i++) {
276  double currentWeight = (((double)nodeCounts[i]*funcWeights[i])/(double)funcDecls.size()/100);
277  double min =INFINITY;
278  int min_rank=start_rank;
279  // find the minimum weight processor
280  for (int rank = start_rank; rank < processes; rank++) {
281  if (processorWeight[rank]<min) {
282  min = processorWeight[rank];
283  min_rank = rank;
284  }
285  }
286  processorWeight[min_rank]+=currentWeight;
287  functionToProcessor.push_back(min_rank);
288  nrOfFunctions[min_rank]+=1;
289  if (my_rank ==0 ) {
290  if (DIS_DEBUG_OUTPUT)
291  std::cout << " Function per Processor : " << funcDecls[i]->get_name().str() << " weight : " <<
292  currentWeight << "/" << totalWeight << " on proc: " << min_rank << std::endl;
293  }
294  }
295  for (int rank = 0; rank < processes; rank++) {
296  if (my_rank ==0 ) {
297  std::cerr << " Processor : " << rank << " has " << nrOfFunctions[rank] <<
298  " functions. Processor weight: " << processorWeight[rank] << std::endl;
299  }
300  }
301 
302 }
303 
304 
305 
306 // --------------------------------------------------------------------------
307 // class DistributedMemoryTraversal
308 // --------------------------------------------------------------------------
309 
310 
311 template <class InheritedAttributeType, class SynthesizedAttributeType>
312 void
313 DistributedMemoryTraversal<InheritedAttributeType, SynthesizedAttributeType>::
314 performAnalysis(SgNode *root, InheritedAttributeType rootInheritedValue,
315  AstTopDownProcessing<InheritedAttributeType> *preTraversal,
316  AstBottomUpProcessing<SynthesizedAttributeType> *postTraversal)
317 {
318 #if DIS_DEBUG_OUTPUT
319  std::cout << " >>> >>>>>>>>>>>>> start computeFunctionIndeces" << std::endl;
320 #endif
321  /* see what functions to run our analysis on */
322  std::pair<int, int> my_limits = computeFunctionIndices(root, rootInheritedValue, preTraversal);
323 #if DIS_DEBUG_OUTPUT
324  std::cout << " >>> >>>>>>>>>>>>> done computeFunctionIndeces\n\n\n" << std::endl;
325 #endif
326 
327 #if DIS_DEBUG_OUTPUT
328  std::cout << " >>> >>>>>>>>>>>>> start serialize results" << std::endl;
329 #endif
330  /* run the analysis on the defining function declarations found above and store the serialized results */
331  std::vector<std::pair<int, void *> > serializedResults;
332  for (int i = my_limits.first; i < my_limits.second; i++)
333  {
334  SynthesizedAttributeType result =
335  analyzeSubtree(DistributedMemoryAnalysisBase<InheritedAttributeType>::funcDecls[i],
336  DistributedMemoryAnalysisBase<InheritedAttributeType>::initialInheritedValues[i]);
337  serializedResults.push_back(serializeAttribute(result));
338  }
339 
340 #if DIS_DEBUG_OUTPUT
341  std::cout << " >>> >>>>>>>>>>>>> done serialize results\n" << std::endl;
342 #endif
343 
344 
345 
346 #if DIS_DEBUG_OUTPUT
347  // in the following we only handle certain functions!!
348  std::cout << " >>> >>>>>>>>>>>>> start creating buffer" << std::endl;
349 #endif
350  /* compute how much total memory our attributes take up, and concatenate the serialized attributes into a single
351  * buffer */
352  size_t functions = DistributedMemoryAnalysisBase<InheritedAttributeType>::funcDecls.size();
353  int myFunctionsPerProcess = DistributedMemoryAnalysisBase<InheritedAttributeType>::functionsPerProcess[
354  DistributedMemoryAnalysisBase<InheritedAttributeType>::myID()];
355  int *myStateSizes = new int[myFunctionsPerProcess];
356  int myTotalSize = 0;
357  for (int i = 0; i < myFunctionsPerProcess; i++)
358  {
359  myStateSizes[i] = serializedResults[i].first;
360  myTotalSize += myStateSizes[i];
361  }
362  unsigned char *myBuffer = new unsigned char[myTotalSize];
363 #if DIS_DEBUG_OUTPUT
364  // buffer contains inherited values, i.e. the nodeCount per function
365  std::cout << " total buffer size = " << myTotalSize << " FunctionsPerProcess: " << myFunctionsPerProcess << std::endl;
366 #endif
367  int sizeSoFar = 0;
368  for (int i = 0; i < myFunctionsPerProcess; i++)
369  {
370  std::memcpy(myBuffer + sizeSoFar, serializedResults[i].second, serializedResults[i].first);
371  sizeSoFar += serializedResults[i].first;
372  // now that we have made a copy of the serialized attribute, we can free the user-allocated memory
373 #if DIS_DEBUG_OUTPUT
374  std::cout << " buffer ["<<i<<"] = " << ((char*)serializedResults[i].second)
375  << " myStateSizes["<<i<<"] = " << myStateSizes[i] << std::endl;
376 #endif
377 
378  deleteSerializedAttribute(serializedResults[i]);
379  }
380 #if DIS_DEBUG_OUTPUT
381  std::cout << " >>> >>>>>>>>>>>>> end creating buffer\n" << std::endl;
382 #endif
383 
384 
385 
386 #if DIS_DEBUG_OUTPUT
387  std::cout << " >>> >>>>>>>>>>>>> start communication" << std::endl;
388 #endif
389  /* communicate results: first, gather the sizes of the respective states into an array */
390  int *stateSizes = NULL;
391  int *displacements = NULL;
392  if (ALLGATHER_MPI || DistributedMemoryAnalysisBase<InheritedAttributeType>::myID() == 0) {
393  displacements = new int[DistributedMemoryAnalysisBase<InheritedAttributeType>::numberOfProcesses()];
394  displacements[0] = 0;
395  for (int i = 1; i < DistributedMemoryAnalysisBase<InheritedAttributeType>::numberOfProcesses(); i++)
396  {
397  // Displacements are in units of data elements, not bytes
398  displacements[i] = displacements[i-1] + DistributedMemoryAnalysisBase<InheritedAttributeType>::functionsPerProcess[i-1];
399 #if DIS_DEBUG_OUTPUT
400  std::cout << " displacements["<<i<<"] = " << displacements[i] << " == functionsPerProcess[i] " << std::endl;
401 #endif
402  }
403  stateSizes = new int[functions];
404  }
405 
406 #if ALLGATHER_MPI
407  MPI_Allgatherv(myStateSizes, myFunctionsPerProcess, MPI_INT,
408  stateSizes, &DistributedMemoryAnalysisBase<InheritedAttributeType>::functionsPerProcess[0],
409  displacements, MPI_INT, MPI_COMM_WORLD);
410 #else
411  MPI_Gatherv(myStateSizes, myFunctionsPerProcess, MPI_INT,
412  stateSizes, &DistributedMemoryAnalysisBase<InheritedAttributeType>::functionsPerProcess[0],
413  displacements, MPI_INT, 0, MPI_COMM_WORLD);
414 #endif
415 
416 #if DIS_DEBUG_OUTPUT
417  if (ALLGATHER_MPI || DistributedMemoryAnalysisBase<InheritedAttributeType>::myID() == 0) {
418  std::cout << " MPI_Allgatherv: " << functions << std::endl;
419  for (unsigned int k=0; k<functions;k++) {
420  std::cout << " stateSize["<<k<<"] = " << stateSizes[k] << std::endl;
421  }
422  }
423 #endif
424 
425  /* from the state sizes communicated above, compute the total buffer size
426  * for all concatenated states, and the indices where each part starts */
427  int totalSize = 0;
428  int *totalStateSizes = NULL;
429  unsigned char* recvbuf = NULL;
430  if (ALLGATHER_MPI || DistributedMemoryAnalysisBase<InheritedAttributeType>::myID() == 0) {
431  totalStateSizes = new int[DistributedMemoryAnalysisBase<InheritedAttributeType>::numberOfProcesses()];
432  int j = 0;
433  for (int i = 0; i < DistributedMemoryAnalysisBase<InheritedAttributeType>::numberOfProcesses(); i++)
434  {
435  displacements[i] = totalSize;
436  totalStateSizes[i] = 0;
437  int j_lim = j + DistributedMemoryAnalysisBase<InheritedAttributeType>::functionsPerProcess[i];
438  while (j < j_lim)
439  totalStateSizes[i] += stateSizes[j++];
440  totalSize += totalStateSizes[i];
441  }
442  recvbuf = new unsigned char[totalSize];
443  }
444 
445  /* communicate results: gather the actual state information, concatenating
446  * it into recvbuf on each process */
447 #if ALLGATHER_MPI
448  MPI_Allgatherv(myBuffer, myTotalSize, MPI_UNSIGNED_CHAR,
449  recvbuf, totalStateSizes, displacements, MPI_UNSIGNED_CHAR,
450  MPI_COMM_WORLD);
451 #else
452  MPI_Gatherv(myBuffer, myTotalSize, MPI_UNSIGNED_CHAR,
453  recvbuf, totalStateSizes, displacements, MPI_UNSIGNED_CHAR,
454  0, MPI_COMM_WORLD);
455 #endif
456 
457 #if DIS_DEBUG_OUTPUT
458  std::cout << " >>> >>>>>>>>>>>>> end communication\n\n" << std::endl;
459 #endif
460 
461 
462 #if DIS_DEBUG_OUTPUT
463  std::cout << " >>> >>>>>>>>>>>>> start deserialize" << std::endl;
464 #endif
465  if (ALLGATHER_MPI || DistributedMemoryAnalysisBase<InheritedAttributeType>::myID() == 0) {
466  /* unpack the serialized states and store them away for the post traversal to use */
467  functionResults.clear();
468 
469  int j = 0;
470  for (int i = 0; i < DistributedMemoryAnalysisBase<InheritedAttributeType>::numberOfProcesses(); i++)
471  {
472  int j_lim = j + DistributedMemoryAnalysisBase<InheritedAttributeType>::functionsPerProcess[i];
473  int sizeSoFar = 0;
474  while (j < j_lim)
475  {
476  std::pair<int, void *> serializedAttribute
477  = std::make_pair(stateSizes[j], recvbuf + displacements[i] + sizeSoFar);
478  SynthesizedAttributeType attribute = deserializeAttribute(serializedAttribute);
479  functionResults.push_back(attribute);
480  sizeSoFar += stateSizes[j];
481  j++;
482  // std::cout << " getting results " << std::endl;
483  }
484  }
485 
486 #if DIS_DEBUG_OUTPUT
487  std::cout << " >>> >>>>>>>>>>>>> end deserialize\n" << std::endl;
488 #endif
489 
490 #if DIS_DEBUG_OUTPUT
491  std::cout << " >>> >>>>>>>>>>>>> start postTraversal" << std::endl;
492 #endif
493 
494  /* perform the post traversal */
495  DistributedMemoryAnalysisPostTraversal<SynthesizedAttributeType> postT(postTraversal, functionResults);
496  finalResults = postT.traverse(root, false);
497 
498 #if DIS_DEBUG_OUTPUT
499  std::cout << " >>> >>>>>>>>>>>>> end postTraversal\n" << std::endl;
500 #endif
501 
502  /* clean up */
503  delete[] stateSizes;
504  delete[] totalStateSizes;
505  delete[] displacements;
506  delete[] recvbuf;
507  }
508  delete[] myStateSizes;
509  delete[] myBuffer;
510 }
511 
512 
513 
514 
515 
516 // --------------------------------------------------------------------------
517 // class DistributedMemoryAnalysisPreTraversal
518 // --------------------------------------------------------------------------
519 template <class InheritedAttributeType>
520 InheritedAttributeType
521 DistributedMemoryAnalysisPreTraversal<InheritedAttributeType>::
522 evaluateInheritedAttribute(SgNode *node, InheritedAttributeType inheritedValue)
523 {
524  // This is the pre-traversal where the load balancing is computed. To change the
525  // grainularity from defining function declarations we have to edit all references
526  // to SgFunctionDeclaration (just a few places). One way to abstract the details
527  // of how the level of gainulatity can be adjusted would be to have the predicate
528  // below use a functior passed in from the outside.
529 
530  // An issue might be that nested defining function declaration (such as those that
531  // arise in class declarations) might be a problem for this code. This should be
532  // tested. A possible solution would be to ignore defining function declaration in
533  // classes (SgMemberFunctionDeclaration).
534 
535  // See note from Gergo at the top of the file.
536 
537  // The grainularity must match that of the other implementation in the
538  // DistributedMemoryAnalysisPostTraversal.
539 
540  // If we are entering a defining function declaration, start counting
541  // nodes and save the function declaration node and the inherited value to
542  // be passed to it.
543  SgFunctionDeclaration *funcDecl = isSgFunctionDeclaration(node);
544 #if RUN_STD
545  if (funcDecl) {
546  std::string funcname = funcDecl->get_name().str();
547  #if DIS_DEBUG_OUTPUT
548  std::cout << " >>>> found function : " << funcname << std::endl;
549  #endif
550  }
551 #else
552  if (funcDecl) {
553  std::string funcname = funcDecl->get_name().str();
554  if (funcname.find("__")!=std::string::npos) {
555  stdFunc=true;
556  } else {
557  stdFunc=false;
558  #if DIS_DEBUG_OUTPUT
559  std::cout << " >>>> found function : " << funcname << std::endl;
560  #endif
561  }
562  }
563  if (stdFunc)
564  return inheritedValue;
565 #endif
566 
567 #if RUN_DECLARATION
568  if (funcDecl)
569 #else
570  if (funcDecl && funcDecl->get_definingDeclaration() == funcDecl)
571 #endif
572  {
573  inFunc = true;
574  nodeCount = 0;
575  weightNullDeref = 1;
576  weightAssignOp = 1;
577  funcDecls.push_back(funcDecl);
578  initialInheritedValues.push_back(inheritedValue);
579  std::string funcname = funcDecl->get_name().str();
580 #if DIS_DEBUG_OUTPUT
581  std::cout << " >>>> found defining function declaration: " << funcname
582  << " inheritedValue: " << inheritedValue << std::endl;
583 #endif
584  }
585 
586  // If we are not inside any function, evaluate the preTraversal.
587  // Otherwise, the preTraversal is not to be called, we count the node and
588  // return our inheritedValue as a dummy (it is not used anywhere deeper in
589  // this subtree).
590  if (!inFunc)
591  {
592 #if DIS_DEBUG_OUTPUT
593  std::cout << " . outside function : " << node->class_name() << std::endl;
594 #endif
595  if (preTraversal != NULL)
596  return preTraversal->evaluateInheritedAttribute(node, inheritedValue);
597  else
598  return inheritedValue;
599  }
600  else
601  {
602 #if DIS_DEBUG_OUTPUT
603  std::cerr << " inside function: " << node->class_name() << " nodeCount =" << nodeCount
604  << " depth=" << inheritedValue << std::endl;
605 #endif
606  nodeCount++;
607  // calculate the weight of the function
608  // this weight is mostly used for the def-use checker
609  if (isSgNode(node))
610  weightAssignOp++;
611  // for defuse we weight loops heigher
612  if (isSgWhileStmt(node) || isSgForStatement(node)
613  || isSgDoWhileStmt(node)) {
614  weightAssignOp+=(weightAssignOp)/5;
615  }
616  // the following weight should be used if null-deref is checked for
617  /*
618  if (isSgArrowExp(node) || isSgPointerDerefExp(node) ||
619  isSgAssignInitializer(node) || isSgFunctionCallExp(node) ) {
620  weightNullDeref++;
621  } else if (isSgAssignOp(node)) {
622  weightAssignOp++;
623  }
624  */
625  return inheritedValue;
626  }
627 }
628 
629 template <class InheritedAttributeType>
630 void
631 DistributedMemoryAnalysisPreTraversal<InheritedAttributeType>::
632 destroyInheritedValue(SgNode *node, InheritedAttributeType inheritedValue)
633 {
634 #if RUN_STD
635 #else
636  if (stdFunc)
637  return ;
638 #endif
639 
640  // If we are outside all functions, the preTraversal computed an
641  // inheritedValue before, so give it a chance to destroy it.
642  if (!inFunc && preTraversal != NULL)
643  preTraversal->destroyInheritedValue(node, inheritedValue);
644 
645  // If we are leaving a function, save its number of nodes.
646  SgFunctionDeclaration *funcDecl = isSgFunctionDeclaration(node);
647 #if RUN_DECLARATION
648  if (funcDecl)
649 #else
650  if (funcDecl && funcDecl->get_definingDeclaration() == funcDecl)
651 #endif
652  {
653  // A better implementation would address that the funcDecl should be
654  // checked against the funcDecls list. This implementation will
655  // likely fail for the case of nested constructs. Both for inherited
656  // and synthesised attributes are a likely problem.
657 
658  nodeCounts.push_back(nodeCount);
659  // double result = (double)weightAssignOp*(double)1/log((double)weightNullDeref+1);
660  // funcWeights.push_back((int)result);
661  // funcWeights.push_back(weightAssignOp*weightNullDeref);
662  funcWeights.push_back(weightAssignOp);
663  // std::cout << " pushing back func : " << funcDecl->get_name().str() << " weightAssignOp : " << weightAssignOp << " weightNullDeref : " << weightNullDeref <<
664  // " 1/log(weightNullDeref) : " << (1/(log(weightNullDeref))) << " result = " << result << std::endl;
665  inFunc = false;
666 #if DIS_DEBUG_OUTPUT
667  std::cout << " destroying - save nodes " << nodeCount << std::endl;
668 #endif
669  }
670 }
671 
672 
673 
674 
675 
676 // --------------------------------------------------------------------------
677 // class DistributedMemoryAnalysisPostTraversal
678 // --------------------------------------------------------------------------
679 
680 
681 //bool
682 //DistributedMemoryAnalysisNamespace::postTraversalEvaluateInheritedAttribute(SgNode *node, bool inFunction)
683 template <class SynthesizedAttributeType>
684 bool
685 DistributedMemoryAnalysisPostTraversal<SynthesizedAttributeType>::
686 evaluateInheritedAttribute(SgNode *node, bool inFunction)
687 {
688  SgFunctionDeclaration *funcDecl = isSgFunctionDeclaration(node);
689 
690 #if RUN_STD
691 #else
692  std::string funcname="";
693  if (funcDecl) {
694  funcname = funcDecl->get_name().str();
695  if (funcname.find("__")!=std::string::npos)
696  stdFunc=true;
697  else
698  stdFunc=false;
699  }
700  if (stdFunc)
701  return false;
702  #if DIS_DEBUG_OUTPUT
703  if (funcDecl)
704  std::cout << " >>> postTraversal - inheritedAttribute: found function: " << funcname << std::endl;
705  #endif
706 #endif
707  #if DIS_DEBUG_OUTPUT
708  std::cout << " postTraversal - inheritedAttribute on node: " << node->class_name() <<
709  " parentEval (inFunction?): " << inFunction << std::endl;
710  #endif
711 
712  // Determine from the inherited attribute and the AST node whether this node is inside a defining function declaration.
713  if (inFunction)
714  return true;
715 
716  // DQ (9/28/2007):
717  // This is where the load balancing grainularity is defined and it must match that of the
718  // other implementation in the DistributedMemoryAnalysisPreTraversal
719 
720 #if RUN_DECLARATION
721  if (funcDecl)
722 #else
723  if (funcDecl && funcDecl->get_definingDeclaration() == funcDecl)
724 #endif
725  return true;
726 
727  return false;
728 }
729 
730 
731 
732 template <class SynthesizedAttributeType>
733 SynthesizedAttributeType
734 DistributedMemoryAnalysisPostTraversal<SynthesizedAttributeType>::
735 evaluateSynthesizedAttribute(SgNode *node, bool inFunction,
736  DistributedMemoryAnalysisPostTraversal<SynthesizedAttributeType>::SynthesizedAttributesList synAttrs)
737 {
738  // If this node is the root of a defining function declaration, return the associated analysis result that was passed
739  // to our constructor. If this node is within a defining function declaration, we would like to pretend that we are not
740  // even here (since this bottom-up pass is not supposed to traverse functions), so we return some default value. If
741  // this node is outside of defining function declarations, perform normal bottom-up evaluation.
742 
743  SgFunctionDeclaration *funcDecl = isSgFunctionDeclaration(node);
744 #if RUN_STD
745 #else
746  std::string funcname="none";
747  if (funcDecl) {
748  funcname = funcDecl->get_name().str();
749  if (funcname.find("__")!=std::string::npos) {
750  stdFunc=true;
751  } else {
752  stdFunc=false;
753  #if DIS_DEBUG_OUTPUT
754  std::cout << " .. post synthesizedAttribute function: " << funcname << " id-nr:" << functionCounter << std::endl;
755  #endif
756  }
757  }
758  if (stdFunc) {
759  return defaultSynthesizedAttribute(inFunction);
760  }
761 #endif
762 
763 #if DIS_DEBUG_OUTPUT
764  std::cout << " post in (NODE): >> " << node->class_name() << " currentNode (inFunction?) " << inFunction << std::endl;
765 #endif
766 
767 #if RUN_DECLARATION
768  if (funcDecl)
769 #else
770  if (funcDecl && funcDecl->get_definingDeclaration() == funcDecl)
771 #endif
772  {
773  return functionResults[functionCounter++];
774  }
775 
776  if (inFunction)
777  {
778  if (!synAttrs.empty()) {
779  SynthesizedAttributeType attr = synAttrs.front(); // this is a default attribute computed somewhere below
780  return attr;
781  } else {
782  return defaultSynthesizedAttribute(inFunction);
783  }
784  }
785 
786 #if DIS_DEBUG_OUTPUT
787  std::cout << " ... EVALUATE synthesized Attribute " << std::endl;
788 #endif
789  return postTraversal->evaluateSynthesizedAttribute(node, synAttrs);
790 }
791 
792 #endif
793 
794