支付宝App瘦身新思路重复指令合并技术

　　前言
　　稳定性、性能、包大小，是保障移动端用户体验的三驾马车，是app承载业务获得稳定、高效、低成本、增长的重要基石。其中包大小对下载转化率、降低拉新拉活成本等方面的影响至关重要，这在业界已经成为共识，近年来头部app针对下沉市场的极小包策略，更是将包大小的价值提升到了极致。但在实际开发过程中，随着功能的不断迭代，App体积越来越大不进行管控的话会直接影响安装转化率，因此App包大小需要持续的管控和优化。 现状
　　目前支付宝已经有不少关于安装包瘦身的方案，如：代码治理、资源治理、业务治理、构建优化，经过几轮治理之后现有手段让App瘦身效果越来越不明显，因此需要一种新的手段来进行App进行瘦身来突破的目前的瓶颈。 新方案
　　新的App瘦身方案是从App的可执行文件开展的，在二进制指令层面进行优化，通过合并大量的重复指令来实现二进制文件体积的减小，从而实现对安装包的瘦身。
　　iOS重复指令合并优化成果：
　　架构：arm64
　　本次共优化了的bundle占比是62%，优化后iOS二进制文件减少16.6MB。全量优化后预计能够减少20MB以上。 瘦身原理
　　下图中最左侧是源代码，中间部分是源代码对应的汇编代码，最右边是源代码进行重复指令合并后的汇编代码。
　　从上图中的操作是将重复的指令片段提取到公共的区域中，原来的重复指令段被替换为跳转指令，实现总指令数目变少。不难看出优化后的指令中长度变短了，这也就意味着指令所占用的空间减少，从而实现了二进制文件的瘦身。 技术架构图
　　本方案架构分为两部分，编译构建和环境适配。编译构建部分主要是解决重复指令合并的编译问题，用来产出经过重复指令合并的App安装包；环境适配主要是重复指令合并的配套设施建设，如crash堆栈的还原、调试信息的还原、产物一致性的校验。
　　工程包构建工具链：主要负责根据基线从git仓库中拉取工程代码，并使用APKit构建编译环境；环境准备好后Xcodebuild会根据工程中的配置文件生成编译命令，具体的编译命令由Apple Clang来执行并生成IR文件（用于编译优化）以及.frameowork文件（用于正常包）；完成编译后LinkLibChecker会根据工程配置提取工程依赖的二进制lib文件；最后将framework和IR和依赖的二进制lib上报到OSS和基线中。
　　编译优化安装包构建工具链：RIMKit根据基线下载需要优化bundle的IR文件、不参与优化的framework文件、依赖的二进制lib文件；AlipayRIMOpt工具会将对个IR文件进行合并优化产出libportalOpt.a文件；APKit工具负责构建安装包的编译环境；RIMLinkFlagsUtil工具负责调整portal工程的链接参数，将参与优化的bundle从中链接参数中剔除，把libisaopt.a和依赖的二进制lib添加到链接参数中；最后由Xcodebuild会根据portal工程的配置打安装包。
　　环境适配的工具链：一致性校验主要负责检查优化后的安装包中资源文件、符号等信息是不是比正常包的有缺失；crash堆栈还原主要是负责在优化时给新添加的符号及其指令增加调试信息，方便后续的符号定位。反解堆栈时将新增的符号导致堆栈的变换还原为正常未优化时的堆栈状态；debug堆栈还原主要是解决编译优化包线下调试的问题。 难点突破重复指令的识别
　　要想合并重复指令第一步必须先找出重复的指令，但对于支付宝这种量级的App而言其指令的数量在亿级，在这个数量级下想要快速找出重复的指令并不是一件容易的事情。必须采取合适的策略才能高效解决该问题，接下来为大家介绍求解的具体策略。
　　重复指令的定义：两条机器指令的汇编指令、寄存器、立即数所组成的数据须完全一致才认为是重复的指令。
　　明确重复指令的定义后，对指令进行编号，结果如下图所示：
　　按照上图所示的编排方式，可以把每一行的指令看成字母，这些指令对应的编号就组成了两个字符串：
　　funcA：ABCDEFGHIKMNOPQR&（&表示终结符）
　　funcB：ABCDEFGHJLMNOPQR$（$表示终结符）
　　寻找重复指令需求就变成了寻找该字符串中的公共子串。这里考虑使用后缀树来解决公共子串问题，后缀树是一种能够快速处理各类字符串问题的数据结构，非常适合应用在这个场景中。
　　下图将字符串
　　ABCDEFGHIKMNOPQR&ABCDEFGHJLMNOPQR$构建成为后缀树的形式。接下来介绍如何通过后缀树找到重复的字符串。
　　针对上图中的后缀树做一个简单的介绍，0号表示根节点，方形框表示叶子节点，圆性框表示中间节点。以三号节点为例：3号节点是21号和22号节点的父节点，这表示ABCDEFGH是字符串
　　ABCDEFGHIKMNOPQR&ABCDEFGHJLMNOPQR$和
　　ABCDEFGHJLMNOPQR$的公共子串。所以子节点数量表示了父节点字符串出现重复的次数。因此在提取公共字符串的时候可以忽略所有的叶子节点（方形），因为他们的子串数目为零表示没有出现重复的情况。
　　分析后缀树的非叶子节点发现4、5、6、7、8、9、10号节点代表的字符串为3号节点代表的字符串的子串；16、17、18、19、20号节点为15号节点的子串。因此只需要将3号15号节点填入下面的表格中。
　　可合并字符串计算表格：
　　原始字符串
　　ABCDEFGHIKMNOPQR&ABCDEFGHJLMNOPQR$
　　节点编号
　　3
　　15
　　公共字符串
　　ABCDEFGH
　　MNOPQR
　　子节点数S
　　2
　　2
　　正因为采取了后缀树算法，让发现重复指令的效率从朴素算法的O(n^3)降低为O( n )。目前优化支付宝300+的bundle的重复指令查找耗时控制在13分钟左右，让重复指令合并能够顺利迈出第一步。 剔除不能合并的指令
　　并不是所有指令都能进行合并的比如：跟LR寄存器有关的操作。这些相关的指令合并后会导致程序进入死循环。所以这里面临的第二个难点是把不能合并的指令找出并剔除。
　　上图中funcA和funcB函数的开头和结尾的两条指令是用来做压栈和出栈操作的都是跟LR和FP寄存器相关的，所以这几条指令是不进行合并的。在求解重复字符串的时候要进行剔除操作如下图所示。
　　了解了不可合并字符串的剔除规则后，接下来介绍如何根据后缀树找出的重复字符串求解出待合并的字符串集合。根据不可合并字符串的剔除规则可以将3号节点和6号节点的字符串分割为下表待合并字符串这一行的形式。
　　可合并字符串计算表格：
　　节点编号
　　3
　　15
　　公共字符串
　　ABCDEFGH
　　MNOPQR
　　子节点数S
　　2
　　2
　　包含的无法合并字符串
　　C
　　M
　　O
　　待合并字符串
　　AB
　　DEFGH
　　N
　　PQR
　　通过上述策略可以有效的剔除不能参与合并的指令避免程序出现异常，同时又可以将重复指令尽可能多得进行合并，如果将存在不能合并的指令序列完全放弃掉合并效果会大幅缩水。 部分指令不能合并的原因分析
　　关于LR寄存器：程序跳转（BL指令）时，会将BL指令后面的指令地址写入LR寄存器中，当程序执行完成后便会回到LR寄存器指向的地址。
　　场景一：压栈和出栈
　　上图中假设发生重复的指令片段在压栈和出栈这两段指令上。当程序执行完1号红色箭头时LR寄存器中原有的数据从指向main函数中的某个指令地址被替换为指向E行指令的地址。接下来要执行到2号红色箭头时需要构造funcA的栈帧，但LR寄存器中的地址不再指向原本要返回的main方法中，而是指向了funcA中的E行指令的地址这就导致程序再也无法返回到main函数中继续执行，所以这种合并会导致程序出错。
　　上图中1号黄色箭头执行完后并不会改变LR寄存器也不需要返回。当2号黄色箭头执行完时，LR寄存器里的数据是指向要返回的main方法中的某条指令，执行ret后即可正常返回，但是带来的副作用是堆栈显示存在异常。异常结果如下图所示：
　　merge1执行完成后应该出栈，但结果确实funcA出了栈。所以这种情况也不能进行重复指令的合并操作。（如果1号黄色箭头指向的不是b指令跳转而是BL指令跳转，则同样会导致程序返回异常）。 场景二：分支指令
　　上图中假设发生重复的指令片段在函数调用这段指令上，存在调用关系main->funcA。当程序执行完1号红色箭头时LR寄存器存储了E指令的地址。接下来要执行完2号红色箭头时LR寄存器存储了D指令的地址。但是由于在merge0函数中没有构造栈帧所以LR中原来指向E指令的数据被覆盖掉了，永远指向了D行的指令导致merge0无法返回到funcA中，程序也就无法正常执行。因此涉及到BL分支指令也不能进行合并。 重复指令的合并
　　找到待合并字符串后，并不意味着都可以进行合并，因为有些字符串合并后反而会变的更长。所以需要预先估计每个待合并字符串的收益，收益大于0才会进行合并。接下来推导一下重复字符串合并所节省的字符数量公式：
　　L：公共字符串长度（重复指令数量）；
　　S：子节点个数量（重复次数）；
　　R：节省的字符数量（节省出的指令数量）。
　　节省字符数量的公式：
　　添加指令为BL时：R = L*(S-1) - (S*1+1)
　　添加指令为B时：R = L*(S-1) - (S*1) (被合并的指令是以ret结尾的时候使用B指令跳转)
　　L*(S-1) 表示：S个长度为L的字符串的长度之和-公共方法中字符的个数。
　　(S*1+1) 表示：S个重复字符串乘以新增加的字符数（bl指令）+合并后的公共方法中新增加的一个L字符（ret指令），如果是B指令则不增加L字符（ret指令）。
　　接下来继续完善重复指令算表格。
　　可合并字符串计算表格：
　　原始字符串
　　ABCDEFGHIKMNOPQR&ABCDEFGHJLMNOPQR$
　　节点编号
　　3
　　15
　　公共字符串
　　ABCDEFGH
　　MNOPQR
　　子节点数S
　　2
　　2
　　无法合并字符串
　　C
　　M
　　O
　　待合并字符串
　　AB
　　DEFGH
　　N
　　PQR
　　待合并字符串长度L
　　2
　　5
　　1
　　3
　　预计节省字符数R
　　-1
　　2
　　-2
　　1
　　可合并字符串
　　无
　　DEFGH
　　无
　　PQR
　　可合并字符串位置坐标
　　无  [4,8]
　　[21,25]
　　无  [14,16]
　　[31,33]
　　利用上文中提到的预计节省字符数的计算公式算出每个节点预计节省的字符数，接下来将预计节省字符数小于1的节点删除，因此可合并字符串只剩下EFGH和PQR。
　　确定待合并字符串后，可以开始进行重复指令的合并操作，具体步骤如下图所示：
　　第一步：根据待合并字符串找出其对应的指令，并在程序原有的指令中插入一个新的函数_ALIPAY_REPEAT_FUNCTION_1。并将字符串的所对应的指令填入该函数中，然后再向指令结尾添加ret指令。
　　第二步：根据待合并字符串中的位置坐标，找到在原程序中的位置。
　　第三步：并将该位置原有的指令替换为 bl _ALIPAY_REPEAT_FUNCTION_1指令（如果被合并的指令是以ret结尾，则可以使用B指令进行跳转），从而实现对重复指令的替换，至此便实现了重复指令的合并优化。 适配新的编译流程
　　为了能够发现并且尽可能多的合并重复指令，需要改造当前的编译工具链流程。将多个传统单个编译单元中的指令合并到一个更大的编译单元中，具体流程如下所示。
　　非重复指令合并的编译流程：
　　非编译优化的编译流程是将一个文件作为一个编译单元进行编译，产生.o文件后由链接器链接为lib库文件，lib文件最后被链接器链接到可执行程序中完成可执行程序的编译流程。如果按照这个流程进行重复指令合并优化，那么只能将这个一个文件中重复的指令进行合并，能够合并的指令数量有限优化后效果不佳。为了能够将更多的重复指令合并，需要对传统的编译流程做出调整。
　　适配重复指令合并的编译流程：
　　适配编译优化后的流程是将单个文件编译为IR中间文件，由llvm-link将其链接为一个IR文件，之后进行常规优化。接着进行重复指令的合并，由于之前将多个编译单元合并为一个编译单元，在做重复指令合并的时候就可以将多个文件里的重复指令进行合并，实现最大化的优化效果。重复指令优化产生.o文件。最后obj文件被链接器链接到二进制可执行文件中，至此编译流程结束。
　　将编译流程配合重复指令优化进行调整后相比较于调整前App体积减少了接近8倍。 对App性能的影响
　　指令合并优化目前只是新增了BL和B指令，并没有真正的去构建函数栈帧，所以不会增加内存的额外开销。通过对启动性能的分析评估，影响在约为0.8ms左右。
　　作者:松茸
　　来源:微信公众号:蚂蚁质量AnTest
　　出处:https://mp.weixin.qq.com/s/whGWV_m4CfcHjamiVuxSUw