最近两天在看某券商的Android App.
当然,说看其实不太确切.
只是dex2jar然后再jd回来的混淆代码.
大概是连猜带蒙的看吧.
看的时候发现一些disassemble失败的部分,直接给的是bytecode.
还有一些是比较奇怪的代码分支层次.
前者倒是没想出什么原因.
而且也大致不算影响阅读,毕竟java bytecode其实还是比较简单可读的.
后者的原因想了想,大概是vm结构的区别了.
毕竟,dalvik是基于register,而jvm是stack base的.
register base的话,因为数量限制,加上一些优化策略,涉及到register的复用.
所以在跟源代码对译的时候,难免会出现不一致的地方.
尤其对于Java这种强类型语言来说.
ClassA和ClassB因为"生命周期"的不同可能导致复用同一个register,导致还原的时候,代码效果不是很理想.
而stack base的原则上来说就没有这个问题.
有多少个源代码级别的local variable就有多少个对应的bytecode里的variable.
所以对译起来相对简单得多.
想了下,自己实现JVM bytecode disassembler的话,好像不难.
变量,分支,签名,异常,类型都有.
大概是时间和精力/兴趣问题了.
然后想了下dalvik的情况.
如果搞定变量对应/区分的话,其他应该跟JVM的难度差不多.
考虑,在从source code到bytecode的translate过程中,对register的allocation策略.
一个naive的方式自然是算下source code级别的变量的作用域/生命周期了.
如果到某个点不再被使用,那么其所占用的register自然可以被复用.
某种程度上来说,这是个data dependency的问题.
那么大致的算法过程应该是以数据为中心展开的.
也就是基本的读写操作的序列化和拆分.
换个角度来说,就是以数据/变量为基本symbol的state machine/DAG了.
如果把某个变量v考虑为一个基本basic symbol或者symbol class.
一个赋值或者自增等操作之类的读写之后衍生一个同一symbol class的derivative symbol.
两个symbol之间做个link或者transfer标记.
那么数据之间如果有依赖的话,就是不同的symbol class之间存在link.
于是,一趟parse下来就得到一个大致的forest like的graph了.
这个graph的用处理论上来说可以做一定程度的并行编译.
如果不考虑实际的物理计算代价的话.
毕竟,每个不同symbol class的link intersect point就是实际的synchronize point.
在此之前的都算是独立数据流,可以分配到不同的CPU上执行.
当然,实际代价是另一回事.
而且真考虑的话,优化过程加上一下代价预估,也是顺手的事情.
另一个用途自然是register的allocation了.
如果不考虑dead code elimination的话,那么所有数据流应该都是会汇集到同一个点的.
不管这个点是真实的数据点(return value),还是一个pseudo/dummy.
那么,从这个角度看的话,其实这个graph就退化成tree了.
于是,重新考虑register allocation的策略.
对于基本的单层或者说双层(包含root)的tree来说,所需要的register数量就是root的children的数量.
递归推广下,对于多层的结构来说,就是整个tree structure里面,需要的register的数量就是至少是某个node的直接children的最大值local_max_children.
但实际所需的最大register数并不一定就是这个local_max_children.
因为当把这个subtree eliminate之后,实际上可用的register数为local_max_children-1,即reduce之后的结果要占一个register.
那么怎么算具体需要多少个register呢?
对于一个给定的tree,eliminate的策略应该是首先找leaf node上一层里children数最多的做prune.
因为这时候只能prune这一层的node,且这时所需的register数必然是最大children数.
于是,递归一下,reduce回root的话,实际上就算出了实际需要的register数量了.
而且,如果不关心具体数量的话,那么递归的过程实际上也就是allocation/reuse的过程了.
这个是source code到bytecode的translate过程.
但问题是如何逆向回来.
考虑到正向的过程其实类似某种变种形式的后续遍历形式.
如果正向过程中,对register的选择有固定的顺序或者选择策略的话,那么直觉上这个过程应该是可逆的.
因为每消耗一个register代表的其实是一层max children的leaf tree的elimination.
而每一个被小号的register的读就意味着一次subtree的merge/面向root的propagate.
所以理论上应该是可行的.
没有评论:
发表评论