支付宝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倍。

指令合并优化目前只是新增了BL和B指令，并没有实正的去构建函数栈帧，所以不会增加内存的额外开销。通过对启动性能的阐发评估，影响在约为0.8ms摆布。

做者:松茸

来源:微信公家号:蚂蚁量量AnTest

出处:https://mp.weixin.电话.com/s/whGWV_m4CfcHjamiVuxSUw