Data flow based regression techniques for scalar variables uses data flow graphs. And each node of that graph can represent a block of source code as small as one variables assignment or some number of sequential instruction. In my approach, the new type node, loop-node, in the control flow graph is introduced. This node represents the part of source code which is bounded by a loop. For example, the source code inside the for loop can be represented by using loop-node. Loop-node can contains some array definitions , array uses or scalar definitions and scalar uses. If there is no scalar definition and uses inside the loop-node, it is called atomic loop-node. If it has some sequence of scalar definitions inside the for loop ( non-atomic loop-node), then we can represent inside of loop-node in a normal control flow subgraph. Therefore, each non-atomic control flow has it's own control flow graph. If there is a reference to a loop-node, then it's control flow graph can be used, otherwise the loop-node itself is used in calculating regression testing. I am calling this new technique as hierarchical techniques because recursive (hierarchical) control flow graph definition inside the loop-node. Each loop-node may have it's own control flow subgraph.
Let's turn to the omega test side, I used the special loop-node in the control flow graph in order to use the omega test to compute dependencies inside the loop. If it is atomic loop-node than you can directly use the omega test and use the dependence information about the arrays inside this loop in regression test (no matter how many loop iteration how many nested loop inside that loop-node). If this node is non-atomic loop-node, then we can use the omega test indirectly but we have to give some attention scalar definition and uses. we can take this scalar variable as if it is an array element whose size is 1, then we can use it in the omega test. If the life time of these scalar (other than the loop variable) is limited inside that loop-node than we can assume that there is no forward dependencies between the scalar variable inside the loop and the source code after that loop node. Also as the omega test find exact data dependencies and eliminates the false definition-use pair by identifying killed definition, it reduces the number of definition-use pair.
Figure 4: Hierarchical Regression test example for a code segment
In the figure 4, you can see the source code segment and it's control flow graph. Loop-node 1 is a atomic node and you can use the omega test directly and no further levelization is required. In loop-node 2, you can also use the omega test, but you can go one level further to find the dependencies. In this example variable t is local variable of loop-node 2. There is a forward dependence between variable K inside the loop-node 2 and block B6.
After giving some high level information about how the omega test combined into the data flow based regression testing. Now, we have to give some low level information about how this system used in regression test. I mean, if there is a change in a line of source code, how this system finds the affected scalar and array variables. As in the normal data flow testing, the new definition or use association can be found by using backward or forward tests if the that new association is in the scalar variable. Here the cases that should be taken into consideration
Figure 5: Hierarchical test example
In order to give an example how hierarchical regression test works, I am using the code segment in left side of figure 5 which is used for a kind of image smoothing technique in a various computer vision applications. The hierarchical control flow graph of that function is given in that figure. In the first level, there are 2 blocks node which contains the parameter initializing (B1) and parameter calculation (B2) and one loop-node (non-atomic) (L1) which has some nested loop and array and scalar definitions inside. L1 has two block nodes and 2 loop-nodes (atomic). In regression testing, we can directly use the omega test to find data dependencies inside the loop-node L1-L2 and L1-L2. So if there is any change inside these loop, we only look at the data dependence information of the omega before and after changing, then if necessary we run the forward and backward test algorithm to find the affected or new definition-use association. Loop-node L1 is non-atomic loop variable. In this kind of loop-variable, the omega test can be used with little modification. For example, if you have a scalar variable in side the loop-node, you can represent it as if it is an array variable whose size is 1. Then using index variable as 1, we can use the omega test for data dependence information. Also, if there is local variable inside the loop-node (e.g., diff and diff2 variable in figure 5). We can run backward and forward algorithm only in that loop-node. It brings the levelization (hierarchical approach to regression testing). For that purposes, the control flow graphs of loop-node2 is used. All the information collected in that level can be used in one up level.
Now, we can give some example in figure 5,how the new method is used in some various kind of changes.