Dependence analysis
≈ 1 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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. S2 y := 3 S3 L1: z := y + 1 Here, S2 only runs if the predicate in S1 is false. S1 x := 10 S2 y := x + c S1 x := y + c S2 y := 10 Here, S2 sets the value of y but S1 reads a prior value of y . S1 x := 10 S2 x := 20 Here, S2 and S1 both set the variable x . S1 y := x + 3 S2 z := x + 5 Here, S2 and S1 both access the variable x . This dependence does not prohibit reordering.
See also
Program analysis (computer science) Automatic parallelization Automatic vectorization Loop dependence analysis Frameworks supporting the polyhedral model Hazard (computer architecture) Program slicing Dead code elimination
Text derived from https://en.wikipedia.org/w/index.php?oldid=1355883625 under CC BY-SA 4.0; modifications have been made.