595:
585:
564:
709:<actually this algorithm is wrong, it can't handle circles, e.g , 4 is precedors of 5, and 5 point to 6, 6 point to 7 and 8, 7 point back to 5, 8 also point back to 5, then the algorithm will never put 4 in the dominators of 5, because 7,8 can appear before 5 in the path, so the intersection can't add 4 into it, but for 7,8 Dom(7), Dom(8) all depend on Dom(6) which depends on Dom(5), which never has 4 in it, so Dom(7),Dom(8) will never have 4 in it, well, you got the idea: -->
320:
243:
222:
191:
814:
Usage of the term "predecessor" among the control flow/data flow analysis related pages of
Knowledge is inconsistent. It would be nice if we always said "immediate predecessor" when we mean immediate predecessors only. I feel like only saying "predecessor" alone is slightly confusing because some may
766:
Def 1 requires the existence (and reachability) of an exit node (compare to start node in dominators). Thus, if there is an infinite loop, nothing post-dominates anything else. Def 2 (which is used on wikipedia) does not require an exit node, and is defined for infinite loops. This has real
755:
Def 1: A node n post-dominates a node m iff every path from m to the distinguished exit node passes through n. For example, Andrew Appel uses this definition in "Modern
Compiler Implementation." Also, the llvm-compiler infrastructure uses this definition in their implementation of ADCE
341:
757:
758:
http://74.125.93.132/search?q=cache:sFD2zsFBl-4J:https://llvm.org/svn/llvm-project/llvm/tags/RELEASE_11/lib/Transforms/Scalar/ADCE.cpp+%22post-dominance%22+infinite+loop&cd=2&hl=en&ct=clnk&gl=us&client=firefox-a
153:
793:
Be careful: definition 1 doesn't strictly require reachability! If the exit node is not reachable from m, then every node post-dominates m (this is a vacuous truth since the set of all paths to the exit node is
673:
The definition of immediate dominator is tautological, it uses concept of immediate dominance without explaining what it is. If I understood correctly, immediate dominator would be defined as something like:
365:
651:
836:
According to the documented definition, it looks like nodes 3 and 4 ought to be dominators for node 5; yet the dominator matrix in the figure doesn't list 5 as a dominated node. Why?
692:
I think your definition is correct, but I added a definition in terms of strict dominators, because this seems a little easier to understand. The original "definition" was quite silly.
505:
147:
422:
360:
884:
293:
283:
762:
Def 2: A node n post-dominates a node m iff every path from m includes n. For example, Muchnick uses this definition in "Advanced
Compiler Design and Implementation"
44:
727:
I suggest moving this article to a different title, because it's not a concept studied graph theory, although it is a property of nodes in data flow graphs. Perhaps
889:
879:
259:
851:
Node 3 isn't a dominator for 5 because there is a path to 5 not going through 3, viz. 1-2-4-5. Similar for node 4 (1-2-3-5). There is no notion of a node
899:
641:
467:
79:
752:
I've heard two competing definitions of post-dominance which are not equivalent. Could anyone comment on which is more proper or more widely accepted?
894:
713:
because it appears to be someone's confused opinion. It would be true if Dom(n) was initialized to {}, but it is initialized to the set of all nodes.
441:
617:
306:
250:
227:
771:
530:
85:
795:
413:
837:
818:
168:
608:
569:
394:
135:
486:
99:
30:
104:
20:
74:
451:
332:
202:
129:
461:
375:
65:
860:
496:
258:
related articles on
Knowledge. If you would like to participate, please visit the project page, where you can join
125:
728:
775:
523:
24:
190:
175:
799:
841:
822:
109:
732:
856:
432:
208:
845:
594:
781:
141:
681:
node n, if it is its dominator, and there exists no dominator of n that isn't also dominator of d"
161:
55:
817:
C, where A and B are predecessors of C, but we really only want to mean B is a predecessor of C).
616:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
767:
implications when one is trying to compute control dependences using post-dominator information.
600:
70:
584:
563:
351:
51:
403:
255:
477:
319:
342:
Requested articles/Applied arts and sciences/Computer science, computing, and
Internet
873:
736:
693:
685:
864:
826:
803:
785:
739:
717:
613:
590:
384:
242:
221:
714:
460:
Find pictures for the biographies of computer scientists (see
184:
15:
855:
dominating a node (like {3,4} dominating 5) defined here. -
160:
612:, a collaborative effort to improve the coverage of
254:, a collaborative effort to improve the coverage of
815:
think this means "all predecessors". (e.g. A -: -->
366:Computer science articles needing expert attention
33:for general discussion of the article's subject.
506:WikiProject Computer science/Unreferenced BLPs
174:
8:
423:Computer science articles without infoboxes
361:Computer science articles needing attention
188:
558:
327:Here are some tasks awaiting attention:
301:
216:
885:Mid-importance Computer science articles
560:
218:
268:Knowledge:WikiProject Computer science
890:WikiProject Computer science articles
880:Start-Class Computer science articles
832:Nodes 3 and 4 aren't dominators of 5?
271:Template:WikiProject Computer science
7:
606:This article is within the scope of
248:This article is within the scope of
207:It is of interest to the following
23:for discussing improvements to the
442:Timeline of computing 2020–present
14:
900:Low-priority mathematics articles
810:Clear up what "predecessor" means
626:Knowledge:WikiProject Mathematics
468:Computing articles needing images
895:Start-Class mathematics articles
831:
629:Template:WikiProject Mathematics
593:
583:
562:
318:
241:
220:
189:
45:Click here to start a new topic.
646:This article has been rated as
288:This article has been rated as
1:
804:12:48, 20 December 2012 (UTC)
740:22:25, 16 February 2009 (UTC)
620:and see a list of open tasks.
522:Tag all relevant articles in
262:and see a list of open tasks.
42:Put new text under old text.
827:00:08, 16 October 2010 (UTC)
786:17:23, 5 November 2009 (UTC)
729:Dominator (computer science)
718:15:47, 24 October 2007 (UTC)
531:WikiProject Computer science
307:WikiProject Computer science
251:WikiProject Computer science
462:List of computer scientists
50:New to Knowledge? Welcome!
916:
865:16:16, 14 March 2015 (UTC)
846:09:08, 14 March 2015 (UTC)
294:project's importance scale
688:11:39, 22 Apr 2005 (UTC)
645:
578:
524:Category:Computer science
300:
287:
274:Computer science articles
236:
215:
80:Be welcoming to newcomers
696:16:55, 22 Apr 2005 (UTC)
652:project's priority scale
526:and sub-categories with
25:Dominator (graph theory)
609:WikiProject Mathematics
711:
487:Computer science stubs
197:This article is rated
75:avoid personal attacks
733:Dominator (compilers)
707:
679:immediately dominates
100:Neutral point of view
632:mathematics articles
305:Things you can help
105:No original research
601:Mathematics portal
203:content assessment
86:dispute resolution
47:
684:Is that correct?
666:
665:
662:
661:
658:
657:
557:
556:
553:
552:
549:
548:
545:
544:
183:
182:
66:Assume good faith
43:
907:
857:Jochen Burghardt
789:
634:
633:
630:
627:
624:
603:
598:
597:
587:
580:
579:
574:
566:
559:
535:
529:
404:Computer science
333:Article requests
322:
315:
314:
302:
276:
275:
272:
269:
266:
265:Computer science
256:Computer science
245:
238:
237:
232:
228:Computer science
224:
217:
200:
194:
193:
185:
179:
178:
164:
95:Article policies
16:
915:
914:
910:
909:
908:
906:
905:
904:
870:
869:
834:
812:
779:
772:128.112.139.195
747:
725:
705:Removing this:
703:
671:
631:
628:
625:
622:
621:
599:
592:
572:
541:
538:
533:
527:
515:Project-related
510:
491:
472:
446:
427:
408:
389:
370:
346:
273:
270:
267:
264:
263:
230:
201:on Knowledge's
198:
121:
116:
115:
114:
91:
61:
12:
11:
5:
913:
911:
903:
902:
897:
892:
887:
882:
872:
871:
868:
867:
833:
830:
811:
808:
807:
806:
784:comment added
765:
746:
745:Post-dominance
743:
724:
723:Suggested move
721:
702:
699:
698:
697:
670:
667:
664:
663:
660:
659:
656:
655:
644:
638:
637:
635:
618:the discussion
605:
604:
588:
576:
575:
567:
555:
554:
551:
550:
547:
546:
543:
542:
540:
539:
537:
536:
519:
511:
509:
508:
502:
492:
490:
489:
483:
473:
471:
470:
465:
457:
447:
445:
444:
438:
428:
426:
425:
419:
409:
407:
406:
400:
390:
388:
387:
381:
371:
369:
368:
363:
357:
347:
345:
344:
338:
326:
324:
323:
311:
310:
298:
297:
290:Mid-importance
286:
280:
279:
277:
260:the discussion
246:
234:
233:
231:Mid‑importance
225:
213:
212:
206:
195:
181:
180:
118:
117:
113:
112:
107:
102:
93:
92:
90:
89:
82:
77:
68:
62:
60:
59:
48:
39:
38:
35:
34:
28:
13:
10:
9:
6:
4:
3:
2:
912:
901:
898:
896:
893:
891:
888:
886:
883:
881:
878:
877:
875:
866:
862:
858:
854:
850:
849:
848:
847:
843:
839:
829:
828:
824:
820:
809:
805:
801:
797:
796:141.58.62.195
792:
791:
790:
787:
783:
777:
773:
768:
763:
760:
759:
753:
750:
744:
742:
741:
738:
734:
730:
722:
720:
719:
716:
710:
706:
700:
695:
691:
690:
689:
687:
682:
680:
675:
668:
653:
649:
643:
640:
639:
636:
619:
615:
611:
610:
602:
596:
591:
589:
586:
582:
581:
577:
571:
568:
565:
561:
532:
525:
521:
520:
518:
516:
512:
507:
504:
503:
501:
499:
498:
493:
488:
485:
484:
482:
480:
479:
474:
469:
466:
463:
459:
458:
456:
454:
453:
448:
443:
440:
439:
437:
435:
434:
429:
424:
421:
420:
418:
416:
415:
410:
405:
402:
401:
399:
397:
396:
391:
386:
383:
382:
380:
378:
377:
372:
367:
364:
362:
359:
358:
356:
354:
353:
348:
343:
340:
339:
337:
335:
334:
329:
328:
325:
321:
317:
316:
313:
312:
308:
304:
303:
299:
295:
291:
285:
282:
281:
278:
261:
257:
253:
252:
247:
244:
240:
239:
235:
229:
226:
223:
219:
214:
210:
204:
196:
192:
187:
186:
177:
173:
170:
167:
163:
159:
155:
152:
149:
146:
143:
140:
137:
134:
131:
127:
124:
123:Find sources:
120:
119:
111:
110:Verifiability
108:
106:
103:
101:
98:
97:
96:
87:
83:
81:
78:
76:
72:
69:
67:
64:
63:
57:
53:
52:Learn to edit
49:
46:
41:
40:
37:
36:
32:
26:
22:
18:
17:
852:
838:173.11.86.22
835:
819:128.62.88.18
813:
769:
764:
761:
754:
751:
748:
726:
712:
708:
704:
683:
678:
676:
672:
648:Low-priority
647:
607:
573:Low‑priority
514:
513:
497:Unreferenced
495:
494:
476:
475:
450:
449:
431:
430:
412:
411:
393:
392:
374:
373:
350:
349:
331:
330:
289:
249:
209:WikiProjects
171:
165:
157:
150:
144:
138:
132:
122:
94:
19:This is the
780:—Preceding
623:Mathematics
614:mathematics
570:Mathematics
199:Start-class
148:free images
31:not a forum
874:Categories
385:Computing
88:if needed
71:Be polite
21:talk page
816:B -: -->
794:empty)--
770:Thanks,
737:Dcoetzee
686:Mathrick
677:"Node d
669:Untitled
433:Maintain
376:Copyedit
56:get help
29:This is
27:article.
782:undated
650:on the
414:Infobox
352:Cleanup
292:on the
154:WP refs
142:scholar
395:Expand
205:scale.
126:Google
701:Wrong
478:Stubs
452:Photo
309:with:
169:JSTOR
130:books
84:Seek
861:talk
842:talk
823:talk
800:talk
776:talk
749:Hi,
694:Deco
162:FENS
136:news
73:and
853:set
778:)
731:or
715:Aij
642:Low
284:Mid
176:TWL
876::
863:)
844:)
825:)
802:)
735:.
534:}}
528:{{
156:)
54:;
859:(
840:(
821:(
798:(
788:.
774:(
654:.
517::
500::
481::
464:)
455::
436::
417::
398::
379::
355::
336::
296:.
211::
172:·
166:·
158:·
151:·
145:·
139:·
133:·
128:(
58:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
