]> andersk Git - splint.git/blob - src/aliasTable.c
Removed some .out files.
[splint.git] / src / aliasTable.c
1 /*
2 ** LCLint - annotation-assisted static program checker
3 ** Copyright (C) 1994-2000 University of Virginia,
4 **         Massachusetts Institute of Technology
5 **
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.
10 ** 
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.
15 ** 
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.
19 **
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
23 */
24 /*
25 ** aliasTable.c
26 */
27
28 # include "lclintMacros.nf"
29 # include "basic.h"
30
31 /*@constant int ATINVALID; @*/
32 # define ATINVALID -1
33
34 static sRefSet
35   aliasTable_canAliasAux (aliasTable p_s, sRef p_sr, int p_lim) /*@*/ ;
36 static sRefSet
37   aliasTable_aliasedByLimit (aliasTable p_s, sRef p_sr, int p_lim) /*@*/ ;
38 static sRefSet 
39   aliasTable_aliasedByAux (aliasTable p_s, sRef p_sr, int p_lim) /*@*/ ;
40
41 aliasTable
42 aliasTable_new ()
43 {
44   return (aliasTable_undefined);
45 }
46
47 static /*@only@*/ /*@notnull@*/ aliasTable
48 aliasTable_newEmpty (void)
49 {
50   aliasTable s = (aliasTable) dmalloc (sizeof (*s));
51   
52   s->nelements = 0;
53   s->nspace = aliasTableBASESIZE;
54   s->keys     = (sRef *) dmalloc (sizeof (*s->keys) * aliasTableBASESIZE);
55   s->values   = (sRefSet *) dmalloc (sizeof (*s->values) * aliasTableBASESIZE);
56   
57   return (s);
58 }
59
60 static void
61 aliasTable_grow (/*@notnull@*/ aliasTable s)
62 {
63   int i;
64   o_sRefSet *oldvalues = s->values;
65   sRef    *oldkeys = s->keys;
66   
67   s->nspace += aliasTableBASESIZE; 
68
69   s->values = (sRefSet *) dmalloc (sizeof (*s->values)
70                                    * (s->nelements + s->nspace));
71   s->keys = (sRef *) dmalloc (sizeof (*s->keys) * (s->nelements + aliasTableBASESIZE));
72
73   if (s->keys == (sRef *) 0 || s->values == (sRefSet *)0)
74     {
75       llfatalerror (cstring_makeLiteral ("aliasTable_grow: out of memory!"));
76     }
77
78   for (i = 0; i < s->nelements; i++)
79     {
80       s->values[i] = oldvalues[i];
81       s->keys[i] = oldkeys[i];
82     }
83   
84   sfree (oldvalues);
85   sfree (oldkeys);
86 }
87
88 static int aliasTable_lookupRefs (/*@notnull@*/ aliasTable s, sRef sr)
89 {
90   int i;
91
92   
93   for (i = 0; i < aliasTable_size (s); i++)
94     {
95       if (sRef_same (sr, s->keys[i])) 
96         {
97           return i;
98         }
99     }
100
101   return ATINVALID;
102 }
103
104 /*
105 ** sr aliases al (and anything al aliases!)
106 */
107
108 aliasTable
109 aliasTable_addMustAlias (/*@returned@*/ aliasTable s,
110                          /*@exposed@*/ sRef sr,
111                          sRef al)
112 {
113   int ind;
114   sRefSet ss;
115   
116   llassert (NOALIAS (sr, al));
117
118   if (aliasTable_isUndefined (s))
119     {
120       s = aliasTable_newEmpty ();
121       ind = ATINVALID;
122     }
123   else
124     {
125       ind = aliasTable_lookupRefs (s, sr);
126     }
127   
128   ss = aliasTable_canAlias (s, al); 
129   
130   
131   if (ind == ATINVALID)
132     {
133       if (s->nspace <= 0) {
134         aliasTable_grow (s);
135       }
136
137       s->nspace--;
138       s->keys[s->nelements] = sr;
139       s->values[s->nelements] = sRefSet_single (al); 
140       ind = s->nelements;
141       s->nelements++;      
142     }
143   else
144     {
145       s->values[ind] = sRefSet_insert (s->values[ind], al); 
146     }
147   
148   s->values[ind] = sRefSet_unionExcept (s->values[ind], ss, s->keys[ind]); 
149
150   sRefSet_free (ss);
151   return s;
152 }
153
154 static aliasTable 
155   aliasTable_addSet (/*@returned@*/ aliasTable s,
156                      /*@exposed@*/ sRef key, /*@only@*/ sRefSet value)
157 {
158   if (!sRefSet_isEmpty (value))
159     {
160       if (aliasTable_isUndefined (s))
161         {
162           s = aliasTable_newEmpty ();
163         }
164       else
165         {
166           if (s->nspace <= 0)
167             {
168               aliasTable_grow (s);
169             }
170         }
171
172       s->nspace--;
173       s->keys[s->nelements] = key;
174       s->values[s->nelements] = value;
175       s->nelements++;      
176     }
177   else
178     {
179       sRefSet_free (value);
180     }
181
182   return s;
183 }
184
185 /*
186 ** When aliases are cleared:
187 **
188 **    o remove all entries for sr
189 **    o replace all aliases for things which alias sr with sr's aliases
190 **
191 ** Clear aliases for sr; if sr is a direct param reference, clear its aliases too.
192 */
193
194 static void aliasTable_clearAliasesAux (/*@notnull@*/ aliasTable p_s, sRef p_sr)
195    /*@modifies p_s@*/ ;
196
197 void aliasTable_clearAliases (aliasTable s, sRef sr)
198 {
199   if (aliasTable_isUndefined (s))
200     {
201       return;
202     }
203   else
204     {
205       sRef rb = sRef_getRootBase (sr);
206
207             
208       if (!sRef_isCvar (sr) && sRef_isLocalVar (rb))
209         {
210           int ind = aliasTable_lookupRefs (s, rb);
211           
212           if (ind != ATINVALID)
213             {
214               sRefSet al = s->values[ind];
215               
216                       
217               sRefSet_realElements (al, el)
218                 {
219                                   
220                   if (sRef_isParam (el))
221                     {
222                       if (sRef_sameName (el, rb))
223                         {
224                           sRef fb = sRef_fixBase (sr, el); 
225
226                           aliasTable_clearAliasesAux (s, fb); 
227                         }
228                     }
229                 } end_sRefSet_realElements ;
230             }
231         }
232       
233       aliasTable_clearAliasesAux (s, sr); 
234     }  
235 }
236
237 static
238 void aliasTable_clearAliasesAux (/*@notnull@*/ aliasTable s, sRef sr)
239 {
240   int i;
241   
242   for (i = 0; i < s->nelements; i++)
243     {
244       sRef key = s->keys[i];
245       
246       if (sRef_includedBy (key, sr))
247         {
248           sRefSet_clear (s->values[i]);
249         }
250       else
251         {
252           (void) sRefSet_deleteBase (s->values[i], sr);   
253         }
254     }
255 }
256
257 /*
258 ** returns set of all sRefs that must alias sr (but are different from sr)
259 */
260
261 static /*@only@*/ sRefSet aliasTable_aliasedByAux (aliasTable s, sRef sr, int lim)
262 {
263   static bool hadWarning = FALSE;
264   sRefSet res = sRefSet_undefined;
265   int i;
266
267   llassert (!sRef_isConj (sr));
268   
269   
270   if (aliasTable_isUndefined (s) || lim >= ALIASSEARCHLIMIT)
271     {
272       if (lim >= ALIASSEARCHLIMIT && !hadWarning)
273         {
274           llquietbug
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.",
278                       sRef_unparse (sr),
279                       ALIASSEARCHLIMIT));
280           
281           hadWarning = TRUE;
282         }
283
284       return sRefSet_undefined;
285     }
286   else
287     {
288       sRefSet abl;
289
290       if (sRef_isPointer (sr))
291         {
292           abl = aliasTable_aliasedByLimit (s, sRef_getBase (sr), lim);
293           res = sRefSet_addIndirection (abl);
294         }
295       else if (sRef_isAddress (sr))
296         {
297           abl = aliasTable_aliasedByLimit (s, sRef_getBase (sr), lim);
298           res = sRefSet_removeIndirection (abl);
299         }
300       else if (sRef_isField (sr))
301         {
302           abl = aliasTable_aliasedByLimit (s, sRef_getBase (sr), lim);
303           res = sRefSet_accessField (abl, sRef_getField (sr));
304         }
305       else if (sRef_isArrayFetch (sr))
306         {
307           abl = aliasTable_aliasedByLimit (s, sRef_getBase (sr), lim);
308
309           if (sRef_isIndexKnown (sr))
310             {
311               int idx = sRef_getIndex (sr);
312               
313               res = sRefSet_fetchKnown (abl, idx);
314             }
315           else
316             {
317               res = sRefSet_fetchUnknown (abl);
318             }
319         }
320       else
321         {
322           abl = sRefSet_undefined;
323         }
324
325       sRefSet_free (abl);
326     }
327
328   for (i = 0; i < s->nelements; i++)
329     {
330       sRef elem = s->keys[i];
331       
332       if (!sRef_same (sr, elem)) /* was sameName */
333         {
334                   
335           sRefSet_realElements (s->values[i], current)
336             {
337                       
338               if (sRef_similar (sr, current))
339                 {
340                                                   res = sRefSet_insert (res, sRef_fixOuterRef (elem));
341                   /*@innerbreak@*/ break;
342                 }
343             } end_sRefSet_realElements;
344         } 
345     }
346   
347     return res;
348 }
349
350 static /*@only@*/ sRefSet aliasTable_aliasedByLimit (aliasTable s, sRef sr, int lim)
351 {
352   sRefSet res;
353   
354   
355   if (sRef_isConj (sr))
356     {
357       res = sRefSet_unionFree (aliasTable_aliasedByLimit (s, sRef_getConjA (sr), lim),
358                                aliasTable_aliasedByLimit (s, sRef_getConjB (sr), lim));
359     }
360   else
361     {
362       res = aliasTable_aliasedByAux (s, sr, lim + 1);
363     }
364   
365     return res;
366 }
367
368 /*@only@*/ sRefSet aliasTable_aliasedBy (aliasTable s, sRef sr)
369
370   if (sRef_isConj (sr))
371     {
372       return (sRefSet_unionFree (aliasTable_aliasedBy (s, sRef_getConjA (sr)),
373                                  aliasTable_aliasedBy (s, sRef_getConjB (sr))));
374     }
375
376   return (aliasTable_aliasedByAux (s, sr, 0));
377 }
378
379 /*@only@*/ sRefSet aliasTable_canAlias (aliasTable s, sRef sr)
380 {
381   sRefSet res;
382
383     
384   if (sRef_isConj (sr))
385     {
386       res = sRefSet_unionFree (aliasTable_canAlias (s, sRef_getConjA (sr)),
387                                aliasTable_canAlias (s, sRef_getConjB (sr)));
388     }
389   else
390     {
391       res = aliasTable_canAliasAux (s, sr, 0);
392           }
393
394     return res;
395 }
396
397 /*
398 ** need to limit the depth of aliasing searches 
399 */
400
401 static /*@only@*/ sRefSet aliasTable_canAliasLimit (aliasTable s, sRef sr, int lim)
402 {
403   sRefSet res;
404   
405   if (sRef_isConj (sr))
406     {
407       sRefSet a = aliasTable_canAliasLimit (s, sRef_getConjA (sr), lim);
408       sRefSet b = aliasTable_canAliasLimit (s, sRef_getConjB (sr), lim);
409
410       res = sRefSet_unionFree (a, b);
411     }
412   else
413     {
414       res = aliasTable_canAliasAux (s, sr, lim + 1);
415     }
416   
417   return res;
418 }
419
420 static /*@only@*/ sRefSet 
421   aliasTable_canAliasAux (aliasTable s, sRef sr, int lim)
422 {
423   static bool hadWarning = FALSE;
424   llassert (!sRef_isConj (sr));
425   
426   
427   if (aliasTable_isUndefined (s) || lim >= ALIASSEARCHLIMIT)
428     {
429       if (lim >= ALIASSEARCHLIMIT && !hadWarning)
430         {
431           llquietbug
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.",
435                       sRef_unparse (sr),
436                       ALIASSEARCHLIMIT));
437           
438           hadWarning = TRUE;
439         }
440
441       return sRefSet_undefined;
442     }
443   else
444     {
445       int ind = aliasTable_lookupRefs (s, sr);
446
447       if (sRef_isPointer (sr) || sRef_isAddress (sr) || sRef_isField (sr)
448           || sRef_isArrayFetch (sr))
449         {
450           sRef base = sRef_getBase (sr);
451           sRefSet tmp = aliasTable_canAliasLimit (s, base, lim);
452           sRefSet ret;
453
454           if (sRef_isPointer (sr))
455             {
456               ret = sRefSet_addIndirection (tmp); 
457             }
458           else if (sRef_isAddress (sr))
459             {
460               ret = sRefSet_removeIndirection (tmp);
461             }
462           else if (sRef_isField (sr))
463             {
464               ret = sRefSet_accessField (tmp, sRef_getField (sr));
465             }
466           else if (sRef_isArrayFetch (sr))
467             {
468               if (sRef_isIndexKnown (sr))
469                 {
470                   ret = sRefSet_fetchKnown (tmp, sRef_getIndex (sr));
471                 }
472               else
473                 {
474                   ret = sRefSet_fetchUnknown (tmp);
475                 }
476             }
477           else
478             {
479               BADBRANCH;
480             }
481
482           if (ind != ATINVALID)
483             {
484               ret = sRefSet_union (ret, s->values[ind]);
485             }
486
487           sRefSet_free (tmp);
488                   return ret;
489         }
490       
491       if (ind == ATINVALID) return sRefSet_undefined;      
492       
493       return sRefSet_newCopy (s->values[ind]);
494     }
495 }
496
497 aliasTable aliasTable_copy (aliasTable s)
498 {
499   if (aliasTable_isEmpty (s))
500     {
501       return aliasTable_undefined;
502     }
503   else
504     {
505       aliasTable t = (aliasTable) dmalloc (sizeof (*s));
506       int i;
507
508       t->nelements = s->nelements;
509       t->nspace = 0;
510       t->keys = (sRef *) dmalloc (sizeof (*s->keys) * s->nelements);
511       t->values = (sRefSet *) dmalloc (sizeof (*s->values) * t->nelements);
512         
513       for (i = 0; i < s->nelements; i++)
514         {
515           t->keys[i] = s->keys[i];
516           t->values[i] = sRefSet_newCopy (s->values[i]);
517         }
518
519       return t;
520     }
521 }
522
523 static void
524 aliasTable_levelPrune (aliasTable s, int lexlevel)
525 {
526   
527   
528   if (aliasTable_isEmpty (s))
529     {
530       return;
531     }
532   else
533     {
534       int i;
535       int backcount = s->nelements - 1;
536       
537       for (i = 0; i <= backcount; i++)
538         {
539           sRef key = s->keys[i];
540           
541           if (sRef_lexLevel (key) > lexlevel)
542             {
543               int j;
544               for (j = backcount; j > i; j--)
545                 {
546                   backcount--;
547                   s->nelements--;
548                   s->nspace++;
549                   
550                   if (sRef_lexLevel (s->keys[j]) <= lexlevel)
551                     {
552                       s->keys[i] = s->keys[j];
553                       s->values[i] = s->values[j];
554                       sRefSet_levelPrune (s->values[i], lexlevel);
555                       /*@innerbreak@*/ break;
556                     }
557                 }
558               if (backcount == i)
559                 s->nelements--;
560             }
561           else
562             {
563               sRefSet_levelPrune (s->values[i], lexlevel);
564             }
565         }
566     }
567 }
568
569 /*
570 ** levelUnionSeq
571 **
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 }.
574 **
575 ** NOTE: t2 is "only".
576 */
577
578 aliasTable aliasTable_levelUnionSeq (/*@returned@*/ aliasTable t1, 
579                                      /*@only@*/ aliasTable t2, int level)
580 {
581   if (aliasTable_isUndefined (t2))
582     {
583       return t1;
584     }
585
586   if (aliasTable_isUndefined (t1))
587     {
588       t1 = aliasTable_newEmpty ();
589     }
590   else
591     {
592       aliasTable_levelPrune (t1, level);
593     }
594
595   aliasTable_elements (t2, key, value)
596     {
597       if (sRef_lexLevel (key) <= level)
598         {
599           int ind = aliasTable_lookupRefs (t1, key);
600
601           sRefSet_levelPrune (value, level);
602               
603           if (ind == ATINVALID)
604             {
605               /* okay, t2 is killed */
606               /*@-exposetrans@*/ /*@-dependenttrans@*/ 
607               t1 = aliasTable_addSet (t1, key, value);
608               /*@=exposetrans@*/ /*@=dependenttrans@*/ 
609             }
610           else
611             {
612               sRefSet_free (t1->values[ind]);
613
614               /*@-dependenttrans@*/ /* okay, t2 is killed */
615               t1->values[ind] = value;
616               /*@=dependenttrans@*/
617             } 
618         }
619       else
620         {
621           /*@-exposetrans@*/ /*@-dependenttrans@*/ 
622           sRefSet_free (value);
623           /*@=exposetrans@*/ /*@=dependenttrans@*/ 
624         }
625
626     } end_aliasTable_elements;
627   
628   sfree (t2->keys);
629   sfree (t2->values);
630   sfree (t2);
631
632     return t1;
633 }
634
635 aliasTable 
636 aliasTable_levelUnion (/*@returned@*/ aliasTable t1, aliasTable t2, int level)
637 {
638   if (aliasTable_isUndefined (t1))
639     {
640       if (aliasTable_isUndefined (t2)) 
641         {
642           return t1;
643         }
644       else
645         {
646           t1 = aliasTable_newEmpty ();
647         }
648     }
649   else
650     {
651       aliasTable_levelPrune (t1, level);
652     }
653
654   aliasTable_elements (t2, key, cvalue)
655     {
656       sRefSet value = sRefSet_newCopy (cvalue);
657
658       if (sRef_lexLevel (key) <= level)
659         {
660           sRefSet_levelPrune (value, level);
661
662           if (sRefSet_size (value) > 0)
663             {
664               int ind = aliasTable_lookupRefs (t1, key);
665               
666               if (ind == ATINVALID)
667                 {
668                   t1 = aliasTable_addSet (t1, key, value);
669                 }
670               else
671                 {
672                   t1->values[ind] = sRefSet_union (t1->values[ind], value);
673                   sRefSet_free (value);
674                 }
675             }
676           else
677             {
678               sRefSet_free (value); 
679             }
680         }
681       else
682         {
683           sRefSet_free (value); 
684         }
685     } end_aliasTable_elements;
686
687     return t1;
688 }
689
690 aliasTable aliasTable_levelUnionNew (aliasTable t1, aliasTable t2, int level)
691 {
692   aliasTable ret = aliasTable_levelUnion (aliasTable_copy (t1), t2, level);
693
694   return ret;
695 }
696
697 /*@only@*/ cstring
698 aliasTable_unparse (aliasTable s)
699 {
700    cstring st = cstring_undefined;
701
702    if (aliasTable_isUndefined (s)) return (cstring_makeLiteral ("<NULL>"));
703
704    aliasTable_elements (s, key, value)
705      {
706        st = message ("%q\t%q -> %q\n", st, sRef_unparse (key), 
707                      sRefSet_unparse (value));
708      } end_aliasTable_elements;
709
710    return st;
711 }
712
713 /*
714 ** bogus!
715 */
716
717 void
718 aliasTable_fixSrefs (aliasTable s)
719 {
720   int i;
721
722   if (aliasTable_isUndefined (s)) return;
723
724   for (i = 0; i < s->nelements; i++)
725     {
726       sRef old = s->keys[i];
727
728       if (sRef_isLocalVar (old))
729         {
730           s->keys[i] = uentry_getSref (sRef_getUentry (old));
731         }
732
733       sRefSet_fixSrefs (s->values[i]);
734     }
735 }
736
737 void
738 aliasTable_free (/*@only@*/ aliasTable s)
739 {
740   int i;
741   
742   if (aliasTable_isUndefined (s)) return;
743   
744   for (i = 0; i < s->nelements; i++)
745     {
746       sRefSet_free (s->values[i]); 
747     }
748   
749   sfree (s->values);
750   sfree (s->keys);
751   sfree (s);
752 }
753
754 void 
755 aliasTable_checkGlobs (aliasTable t)
756 {
757   aliasTable_elements (t, key, value)
758     {
759       sRef root = sRef_getRootBase (key);
760
761       if (sRef_isAliasCheckedGlobal (root))
762         {
763           sRefSet_realElements (value, sr)
764             {
765               root = sRef_getRootBase (sr);
766
767               if (((sRef_isAliasCheckedGlobal (root) 
768                     && !(sRef_similar (root, key)))
769                    || sRef_isAnyParam (root))
770                   && !sRef_isExposed (root))
771                 {
772                   if (sRef_isAliasCheckedGlobal (key))
773                     {
774                       if (!(sRef_isShared (key) 
775                             && sRef_isShared (root)))
776                         {
777                           voptgenerror 
778                             (FLG_GLOBALIAS,
779                              message 
780                              ("Function returns with %q variable %q aliasing %q %q",
781                               cstring_makeLiteral (sRef_isRealGlobal (key) 
782                                                    ? "global" : "file static"),
783                               sRef_unparse (key),
784                               cstring_makeLiteral (sRef_isAnyParam (root) 
785                                                    ? "parameter" : "global"),
786                               sRef_unparse (sr)),
787                              g_currentloc);
788                         }
789                     }
790
791                 }
792             } end_sRefSet_realElements;
793         }
794       else if (sRef_isAnyParam (key) || sRef_isAnyParam (root))
795         {
796           sRefSet_realElements (value, sr)
797             {
798               root = sRef_getRootBase (sr);
799               
800               if (sRef_isAliasCheckedGlobal (root) 
801                   && !sRef_isExposed (root)
802                   && !sRef_isDead (key)
803                   && !sRef_isShared (root))
804                 {
805                   voptgenerror 
806                     (FLG_GLOBALIAS,
807                      message ("Function returns with parameter %q aliasing %q %q",
808                               sRef_unparse (key),
809                               cstring_makeLiteral (sRef_isRealGlobal (root) 
810                                                    ? "global" : "file static"),
811                               sRef_unparse (sr)),
812                      g_currentloc);
813                 }
814             } end_sRefSet_realElements;
815         }
816       else
817         {
818           ;
819         }
820     } end_aliasTable_elements;
821 }
822
823
824
This page took 0.118065 seconds and 5 git commands to generate.