2 ** LCLint - annotation-assisted static program checker
3 ** Copyright (C) 1994-2000 University of Virginia,
4 ** Massachusetts Institute of Technology
6 ** This program is free software; you can redistribute it and/or modify it
7 ** under the terms of the GNU General Public License as published by the
8 ** Free Software Foundation; either version 2 of the License, or (at your
9 ** option) any later version.
11 ** This program is distributed in the hope that it will be useful, but
12 ** WITHOUT ANY WARRANTY; without even the implied warranty of
13 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 ** General Public License for more details.
16 ** The GNU General Public License is available from http://www.gnu.org/ or
17 ** the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
18 ** MA 02111-1307, USA.
20 ** For information on lclint: lclint-request@cs.virginia.edu
21 ** To report a bug: lclint-bug@cs.virginia.edu
22 ** For more information: http://lclint.cs.virginia.edu
28 # include "lclintMacros.nf"
31 /*@constant int ATINVALID; @*/
35 aliasTable_canAliasAux (aliasTable p_s, sRef p_sr, int p_lim) /*@*/ ;
37 aliasTable_aliasedByLimit (aliasTable p_s, sRef p_sr, int p_lim) /*@*/ ;
39 aliasTable_aliasedByAux (aliasTable p_s, sRef p_sr, int p_lim) /*@*/ ;
44 return (aliasTable_undefined);
47 static /*@only@*/ /*@notnull@*/ aliasTable
48 aliasTable_newEmpty (void)
50 aliasTable s = (aliasTable) dmalloc (sizeof (*s));
53 s->nspace = aliasTableBASESIZE;
54 s->keys = (sRef *) dmalloc (sizeof (*s->keys) * aliasTableBASESIZE);
55 s->values = (sRefSet *) dmalloc (sizeof (*s->values) * aliasTableBASESIZE);
61 aliasTable_grow (/*@notnull@*/ aliasTable s)
64 o_sRefSet *oldvalues = s->values;
65 sRef *oldkeys = s->keys;
67 s->nspace += aliasTableBASESIZE;
69 s->values = (sRefSet *) dmalloc (sizeof (*s->values)
70 * (s->nelements + s->nspace));
71 s->keys = (sRef *) dmalloc (sizeof (*s->keys) * (s->nelements + aliasTableBASESIZE));
73 if (s->keys == (sRef *) 0 || s->values == (sRefSet *)0)
75 llfatalerror (cstring_makeLiteral ("aliasTable_grow: out of memory!"));
78 for (i = 0; i < s->nelements; i++)
80 s->values[i] = oldvalues[i];
81 s->keys[i] = oldkeys[i];
88 static int aliasTable_lookupRefs (/*@notnull@*/ aliasTable s, sRef sr)
93 for (i = 0; i < aliasTable_size (s); i++)
95 if (sRef_same (sr, s->keys[i]))
105 ** sr aliases al (and anything al aliases!)
109 aliasTable_addMustAlias (/*@returned@*/ aliasTable s,
110 /*@exposed@*/ sRef sr,
116 llassert (NOALIAS (sr, al));
118 if (aliasTable_isUndefined (s))
120 s = aliasTable_newEmpty ();
125 ind = aliasTable_lookupRefs (s, sr);
128 ss = aliasTable_canAlias (s, al);
131 if (ind == ATINVALID)
133 if (s->nspace <= 0) {
138 s->keys[s->nelements] = sr;
139 s->values[s->nelements] = sRefSet_single (al);
145 s->values[ind] = sRefSet_insert (s->values[ind], al);
148 s->values[ind] = sRefSet_unionExcept (s->values[ind], ss, s->keys[ind]);
155 aliasTable_addSet (/*@returned@*/ aliasTable s,
156 /*@exposed@*/ sRef key, /*@only@*/ sRefSet value)
158 if (!sRefSet_isEmpty (value))
160 if (aliasTable_isUndefined (s))
162 s = aliasTable_newEmpty ();
173 s->keys[s->nelements] = key;
174 s->values[s->nelements] = value;
179 sRefSet_free (value);
186 ** When aliases are cleared:
188 ** o remove all entries for sr
189 ** o replace all aliases for things which alias sr with sr's aliases
191 ** Clear aliases for sr; if sr is a direct param reference, clear its aliases too.
194 static void aliasTable_clearAliasesAux (/*@notnull@*/ aliasTable p_s, sRef p_sr)
197 void aliasTable_clearAliases (aliasTable s, sRef sr)
199 if (aliasTable_isUndefined (s))
205 sRef rb = sRef_getRootBase (sr);
208 if (!sRef_isCvar (sr) && sRef_isLocalVar (rb))
210 int ind = aliasTable_lookupRefs (s, rb);
212 if (ind != ATINVALID)
214 sRefSet al = s->values[ind];
217 sRefSet_realElements (al, el)
220 if (sRef_isParam (el))
222 if (sRef_sameName (el, rb))
224 sRef fb = sRef_fixBase (sr, el);
226 aliasTable_clearAliasesAux (s, fb);
229 } end_sRefSet_realElements ;
233 aliasTable_clearAliasesAux (s, sr);
238 void aliasTable_clearAliasesAux (/*@notnull@*/ aliasTable s, sRef sr)
242 for (i = 0; i < s->nelements; i++)
244 sRef key = s->keys[i];
246 if (sRef_includedBy (key, sr))
248 sRefSet_clear (s->values[i]);
252 (void) sRefSet_deleteBase (s->values[i], sr);
258 ** returns set of all sRefs that must alias sr (but are different from sr)
261 static /*@only@*/ sRefSet aliasTable_aliasedByAux (aliasTable s, sRef sr, int lim)
263 static bool hadWarning = FALSE;
264 sRefSet res = sRefSet_undefined;
267 llassert (!sRef_isConj (sr));
270 if (aliasTable_isUndefined (s) || lim >= ALIASSEARCHLIMIT)
272 if (lim >= ALIASSEARCHLIMIT && !hadWarning)
275 (message ("Alias search limit exceeded, checking %q. "
276 "This either means there is a variable with at least "
277 "%d indirections, or there is a bug in LCLint.",
284 return sRefSet_undefined;
290 if (sRef_isPointer (sr))
292 abl = aliasTable_aliasedByLimit (s, sRef_getBase (sr), lim);
293 res = sRefSet_addIndirection (abl);
295 else if (sRef_isAddress (sr))
297 abl = aliasTable_aliasedByLimit (s, sRef_getBase (sr), lim);
298 res = sRefSet_removeIndirection (abl);
300 else if (sRef_isField (sr))
302 abl = aliasTable_aliasedByLimit (s, sRef_getBase (sr), lim);
303 res = sRefSet_accessField (abl, sRef_getField (sr));
305 else if (sRef_isArrayFetch (sr))
307 abl = aliasTable_aliasedByLimit (s, sRef_getBase (sr), lim);
309 if (sRef_isIndexKnown (sr))
311 int idx = sRef_getIndex (sr);
313 res = sRefSet_fetchKnown (abl, idx);
317 res = sRefSet_fetchUnknown (abl);
322 abl = sRefSet_undefined;
328 for (i = 0; i < s->nelements; i++)
330 sRef elem = s->keys[i];
332 if (!sRef_same (sr, elem)) /* was sameName */
335 sRefSet_realElements (s->values[i], current)
338 if (sRef_similar (sr, current))
340 res = sRefSet_insert (res, sRef_fixOuterRef (elem));
341 /*@innerbreak@*/ break;
343 } end_sRefSet_realElements;
350 static /*@only@*/ sRefSet aliasTable_aliasedByLimit (aliasTable s, sRef sr, int lim)
355 if (sRef_isConj (sr))
357 res = sRefSet_unionFree (aliasTable_aliasedByLimit (s, sRef_getConjA (sr), lim),
358 aliasTable_aliasedByLimit (s, sRef_getConjB (sr), lim));
362 res = aliasTable_aliasedByAux (s, sr, lim + 1);
368 /*@only@*/ sRefSet aliasTable_aliasedBy (aliasTable s, sRef sr)
370 if (sRef_isConj (sr))
372 return (sRefSet_unionFree (aliasTable_aliasedBy (s, sRef_getConjA (sr)),
373 aliasTable_aliasedBy (s, sRef_getConjB (sr))));
376 return (aliasTable_aliasedByAux (s, sr, 0));
379 /*@only@*/ sRefSet aliasTable_canAlias (aliasTable s, sRef sr)
384 if (sRef_isConj (sr))
386 res = sRefSet_unionFree (aliasTable_canAlias (s, sRef_getConjA (sr)),
387 aliasTable_canAlias (s, sRef_getConjB (sr)));
391 res = aliasTable_canAliasAux (s, sr, 0);
398 ** need to limit the depth of aliasing searches
401 static /*@only@*/ sRefSet aliasTable_canAliasLimit (aliasTable s, sRef sr, int lim)
405 if (sRef_isConj (sr))
407 sRefSet a = aliasTable_canAliasLimit (s, sRef_getConjA (sr), lim);
408 sRefSet b = aliasTable_canAliasLimit (s, sRef_getConjB (sr), lim);
410 res = sRefSet_unionFree (a, b);
414 res = aliasTable_canAliasAux (s, sr, lim + 1);
420 static /*@only@*/ sRefSet
421 aliasTable_canAliasAux (aliasTable s, sRef sr, int lim)
423 static bool hadWarning = FALSE;
424 llassert (!sRef_isConj (sr));
427 if (aliasTable_isUndefined (s) || lim >= ALIASSEARCHLIMIT)
429 if (lim >= ALIASSEARCHLIMIT && !hadWarning)
432 (message ("Alias search limit exceeded, checking %q. "
433 "This either means there is a variable with at least "
434 "%d indirections, or there is a bug in LCLint.",
441 return sRefSet_undefined;
445 int ind = aliasTable_lookupRefs (s, sr);
447 if (sRef_isPointer (sr) || sRef_isAddress (sr) || sRef_isField (sr)
448 || sRef_isArrayFetch (sr))
450 sRef base = sRef_getBase (sr);
451 sRefSet tmp = aliasTable_canAliasLimit (s, base, lim);
454 if (sRef_isPointer (sr))
456 ret = sRefSet_addIndirection (tmp);
458 else if (sRef_isAddress (sr))
460 ret = sRefSet_removeIndirection (tmp);
462 else if (sRef_isField (sr))
464 ret = sRefSet_accessField (tmp, sRef_getField (sr));
466 else if (sRef_isArrayFetch (sr))
468 if (sRef_isIndexKnown (sr))
470 ret = sRefSet_fetchKnown (tmp, sRef_getIndex (sr));
474 ret = sRefSet_fetchUnknown (tmp);
482 if (ind != ATINVALID)
484 ret = sRefSet_union (ret, s->values[ind]);
491 if (ind == ATINVALID) return sRefSet_undefined;
493 return sRefSet_newCopy (s->values[ind]);
497 aliasTable aliasTable_copy (aliasTable s)
499 if (aliasTable_isEmpty (s))
501 return aliasTable_undefined;
505 aliasTable t = (aliasTable) dmalloc (sizeof (*s));
508 t->nelements = s->nelements;
510 t->keys = (sRef *) dmalloc (sizeof (*s->keys) * s->nelements);
511 t->values = (sRefSet *) dmalloc (sizeof (*s->values) * t->nelements);
513 for (i = 0; i < s->nelements; i++)
515 t->keys[i] = s->keys[i];
516 t->values[i] = sRefSet_newCopy (s->values[i]);
524 aliasTable_levelPrune (aliasTable s, int lexlevel)
528 if (aliasTable_isEmpty (s))
535 int backcount = s->nelements - 1;
537 for (i = 0; i <= backcount; i++)
539 sRef key = s->keys[i];
541 if (sRef_lexLevel (key) > lexlevel)
544 for (j = backcount; j > i; j--)
550 if (sRef_lexLevel (s->keys[j]) <= lexlevel)
552 s->keys[i] = s->keys[j];
553 s->values[i] = s->values[j];
554 sRefSet_levelPrune (s->values[i], lexlevel);
555 /*@innerbreak@*/ break;
563 sRefSet_levelPrune (s->values[i], lexlevel);
572 ** like level union, but know that t2 was executed after t1. So if
573 ** t1 has x -> { a, b } and t2 has x -> { a }, then result has x -> { a }.
575 ** NOTE: t2 is "only".
578 aliasTable aliasTable_levelUnionSeq (/*@returned@*/ aliasTable t1,
579 /*@only@*/ aliasTable t2, int level)
581 if (aliasTable_isUndefined (t2))
586 if (aliasTable_isUndefined (t1))
588 t1 = aliasTable_newEmpty ();
592 aliasTable_levelPrune (t1, level);
595 aliasTable_elements (t2, key, value)
597 if (sRef_lexLevel (key) <= level)
599 int ind = aliasTable_lookupRefs (t1, key);
601 sRefSet_levelPrune (value, level);
603 if (ind == ATINVALID)
605 /* okay, t2 is killed */
606 /*@-exposetrans@*/ /*@-dependenttrans@*/
607 t1 = aliasTable_addSet (t1, key, value);
608 /*@=exposetrans@*/ /*@=dependenttrans@*/
612 sRefSet_free (t1->values[ind]);
614 /*@-dependenttrans@*/ /* okay, t2 is killed */
615 t1->values[ind] = value;
616 /*@=dependenttrans@*/
621 /*@-exposetrans@*/ /*@-dependenttrans@*/
622 sRefSet_free (value);
623 /*@=exposetrans@*/ /*@=dependenttrans@*/
626 } end_aliasTable_elements;
636 aliasTable_levelUnion (/*@returned@*/ aliasTable t1, aliasTable t2, int level)
638 if (aliasTable_isUndefined (t1))
640 if (aliasTable_isUndefined (t2))
646 t1 = aliasTable_newEmpty ();
651 aliasTable_levelPrune (t1, level);
654 aliasTable_elements (t2, key, cvalue)
656 sRefSet value = sRefSet_newCopy (cvalue);
658 if (sRef_lexLevel (key) <= level)
660 sRefSet_levelPrune (value, level);
662 if (sRefSet_size (value) > 0)
664 int ind = aliasTable_lookupRefs (t1, key);
666 if (ind == ATINVALID)
668 t1 = aliasTable_addSet (t1, key, value);
672 t1->values[ind] = sRefSet_union (t1->values[ind], value);
673 sRefSet_free (value);
678 sRefSet_free (value);
683 sRefSet_free (value);
685 } end_aliasTable_elements;
690 aliasTable aliasTable_levelUnionNew (aliasTable t1, aliasTable t2, int level)
692 aliasTable ret = aliasTable_levelUnion (aliasTable_copy (t1), t2, level);
698 aliasTable_unparse (aliasTable s)
700 cstring st = cstring_undefined;
702 if (aliasTable_isUndefined (s)) return (cstring_makeLiteral ("<NULL>"));
704 aliasTable_elements (s, key, value)
706 st = message ("%q\t%q -> %q\n", st, sRef_unparse (key),
707 sRefSet_unparse (value));
708 } end_aliasTable_elements;
718 aliasTable_fixSrefs (aliasTable s)
722 if (aliasTable_isUndefined (s)) return;
724 for (i = 0; i < s->nelements; i++)
726 sRef old = s->keys[i];
728 if (sRef_isLocalVar (old))
730 s->keys[i] = uentry_getSref (sRef_getUentry (old));
733 sRefSet_fixSrefs (s->values[i]);
738 aliasTable_free (/*@only@*/ aliasTable s)
742 if (aliasTable_isUndefined (s)) return;
744 for (i = 0; i < s->nelements; i++)
746 sRefSet_free (s->values[i]);
755 aliasTable_checkGlobs (aliasTable t)
757 aliasTable_elements (t, key, value)
759 sRef root = sRef_getRootBase (key);
761 if (sRef_isAliasCheckedGlobal (root))
763 sRefSet_realElements (value, sr)
765 root = sRef_getRootBase (sr);
767 if (((sRef_isAliasCheckedGlobal (root)
768 && !(sRef_similar (root, key)))
769 || sRef_isAnyParam (root))
770 && !sRef_isExposed (root))
772 if (sRef_isAliasCheckedGlobal (key))
774 if (!(sRef_isShared (key)
775 && sRef_isShared (root)))
780 ("Function returns with %q variable %q aliasing %q %q",
781 cstring_makeLiteral (sRef_isRealGlobal (key)
782 ? "global" : "file static"),
784 cstring_makeLiteral (sRef_isAnyParam (root)
785 ? "parameter" : "global"),
792 } end_sRefSet_realElements;
794 else if (sRef_isAnyParam (key) || sRef_isAnyParam (root))
796 sRefSet_realElements (value, sr)
798 root = sRef_getRootBase (sr);
800 if (sRef_isAliasCheckedGlobal (root)
801 && !sRef_isExposed (root)
802 && !sRef_isDead (key)
803 && !sRef_isShared (root))
807 message ("Function returns with parameter %q aliasing %q %q",
809 cstring_makeLiteral (sRef_isRealGlobal (root)
810 ? "global" : "file static"),
814 } end_sRefSet_realElements;
820 } end_aliasTable_elements;