In addition to Weibo, there is also WeChat
Please pay attention
WeChat public account
Shulou
2025-01-28 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Development >
Share
Shulou(Shulou.com)06/01 Report--
This article mainly explains "how to use Python to achieve a simple C++ program scope", interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Now let the editor take you to learn "how to use Python to achieve a simple C++ program scope"!
1. The experiment shows that
Problem requirements: for static single assignment (SSA) form of function intermediate code input, output function return value range
Realization idea: basically according to the "three-step method" range analysis method put forward at the CGO meeting in 2013, it is realized [3] to obtain the range of each variable.
Advantages of the algorithm: both space complexity and time complexity are O (n), and the efficiency is high.
Algorithm bottleneck: there is a great limitation in the function of the "three-step method". It can only analyze the maximum range of each variable, and only makes the simplest consideration to the active variable, so the final range is not accurate and often can only get a bound of the range.
two。 Project usage
Python main.py (the ssa file path is set in main.py)
No libraries need to be installed.
3. Algorithm principle
Simple summary: adopt a three-step approach (proposed at the CGO meeting in 2013)
3.1Building CFG
Code:\ src\ eSSAConstraintGraph.py;\ src\ structure.py
Function: parse SSA and build CFG.
Because of the call relationship between functions, SSA is first divided into SSA of different functions, and then CFG is built separately. The statement of each function and the relationship between Block are retained in CFG, which lays the foundation for the next step of building Constraint Graph.
The structure of CFG is as follows:
# CFG class class CFG: def _ _ init__ (self): self.name =''self.Blocks = [] self.Edges = [] self.Arguments = [] 3.2 build Constraint Graph
Code:\ src\ eSSAConstraintGraph.py
The premise of the three-step approach is to build Constraint Graph. The data structure is as follows. In this step, I use my own defined data type MyNode to represent a Constraint.
# ConstraintGraph class class ConstraintGraph: def _ _ init__ (self, cfg): self.MyNodes = [] # basic node Each node is a Constraint self.MyConditions = [] # node for the following E-SSA Constraint Graph supplementary condition self.cfg = cfg self.Arguments = [] # input parameter self.returnName =''# output parameter # MyNode: Constraint Graph Class MyNode: def _ init__ (self, t = ", name =", args = [], result = [], fromBlock = 0, Statement =''): self.type = t # Node Type: leave leaf node storage range and value # op operator # var variable name self.name = name.strip () # Node name: operation name Or variable name self.args = args # parameter, one node is the argument of the other node, which means that there is an edge connection between the two self.result = result # which is used, and one node is the result of the other node, which means that there is an edge connection between the two self.Conditions = [] # constraint Add the condition self.fromBlock = fromBlock # in which Block of the CFG self.Statement = Statement # in which Statement in the SSA self.Range = Range () # Node range self.size =''self.input = False# Range consists of two Bound class Range: def _ init__ (self): Self.lowBound = Bound () self.highBound = Bound () # Bound consists of values and types class Bound: def _ _ init__ (self): self.value = 'None' # inf maximum -inf minimum; None is not set; Not Exists does not exist self.size = 'None' # the boundary is int or float
It should be noted that when solving the calling relationship between the two functions, the called function is * * inlined into the original function * *. I append all the variable names of the called function with corresponding suffixes. For example, if `foo` calls the `bar` function, the variable `i1` in `bar` will be renamed to `iseparator 1bar1`, where # is the original name and suffix separator of the variable, and $is the delimiter of the function name and a random number. The purpose of\ $is to distinguish between multiple calls to the same function.
3.3.Building E-SSA Constraint Graph
Code: `\ src\ eSSAConstraintGraph.py`
This step is used to solve the addition of conditions. Such as `if (iTun2)
< j_3)`这样的条件。在MyNode节点类型中,我设置了Conditions结构用于保存条件。Condition的数据结构如下: Class Description : Constraint Graph中的条件,附加在MyNode中 class MyCondition: def __init__(self, condition, index): self.condition = condition self.arg1 = re.sub("\(.*\)", "",condition.split()[0].strip()) self.arg2 = re.sub("\(.*\)", "",condition.split()[2].strip()) self.op = condition.split()[1].strip() self.index = index 其中,arg1和arg2分别表示条件的两个参数,op表示条件的比较运算符。在Future Resolution这一步会进行比较,进行范围的约束。 以t7.ssa为例,得到的E-SSA Constraint Graph如下: call bar$1 in 2 : |Arguments: i_2,|Result: |Conditions: var i_2 in 2 : |Arguments: |Result: bar$1,i#bar$1,i_2#bar$1,|Conditions: var j_4 in 2 : |Arguments: _1#bar$1,|Result: bar$2,i#bar$2,i_2#bar$2,|Conditions: ret bar$1 in 2 : |Arguments: |Result: j_4,|Conditions: call bar$2 in 2 : |Arguments: j_4,|Result: |Conditions: var k_6 in 2 : |Arguments: _1#bar$2,|Result: _7,|Conditions: ret bar$2 in 2 : |Arguments: |Result: k_6,|Conditions: var _7 in 2 : |Arguments: k_6,|Result: |Conditions: var i_2#bar$1 in 3 : |Arguments: i_2,|Result: +,-,|Conditions: 0#bar$1 0|leaf 10 in 3 : |Arguments: |Result: +,|Conditions: op + in 3 : |Arguments: i_2#bar$1,10,|Result: _3#bar$1,|Conditions: 0#bar$1 0|var _3#bar$1 in 3 : |Arguments: +,|Result: PHI,|Conditions: 0#bar$1 0|leaf 5 in 4 : |Arguments: |Result: -,|Conditions: op - in 4 : |Arguments: 5,i_2#bar$1,|Result: _4#bar$1,|Conditions: 0#bar$1 1|var _4#bar$1 in 4 : |Arguments: -,|Result: PHI,|Conditions: 0#bar$1 1|op PHI in 4 : |Arguments: _3#bar$1,_4#bar$1,|Result: _1#bar$1,|Conditions: 0#bar$1 1|var _1#bar$1 in 4 : |Arguments: PHI,|Result: j_4,|Conditions: 0#bar$1 1|leaf i#bar$1 in : |Arguments: i_2,|Result: |Conditions: var i_2#bar$2 in 3 : |Arguments: j_4,|Result: +,-,|Conditions: 0#bar$2 0|leaf 10 in 3 : |Arguments: |Result: +,|Conditions: op + in 3 : |Arguments: i_2#bar$2,10,|Result: _3#bar$2,|Conditions: 0#bar$2 0|var _3#bar$2 in 3 : |Arguments: +,|Result: PHI,|Conditions: 0#bar$2 0|leaf 5 in 4 : |Arguments: |Result: -,|Conditions: op - in 4 : |Arguments: 5,i_2#bar$2,|Result: _4#bar$2,|Conditions: 0#bar$2 1|var _4#bar$2 in 4 : |Arguments: -,|Result: PHI,|Conditions: 0#bar$2 1|op PHI in 4 : |Arguments: _3#bar$2,_4#bar$2,|Result: _1#bar$2,|Conditions: 0#bar$2 1|var _1#bar$2 in 4 : |Arguments: PHI,|Result: k_6,|Conditions: 0#bar$2 1|leaf i#bar$2 in : |Arguments: j_4,|Result: |Conditions: Conditions:i_2(D) >= 0#bar$1 0 steps barrack 1 ~ 2 (D) > = 0#bar$2 0#bar$2, ````http://www.biyezuopin.vip3.4 three-step method 3.4.1 Widen
Code: `\ src\ rangeAnalysis.py`
The Widen step is used to expand the range of variables. This step can be completed within the O (n) phase. Based on the principle as follows: can be vividly understood as: in the Φ operation, if it is found that the range of variables increases upward, it will be directly expanded to inf, and if it is found that the range of variables decreases downward, it will be directly reduced to-inf.
In this way, the scope of each MyNode will be expanded to the maximum.
3.4.2 Future Resolution & Narrow
Code: `\ src\ rangeAnalysis.py`
In the Widen step, you can only solve the assignment behavior within each variable, and in the Future Resolution step, you can deal with the operations between variables, as well as conditions.
I used the complex ``ConditionHandle () `function to solve the Constraint problem of conditional variables. I added a Conditions structure to each MyNode, replacing variable substitution with Condition constraints. This can greatly reduce the hassle of variable replacement.
In `arg1``arg2`, I split the condition into `arg1``arg2` and `op` and combine them into a range in which the condition is true and a range in which the condition is false. And assign the corresponding scope to the corresponding variable, and check to see if the path can be connected.
Taking `t7.ssa` as an example, the range of all variables obtained by the three-step method is as follows:
Enter Range For i:-10 10bar$1 None None | Range: Not Exists Not Existsi_2 int int | Range:-10 10j_4 int int | Range: 0 20bar$1 None None | Range: Not Exists Not Existsbar$2 None None | Range: Not Exists Not Existsk_6 int int | Range: 5 30bar$2 None None | Range: Not Exists Not Exists_7 int int | Range: 5 30i_2#bar$1 int int | Range:-10 1010 None None | Range: 1010 + int int | Range: 020 _ 3#bar$1 int int | Range: 0205 None None | Range: 55-int int | Range: Not Exists Not Exists_4#bar$1 int int | Range: 15-5PHI int int | Range: 0 20_1#bar$1 int int | Range: 0 20i#bar$1 None None | Range: Not Exists Not Existsi_2#bar$2 int int | Range: 0 2010 None None | Range: 10 10 + int int | Range: 10 30_3#bar$2 int int | Range: 10 305 None None | Range: 5-int int | Range: Not Exists Not Exists_4#bar$2 int int | Range: 5-15PHI int int | Range: 5 30_1#bar$2 int int | Range: 5 30i#bar$2 None None | Range: Not Exists Not Exists
You can directly get the range of the result variable _ 7: _ 7 int int | Range: 5 30
4. Experimental results # t1.SSAReference Range: [100,100] Output Range: [100,100] # t2.SSAReference Range: [200,300] Output Range: [200,300] Output Range: [200,300] t3.SSAReference Range: [20,50] Output Range: [20, + inf] # t4.SSAReference Range: [0, + inf] Output Range: [0, + inf] # t5.SSAReference Range: [210,210] Output Range: [0, + inf] # t6.SSAReference Range: [- 9,10] Output Range: [- 9 10] # t7.SSAReference Range: [16,30] Output Range: [5,30] # t8.SSAReference Range: [- 3.2192308, 5.94230769] Output Range: [- 0.4192 3075526423315,14.700000286102295] # t9.SSAReference Range: [9791,9791] Output Range: [- 10, + inf] # t10.SSAReference Range: [- 10,40] Output Range: [1,1] so far I believe that everyone on the "how to use Python to achieve a simple C++ program scope" have a deeper understanding, might as well to practical operation of it! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!
Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.
Views: 0
*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.
Continue with the installation of the previous hadoop.First, install zookooper1. Decompress zookoope
"Every 5-10 years, there's a rare product, a really special, very unusual product that's the most un
© 2024 shulou.com SLNews company. All rights reserved.