ROSE 0.11.145.147
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
33template <class I, class S>
37 const typename AstSharedMemoryParallelizableTopDownBottomUpProcessing<I, S>::TraversalPtrList &t)
40 visitedNodes(0), runningParallelTraversal(false),
41 synchronizationWindowSize(syncInfo.synchronizationWindowSize)
42{
43}
44
45template <class I, class S>
46void
48{
49 runningParallelTraversal = val;
50}
51
52template <class I, class S>
53typename 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
68template <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.
87template <class I, class S>
88struct 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.
107template <class I, class S>
108void *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
125template <class I, class S>
126typename 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
195template <class I, class S>
197 : numberOfThreads(2), synchronizationWindowSize(100000)
198{
199}
200
201template <class I, class S>
203AstSharedMemoryParallelTopDownBottomUpProcessing(const AstSharedMemoryParallelTopDownBottomUpProcessing<I,S>::TraversalPtrList &traversals)
204 : AstCombinedTopDownBottomUpProcessing<I, S>(traversals), numberOfThreads(2), synchronizationWindowSize(100000)
205{
206}
207
208template <class I, class S>
209void
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
220template <class I, class S>
221void
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
234template <class I>
238 const typename AstSharedMemoryParallelizableTopDownProcessing<I>::TraversalPtrList &t)
241 visitedNodes(0), runningParallelTraversal(false),
242 synchronizationWindowSize(syncInfo.synchronizationWindowSize)
243{
244}
245
246template <class I>
247void
249{
250 runningParallelTraversal = val;
251}
252
253template <class I>
254typename 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
269template <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.
288template <class I>
289struct 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.
308template <class I>
309void *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
329template <class I>
330void
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
390template <class I>
392 : numberOfThreads(2), synchronizationWindowSize(100000)
393{
394}
395
396template <class I>
398AstSharedMemoryParallelTopDownProcessing(const AstSharedMemoryParallelTopDownProcessing<I>::TraversalPtrList &traversals)
399 : AstCombinedTopDownProcessing<I>(traversals), numberOfThreads(2), synchronizationWindowSize(100000)
400{
401}
402
403template <class I>
404void
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
415template <class I>
416void
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
429template <class S>
433 const typename AstSharedMemoryParallelizableBottomUpProcessing<S>::TraversalPtrList &t)
436 visitedNodes(0), runningParallelTraversal(false),
437 synchronizationWindowSize(syncInfo.synchronizationWindowSize)
438{
439}
440
441template <class S>
442void
444{
445 runningParallelTraversal = val;
446}
447
448template <class S>
449typename 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
464template <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.
483template <class S>
484struct 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.
501template <class S>
502void *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
517template <class S>
518typename 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
577template <class S>
579 : numberOfThreads(2), synchronizationWindowSize(100000)
580{
581}
582
583template <class S>
585AstSharedMemoryParallelBottomUpProcessing(const AstSharedMemoryParallelBottomUpProcessing<S>::TraversalPtrList &traversals)
586 : AstCombinedBottomUpProcessing<S>(traversals), numberOfThreads(2), synchronizationWindowSize(100000)
587{
588}
589
590template <class S>
591void
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
602template <class S>
603void
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
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
virtual InheritedAttributeTypeList * evaluateInheritedAttribute(SgNode *astNode, InheritedAttributeTypeList *inheritedValues)
pure virtual function which must be implemented to compute the inherited attribute at a node
SynthesizedAttributeType traverse(SgNode *node, InheritedAttributeType inheritedValue)
evaluates attributes on the entire AST
void traverse(SgNode *node, InheritedAttributeType inheritedValue)
evaluates attributes on the entire AST
This class represents the base class for all IR nodes within Sage III.