Loading...
Please wait, while we are loading the content...
Similar Documents
Symbolic Analysis for Parallelizing Compilers
| Content Provider | Semantic Scholar |
|---|---|
| Author | Haghighat, Mohammad R. |
| Copyright Year | 1995 |
| Abstract | operations; in particular, the abstract equalityopcmtion has a key role. Since many compiler optimization problems require the capability of verification or discovery of equality relationship between expressions of programs, it is desirable to make the abstract equality operation as efficient as possible. An efficient way to decide whether two objects are equal is to decide whether their representing data structures are identical However, axioms of the integral domain Z, described above, indicate the existence of equal but not identical arithmetic expressions such as {i + j) * (i — j) and i^ — p. This suggests a canonical system in which equivalent objects have unique representations. In fact, there are two main reasons for having a canonical representation system. First, efficient procedures can be built for carrying out operations on the objects when they are in a canonical form. Second, the zero equivalence problem, that is, the problem of deciding equivalence between two objects, is immediately solved when equivalent objects have identical representations. Richardson [Ric68]has shown that the zero equivalence problem is recursively unsolvable for a sufficiently rich class of transcendental expressions. Theoretical limitations and other unsolvability results concerning transcendental terms in computer algebra may be found in [BL82, Cav70, Mos71]. The zero equivalence problem, however, can be solved in many cases of practical interest. In particular, the case of polynomials does not pose any difficulties. There is a variety of choices for canonical representation of polynomials [DST93, GCL92]. We represent multivariate polynomials in a sparse distributivecdinomcdil form using the lexicographical orderingof program variables. In this form, only non zero elements are represented, with the exception of z^rapolynomial. For example, j * {3k + 2i) will be represented as 2ij + 3jk. Later, we shall discuss the necessary modifications of this form to handle symbolic division operation and also to take care of side effects of operations that cannot be precisely abstracted. In the distributive representation all variables forming a polynomial are given the same importance, unlike the recursive repSYMBOLIC ANALYSIS 11 Commutativity: Vi, j e V, £ [i + ji^ = 5 ij + ii^ = ^ [ii^ + e ms, 5I i* j l5 = £:[j*ils = £:[ils*5[jl5. Associativity: Vi, j , k e V, £:[i + ( j+k) l s = £ l ( i + j) + kl5, 5 f i * (j * k)ls = £ |( i * j) * kls. Distributivity: Vi, j , k e V, 5 [i * (j + k)l5 = 5 | ( i * j) + (i * k)l5. Identities: Vi € V, £: [i + ols = £: Iil3, Inverse: Vi G V, Sli-i}s = SlO}s. Cancellation: Vi, j , k € V, 6 lijs ^ S {Ojs, Figure 3.1 Algebraic properties of integer arithmetic. |
| File Format | PDF HTM / HTML |
| DOI | 10.1007/b102246 |
| Alternate Webpage(s) | http://sarcasm.store/symbolic/analysis/symbolic_analysis_for_parallelizing_compilers.pdf |
| Alternate Webpage(s) | http://cizhuan.store/symbolic/analysis/symbolic_analysis_for_parallelizing_compilers.pdf |
| Alternate Webpage(s) | http://sportex.store/symbolic/analysis/symbolic_analysis_for_parallelizing_compilers.pdf |
| Alternate Webpage(s) | https://doi.org/10.1007/b102246 |
| Journal | Springer US |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
