5.2 Daikon based Reverse Engineering of Register to Variable Mapping
5.2.2 Challenges Resolved
REVAMP: Reverse Engineering Register to Variable Mapping in High-Level Synthesis
state1():::exit
::add_ln20_fu_96_p0 == ::add_ln20_fu_96_p0_temp ::add_ln20_fu_96_p0 == orig(::add_ln20_fu_96_p0) ::t1_reg_110 == ::t1
::add_ln20_fu_96_p0 == 0 ::mul_ln4_fu_56_p0 == 0 ::dx != ::u
::x != ::t3
3 * ::x - ::t1_reg_110 == 0 4 * ::x - ::shl_ln12 == 0 ::t5 >= orig(::t4)
::t6 >= ::sub_ln18 ::dx == ::dx_read ::u == ::u_read ::x == ::x_read
::mul_ln14_reg_115 == ::mul_ln14 ::t1_reg_110 == ::t1
::t4_reg_120 == ::t4
Figure 5.7: Daikon invariants output for state 1
state1 :
::mul_ln14_reg_115 == ::mul_ln14;
::t1_reg_110 == ::t1;
::t4_reg_120 == ::t4;
Figure 5.8: Mapping of State 1 registers to variables
Daikon based Reverse Engineering of Register to Variable Mapping
code. To add diversity to the test cases, we include some random test cases as well.
5.2.2.2 Unmapped Temporary Variables
The RTL-C code contains more than one operation in a single statement due to operation chaining in hardware. The expressions in SD-C, on the other hand, contain only one opera- tion (since it is in three address form). Therefore, many temporary variables are created in SD-C which are not mapped to any register in the RTL. Since these operations are happen- ing in a single state and they have no further use in any future states, we don’t need to find the mapping for these temporary variables of SD-C. So before calling Daikon, the combined code needs to be pre-processed so that all the temporary variables that are not being used in other states are removed. Its value is substituted in expressions where it is being read.
Example 16. For instance, the operation of one state of RTL-C in Waka benchmark is t23 reg 365 = in3 - in4 + in22 + in7 + in12 + in8.
The operations in the corresponding state of SD-C are t5 = in3 - in4,
add ln21 = t5 + in22, add in12 = in7 + in12, t11 = add in12 + in8, t23 = add ln21 + t11.
Here we see that there is operation chaining happened in the RTL-C code. The variables add ln21, add in12, t5 and t11are temporary variables in a same state. So, we remove these temporary variables and replace their occurrence with their expressions in that state.
l
5.2.2.3 Transitive Analysis of Daikon Output
In some cases, the direct register to variable mapping may not be found in the Daikon output. Specifically, some of the mappings is missing in Daikon output due to transitive dependency. To resolve this issue, we perform transitive analysis on Daikon output to obtain relevant invariants in such cases.
Example 17. Consider the following instructions from Matrixop benchmark:
mat1 load reg 651 = mat1 q0, and mat1 load = mat1 addr 1.
REVAMP: Reverse Engineering Register to Variable Mapping in High-Level Synthesis
The above two instructions are of RTL-C and SD-C, respectively. From Daikon output, we obtain the following mappings:
::mat1 q0 == ::mat1 addr 1, ::mat1 q0 == ::mat1 load and ::mat1 q0 == ::mat1 load reg 651.
Here mapping ofmat1 load reg 651 andmat1 load is missing. By transitivity, we can get
the required mapping. l
5.2.2.4 One Register to Many Variables Mapping in a State
We know that in a time step one register can not hold more than one value. Both RTL-C and SD-C are cycle accurate. So, the mapping of one register to many variables in a state is not possible. But in Daikon output, we find such one-to-many mapping due to copy propagation. In such a case, we can use one of the mappings in all places since both the variables have the same value.
Example 18. For instance, the operation of one state of RTL-C is
res1 load 1 reg 161 = mul ln12 reg 661 + res1 load 1 reg 161 temp.
The operations in the corresponding state of SD-C are add ln12 = mul ln12 + res1 load 1,
res1 load 1 = add ln12.
Here we see that there is copy propagation is happening in SD-C. Daikon gives us following mappings
::res1 load 1 reg 161 == ::add ln12 and ::res1 load 1 reg 161 == ::res1 load 1.
So, the register res1 load 1 reg 161 maps to two variables in a same state. As register res1 load 1 reg 161 maps to two variables, we can use any one of two mappings in that
state. l
5.2.2.5 Mealy vs Moore Models
The controller FSM can be a Mealy or Moore machines. In our framework, we support both as discussed below.
Mealy Model: In this model, operations are associated with the state transition. Based on transition condition, the operation performed is decided. For the Mealy machine, we
Daikon based Reverse Engineering of Register to Variable Mapping
//Control Structure state1:
o1;
c = exp ? 1 : 0;
if (c){
o2;
goto state2;
}
if (!c){
o3;
goto state3;
}
(a)
//Mealy model:
e1(){
o1;
o2;
} e2(){
o1;
o3;
} state1:
c = exp ? 1 : 0;
if (c){
e1();
goto state2;
}
if (!c){
e2();
goto state3;
} (b)
//Moore model:
state1(){
o1;
if(c){
o2;
} if(!c){
o3;
} } state1:
c = exp ? 1 : 0;
state1();
if(c){
goto state2;}
if(!c){
goto state3;
} (c)
Figure 5.9: (a) Control Structure (b) Code structure following Mealy Model (c) Code structure following Moore Model
model the transitions as function in the combined code.
Example 19. Consider the control flow example shown in Fig. 5.9(a). There are three states in the FSM, and from state1 (s1) there are two transitions based on the condition
’c’. If c is True, then control goes to state2 (s2), and if c is False, control goes to state3 (s3). Operations in state1 are o1, o2, and o3. The operation o2 executes when there is the transition from state1 to state2, the operation o3 executes when there is the transition from state1 to state3 and the operation o1 executes in all the cases. So, the operation associated with transition e1 (from state1 to state2) is o1, o2 and the same for the transition e2 (from state1 to state3) is o1, o3. The Mealy model of this scenario is shown in Fig.5.9(b) and in Fig. 5.10(a) with a diagram. Daikon finds invariants at the entry and exit of the transition
functions e1 and e2. l
Moore Model: In this model, operations are associated with states. All the operations are performed in the state, and based on the condition transitions are made separately. For the Moore machine, we model the states as functions in the combined code.
REVAMP: Reverse Engineering Register to Variable Mapping in High-Level Synthesis
c/{o1,o2} !c/{o1,o2}
S1
s2 s3
S1{o1 ,02,03
}
s2 s3
c !c
(a) (b)
Figure 5.10: (a) Mealy Model. (b) Moore Model.
Example 20. Consider the control flow Fig. 5.9(a) again. The state1 (s1) contains three operations {o1, o2, o3}. The operation o2 is performed when condition c is True. The operation o3 is performed when condition c is False. The o1 is the operation performed in all the conditions. So, all the operations are associated with state1. But, they will be executed when the corresponding condition is True. The transition is performed separately.
If c is True in state 1, then transition to state2 occurs and if c is False in state 1, then the transition to state3 occurs. The Moore model of this scenario is shown in Fig. 5.9(c) and
in Fig. 5.10(b) with a diagram. l
