[core] Switch-case constructs with multiple exits may cause decompilation errors

[huku-]

After messing around with several decompilation failures, I noticed that processSwitch() in RegionMaker.java may return null for switch-case constructs with multiple exits. In such a case, the dominance frontier of the switch-case contains multiple basic-blocks and outs.cardinality() > 1. However, the return value of processSwitch(), stored in out, is only set in the following if clause, which might not be triggered.

if (outs.cardinality() == 1) {
    out = basicBlocks.get(outs.nextSetBit(0));
    stack.addExit(out);
}

When this happens processSwitch() returns null and makeRegion() terminates prematurely, resulting in several errors informing of lost code (a lost basic-block results in all basic-blocks it dominates being lost as well). This is common case in big switch-case constructs and, if I understand correctly, this is the root cause of various decompilation regressions reported by users.

Now the hard part :) Solving this problem, requires processSwitch(), processIf() etc in RegionMaker.java being modified to return Collection<BlockNode> instead of a single BlockNode. Alternatively, I think the problem can also be solved by using a stack of blocks in addition to the region stack currently used. In any way, I think the overall logic implemented in RegionMaker.java needs to be modified a bit.

I'm also currently trying to minimize my test-case which is kinda large.

@skylot feel free to share any thoughts. I have created this issue so that we can coordinate towards solving this.

[skylot]

@huku- without test case it is hard to tell exactly cause of the issue, so I just try to describe what happen in RegionMaker and this method:
out or next block returned from processSwitch() method (or any other called from traverse method) is a code which will be executed after current region and this is only one block because regions structure must preserve execution order so multiple branches are not possible here. All branching occurs inside special regions (which implements IBranchRegion) such regions store conditions to select an exact branch. As example, SwitchRegion stores branches in cases list, this list filled here (check caseRegion variable which is result of recursive call to makeRegion method) and returned in getBranches() method.
So return null is ok if no code after the switch.
But the search for correct out block is hard, there are lots of filtering code (track all outs usage) and looks like the cause of issue inside this 'filtering' code.

And another example of blocks and regions for test TestSwitchSimple:

1. Java code

    public void test(int a) {
        String s = null;
        switch (a % 4) {
            case 1:
                s = "1";
                break;
            case 2:
                s = "2";
                break;
            case 3:
                s = "3";
                break;
            case 4:
                s = "4";
                break;
            default:
                System.out.println("Not Reach");
                break;
        }
        System.out.println(s);
    }

2. CFG
   
   Here block 3: 0x000d is out block.

3. Regions structure

jadx.tests.integration.switches.TestSwitchSimple$TestCls.test(int):void
  R(3:0|1|3)
  |  B:0:0x0000
  |  |> java.lang.String r0 = null;
  |  Switch: 4, default: R(2:2|1)
  |  |  B:1:0x0003
  |  |  |> switch((r4 % 4)) {
  |  |  |    case 1: goto L_0x0013;
  |  |  |    case 2: goto L_0x0016;
  |  |  |    case 3: goto L_0x0019;
  |  |  |    case 4: goto L_0x001c;
  |  |  |    default: goto L_0x0006;
  |  |  |};
  |  |  R(2:5|1)
  |  |  |  B:5:0x0013
  |  |  |  |> r0 = "1";
  |  |  |  InsnContainer:1
  |  |  |  |> break;
  |  |  R(2:6|1)
  |  |  |  B:6:0x0016
  |  |  |  |> r0 = "2";
  |  |  |  InsnContainer:1
  |  |  |  |> break;
  |  |  R(2:7|1)
  |  |  |  B:7:0x0019
  |  |  |  |> r0 = "3";
  |  |  |  InsnContainer:1
  |  |  |  |> break;
  |  |  R(2:8|1)
  |  |  |  B:8:0x001c
  |  |  |  |> r0 = "4";
  |  |  |  InsnContainer:1
  |  |  |  |> break;
  |  |  R(2:2|1)
  |  |  |  B:2:0x0006
  |  |  |  |> java.lang.System.out.println("Not Reach");
  |  |  |  InsnContainer:1
  |  |  |  |> break;
  |  B:3:0x000d
  |  |> java.lang.System.out.println(r0);

Notice Switch region with first condition block and next branching regions on same level.
Also out (B:3:0x000d) block on same level as switch region.

[huku-]

@skylot thank you very much for the information. I have examined this further and I think I understand the problem better now.

Since minimizing my test-case is not a priority, I just anonymized it a bit. Here's how my switch-case looks like (I have also attached the smail code):

The loop in processSwitch() that computes the union of the dominance-frontiers of the switch-case head successors, gives the following result (these blocks are also set in outs using outs.or()):

[B:3:0x0032, B:5:0x0045, B:33:0x014c]

Obviously this is not correct. As far as I understand, only B:5:0x0045 is a valid region exit and should be returned by processSwitch(). The other two are dominance frontiers of basic-blocks already dominated by the switch-case head (B:3:0x0032 is the DF of B:2:0x0030 and B:17:0x00c9, while B:33:0x014c is the DF of B:32:0x0147).

Later on, the correct basic-block (B:5:0x0045) is filtered-out here.

In this case, it just happens that valid exits of the switch-case region are only the basic-blocks that post-dominate the switch-case head (B:5:0x0045). This could simplify the logic in processSwitch() a bit, but I'm not sure this is a general solution.

As a side note, I believe it's perfectly valid for a switch-case to have multiple exits. For example B:40:0x0197 is another exit of the switch-case region, but as you have pointed out it's not followed by any code. However, it could have been the case that the aforementioned block was followed by valid code leading to a different return location. Since processSwitch() returns only a single basic-block, how can this situation be handled without resulting in lost code?

[skylot]

@huku- thank you for a nice test case!
Looks like cause of the issue is a fallthrough cases. All such blocks occur in the initial outs list with some variations:

1. B:33:0x014c - is a simple fallthrough case. I made a test-case but jadx can't handle it and generate incorrect code without any warning. This is bad so I will try to fix this ASAP.
2. B:3:0x0032 - worst case. In general, it is impossible to express such code flow in java. But here we can deduplicate code and move same instruction into next block and merge these cases.

Also, I notice that such incorrect outs list added as exits here and this lead to another code lost.

valid exits of the switch-case region are only the basic-blocks that post-dominate

You are right out is just post-dominator for switch block. But as I remembered it does not play nice with terminal paths like B:40:0x0197. I will try to check this.

I believe it's perfectly valid for a switch-case to have multiple exits

Yes it valid for exits but here we need find out block which is next code after switch statement. In java after every statement is only one next statement (see Block definition in JLS). Sorry, I don't know how to express this easily :(
And all terminal paths (like return or throw) can be embedded inside respective case region which result to something like this:

            case 22:
                throw new IllegalStateException(...);

[skylot]

@huku- I made a fix for a switch with fallthrough cases. As you suggested I use post-dominance info for search out block, but as soon as post-dominance algorithm expects only one exit node I use partial calculation on the needed subgraph.
For your test case I don't yet implement code deduplication, but made some fixes, so jadx produces correct code flow.

[huku-]

Great! The method is decompiled fine now. I only get the following informational message, but this is something that I will look into at a later time.

/* JADX INFO: Can't fix incorrect switch cases order, some code will duplicate */

Closing the issue for now as it looks like it has been resolved.

@skylot thank you very much for your time. I wish I had more time to help you out a bit, especially with the post-dominance stuff which looks pretty interesting.