Dominance FrontiersThe other part o

Dominance Frontiers
The other part of dominance that plays an important part in the ssa construction is the calculation of
dominance frontiers for each node in the cfg. Cytron et al. define the dominance frontier of a node, b, as:
. . . the set of all cfg nodes, y, such that b dominates a predecessor of y but does not strictly
dominate y [13].
Dominance frontiers have applications to algorithms other than ssa, as well. For example, finding postdominance
frontiers is an efficient method of computing control dependence, a critical analysis for automatic
parallelization [6].
Cytron et al. propose finding the dominance frontier set for each node in a two step manner. They begin
by walking over the dominator tree in a bottom-up traversal. At each node, b, they add to b’s dominancefrontier
set any cfg successors not dominated by b. They then traverse the dominance-frontier sets of b’s
dominator-tree children – each member of these frontiers that is not dominated by b is copied into b’s
dominance frontier.
We approach the problem from the opposite direction, based on three observations. First, nodes in a
dominance frontier represent join points in the graph, nodes into which control flows from multiple predecessors.
Second, the predecessors of any join point, j, must have j in their respective dominance-frontier sets,
unless the predecessor dominates j. This is a direct result of the definition of dominance frontiers, above.
Finally, the dominators of j’s predecessors must themselves have j in their dominance-frontier sets unless
they also dominate j.
8
for all nodes, b
if the number of predecessors of b ≥ 2
for all predecessors, p, of b
runner ← p
while runner 6= doms[b]
add b to runner’s dominance frontier set
runner = doms[runner]
Figure 5: The Dominance-Frontier Algorithm

ผลลัพธ์ (ไทย) 1:

ขอบเขตการปกครองส่วนอื่น ๆ ของการครอบงำที่เล่นเป็นส่วนสำคัญในการก่อสร้างของ ssa มีการคำนวณขอบเขตปกครองในแต่ละโหนดใน cfg Cytron et al. กำหนดชายแดนปกครองของโหน บี เป็น:...ชุด cfg ทุกโหน y ให้บีกุมอำนาจรุ่นก่อนของ y แต่ไม่เคร่งครัดครอง y [13]ขอบเขตการปกครองมีโปรแกรมอัลกอริทึมอื่น ๆ ssa เช่น การค้นหาเช่น postdominanceขอบเขตเป็นวิธีมีประสิทธิภาพของคอมพิวเตอร์ควบคุมพึ่งพา วิเคราะห์อัตโนมัติสำคัญparallelization [6]Cytron et al. เสนอหาปกครองชายแดนตั้งสำหรับแต่ละโหนดในลักษณะที่เป็นขั้นตอนที่สอง ผู้เริ่มต้นเดินผ่านต้น dominator ในข้ามสายล่าง ในแต่ละโหน บี เพิ่มการ b's dominancefrontierตั้งผู้สืบทอด cfg ใด ๆ ไม่ครอบงำ โดย b พวกเขาได้ข้ามชุดชายแดนปกครองของ b's แล้วเด็ก dominator-ทรีสมาชิกแต่ละคนขอบเขตเหล่านี้ที่ไม่ถูกครอบงำ ด้วย b จะถูกคัดลอกลงใน b'sปกครองชายแดนเราเข้าหาปัญหาจากทิศทางตรงกันข้าม ตามสังเกตสาม โหนแรก ในการปกครองชายแดนแสดงถึงรวมคะแนนในกราฟ โหนเป็นขั้นตอนที่ควบคุมจากรุ่นก่อนหลายรุ่นก่อนของเข้าร่วมจุด สอง เจ ต้องมีเจตนครอบงำชายแดนแต่ละชุดนอกจากรุ่นก่อนกุมอำนาจเจ นี้เป็นผลโดยตรงของการกำหนดขอบเขตการปกครอง ข้างต้นสุดท้าย dominators ของ j's รุ่นก่อนตัวเองต้องเจในชุดชายแดนปกครองของตนเว้นแต่นอกจากนี้พวกเขายังครองเจ8สำหรับโหนดทั้งหมด bถ้าหมายเลขของรุ่นก่อนของ b ≥ 2สำหรับบรรดาลูกหลานทั้งหมด p, bวิ่ง← pขณะวิ่ง 6 = doms [b]เพิ่มบีชุดชายแดนปกครองของนักวิ่งวิ่ง = doms [วิ่ง]รูปที่ 5: การปกครองชายแดนอัลกอริทึม

ผลลัพธ์ (ไทย) 2:

Dominance พรมแดน
ส่วนอื่น ๆ ของการปกครองที่มีบทบาทสำคัญในการก่อสร้างในภาษาคือการคำนวณของ
พรมแดนการปกครองสำหรับแต่ละโหนดใน cfg Cytron และคณะ กำหนดชายแดนปกครองของโหนด b,
เช่น: . . ชุดของโหนด cfg, y เช่นว่าข dominates บรรพบุรุษของ y แต่ไม่เคร่งครัด
ครองและได้ [13].
พรมแดนปกครองมีการใช้งานขั้นตอนวิธีอื่นนอกเหนือจากภาษาไทยเป็นอย่างดี ยกตัวอย่างเช่นการหา postdominance
พรมแดนเป็นวิธีที่มีประสิทธิภาพของการพึ่งพาอาศัยการควบคุมคอมพิวเตอร์ที่สำคัญสำหรับการวิเคราะห์อัตโนมัติ
ขนาน [6].
Cytron และคณะ เสนอหาชายแดนครอบงำชุดสำหรับแต่ละโหนดในลักษณะขั้นตอนที่สอง พวกเขาเริ่มต้น
ด้วยการเดินมากกว่าต้นไม้ Dominator ในสำรวจเส้นทางจากล่างขึ้นบน ในแต่ละโหนด b, พวกเขาเพิ่มขของ dominancefrontier
ตั้งใด ๆ สืบทอด cfg ไม่ครอบงำโดย b จากนั้นพวกเขาสำรวจชุดการปกครองชายแดนของขของ
เด็ก Dominator ต้นไม้ - สมาชิกแต่ละคนของพรมแดนเหล่านี้ที่ไม่ได้ถูกครอบงำโดย b ถูกคัดลอกลงขของ
ชายแดนครอบงำ.
เราเข้าถึงปัญหาจากทิศทางที่ตรงข้าม, ขึ้นอยู่กับสามสังเกต ครั้งแรกในโหนด
ชายแดนครอบงำเป็นตัวแทนเข้าร่วมจุดในกราฟโหนดเป็นที่ควบคุมกระแสจากรุ่นก่อนหลาย.
สองรุ่นก่อนของจุดร่วมใด ๆ ที่เจเจจะต้องมีการปกครองในชุดชายแดนของตน
เว้นแต่บรรพบุรุษ dominates J . นี้เป็นผลโดยตรงจากความหมายของพรมแดนครอบงำเหนือ.
สุดท้าย dominators ของรุ่นก่อนของ j ตัวเองต้องมีเจในชุดการปกครองชายแดนของพวกเขาเว้นแต่
พวกเขายังครองญ.
8
สำหรับทุกโหนดข
ถ้าจำนวนของรุ่นก่อนของข ≥ 2
สำหรับทุกรุ่นก่อนหน้าของข
P วิ่ง←
ขณะที่รองชนะเลิศอันดับ 6 Doms = [b]
เพิ่ม b เพื่อชายแดนครอบงำของนักวิ่งชุด
วิ่ง Doms = [วิ่ง]
รูปที่ 5: การครอบงำ-ชายแดนอัลกอริทึม

ผลลัพธ์ (ไทย) 3:

การปกครองพรมแดน
อีกส่วนหนึ่งของการปกครองที่เล่นเป็นส่วนสำคัญในการก่อสร้าง SSA คือการคำนวณ
การปกครองแต่ละโหนดใน . cfg . cytron et al . นิยามการปกครองชายแดนของโหนด B :
. . . . . . . ชุดของโหนดทั้งหมด cfg , Y , B อยู่ที่บรรพบุรุษของ Y
Y แต่ไม่เคร่งครัดครอง [ 13 ] .
การปกครองพรมแดนมีโปรแกรมขั้นตอนวิธีอื่นนอกจาก SSA ได้เช่นกัน ตัวอย่างเช่น การค้นหา postdominance
พรมแดนเป็นวิธีที่มีประสิทธิภาพของการควบคุมคอมพิวเตอร์ การวิเคราะห์ parallelization ไปอัตโนมัติสำหรับ
[ 6 ] .
cytron et al . เสนอการค้นหาการปกครองชายแดนชุดสำหรับแต่ละโหนดในลักษณะสองขั้น พวกเขาเริ่มต้นด้วยการเดินผ่านต้นไม้
Dominator ในประโยคหรือ .ในแต่ละโหนด B พวกเขาเพิ่ม B dominancefrontier
ตั้งค่าใด ๆ ค้นหา สืบไม่ถูกครอบงำโดย พวกเขาก็ท่องแดนเด่นชุด B
Dominator ต้นไม้เด็ก–แต่ละสมาชิกของพรมแดนเหล่านี้จะไม่ถูกครอบงำด้วย B จะถูกคัดลอกลงใน B

เราแนวทางการปกครองชายแดน ปัญหาจากทิศทาง ตรงกันข้าม จากสามเดือน แรก ๆใน
พรมแดนการปกครองเป็นตัวแทนเข้าร่วมในจุดโหนดลงในกราฟ ซึ่งควบคุมการไหลจากหลายรุ่นก่อน .
2 , รุ่นก่อน ๆเข้าร่วมจุด J J ในชุดต้องมีพรมแดนการปกครองของตน
นอกจากบรรพบุรุษ dominates J นี้เป็นผลโดยตรงของความหมายของการปกครองพรมแดนเหนือ .
ในที่สุดการปรึกษาของ J J ในชุดก่อนหน้าต้องตัวเองมีพรมแดนการปกครองของพวกเขาเว้นแต่พวกเขายังครอง
J
8
ทุกโหนด B
ถ้าจำนวนของ B ≥ 2
บรรพบุรุษทุกรุ่น P , B
p
วิ่ง←ขณะวิ่ง 6 = ชั่ว [ B ]
เพิ่มข เพื่อนักวิ่งของการปกครองชายแดนชุด
[ ]
= หากนักวิ่งวิ่งรูปที่ 5 : การปกครองชายแดนขั้นตอนวิธี