ROSE  0.9.9.109
AstSharedMemoryParallelProcessingImpl.h
1 // Author: Gergo Barany
2 #ifndef ASTSHAREDMEMORYPARALLELPROCESSING_C
3 #define ASTSHAREDMEMORYPARALLELPROCESSING_C
4 
5 #include "rosePublicConfig.h"
6 
7 #ifdef _REENTRANT // Does user want multi-thread support? (e.g., g++ -pthread)
8 # ifdef ROSE_HAVE_PTHREAD_H // POSIX threads are available?
9 # include <pthread.h>
10 # else
11  // This should all be switched to Boost Threads instead, which is more portable
12 # ifdef _MSC_VER
13 # pragma message ("POSIX threads are unavailable on this platform.")
14 # else
15 # warning "POSIX threads are unavailable on this platform."
16 # endif
17 # endif
18 #endif
19 
20 // Perhaps this code should be fixed so it works on a single thread when multi-thread support is disabled by the user.
21 // Until then, I am commenting out this entire file when multi-threading support is not configured. [Robb P. Matzke 2015-03-14]
22 #ifdef _REENTRANT // Does the user want multi-threaded support? (e.g., g++ -pthread)
23 
24 
25 
26 #include "AstSharedMemoryParallelProcessing.h"
27 
28 // Throughout this file, I is the InheritedAttributeType, S is the
29 // SynthesizedAttributeType -- the type names are still horrible
30 
31 // parallel TOP DOWN BOTTOM UP implementation
32 
33 template <class I, class S>
37  const typename AstSharedMemoryParallelizableTopDownBottomUpProcessing<I, S>::TraversalPtrList &t)
40  visitedNodes(0), runningParallelTraversal(false),
41  synchronizationWindowSize(syncInfo.synchronizationWindowSize)
42 {
43 }
44 
45 template <class I, class S>
46 void
48 {
49  runningParallelTraversal = val;
50 }
51 
52 template <class I, class S>
53 typename AstSharedMemoryParallelizableTopDownBottomUpProcessing<I, S>::InheritedAttributeTypeList *
56  typename AstSharedMemoryParallelizableTopDownBottomUpProcessing<I, S>::InheritedAttributeTypeList *inheritedValues)
57 {
58  if (runningParallelTraversal && ++visitedNodes > synchronizationWindowSize)
59  {
60  synchronize();
61  visitedNodes = 0;
62  }
63 
64  // let the superclass handle actual attribute evaluation
65  return Superclass::evaluateInheritedAttribute(astNode, inheritedValues);
66 }
67 
68 template <class I, class S>
71 {
72  // delegate the call to the superclass
73  Superclass::atTraversalEnd();
74 
75  // signal that we are done
76  if (runningParallelTraversal)
77  {
78  signalFinish();
79  // clear the flag so subsequent traversals can be non-parallel
80  runningParallelTraversal = false;
81  }
82 }
83 
84 // This class holds the arguments to a traversal thread: The parallelizable
85 // traversal class that contains a number of traversals, the node to start the
86 // traversal from, and the list of initial inherited values.
87 template <class I, class S>
88 struct AstSharedMemoryParallelTopDownBottomUpThreadArgs
89 {
91  SgNode *basenode;
92  typename AstSharedMemoryParallelizableTopDownBottomUpProcessing<I, S>::InheritedAttributeTypeList *inheritedValues;
93 
94  AstSharedMemoryParallelTopDownBottomUpThreadArgs(
96  SgNode *basenode,
97  typename AstSharedMemoryParallelizableTopDownBottomUpProcessing<I, S>::InheritedAttributeTypeList *inheritedValues)
98  : traversal(traversal), basenode(basenode), inheritedValues(inheritedValues)
99  {
100  }
101 };
102 
103 // This is the function that is executed in each thread. It basically unpacks
104 // its arguments and starts the traversal on them; the traversal's final
105 // result is returned. Synchronization is built into the parallelizable
106 // processing classes.
107 template <class I, class S>
108 void *parallelTopDownBottomUpProcessingThread(void *p)
109 {
110  AstSharedMemoryParallelTopDownBottomUpThreadArgs<I, S> *threadArgs = (AstSharedMemoryParallelTopDownBottomUpThreadArgs<I, S> *) p;
111 
112  AstSharedMemoryParallelizableTopDownBottomUpProcessing<I, S> *traversal = threadArgs->traversal;
113  SgNode *basenode = threadArgs->basenode;
114  typename AstSharedMemoryParallelizableTopDownBottomUpProcessing<I, S>::InheritedAttributeTypeList
115  *inheritedValues = threadArgs->inheritedValues;
116  delete threadArgs;
117 
118  // Set the flag that indicates that this is indeed a parallel traversal;
119  // it is cleared by the traversal class itself when it is done.
120  traversal->set_runningParallelTraversal(true);
121  // Start the traversal.
122  return traversal->traverse(basenode, inheritedValues);
123 }
124 
125 template <class I, class S>
126 typename AstSharedMemoryParallelTopDownBottomUpProcessing<I, S>::SynthesizedAttributeTypeList *
128  SgNode *basenode,
129  typename AstSharedMemoryParallelTopDownBottomUpProcessing<I, S>::InheritedAttributeTypeList *inheritedValues)
130 {
131  // GB (09/27/2007): Is this really required? Inheritance of templated classes is just weird.
132  const typename Superclass::TraversalPtrList &traversals = Superclass::traversals;
133 
134  size_t numberOfTraversals = traversals.size();
135  size_t i;
136 
137  AstSharedMemoryParallelProcessingSynchronizationInfo syncInfo(numberOfThreads, synchronizationWindowSize);
138 
139  // Chop the flat list of traversals apart and distribute them into a few
140  // parallelizable traversals.
141  ParallelizableTraversalPtrList parallelTraversals(numberOfThreads);
142  std::vector<InheritedAttributeTypeList *> parallelInheritedValues(numberOfThreads);
143  size_t begin = 0, end;
144  for (i = 0; i < numberOfThreads; i++)
145  {
146  end = begin + numberOfTraversals / numberOfThreads;
147  if (end > numberOfTraversals)
148  end = numberOfTraversals;
149 
150  parallelTraversals[i]
152  std::vector<TraversalPtr>(traversals.begin() + begin, traversals.begin() + end));
153  parallelInheritedValues[i]
154  = new InheritedAttributeTypeList(
155  inheritedValues->begin() + begin, inheritedValues->begin() + end);
156  begin = end;
157  }
158 
159 #if defined(_REENTRANT) && defined(ROSE_HAVE_PTHREAD_H) // user wants multi-thread support and POSIX threads are available?
160  // Start a thread for each of the parallelizable traversals with its share
161  // of the initial inherited attributes.
162  pthread_t *threads = new pthread_t[numberOfThreads];
163  for (i = 0; i < numberOfThreads; i++)
164  {
165  pthread_create(&threads[i], NULL,
166  parallelTopDownBottomUpProcessingThread<I, S>,
167  new AstSharedMemoryParallelTopDownBottomUpThreadArgs<I, S>(
168  parallelTraversals[i], basenode, parallelInheritedValues[i]));
169  }
170 
171  // Main "event loop" for the "master" thread: Simply wait for the
172  // condition that is signalled when a thread is completely done with its
173  // traversal. The counter tells us when we are finished.
174  pthread_mutex_lock(syncInfo.mutex);
175  while (*syncInfo.finishedThreads < numberOfThreads)
176  pthread_cond_wait(syncInfo.threadFinishedEvent, syncInfo.mutex);
177  pthread_mutex_unlock(syncInfo.mutex);
178 
179  // Grab the results from each traversal.
180  std::vector<SynthesizedAttributeTypeList *> finalResults(numberOfThreads);
181  for (i = 0; i < numberOfThreads; i++)
182  pthread_join(threads[i], (void **) &finalResults[i]);
183  delete[] threads;
184 #endif
185 
186  // Flatten the nested list of traversal results.
187  SynthesizedAttributeTypeList *flatFinalResults = new SynthesizedAttributeTypeList;
188  for (i = 0; i < numberOfThreads; i++)
189  std::copy(finalResults[i]->begin(), finalResults[i]->end(), std::back_inserter(*flatFinalResults));
190 
191  // Done! Return the final results.
192  return flatFinalResults;
193 }
194 
195 template <class I, class S>
197  : numberOfThreads(2), synchronizationWindowSize(100000)
198 {
199 }
200 
201 template <class I, class S>
203 AstSharedMemoryParallelTopDownBottomUpProcessing(const AstSharedMemoryParallelTopDownBottomUpProcessing<I,S>::TraversalPtrList &traversals)
204  : AstCombinedTopDownBottomUpProcessing<I, S>(traversals), numberOfThreads(2), synchronizationWindowSize(100000)
205 {
206 }
207 
208 template <class I, class S>
209 void
211 {
212 #if !USE_ROSE
213 // DQ (11/3/2011): EDG compilains about this (but GNU allowed it, I think that EDG might be correct
214 // since it is a private variable. But since we are only trying to compile ROSE with ROSE (using the
215 // new EDG 4.3 front-end as a tests) we can just skip this case for now.
216  numberOfThreads = threads;
217 #endif
218 }
219 
220 template <class I, class S>
221 void
223 {
224 #if !USE_ROSE
225 // DQ (11/3/2011): EDG compilains about this (but GNU allowed it, I think that EDG might be correct
226 // since it is a private variable. But since we are only trying to compile ROSE with ROSE (using the
227 // new EDG 4.3 front-end as a tests) we can just skip this case for now.
228  synchronizationWindowSize = windowSize;
229 #endif
230 }
231 
232 // parallel TOP DOWN implementation
233 
234 template <class I>
238  const typename AstSharedMemoryParallelizableTopDownProcessing<I>::TraversalPtrList &t)
241  visitedNodes(0), runningParallelTraversal(false),
242  synchronizationWindowSize(syncInfo.synchronizationWindowSize)
243 {
244 }
245 
246 template <class I>
247 void
249 {
250  runningParallelTraversal = val;
251 }
252 
253 template <class I>
254 typename AstSharedMemoryParallelizableTopDownProcessing<I>::InheritedAttributeTypeList *
257  typename AstSharedMemoryParallelizableTopDownProcessing<I>::InheritedAttributeTypeList *inheritedValues)
258 {
259  if (runningParallelTraversal && ++visitedNodes > synchronizationWindowSize)
260  {
261  synchronize();
262  visitedNodes = 0;
263  }
264 
265  // let the superclass handle actual attribute evaluation
266  return Superclass::evaluateInheritedAttribute(astNode, inheritedValues);
267 }
268 
269 template <class I>
272 {
273  // delegate the call to the superclass
274  Superclass::atTraversalEnd();
275 
276  // signal that we are done
277  if (runningParallelTraversal)
278  {
279  signalFinish();
280  // clear the flag so subsequent traversals can be non-parallel
281  runningParallelTraversal = false;
282  }
283 }
284 
285 // This class holds the arguments to a traversal thread: The parallelizable
286 // traversal class that contains a number of traversals, the node to start the
287 // traversal from, and the list of initial inherited values.
288 template <class I>
289 struct AstSharedMemoryParallelTopDownThreadArgs
290 {
292  SgNode *basenode;
293  typename AstSharedMemoryParallelizableTopDownProcessing<I>::InheritedAttributeTypeList *inheritedValues;
294 
295  AstSharedMemoryParallelTopDownThreadArgs(
297  SgNode *basenode,
298  typename AstSharedMemoryParallelizableTopDownProcessing<I>::InheritedAttributeTypeList *inheritedValues)
299  : traversal(traversal), basenode(basenode), inheritedValues(inheritedValues)
300  {
301  }
302 };
303 
304 // This is the function that is executed in each thread. It basically unpacks
305 // its arguments and starts the traversal on them; the traversal's final
306 // result is returned. Synchronization is built into the parallelizable
307 // processing classes.
308 template <class I>
309 void *parallelTopDownProcessingThread(void *p)
310 {
311  AstSharedMemoryParallelTopDownThreadArgs<I> *threadArgs = (AstSharedMemoryParallelTopDownThreadArgs<I> *) p;
312 
313  AstSharedMemoryParallelizableTopDownProcessing<I> *traversal = threadArgs->traversal;
314  SgNode *basenode = threadArgs->basenode;
315  typename AstSharedMemoryParallelizableTopDownProcessing<I>::InheritedAttributeTypeList
316  *inheritedValues = threadArgs->inheritedValues;
317  delete threadArgs;
318 
319  // Set the flag that indicates that this is indeed a parallel traversal;
320  // it is cleared by the traversal class itself when it is done.
321  traversal->set_runningParallelTraversal(true);
322  // Start the traversal.
323  traversal->traverse(basenode, inheritedValues);
324 
325  // Need to return something.
326  return NULL;
327 }
328 
329 template <class I>
330 void
332  SgNode *basenode,
333  typename AstSharedMemoryParallelTopDownProcessing<I>::InheritedAttributeTypeList *inheritedValues)
334 {
335  const typename Superclass::TraversalPtrList &traversals = Superclass::traversals;
336 
337  size_t numberOfTraversals = traversals.size();
338  size_t i;
339 
340  AstSharedMemoryParallelProcessingSynchronizationInfo syncInfo(numberOfThreads, synchronizationWindowSize);
341 
342  // Chop the flat list of traversals apart and distribute them into a few
343  // parallelizable traversals.
344  ParallelizableTraversalPtrList parallelTraversals(numberOfThreads);
345  std::vector<InheritedAttributeTypeList *> parallelInheritedValues(numberOfThreads);
346  size_t begin = 0, end;
347  for (i = 0; i < numberOfThreads; i++)
348  {
349  end = begin + numberOfTraversals / numberOfThreads;
350  if (end > numberOfTraversals)
351  end = numberOfTraversals;
352 
353  parallelTraversals[i]
355  std::vector<TraversalPtr>(traversals.begin() + begin, traversals.begin() + end));
356  parallelInheritedValues[i]
357  = new InheritedAttributeTypeList(
358  inheritedValues->begin() + begin, inheritedValues->begin() + end);
359  begin = end;
360  }
361 
362  // Start a thread for each of the parallelizable traversals with its share
363  // of the initial inherited attributes.
364  pthread_t *threads = new pthread_t[numberOfThreads];
365  for (i = 0; i < numberOfThreads; i++)
366  {
367  pthread_create(&threads[i], NULL,
368  parallelTopDownProcessingThread<I>,
369  new AstSharedMemoryParallelTopDownThreadArgs<I>(
370  parallelTraversals[i], basenode, parallelInheritedValues[i]));
371  }
372 
373  // Main "event loop" for the "master" thread: Simply wait for the
374  // condition that is signalled when a thread is completely done with its
375  // traversal. The counter tells us when we are finished.
376  pthread_mutex_lock(syncInfo.mutex);
377  while (*syncInfo.finishedThreads < numberOfThreads)
378  pthread_cond_wait(syncInfo.threadFinishedEvent, syncInfo.mutex);
379  pthread_mutex_unlock(syncInfo.mutex);
380 
381  // Grab the results from each traversal.
382  std::vector<void *> finalResults(numberOfThreads);
383  for (i = 0; i < numberOfThreads; i++)
384  pthread_join(threads[i], &finalResults[i]);
385  delete[] threads;
386 
387  // Done!
388 }
389 
390 template <class I>
392  : numberOfThreads(2), synchronizationWindowSize(100000)
393 {
394 }
395 
396 template <class I>
398 AstSharedMemoryParallelTopDownProcessing(const AstSharedMemoryParallelTopDownProcessing<I>::TraversalPtrList &traversals)
399  : AstCombinedTopDownProcessing<I>(traversals), numberOfThreads(2), synchronizationWindowSize(100000)
400 {
401 }
402 
403 template <class I>
404 void
406 {
407 #if !USE_ROSE
408 // DQ (11/3/2011): EDG compilains about this (but GNU allowed it, I think that EDG might be correct
409 // since it is a private variable. But since we are only trying to compile ROSE with ROSE (using the
410 // new EDG 4.3 front-end as a tests) we can just skip this case for now.
411  numberOfThreads = threads;
412 #endif
413 }
414 
415 template <class I>
416 void
418 {
419 #if !USE_ROSE
420 // DQ (11/3/2011): EDG compilains about this (but GNU allowed it, I think that EDG might be correct
421 // since it is a private variable. But since we are only trying to compile ROSE with ROSE (using the
422 // new EDG 4.3 front-end as a tests) we can just skip this case for now.
423  synchronizationWindowSize = windowSize;
424 #endif
425 }
426 
427 // parallel BOTTOM UP implementation
428 
429 template <class S>
433  const typename AstSharedMemoryParallelizableBottomUpProcessing<S>::TraversalPtrList &t)
436  visitedNodes(0), runningParallelTraversal(false),
437  synchronizationWindowSize(syncInfo.synchronizationWindowSize)
438 {
439 }
440 
441 template <class S>
442 void
444 {
445  runningParallelTraversal = val;
446 }
447 
448 template <class S>
449 typename AstSharedMemoryParallelizableBottomUpProcessing<S>::SynthesizedAttributeTypeList *
452  typename AstSharedMemoryParallelizableBottomUpProcessing<S>::SynthesizedAttributesList synthesizedAttributes)
453 {
454  if (runningParallelTraversal && ++visitedNodes > synchronizationWindowSize)
455  {
456  synchronize();
457  visitedNodes = 0;
458  }
459 
460  // let the superclass handle actual attribute evaluation
461  return Superclass::evaluateSynthesizedAttribute(astNode, synthesizedAttributes);
462 }
463 
464 template <class S>
467 {
468  // delegate the call to the superclass
469  Superclass::atTraversalEnd();
470 
471  // signal that we are done
472  if (runningParallelTraversal)
473  {
474  signalFinish();
475  // clear the flag so subsequent traversals can be non-parallel
476  runningParallelTraversal = false;
477  }
478 }
479 
480 // This class holds the arguments to a traversal thread: The parallelizable
481 // traversal class that contains a number of traversals, and the node to start the
482 // traversal from.
483 template <class S>
484 struct AstSharedMemoryParallelBottomUpThreadArgs
485 {
487  SgNode *basenode;
488 
489  AstSharedMemoryParallelBottomUpThreadArgs(
491  SgNode *basenode)
492  : traversal(traversal), basenode(basenode)
493  {
494  }
495 };
496 
497 // This is the function that is executed in each thread. It basically unpacks
498 // its arguments and starts the traversal on them; the traversal's final
499 // result is returned. Synchronization is built into the parallelizable
500 // processing classes.
501 template <class S>
502 void *parallelBottomUpProcessingThread(void *p)
503 {
504  AstSharedMemoryParallelBottomUpThreadArgs<S> *threadArgs = (AstSharedMemoryParallelBottomUpThreadArgs<S> *) p;
505 
506  AstSharedMemoryParallelizableBottomUpProcessing<S> *traversal = threadArgs->traversal;
507  SgNode *basenode = threadArgs->basenode;
508  delete threadArgs;
509 
510  // Set the flag that indicates that this is indeed a parallel traversal;
511  // it is cleared by the traversal class itself when it is done.
512  traversal->set_runningParallelTraversal(true);
513  // Start the traversal.
514  return traversal->traverse(basenode);
515 }
516 
517 template <class S>
518 typename AstSharedMemoryParallelBottomUpProcessing<S>::SynthesizedAttributeTypeList *
520 {
521  const typename Superclass::TraversalPtrList &traversals = Superclass::traversals;
522 
523  size_t numberOfTraversals = traversals.size();
524  size_t i;
525 
526  AstSharedMemoryParallelProcessingSynchronizationInfo syncInfo(numberOfThreads, synchronizationWindowSize);
527 
528  // Chop the flat list of traversals apart and distribute them into a few
529  // parallelizable traversals.
530  ParallelizableTraversalPtrList parallelTraversals(numberOfThreads);
531  size_t begin = 0, end;
532  for (i = 0; i < numberOfThreads; i++)
533  {
534  end = begin + numberOfTraversals / numberOfThreads;
535  if (end > numberOfTraversals)
536  end = numberOfTraversals;
537 
538  parallelTraversals[i]
540  std::vector<TraversalPtr>(traversals.begin() + begin, traversals.begin() + end));
541  begin = end;
542  }
543 
544  // Start a thread for each of the parallelizable traversals.
545  pthread_t *threads = new pthread_t[numberOfThreads];
546  for (i = 0; i < numberOfThreads; i++)
547  {
548  pthread_create(&threads[i], NULL,
549  parallelBottomUpProcessingThread<S>,
550  new AstSharedMemoryParallelBottomUpThreadArgs<S>(
551  parallelTraversals[i], basenode));
552  }
553 
554  // Main "event loop" for the "master" thread: Simply wait for the
555  // condition that is signalled when a thread is completely done with its
556  // traversal. The counter tells us when we are finished.
557  pthread_mutex_lock(syncInfo.mutex);
558  while (*syncInfo.finishedThreads < numberOfThreads)
559  pthread_cond_wait(syncInfo.threadFinishedEvent, syncInfo.mutex);
560  pthread_mutex_unlock(syncInfo.mutex);
561 
562  // Grab the results from each traversal.
563  std::vector<SynthesizedAttributeTypeList *> finalResults(numberOfThreads);
564  for (i = 0; i < numberOfThreads; i++)
565  pthread_join(threads[i], (void **) &finalResults[i]);
566  delete[] threads;
567 
568  // Flatten the nested list of traversal results.
569  SynthesizedAttributeTypeList *flatFinalResults = new SynthesizedAttributeTypeList;
570  for (i = 0; i < numberOfThreads; i++)
571  std::copy(finalResults[i]->begin(), finalResults[i]->end(), std::back_inserter(*flatFinalResults));
572 
573  // Done! Return the final results.
574  return flatFinalResults;
575 }
576 
577 template <class S>
579  : numberOfThreads(2), synchronizationWindowSize(100000)
580 {
581 }
582 
583 template <class S>
585 AstSharedMemoryParallelBottomUpProcessing(const AstSharedMemoryParallelBottomUpProcessing<S>::TraversalPtrList &traversals)
586  : AstCombinedBottomUpProcessing<S>(traversals), numberOfThreads(2), synchronizationWindowSize(100000)
587 {
588 }
589 
590 template <class S>
591 void
593 {
594 #if !USE_ROSE
595 // DQ (11/3/2011): EDG compilains about this (but GNU allowed it, I think that EDG might be correct
596 // since it is a private variable. But since we are only trying to compile ROSE with ROSE (using the
597 // new EDG 4.3 front-end as a tests) we can just skip this case for now.
598  numberOfThreads = threads;
599 #endif
600 }
601 
602 template <class S>
603 void
605 {
606 #if !USE_ROSE
607 // DQ (11/3/2011): EDG compilains about this (but GNU allowed it, I think that EDG might be correct
608 // since it is a private variable. But since we are only trying to compile ROSE with ROSE (using the
609 // new EDG 4.3 front-end as a tests) we can just skip this case for now.
610  synchronizationWindowSize = windowSize;
611 #endif
612 }
613 
614 #endif
615 #endif
std::vector< SynthesizedAttributeType > * traverse(SgNode *node)
evaluates attributes on the entire AST
virtual InheritedAttributeTypeList * evaluateInheritedAttribute(SgNode *astNode, InheritedAttributeTypeList *inheritedValues)
pure virtual function which must be implemented to compute the inherited attribute at a node ...
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:8322
virtual InheritedAttributeTypeList * evaluateInheritedAttribute(SgNode *astNode, InheritedAttributeTypeList *inheritedValues)
pure virtual function which must be implemented to compute the inherited attribute at a node ...
std::vector< SynthesizedAttributeType > * traverse(SgNode *node, std::vector< InheritedAttributeType > * inheritedValue)
evaluates attributes on the entire AST
void traverse(SgNode *node, std::vector< InheritedAttributeType > * inheritedValue)
evaluates attributes on the entire AST