[LLVMdev] A question about alias analysis
Chris Lattner
sabre at nondot.org
Sat Jan 14 22:28:25 PST 2006
On Sun, 15 Jan 2006, [gb2312] ÏÄÒ»Ãñ wrote:
> Oh, your meaning is pointers in a aliasset have equal address logically?
> But I think that two pointers are alias means they point to a same
> memory object, so if pointers "p" and "q" are alias, it seem as p = q,
> not &p = &q.
No, you're confused how globals are represented in LLVM. Looking at C
source isn't going to get you very far, because the C compiler does a lot
of optimization. If you want to see what your analysis is analyzing, use
something like this:
$ llvm-gcc hello.c -o hello.bc
$ opt -ds-aa -load ../Debug/lib/fps.so -FPS < hello.bc > /dev/null
$ llvm-dis < hello.bc
In LLVM, globals are represented by their address. To get the the value
of a global, you have to use a load or store instruction. Check out the
LangRef.html and other documents for more details.
> Another question is about "forwarding". "AliasSet[XXXX, 0] may alias,
> Mod/Ref forwarding to YYYY" (XXXX != YYYY) means the address XXXX can be
> regarded as YYYY in interprocedural analysis, and XXXX should be
> ignored?
The AliasSetTracker uses a union-find algorithm internally, and forwarding
links are part of this. If a set "A" is forwarding to a set "B", this
means that all of the pointers in sets "A" and "B" are really in the same
set.
-Chris
>> On Sat, 14 Jan 2006, ymxia wrote:
>>> 1. The following is the primary body of my pass "fps.cpp":
>>>
>>> AliasAnalysis *AA = &getAnalysis<AliasAnalysis>();
>>> AliasSetTracker AST(*AA);
>>>
>>> for (Module::iterator fi = M.begin(), fe = M.end(); fi != fe; ++fi )
>>> for (Function::iterator bi = fi->begin(), be = fi->end(); bi != be; ++bi)
>>> AST.add(*bi);
>>>
>>> for (AliasSetTracker::iterator I = AST.begin(), E = AST.end(); I != E; ++I) {
>>> AliasSet &AS = *I;
>>> AS.print (std::cerr);
>>> }
>>>
>>> 2. The follwoing is the test program "hello.cpp":
>>>
>>> int *a, *b;
>>> int main() {
>>> int t;
>>> a = &t;
>>> b = &t;
>>> printf ("%d, %d", a, b);
>>> }
>>>
>>> 3. I compiled the test program with "llvm-gcc hello.cpp -o hello", and made alias
>>> analysis with:
>>> opt -ds-aa -load ../Debug/lib/fps.so -FPS < hello.bc > /dev/null
>>>
>>> opt printed that:
>>> AliasSet[XXXX,1] must alis, Mod Pointers: (sbyte** %a, 4)
>>> AliasSet[YYYY,1] must alis, Mod Pointers: (sbyte** %b, 4)
>>>
>>> I donot know why "a" and "b" are not alias? They donot point to a same memory
>>> object? But, when I donot use DSAA, that is, "opt -load ../Debug/lib/fps.so -FPS <
>>> hello.bc > /dev/null", "a" and "b" are alias!
>>
>> This is telling you that &a != &b.
>>
>> -Chris
>>
>> --
>> http://nondot.org/sabre/
>> http://llvm.org
>
>
>
> ------=_1137305123_23829.html
> Content-Type: text/html
>
> <center>
> <table border=0 cellpadding=0 width=550 height=600 background="cid:__1137305123_23829 at none.net">
> <tr>
> <td valign="top" align="left"><br>
> Oh, your meaning is pointers in a aliasset have equal address logically?<br>
> But I think that two pointers are alias means they point to a same <br>
> memory object, so if pointers "p" and "q" are alias, it seem as p = q, <br>
> not &p = &q.<br>
> <br>
> Another question is about "forwarding". <br>
> "AliasSet[XXXX, 0] may alias, Mod/Ref forwarding to YYYY" (XXXX != YYYY) <br>
> means the address XXXX can be regarded as YYYY in interprocedural analysis, <br>
> and XXXX should be ignored? <br>
> <br>
> Thank you.<br>
> <br>
> >On Sat, 14 Jan 2006, ymxia wrote:<br>
> >> 1. The following is the primary body of my pass "fps.cpp":<br>
> >><br>
> >> AliasAnalysis *AA = &getAnalysis<AliasAnalysis>();<br>
> >> AliasSetTracker AST(*AA);<br>
> >><br>
> >> for (Module::iterator fi = M.begin(), fe = M.end(); fi != fe; ++fi )<br>
> >> for (Function::iterator bi = fi->begin(), be = fi->end(); bi != be; ++bi)<br>
> >> AST.add(*bi);<br>
> >><br>
> >> for (AliasSetTracker::iterator I = AST.begin(), E = AST.end(); I != E; ++I) {<br>
> >> AliasSet &AS = *I;<br>
> >> AS.print (std::cerr);<br>
> >> }<br>
> >><br>
> >> 2. The follwoing is the test program "hello.cpp":<br>
> >><br>
> >> int *a, *b;<br>
> >> int main() {<br>
> >> int t;<br>
> >> a = &t;<br>
> >> b = &t;<br>
> >> printf ("%d, %d", a, b);<br>
> >> }<br>
> >><br>
> >> 3. I compiled the test program with "llvm-gcc hello.cpp -o hello", and made alias<br>
> >> analysis with:<br>
> >> opt -ds-aa -load ../Debug/lib/fps.so -FPS < hello.bc > /dev/null<br>
> >><br>
> >> opt printed that:<br>
> >> AliasSet[XXXX,1] must alis, Mod Pointers: (sbyte** %a, 4)<br>
> >> AliasSet[YYYY,1] must alis, Mod Pointers: (sbyte** %b, 4)<br>
> >><br>
> >> I donot know why "a" and "b" are not alias? They donot point to a same memory<br>
> >> object? But, when I donot use DSAA, that is, "opt -load ../Debug/lib/fps.so -FPS <<br>
> >> hello.bc > /dev/null", "a" and "b" are alias!<br>
> ><br>
> >This is telling you that &a != &b.<br>
> ><br>
> >-Chris<br>
> ><br>
> >-- <br>
> >http://nondot.org/sabre/<br>
> >http://llvm.org<br>
>
>
>
> <br>
> </td>
> </tr>
> </table>
> </center>
> ------=_1137305123_23829.html--
>
> ------=_1137305123_23829.background
> Content-Type: image/gif;
> name="¾°Îï3"
> Content-Transfer-Encoding: base64
> Content-ID: <__1137305123_23829 at none.net>
>
> R0lGODlh9AFYArP/AP////716Ojk3dbWy8XKubS/pKCzj4+kfoKVcAAAAAAAAAAAAAAAAAAA
> AAAAAAAAACwAAAAA9AFYAkAE/zDISau9OOvNu/9gKI5kaZ5oqq5s675wLM90bd94ru987//A
> oHBILBqPyKRyyWw6n9CodEqtWq/YrHbL7Xq/4LB4TC6bz+i0es1uu9/wuHxOr9vv+Lx+z+/7
> /4CBgoOEhYaHiImKi4yNjo+QkZKTlJWWl5iZmpucnZ6foKGio6SlpqeoqaqrrK0lArCxsK60
> tRoDuLESursDs7bArgK+w7G4xMQBsL7HucHPpwIE0wMEBgUEuATYzAUC0OCrBgPh5cHT5um1
> BeTq7qwG7/Kp2fP2pfEWAwYH+ff/lNhVIPALoEFJ1SS0O8hw0gCBDSNKMkBAokVHuPxd3Gho
> loFvHP9DEvpWT6RJQOQEFGAxbNfJl04KHDiwUgPBA8dMkNQ2bVlOmECJFPBW4eHKWPxAUlDa
> YVi2odXYwZpWMqjVHgs5DECQQtrVr0eydvg4QiXYs0ZahkDngSDat2mZehhwQO5Au3DzBvEK
> Yl/FCmr1Cj4SWCvFCW4HKyaS69pQCTL59TNAeRs/bJUFxBPQL+Hizzd8BRAbgGwGzjRvgV7d
> w9q4Cw81s56dtpksWcd40d5tY1gu3MWkVQzOzJhn3shb+KZ2uxm1Y4mTS5cBctm2bCSJ4p3O
> 3YUBBFDpEvSLTgCCA3+7q1fBj3K1kv0QI5g/c3769fhHtONbuuaEfAVNoNL/dvkVOEE7/o2m
> kQSvtUWagdztQ1kBlJlm3gXYiHAfhNNFJttQ35iF4YYeBMihdO0hhlMGdZFA4om7mYfeBERl
> 8KBqytwI42w1KoMAgTK9iME2AUS3Y3LHNXjBihxwZlmCFPq4j45H5pUPXacl2AGJGvFX5WdE
> zYiBlhsYacFQ13y5WgH0jVZXhhTOZJoGImLApJqzyTnTfVuBROZSN54nJJ6CfUMhP+chkNIu
> gx5ImjUBtCigkoTqNdMB52FKIXjf2acBmf70Y1mFPVaqV3v1XToNeERe4OVjysypT5FUmhrU
> fNdkSllqkZ6XVVb+QWrrsMQWa+yxyCar7LLMNuvs/7PQRivttNRWa+212Gar7bbcduvtt+CG
> K+645JZr7rnopqvuuuy26+67wDQnizLzwmsSM8ncBhIxt9m7kXDM5DgVN800469IRFajTcAH
> v/Rnw0HVCTFYsk5slcQWW1VxxjBhXFo//RDIMUAa1TpyQwCeDJOkKpuk0sMtS/TNgjFb5FHN
> IqXU6Aci45wKSP70vEEuos1ijM+WGBXkLTJxs43QFvjmnMI8mYk0JNvtQ4FMUG+pVDFXY2Li
> Bizrt3PYlZh8ptoUVIU2KKKtRTOGXb+dydn6/IgBLnavUphhG+LdNynpVcdodWmOJuDgq8TN
> 4NwSoAOyUnHLpgzjqLhG6f9S3wmOeSrkVCyNbp8HU4zCRy+zC+mlmxJciMQQ5NRvPoVY09+t
> f2I0MgVX7YvVubNi9FDeyBRV3cHrPiGI+SxdpDJD3Zl8NI4FUOOFFIBMH6ZsTy/2fwJyVcHG
> dHvPSTvX/FJ25J5Hbn4l8WiTcmkPsrXW+xMdWl1FB2SweYntw58gLgUSYQ0JeQIKoAABUSq9
> YaBCbMuQ9RYYCfthiUUh+EjgrpE4CnbEP+vrRf+2tIuS5QMdfPOgIUZoQAuQLwPAo1H3VJgH
> 7PSPKUCrG+7apigaJqI+FLiMTGYiNC+NT4E+1AMBMoUN2E3wQHgxIoMo9KAdJjEPsLgUprY3
> H0//0SlqNSGLeZB4xTmAbIt/8VORgDS+drTQeiDBlHvK6If6dPFSCNjMfEiDw/T8L2oVmSEd
> 3XDH+gxnIXl0S2BqRBcEDvKRkIykJCdJyUpa8pKYzKQmN8nJTnryk6AMpShHScpSmvKUqEyl
> KlfJyla68pWwjKUsZ0nLWtrylrjMpS53ycte+vKXwAymMIdJzGIa85jITKYyl8nMZjpzMfrS
> xdieiYUQSXMZ1XEkNZcQTV5c83LbvMLrjPaNlBhDasEJpxSwKQ3USY05BcOOOqegkmw8ZBrs
> 6AkunOa2eUpBnluhhj2pEkN/TkGC0zSoFkqlUDAUtKFaeAhExwCziWbB/2MW3UI/M7oFiHC0
> CxX9KBUsJ9ItSNRVHi1pTEgTmfSp9Alkco30XsrNBGmTpkG43k1x+gPLCZKnQ/DGT4E6hB4S
> dQovPOoSxKTUJ1QDck1FAkGgGtW0lGanVb2BR7Ca1d7AsavcHA0ZwWqDlIQUBCEi6wqAtlZ6
> PVStCRWQL1iY1NM4xZ6+OedQS7oPXImMfxShylCnUg12DtRxYJUM5PaVFMCMgBsTsuc9qaJW
> lywlRP7YRwgHW5N7LkxxlY2r4wgQwhFstLKw4dkIdTLWqCKwtB5IKWrpJEjZduA4s72thtp3
> 2tzayJFvhCFXyYrYuawWhr4lgRS1AtvRDHe2xf9t0kwVstfkti0EfgFMda17F54dBjHcZUEM
> 5ZJdeoV3BdhIDIgqcLvUvAdNmTmvCGSjGXIA71B5nCNnQkSTn8gXAwUEDFQLy49BXfC/a0GT
> jkh7VgTPd1fbwUZzHWwC/n0NerBoMIVDMAu2sBObG1ZOXgsbT8KG+BX7PGe9YgO76qTwxKfJ
> zehGk96FGQM714HxXGR8uXfiixnUsKyON0AcbBannTweMlqhgtccoQ4bUnluiAvCt6rVVclo
> 3YZACjsTX8wRyzzLxjW63BPS/mWEMjEqmDlA2nEYzHqrfU6iNKxkzpBqG8RQ81bsiKs1NykW
> cV7QOOxYF2kw1M8KgYz/UmZ65ZMiuh0vxl4Q2fZWCofoPt/dWvvozF0RXWM/DmxbAF+84Y9o
> hjLtVMhxaaRAK553iAW2rPj0gcRK+3ZXJXHLoRm01+12tTKIwagEpjsXGEvGTwgYFFXLZOzz
> FLCiY21tVS2D6Uatemh/sXVy58QZDUgmgkfxdVc92kgMlig4G2Idd6siwQu0qkmBLFs+OShu
> nB6HqQO59pjaUbYVkRY9Un6piCRdFEcT2X1L6WxF7BdeAOnbUDOMbkGkfdR8ZNoC+rbJBhR1
> ce6G6Ua45UBFUUNxouZihDNWCHi6NnI1OzhTqaGQNeqz7GD7r95R1dRfjGqecnbR5TSCYc07
> /y3H+GRv1s8b0wMpM2SVZCrb4mvwn6g4t13P1lC72mIeIQMekVuASHVSCc55qkVC0yfNtRKL
> 5ZaIKVGVmiaZ+nkX8WyjDZmmg9YbB2psm9sz7ql8gIfMX7YCmH3FRr6SKaSm4JzxrNTpj+P7
> 7xYl0xlJfWdBgeFPu8FMH7Znve1Nm/XE95XxIcd97kkftlEX0irNBBzRsI+97GdP+9rb/va4
> z73ud8/73vv+98APvvCHT/ziG//4yE++8pfP/OY7//nQj770p0/96lv/+tjPvva3z/3ue//7
> 4A+/+MdP/vKb//zoT7/618/+9rv//fCPv/znT//62//++M+//vfP///++///ABiAAjiABFiA
> BniACJiACriAlRJXwNdN6sZ7wBFNwtcc9GJNEZh7+rI6KZRWvpdXuFE5F/iB9ZJNi7Mvr3de
> NsYLhSUwp/MbtzdOMphOwOEMtGcdRiNZIMg72qCBuYBXsqBlUgMd2oZl8MQTAPMekhVdtTdZ
> BLWEzbBeu2do2bBE+SQNFGFiH4gY3lBmA5OCMPYYTpFXxrd5ymd1Zfh8nPZ7vWV8IZd8Brd8
> Qyd8VzZ8bWh8cxh8aFh8cQhOePh8d0h8JMV8fHd8fZh8eQh8heiHwSdsTUN8G2MZ+PZ7b7gr
> qDZ8NBMnRkeHcuEaa0h7DAdaxjeIY4do3Kb/fCUBhms2cMy3GaUIe97ggMInT8y3X843YZCo
> iqb4irHXccinGSVHe1HRfBnRfFPVfDOji1jGVrVYGs3ojMvHjMo3C3tYgV81jeUUjLKXjcxn
> Vt0IPWtlg8vIIGvVEky4YdJ4AjdmIsqoUsUAIHUIQy24g0XIUxLSM6syM5/ogoJFO/5FVprR
> ZxrXX1jlY0QjWKglIbH2W/3lDI5kkMvBE7yoTqfGPTaxkEKGXdowFNihhE2kVodCIhkRSN8x
> XA8xklCxHEFWWaSBIL3QWI6FVsmIhQNVhdAVk1qzC1wTNWXBekTjW+zIKG2Dix+Aedx1jh5Y
> JETpNQ7WPbZ4AtWY/1tOuZSf0o4fJYsVQJVDEmKCpJVFoY1HVVtDFZXJhZXs9VP7WFkKFIiA
> AZZK5Wow5DnL1ZTApWFz6WD1GDlDd5d4CVw194YnRmptUXq9sIo/dWCu4pZgpUDlhlKwd442
> Qmyp52dwCRvEppiVtYbl1TZWmVWVWRQdh5mzxWmbORoTCV114xcuhntymYWJhnuCGTkfWUJE
> AZmIlmGIgViHpxlHMRwI+ZhGwRZRIlb7FCszcijp0zRkKV+/kF7NQxPyNAz4xUFkQRbGw5eW
> Jjs0ZkUUsRWHQiN+8hqdKXCGMhAD5g2TsRTZsx86Fm4udAuaMYnjM548xRT3hIZ2Rp+5pf85
> OuI8vSdTIMcPp/lfEIZSPaeHoagQBJGWhnlVX6c6wUcODDU6n2l7KUE7+pIMvudOBeMbUhGb
> uKdi2glizjWFyPA6DqmdI8iIlBmCFzhiOTIeH8Y3ZomXHApxPyhUsVM0AwpXRfOiVJOSxLFP
> ohlaQHhk7EQ7K9mjAIkvv6CSEvlZIbocEPgeSRaDuzOEvdOPtvlossMvSEYQ+BRlG9pE1uEW
> eFahs2d4VQgdt0N89aAwrqGf59WR7wFnh7KcsZdeUAZknYGndApXeTQTbpIRzTNsmBKoXfUQ
> lmgNhiImJ/RlsCkq2FETMiEgUyEnijptnSGlhCqbcdImuDcZ45D/YwGQbAdyevPBoA52apXh
> kKEmI1rkbLCZJhYSapHyHakSX6zpD2ZoahTiUU8jjAoBQlpCmOC4jeQ4AUjHIELDljDGHwQ3
> bGqDnRuGIJRzbZCHIauoRqzmQjNUpG9pPfcxXQkKn1iGPkrSrOwTAqxKXOtFIdXBruSqIcaG
> Ge3RIIiJGIzJpCVVF/sghghSdbV2YhShQfNTWufqdSGGazQhFaNBr0WCRF26bXtyFK8BovTT
> kyEWJw2yVQ/Uaw3rIeAFM5LJZsa2iXdqJzclri91bFxHIF55XQZ7HvKhI9X1rlmVKQVEVRXr
> Kv5aUpdXQI0iSPszZauqFL5IATPEFy77/1IpJZ8qom1skZeo1UDeJqllUhNPq1I9Mq3j86lb
> snCbOlEeBbbrWSK08kQwZkFUhazalXK0ua2z9W6w4pggwJGcUyF0y5J+pCNLiyHB2iXxECQn
> m5AgdCNPOTQfF0Qr4Z2LiFr8IZn7mgHtxTmR0xllS00DJ7HDsJeQxieWGkhdq1AiUrlB5K6A
> 4R/k8LNg5VOlp7EA9iiThmBkQVqWG64iI2zbJnjm9gE786byFUYwk4hwaR5bEbQNFSZCYq1b
> IzKUIbHJ5RbSG7lncgti+1/YwRVjo5UPxQ/Xeh6bgR6JoSqxZRNwC5RdNBVOMkTgoTaym5Po
> CDKQxg6JJzgw0/+YIUZAmetz5FBosBCJBAJ0FHYZ+VU4evMygfswnKGzXdV2RMRDUCRcrhIy
> Q3Z50kMXLNO8f8KbiZhce4YT9XSo6nm9UYMTITQg8uUa24OCbKsB+vYjdytDzFkku9JFHrWJ
> lmsXRNGs1iu5HzOr75tmIYU7RAER9UVhuFB2WpcoqIojtRspuJBHymtREJwqbWZHRSsXEqSr
> l9K3fadFXuzEbme5RdFZDoSF+kOg2oOq5iG+a7TDTOtwTOGalFfF6lQhbVc/2+El3cZrA7EL
> icqiufV5l/J1/oO5kAEzgYTH8zSrZbcSh5xaqauXHBCPYMVnZRc/8wG0nKlq0pWRvpVYKlf8
> xItXFJ/sJmorXzQ3qPHAJJpawpGzH5iMYPTRKV+MEw+RRwmyEI5Wy7Z8HkPUGcE6DOixegn0
> rbC3PfXRutnDJAXhHzPsZ3vSKbiqepD2H9nmwCsQAQA7
>
> ------=_1137305123_23829.background--
>
>
> --===============1770482800==
> Content-Type: text/plain; charset="us-ascii"
> MIME-Version: 1.0
> Content-Transfer-Encoding: 7bit
> Content-Disposition: inline
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> --===============1770482800==--
>
-Chris
--
http://nondot.org/sabre/
http://llvm.org/
More information about the llvm-dev
mailing list