Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Dependence analysis
Résumé
In compiler theory, dependence analysis produces execution-order constraints between statements/instructions. Broadly speaking, a statement S2 depends on S1 if S1 must be executed before S2. Broadly, there are two classes of dependencies--control dependencies and data dependencies.
Dependence analysis determines whether it is safe to reorder or parallelize statements.
Control dependency is a situation in which a program instruction executes if the previous instruction evaluates in a way that allows its execution.
A statement S2 is control dependent on S1 (written ) if and only if S2s execution is conditionally guarded by S1. S2 is control dependent on S1 if and only if where is the post dominance frontier of statement . The following is an example of such a control dependence:
S1 if x > 2 goto L1
S2 y := 3
S3 L1: z := y + 1
Here, S2 only runs if the predicate in S1 is false.
See data dependencies for more details.
A data dependence arises from two statements which access or modify the same resource.
A statement S2 is flow dependent on S1 (written ) if and only if S1 modifies a resource that S2 reads and S1 precedes S2 in execution. The following is an example of a flow dependence (RAW: Read After Write):
S1 x := 10
S2 y := x + c
A statement S2 is antidependent on S1 (written ) if and only if S2 modifies a resource that S1 reads and S1 precedes S2 in execution. The following is an example of an antidependence (WAR: Write After Read):
S1 x := y + c
S2 y := 10
Here, S2 sets the value of y but S1 reads a prior value of y.
A statement S2 is output dependent on S1 (written ) if and only if S1 and S2 modify the same resource and S1 precedes S2 in execution. The following is an example of an output dependence (WAW: Write After Write):
S1 x := 10
S2 x := 20
Here, S2 and S1 both set the variable x.
A statement S2 is input dependent''' on S1 (written ) if and only if S1 and S2 read the same resource and S1 precedes S2 in execution. The following is an example of an input dependence (RAR: Read-After-Read):
S1 y := x + 3
S2 z := x + 5
Here, S2 and S1'' both access the variable x.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.