如何从java的字节码中识别三元运算符

Question

我正在做一个java的字节码项目，需要识别三元运算符和嵌套三元运算符。

我有两个问题

1. 如何根据堆栈判断if语句是三元运算符 变量？
2. 如何确定 if 语句在堆栈操作数上消耗的值 是三元运算符的结果

示例：

((a>b ? 0 : 1 ) > (a > c ? 10 : 20) ? 100 : 101

这是三元运算符链的完整示例：

源代码：

public void ddddd()
{
    int m,k, n, z;
    Random r = new Random();
    boolean p = (r.nextInt() > 100 || (30 > r.nextInt() ? (r.nextInt() > 4000 ? 1 : 0) : (r.nextInt() > 2000 ? 100 : 20)) <  (r.nextInt() > 1000 ? 0 : 1));
}

结构化字节码：

[

   7          astore] java/util/Random var1(1) = <init>(v0)
 [   9           aload] java/util/Random var1(1) = (stack_var)var1
 [  11   invokevirtual] I v11 = var1.nextInt()
 [  14          bipush] (I)v14 = 100
 if { // block_id: 16 16 => 89  parent_id: 0
    [  16       if_icmpgt] v11 > v14 : goto => 85
    if_false_block { // block_id: 15 19 => 89  parent_id: 16
        [  19          bipush] (I)v19 = 30
        [  21           aload] java/util/Random var1(1) = (stack_var)var1
        [  23   invokevirtual] I v23 = var1.nextInt()
        if { // block_id: 9 26 => 64  parent_id: 15
            [  26       if_icmple] v19 <= v23 : goto => 48
            if_false_block { // block_id: 8 29 => 45  parent_id: 9
                [  29           aload] java/util/Random var1(1) = (stack_var)var1
                [  31   invokevirtual] I v31 = var1.nextInt()
                [  34          sipush] (I)v34 = 4000
                if { // block_id: 6 37 => 45  parent_id: 8
                    [  37       if_icmple] v31 <= v34 : goto => 44
                    if_false_block { // block_id: 5 40 => 41  parent_id: 6
                        [  40        iconst_1] (I)v40 = 1
                        [  41            goto] goto: 66
                    }
                    if_true_block { // block_id: 4 44 => 45  parent_id: 6
                        [  44        iconst_0] (I)v44 = 0
                        [  45            goto] goto: 66
                    }
                }
            }
            if_true_block { // block_id: 7 48 => 64  parent_id: 9
                [  48           aload] java/util/Random var1(1) = (stack_var)var1
                [  50   invokevirtual] I v50 = var1.nextInt()
                [  53          sipush] (I)v53 = 2000
                if { // block_id: 3 56 => 64  parent_id: 7
                    [  56       if_icmple] v50 <= v53 : goto => 64
                    if_false_block { // block_id: 2 59 => 61  parent_id: 3
                        [  59          bipush] (I)v59 = 100
                        [  61            goto] goto: 66
                    }
                    if_true_block { // block_id: 1 64 => 64  parent_id: 3
                        [  64          bipush] (I)v64 = 20
                    }
                }
            }
        }
        [  66           aload] java/util/Random var1(1) = (stack_var)var1
        [  68   invokevirtual] I v68 = var1.nextInt()
        [  71          sipush] (I)v71 = 1000
        if { // block_id: 12 74 => 81  parent_id: 15
            [  74       if_icmple] v68 <= v71 : goto => 81
            if_false_block { // block_id: 11 77 => 78  parent_id: 12
                [  77        iconst_0] (I)v77 = 0
                [  78            goto] goto: 82
            }
            if_true_block { // block_id: 10 81 => 81  parent_id: 12
                [  81        iconst_1] (I)v81 = 1
            }
        }
        if { // block_id: 14 82 => 89  parent_id: 15
            [  82       if_icmpge] v40 >= v77 : goto => 89
            [  85        iconst_1] (I)v85 = 1
            [  86            goto] goto: 90
            if_true_block { // block_id: 13 89 => 89  parent_id: 14
                [  89        iconst_0] (I)v89 = 0
            }
        }
    }
 }
 [  90          istore] I var2(1) = (stack_var)var2
 [  92          return] return

Answer 1

对于三元运算符，java编译器将字节码生成为if/else块，例如：

int a = m > 1 ? 0 : 1

编译后，类文件的字节码如下所示（不关心伪造的偏移量）

0. aload_1  // load local variable m
1. ifeq #4
2. iconst_1
3. goto #5
4. iconst_0
5. istore   // store local variable a

控制流程图

block_0:
    0. aload_1
    1. ifeq #4
block_1:
    2. iconst_1
    3. goto #5
block_3
    4. iconst_0
block_4
    5. istore
    

它清楚地表明

1. 第一个block_4以store/return开始，操作数栈有一些值。
2. if (block_4->prev->prev) == block_0 和 block_0 以 if 语句结束。
3. 宾果游戏！从block_0到block_4可以是三元运算符。

这是我一开始的愚蠢想法，但不是现实世界！

对于下面的例子，上面的方法不起作用

boolean dddd = (m = 20) > 100 || (30 > ((r.nextInt() > 100 && r.nextInt() != 1000) ? (100 & r.nextInt()) : 20) ? (Or.a1 = this.b1 = m = k = n = 100 > r.nextInt() ? r.nextInt() : 0) : (r.nextInt() > 2000 ? 100 : 20)) < (z = r.nextInt() > 1000 ? 0 : 1);

我卡住了，这就是我问这个问题的原因。

折腾了好几天，终于找到解决办法了

控制流程图应构建如下

block_0:
    0. v0 = aload_1
    1. ifeq v0 == 0 goto #4
block_1:
    2. v1 = iconst_1
    3. goto #5
block_3
    4. v2 = iconst_0
block_4
    5. var1 = v3

因为我的代码将运行cfg的每个路径，v3很容易被标记为v1和v2的交集，那么cfg应该是

block_0:
  0. v0 = aload_1
    1. ifeq v0 == 0 goto #4
block_1:
    2. v1 = iconst_1
       v3 = v1
    3. goto #5
block_3
    4. v2 = iconst_0
       v3 = v2
block_4
    5. var1 = v3

将 v3 复制到 block_3 和 block_1 以及内联堆栈变量后：

block_0:
  0. v0 = aload_1
    1. ifeq v0 == 0 goto #4
block_1:
    2. 
    v3 = iconst_1
    3. goto #5
block_3
    4. 
    v3 = iconst_0
block_4
    5. var1 = v3

好的，堆栈变量 v3 是三元的。

这不是完整的故事，在我学习了静态单一作业表

之后

if block A (have dominate frontiers && block's stack out's depth > 0)
  for block child in block A's successors
    insert phi node to child head

依赖于phi节点，更容易找到v3，不需要循环控制流图的每条路径。

我都写到这里了，太多了。 希望对其他人有帮助。