Optimizer sometimes collapses simultaneously live registers

[brazdil]

Hi, I know you've already identified this issue, but want to give you more testing data. The Kakao messenger now successfully compiles (!!!), though only with 2GB heap, but then fails on the verifier due to a typing issue.

The problematic method is the <clinit> of class Lcom/kakao/talk/application/GlobalApplication;. The instrumented code begins with initialization of the static taint fields:

0: const a19, #0
1: const a18, #0
2: invoke-static Luk/ac/cam/db538/dexter/aux/struct/Assigner$$1;->newExternal_NULL(I)Luk/ac/cam/db538/dexter/aux/struct/TaintExternal$$1; (a19)
3: move-result-obj a17
4: sput-object a17, Lcom/kakao/talk/application/GlobalApplication;->t_kly:Luk/ac/cam/db538/dexter/aux/struct/Taint$$1;
5: invoke-static Luk/ac/cam/db538/dexter/aux/struct/Assigner$$1;->newExternal_NULL(I)Luk/ac/cam/db538/dexter/aux/struct/TaintExternal$$1; (a19)
6: move-result-obj a17
7: sput-object a17, Lcom/kakao/talk/application/GlobalApplication;->t_jnc:Luk/ac/cam/db538/dexter/aux/struct/Taint$$1;
8: invoke-static Luk/ac/cam/db538/dexter/aux/struct/Assigner$$1;->newExternal_NULL(I)Luk/ac/cam/db538/dexter/aux/struct/TaintExternal$$1; (a19)
9: move-result-obj a17
10: sput-object a17, Lcom/kakao/talk/application/GlobalApplication;->t_gga:Luk/ac/cam/db538/dexter/aux/struct/Taint$$1;

You might notice that a18 is not used and therefore line 1 is dead. It would be used as NULL if some of the taint fields corresponded to a field of array type. (I might actually simplify this, but it is nonetheless a valid piece of code). The full method body is at http://pastebin.com/JtVYgh47

After compilation (and presumably due to the optimizer), this snippet becomes:

const/4 v0, 0x0
const/4 v0, 0x0

invoke-static {v0}, Luk/ac/cam/db538/dexter/aux/struct/Assigner$$1;->newExternal_NULL(I)Luk/ac/cam/db538/dexter/aux/struct/TaintExternal$$1;
move-result-object v0
sput-object v0, Lcom/kakao/talk/application/GlobalApplication;->t_jnc:Luk/ac/cam/db538/dexter/aux/struct/Taint$$1;

invoke-static {v0}, Luk/ac/cam/db538/dexter/aux/struct/Assigner$$1;->newExternal_NULL(I)Luk/ac/cam/db538/dexter/aux/struct/TaintExternal$$1;
move-result-object v0
sput-object v0, Lcom/kakao/talk/application/GlobalApplication;->t_gga:Luk/ac/cam/db538/dexter/aux/struct/Taint$$1;

invoke-static {v0}, Luk/ac/cam/db538/dexter/aux/struct/Assigner$$1;->newExternal_NULL(I)Luk/ac/cam/db538/dexter/aux/struct/TaintExternal$$1;
move-result-object v0
sput-object v0, Lcom/kakao/talk/application/GlobalApplication;->t_kly:Luk/ac/cam/db538/dexter/aux/struct/Taint$$1;

The problem is obvious: a17 and a19 were allocated into the same register r0, and therefore the second INVOKE will fail, because it tries to use a TaintExternal object as an int. It is, however, interesting that the second CONST is not identified as dead. Depending on when dead code removal happens, one of the CONSTs should have been removed. Full code again available at: http://pastebin.com/LNKb5Lxg

The original APK is at: https://www.dropbox.com/s/pjqhkrqmma0p66e/Dexter_Issue22.apk

[xurubin]

My bad. SparseBitSet is not playing well with existing BitSet instances. I've now replaced all control flow related BitSet instances with SparseBitSet in 7669fad.

[xurubin]

Don't forget to run init.sh to apply the latest patch to dx.