1(* 	$Id: Aliasing.Mod,v 1.1 2004/06/02 08:55:43 mva Exp $	 *)
2MODULE OOC:X86:Aliasing;
3(*  Calculates aliasing between instructions.
4    Copyright (C) 2002-2004  Michael van Acken
5
6    This file is part of OOC.
7
8    OOC is free software; you can redistribute it and/or modify it
9    under the terms of the GNU General Public License as published by
10    the Free Software Foundation; either version 2 of the License, or
11    (at your option) any later version.
12
13    OOC is distributed in the hope that it will be useful, but WITHOUT
14    ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15    or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
16    License for more details.
17
18    You should have received a copy of the GNU General Public License
19    along with OOC. If not, write to the Free Software Foundation, 59
20    Temple Place - Suite 330, Boston, MA 02111-1307, USA.
21*)
22
23IMPORT
24  Sym := OOC:SymbolTable, TR := OOC:SymbolTable:TypeRules, S := OOC:X86:SSA;
25
26(**
27
28   If instructions work on memory areas, then the areas from which they read
29   data, or to which they write data, may intersect.  If this happens, then the
30   instructions may no longer be independent of each other.  This module
31   provides functions to determine if and how a given variable access aliases
32   with that of another instruction.
33
34   Aliasing statements are a function of the memory areas touched by
35   instructions.  If the instructions work on distinct memory locations, then
36   they do not alias.  On the other hand, if they access even a single common
37   byte, or if there is a chance that this may happen, then they do alias.
38
39   Read and write access to memory is distinguished.  For example, if two
40   reading instructions alias, they can still be scheduled in either order.
41   For two aliasing write instructions, order is significant and must not be
42   changed.
43
44   When comparing the set of memory locations accessed by two instructions that
45   read or write variables, different situations can arise:
46
47   @table @asis
48   @item Empty Intersection
49   In this case, both instructions are independent of each other, because they
50   access distinct subsets of the program's state.
51
52   @item Equal Sets
53   The instructions work on the same set of data.  This allows various
54   improvements, for example eliminating the second read instruction because it
55   delivers the same result as the first.
56
57   @item Non-empty Intersection
58   If the sets of memory locations are not equal, but still share common
59   locations, then the instructions are not independent.  Interpretation of
60   such a situation depends on the context.
61
62   @item Indefinite Intersection
63   Most of the time, static program analysis cannot determine the intersection
64   set during compile time.  For one and the same instruction, the aliasing
65   status may differ with each evaluation during run-time.  In this case, no
66   program transformation can be applied that depends on knowledge about its
67   aliasing status.
68   @end table
69
70   The aliasing relationship between two instructions is commutative for empty
71   intersections and for equal sets of memory locations, but not for indefinite
72   aliasing or non-empty intersections.  *)
73
74TYPE
75  Id* = SHORTINT;
76  (**One of @oconst{noAliasing}, @oconst{completelyCovered},
77     @oconst{partiallyCovered}, or @oconst{mayAlias}.  *)
78
79CONST
80  noAliasing* = 0;
81  (**The two designators access different memory areas.  *)
82  completelyCovered* = 1;
83  (**The designator accesses a memory area that is completely covered by the
84     other designator.  For example, if the designator is a read, and the other
85     one a write, then the result of the read operation is completely defined
86     by the written data.  *)
87  partiallyCovered* = 2;
88  (**The designator accesses a memory area that is partially covered by the
89     other one.  For example, if the designator is a read, and the other one a
90     write, then the result of the read operation is only partially defined by
91     the written data, and partially by the old data in memory.  *)
92  mayAlias* = 3;
93  (**The designators may access the same memory area.  Any of the the variants
94     @oconst{noAliasing}, @oconst{completelyCovered}, or
95     @oconst{partiallyCovered} may be true during run-time.  *)
96
97
98
99PROCEDURE DesignatorAlias* (instr, reference: S.Designator): Id;
100(**Determines the aliasing status of the designator @oparam{instr} with
101   respect to the designator @oparam{reference}.  *)
102  VAR
103    typeInstr, typeRef: Sym.Type;
104
105  PROCEDURE IsVariable (sel: S.Selector): BOOLEAN;
106  (* TRUE iff `sel' refers to a variable that is not a variable parameter *)
107    BEGIN
108      RETURN (sel IS S.Var) & ~sel(S.Var).decl.isVarParam;
109    END IsVariable;
110
111  PROCEDURE IsVarParam (sel: S.Selector): BOOLEAN;
112  (* TRUE iff `sel' refers to a VAR parameter *)
113    BEGIN
114      RETURN (sel IS S.Var) & sel(S.Var).decl.isVarParam;
115    END IsVarParam;
116
117  PROCEDURE IsHeapObject (sel: S.Selector): BOOLEAN;
118  (* TRUE iff `sel' refers to a heap object.  *)
119    BEGIN
120      RETURN (sel IS S.HeapObj)
121    END IsHeapObject;
122
123  PROCEDURE CompatiblePointers (a, b: Sym.Type): BOOLEAN;
124    BEGIN
125      IF TR.SameType(a, b) THEN
126        RETURN TRUE;
127      ELSE
128        a := a.Bound(); b := b.Bound();
129        IF TR.IsPointer(a) & TR.IsPointer(b) THEN
130          RETURN TR.IsExtensionOf (a, b) OR TR.IsExtensionOf (b, a);
131        ELSE
132          RETURN FALSE;
133        END;
134      END;
135    END CompatiblePointers;
136
137  PROCEDURE CheckSelectors (instr: S.Designator; indexInstr: LONGINT;
138                            reference: S.Designator; indexReference: LONGINT;
139                            prefixClass: Id): Id;
140  (* pre: the classification of the prefix of the designators `selInstr' and
141     `selReference' is `prefixClass'.  *)
142
143    PROCEDURE PartiallyCovered (id: Id): Id;
144      BEGIN
145        IF (id = mayAlias) THEN
146          RETURN mayAlias
147        ELSE
148          ASSERT (id = completelyCovered);
149          RETURN partiallyCovered
150        END;
151      END PartiallyCovered;
152
153    BEGIN
154      ASSERT((prefixClass = completelyCovered) OR
155             (prefixClass = mayAlias));
156      IF (indexInstr = LEN(instr^)) THEN
157        (* no further selectors for our designator *)
158        IF (indexReference = LEN(reference^)) THEN
159          (* reference designator also ends here *)
160          RETURN prefixClass;
161        ELSE
162          (* reference designator has further selectors, which means it
163             covers less ground than our designator *)
164          RETURN PartiallyCovered(prefixClass);
165        END;
166
167      ELSIF (indexReference = LEN(reference^)) THEN
168        (* the reference designator ends before our designator, which means
169           our designator works on something that is completely included in
170           the other designator *)
171        RETURN prefixClass;
172
173      ELSE  (* everything else has to be an array index *)
174        IF instr[indexInstr].SameSelector(reference[indexReference]) THEN
175          (* same index *)
176          RETURN CheckSelectors(instr, indexInstr+1,
177                                reference, indexReference+1,
178                                prefixClass);
179        ELSE
180          (* possibly different indices *)
181          RETURN CheckSelectors(instr, indexInstr+1,
182                                reference, indexReference+1,
183                                mayAlias);
184        END;
185      END;
186    END CheckSelectors;
187
188  PROCEDURE NotHigherLevel (varParam, variable: Sym.Declaration): BOOLEAN;
189  (* Returns TRUE if `varParam' is declared in the same procedure as
190     `variable', or in a procedure that encloses that of `variable'.  *)
191    VAR
192      pVarParam, pVariable: Sym.Item;
193    BEGIN
194      pVariable := variable.Procedure();
195      IF (pVariable = NIL) THEN
196        (* variable is declared globally; this means it is declared by
197           definition on a higher level than any parameter *)
198        RETURN FALSE;
199      ELSE
200        pVarParam := varParam.Procedure();
201        REPEAT
202          pVarParam := pVarParam.parent;
203        UNTIL (pVarParam = NIL) OR (pVarParam = pVariable);
204        RETURN (pVarParam = NIL);
205      END;
206    END NotHigherLevel;
207
208  BEGIN
209    IF IsVariable(instr[0]) & IsVariable(reference[0]) THEN
210      (* both designators begin with a variable name (this excludes variable
211         parameters, but includes value parameters); this is probably one
212         of the most common cases, and a very simple one *)
213      IF instr[0].SameSelector(reference[0]) THEN
214        (* both designators begin with the same variable: inspect selectors *)
215        RETURN CheckSelectors (instr, 1, reference, 1, completelyCovered);
216      ELSE
217        (* the designators begin with different variable names, and neither of
218           the variables is a variable parameter: the designators cannot
219           possibly access the same memory *)
220        RETURN noAliasing;
221      END;
222
223    ELSIF IsHeapObject(instr[0]) & IsHeapObject(reference[0]) THEN
224      (* both designators refer to an object on the heap *)
225      IF CompatiblePointers(instr[0](S.HeapObj).type,
226                            reference[0](S.HeapObj).type) THEN
227        IF instr[0].SameSelector(reference[0]) THEN
228          (* both designators begin with the same pointer: inspect selectors *)
229          RETURN CheckSelectors(instr, 1, reference, 1, completelyCovered);
230        ELSE
231          (* both designators may or may not begin with the same pointer:
232             inspect selectors *)
233          RETURN CheckSelectors(instr, 1, reference, 1, mayAlias);
234        END;
235      ELSE
236        (* the designators begin with different variable names, and neither of
237           the variables is a variable parameter: the designators cannot
238           possibly access the same memory *)
239        RETURN noAliasing;
240      END;
241
242    ELSIF IsVarParam(instr[0]) THEN
243      IF IsVarParam(reference[0]) &
244         instr[0].SameSelector(reference[0]) THEN
245        (* both designators begin with one and the same variable parameter:
246           inspect selectors *)
247        RETURN CheckSelectors(instr, 1, reference, 1, completelyCovered);
248      ELSIF IsVariable(reference[0]) &
249            NotHigherLevel(instr[0](S.Var).decl,
250                           reference[0](S.Var).decl) THEN
251        (* the variable parameter is declared on the same, or on a lower level
252           than the variable: there is no way that it may refer to the
253           variable *)
254        RETURN noAliasing;
255      ELSE
256        (* for all other cases: inspect the types of the designators and
257           try to find out if the variable parameter can point anywhere into
258           the other variable; because of the strict type rules of Oberon-2,
259           a static type analysis can rule out many potential aliases *)
260        typeInstr := instr[0].Type();
261        typeRef := reference[0].Type();
262
263        IF TR.IsComponentOf(typeInstr, typeRef, TRUE) OR
264           (IsVarParam(reference[0]) &
265            TR.IsComponentOf(typeRef, typeInstr, TRUE)) THEN
266          RETURN mayAlias;
267        ELSE
268          RETURN noAliasing;
269        END;
270      END;
271
272    ELSIF IsVarParam(reference[0]) THEN
273      (* if one of the inspected designators is a variable parameter, then the
274         result is other `noAliasing' or `mayAlias', because the other classes
275         make no sense in the context of a var param that may point anywhere;
276         this means that this function is symmetric in the presence of variable
277         parameters, and we can save half the work by normalizing the arguments
278         so that `instr' is the variable parameter *)
279      RETURN DesignatorAlias(reference, instr);
280
281    ELSIF IsHeapObject(instr[0]) THEN
282      (* ~IsHeapObject (reference) & ~IsVarParam (reference); in other words,
283         reference must be a variable of the procedure or module *)
284      RETURN noAliasing;
285
286    ELSIF IsHeapObject(reference[0]) THEN
287      (* ~IsHeapObject (instr) & ~IsVarParam (instr); in other words,
288         instr must be a variable of the procedure or module *)
289      RETURN noAliasing;
290    END;
291
292    (* default: assume the worst *)
293    RETURN mayAlias;
294  END DesignatorAlias;
295
296END OOC:X86:Aliasing.
297