Basic Structure for VSA

[ZhangZhuoSJTU]

I am working on VSA, and need some help about basic structure design for VSA.

Now, I have some ideas about the implement.

• Add a new member in SSAStorage, used for Value Set. And implement new methods in SSAExtra to calculate it.
• Design a new analysis stage, which could analyses Value Set and generate a mapping from IR to Value Set.
• Add a new member which looks like Option<ValueSet> in SSAStorage, and a new analysis stage to calculate the Value Set.

The advantage for the first way is we could make Value Set as a IR's property, while the one for the second way is more logical. Ofc, The third one is a transition between the first two ways.

[XVilka]

Is it still true?

[ZhangZhuoSJTU]

No need to worry the Basic Structure for VSA right now.

Because right now Radeco could support analysis between functions, the valueset could be used just as an internal data structure inside the analysis stage.

On the other hand, the value set analysis could perform on all the functions to gather precise or chosen functions to speed up. And it could do two works:

• Variable entities identification
• Use-def chain between memory variables
• Feed back for reference_marking
• Help a lot for preserved register analysis.

Because a sound VSA is much complex, work will be cut into following stages:

• [ ] Predicates for Conditional Branch Instructions (fold flag registers back to the original comparisons), to do Affine-Relation Analysis, more discussion could be seen #155
• [ ] Aggregate Structure Identification (ASI) for variable entities identification
• [x] Basic math operations for Strided Interval and Value Set, seen PR #159
• [ ] A useable intraprocedural VSA first
• [ ] Interprocedural VSA
• [ ] Other improvment (Priority-based Iteration, GMOD-based Merge function, and so on)

Btw, the original analysis/valueset is deprecated and old, while I will make a new folder analysis/vsa to rewrite it. When I finish these work, we could replace folder valueset by vsa

[XVilka]

See also VSA implementation for BAP https://github.com/draperlaboratory/cbat_tools