Comments (8)
Hi, please correct me if I'm wrong.
By reading the code, I found there are two cases that node would collapse to field-insensitive.
- variable GEP edge
- if it's a PWC Node
The first case is self-explained. But I still don't get the second case. For example, if gep edges inside SCC cycle, I don't know why its pts should be collapsed to field-insensitive? It will be great if you can give me a example. I'm not sure if I understand PWC correctly since I could not find its explanation online. Thanks in advance.
from svf.
Hi Yue,
It is good that you read the code in depth.
Field-sensitive analysis of a struct object may become field-insensitive due to constraint cycles (PWC, positive weight cycles).
For example
p=q
q=p gep 1
The above llvm ir has a constraint cycle with one copy edge from q to p and one gep edge from p to q.
To trade precision for efficiency and avoid infinite derivations, we set the objects that p points to as field-insensitive. This is a standard way to handle field-sensitivity.
The two cases you point out are two scenarios when a node becomes a PWC node in a constraint cycle.
A PWC node is field-insensitive in our case. Any precision improvement you can think of?
from svf.
Thanks for your explanation, Yulei. I understand your IR example, but it's a little bit hard to replay it through source code, since IR follows a SSA form. If it's convenient for you, could you also show me a source code example? Thanks very much.
from svf.
You may wish to take a look at the micro-benchmarks. We had a few cycle examples.
Hope this one can help you understand.
https://github.com/SVF-tools/PTABen/blob/master/basic_c_tests/constraint-cycle-pwc.c
from svf.
Hi Yulei,
In order to improve the precision regarding field collapsing issue, one simple idea is to utilize type information to filter unrelated result during alias analysis. I guess it's implemented in AndersenWaveWithType solver, right? But you mentioned in #48 that AndersenWaveDiffWithType solver may not be conservative for C program. One possible reason is that type information cannot handle list retrieve well. Are there any other cases there? Please correct me if there's any misunderstanding. Thanks!
BTW, when I run your micro-benchmarks with SVF, it shows 2 NumOfSCCDetect, 1 TotalCycleNum, BUT 0 TotalPWCCycleNum according to statistic result. I wonder if this result is right?
from svf.
"AndersenWaveDiffWithType" is an improvement over "AndersenWaveDiff" to increase precision. Its implementation is relatively easy. It is conservative for C but may not be C++. You may wish to continue to improve "AndersenWaveDiffWithType" if you like.
For the small PWC case, I think you should not optimise (don't use -mem2reg) the bc before analyzing it, otherwise, the PWC will not be opted out. Following our case and concept, you can also write yours to test PWC.
from svf.
I see. By checking the codes, AndersenWaveDiffWithType solver has nothing to do with field collapsing issue. Would you think it's a good idea (e.g., conservative) to add a separated type information for each field? This type information should not be merged during field collapsing process, so it can be used to filter Objs with different types, which are introduced by the other fields from the same struct.
from svf.
It is doable. You may wish to take at look at PTAType for some extension if you like:
https://github.com/SVF-tools/SVF/blob/3038078e90eb037ea43aa28ff3a28c05d631be5d/include/MemoryModel/PTAType.h
from svf.
Related Issues (20)
- Performing reachability analysis between PAG edges HOT 1
- How to show more attributes on graphs? HOT 2
- How to create a CDG with SVF? HOT 25
- I encountered a segmentation fault.
- Failed to Extract Bc Files for Spec2006 HOT 1
- Hello, is there any mechanism in SVF to update TCT?
- How to run SVF on a C++ project? HOT 9
- dylib path issue on macOS
- How to maintain structure field-sensitivity across functions (in C)?
- How to modify PAG/ICFG? HOT 2
- Question regarding different modes of wpa
- [SVF API] Delete ICFG Node/Edge / Create new abstract ICFG from ground?
- Faced a crash on saber HOT 7
- Get pointer type in absence of `getPtrElementType` HOT 2
- Failed when using `getLLVMValue()` on Value got from `IntraICFGNode->getInst()`
- Type inference failure for linked list HOT 1
- SVF::FlowSensitive analyze failed HOT 3
- Flow sensitive wpa misses alias of global pointer? HOT 7
- Same Node but with Different Source Loc in -vfspta Pointer Analysis HOT 3
- Querying WPAPass APIs using LLVM Value* and CallInst* HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from svf.