Beroendeanalys

I kompilatorteori producerar beroendeanalys exekveringsorderbegränsningar mellan satser/instruktioner . I stort sett beror en sats S2 på S1 om S1 måste exekveras före S2 . I stort sett finns det två klasser av beroenden - kontrollberoenden och databeroenden .

Beroendeanalys avgör om det är säkert att ordna om eller parallellisera uttalanden.

Kontrollberoenden

Kontrollberoende är en situation där en programinstruktion körs om den föregående instruktionen utvärderas på ett sätt som tillåter dess exekvering.

En sats S2 är kontrollberoende av S1 (skriven $S1\ \delta ^{c}\ S2$ ) om och endast om S2 :s exekvering är villkorligt skyddad av S1 . S2 är kontrollberoende på S1 om och endast om $S1\in PDF(S2)$ där $PDF(S)$ är postdominansen frontier of statement $S$ . Följande är ett exempel på ett sådant kontrollberoende:

S1 om x > 2 går till L1 S2 y := 3 S3 L1: z := y + 1

Här körs S2 bara om predikatet i S1 är falskt.

Se databeroende för mer information.

Databeroende

Ett databeroende uppstår från två satser som får åtkomst till eller modifierar samma resurs.

Flödesberoende (True).

En sats S2 är flödesberoende på S1 (skriven $S1\ \delta ^{f}\ S2$ ) om och endast om S1 modifierar en resurs som S2 läser och S1 föregår S2 i exekvering. Följande är ett exempel på ett flödesberoende (RAW: Read After Write):

S1 x := 10 S2 y := x + c

Antiberoende

En sats S2 är antiberoende på S1 (skriven $S1\ \delta ^{a}\ S2$ ) om och endast om S2 modifierar en resurs som S1 läser och S1 föregår S2 i exekvering. Följande är ett exempel på ett antiberoende (WAR: Write After Read):

S1 x := y + c S2 y := 10

Här sätter S2 värdet på y men S1 läser ett tidigare värde på y .

Utgångsberoende

En sats S2 matas ut beroende av S1 (skriven $S1\ \delta ^{o}\ S2$ ) om och endast om S1 och S2 modifierar samma resurs och S1 föregår S2 i exekvering. Följande är ett exempel på ett utdataberoende (WAW: Write After Write):

S1 x := 10 S2 x := 20

Här sätter båda S2 och S1 variabeln x .

Ingångsberoende

En sats S2 matas in beroende av S1 (skriven $S1\ \delta ^{i}\ S2$ ) om och endast om S1 och S2 läser samma resurs och S1 föregår S2 i exekvering. Följande är ett exempel på ett indataberoende (RAR: Read-After-Read):

S1 y := x + 3 S2 z := x + 5

Här har både S2 och S1 åtkomst till variabeln x . Detta beroende förbjuder inte omordning.

Loop-beroenden

Problemet med beräkningsberoenden inom loopar, vilket är ett betydande och icke-trivialt problem, tacklas av loopberoendeanalys, som utvidgar det beroenderamverk som ges här.

Se även

• Programanalys (datavetenskap)
• Automatisk parallellisering
• Automatisk vektorisering
• Analys av loopberoende
• Ramar som stödjer den polyedriska modellen
• Hazard (datorarkitektur)
• Program skärning
• Eliminering av död kod

Vidare läsning

•   Cooper, Keith D.; Torczon, Linda. (2005). Konstruera en kompilator . Morgan Kaufmann. ISBN 1-55860-698-X .
•   Kennedy, Ken; Allen, Randy. (2001). Optimera kompilatorer för moderna arkitekturer: en beroendebaserad metod . Morgan Kaufmann. ISBN 1-55860-286-0 .
•   Muchnick, Steven S. (1997). Avancerad kompilatordesign och implementering . Morgan Kaufmann. ISBN 1-55860-320-4 .