看懂编译原理：目标代码指令生成和优化
原创
优化主要分为三个部分
- 针对特定的硬件平台提供的指令集选择最优的指令
- 选择合适的寄存器分配，每个cpu上的寄存器都是有限的，因此要有效利用寄存器（寄存器分配还是栈上分配（方法栈帧随方法退出销毁）还是堆中分配）
- 指令重排序优化，对于串行的执行流程如果指令交换顺序可以提高效率并且不影响执行结果的情况下，则进行指令重排序。但是这也是导致多线程安全的问题，因为只保证了串行没考虑多线程并行
针对特定的硬件平台提供的指令集选择最优的指令
为什么需要选择最优的指令？
首先开发者编写的代码是给人看的，有些时候会为了可读性牺牲一些性能；其次如果只是将代码机械的进行翻译则会出现很多无用的机器指令，就如同ir中的优化（无用ir删除）。因此我们需要对指令进行一些删除操作，将无用的指令删除。
在一个对于不同的机器平台对于同一个功能有很多不同的指令，这些指令都各有优点（应该说成各有各的场景更好）因此生成目标代码的时候需要根据上下文信息来从中选择一个效率最高的指令
如何选择合适的指令（拆分思想，上下文思想）？
指令树：一个指令拆分为很多指令形成一棵树，直到不能再拆分。这样就可以形成一个几乎和指令类似的语法树，而且他携带着这个指令的上下文信息（也就是其他子树的信息）
大部分采用的算法是树覆盖法（就是上面说的，转换为机器指令相关的ast）。大树有很多小树，这对应着一个复杂的ir里面是由很多小的ir组成，复杂的指令也是由小的指令组成。
因此根据这种拆分的思想，只需要确认每个小树都可以生成最优的指令也就代表了整个ast生成的是最优的指令。
每个小树也在这个算法里有个名字叫做“瓦片”，瓦片和机器指令的关系是一对多的。
选择合适的寄存器分配
为什么需要选择合适的寄存器？
在理想情况下，也就是ir中，我们假设所有的变量都存在寄存器中，但实际上目标机器寄存器的数量不是，是有限的。
寄存器的使用如何进行优化？
原理
- 中间临时变量不需要使用寄存器存储：但是这并不意味着一个变量要一直存储在寄存器中即使他之后并没有被使用到，比如a+b+c+d被翻译为ir需要有寄存器临时存储a+b的结果，也需要寄存器存储这个寄存器+c的结果，以此类推。这些中间值保存临时值的寄存器只用过一次就没有再用。对于这种情况我们可以只使用一个寄存器覆盖结果即可，寄存器的速度是最快的合理利用寄存器可以提高效率。
- 存取效率更高（经常使用）的变量应当优先存放在寄存器：寄存器的存取速度要比缓存读取快很多，因此应当优先存放使用频率高的变量。
怎么做：图染色算法
复用寄存器原理：根据cfg控制流图推导，不同基本快之间如果没有引用关系可以公用一个寄存器。
程序分为不同的基本快（顺序执行的流程块）顺序执行流程中寄存器肯定不能公用；但是另外一个基本快中的变量如果没有引用之前基本快中的变量也可以公用一个寄存器，反之则不可以。
思路：把这些变量都当做一个个节点，跨基本快的节点引用关系连成一条线叫做边（只要有连线两个节点就染成不同颜色，没有连线就相同颜色），最后只要在cfg中数*最少的颜色数量有几个就代表最少使用的寄存器数量。 *（该规律在举例中解释）
举例解释
abcd四个节点，总共六条边。bc之间有引用关系，也就是b和c不能公用一个寄存器，其他的都可以公用。也就是最少只需要两个寄存器就可以。（整个节点中只有c或者b和其他节点是不同颜色，有连线就代表最少需要多一个寄存器，）
寄存器优化中的注意点：使用cfg数据流分析出来的最少使用寄存器数量比实际的寄存器数量大，寄存器不够用怎么办？
- 检测最少寄存区数量溢出
查看节点中的不同颜色有多少。如果大于寄存器的数量就会溢出
- 寄存器溢出怎么处理
寄存器不够用的时候就用栈，对于超出寄存器数量的变量节点其指令要进行替换修改。
llvmir中使用变量默认都是寄存器，因此
对于超出数量的节点，要把默认使用寄存器的指令要修改为读取保存栈的指令。读取和保存的方式要修改为load和store这种使用栈的变量。在cfg中分析引用这些变量的地方替换指令
指令重排序优化
为什么需要重排序？
首先不要被打乱顺序吓到，软件代码最终都会编译成指令，有的指令在执行时cpu内部会有多个部件同时工作，而有的指令只需要一两个部件。
处于效率的考虑 指令优化的目标应当是尽量不让部件空闲下来
但是重排序要保证 计算结果不能变化，显而易见的比如数据依赖这种/寄存器依赖 统称 资源约束的指令不能进行重排序（分为两种先写后写和先读后写）
比如你只用到寄存器那么内存可以工作......，又或者某个指令会阻塞,阻塞期间的部件总不能也不工作吧？
先写后写是 同一时间更改某个变量的顺序不能发生变化，先读后写是 为了保证读的值是正确的
如何实现指令重排序？
原理：因为重排序不能改变执行结果也就是有数据依赖的指令不能重排。因此只要分析出数据流转的依赖关系就可以知道是否可以更换顺序。
寄存器有什么好处？就是快。你以前存256存不下要放到cpu高速缓存L1/2/3缓存 或 内存中取就很慢，现在直接寄存器取非常快。
一个是因为高速缓存（寄存器存放的东西更多了也因此能放到内存高速缓存的东西也就更多了）和数据局部性（cpu读取是按照一个缓存行读取的而不是只取需要的数据，因为取完之后大概率之后还会访问附近的数据因此直接读取一个缓存行；如果有多线程对同一个缓存行修改那么回写主存就会造成效率降低，但是如果没有多核多线程的干扰，数据局部性的处理效率就会很快不需要回写）
关于局部性提供程序运行效率的例子就是 在变量前后塞无用数据，让这个变量独占一个缓存行，不因为其他变量被修改而导致当前变量也要重新从低级缓存读取
处于同一个缓存行内的数据 其中一个修改了那么整个缓存行都会失效从低级缓存重新读取，因此只要独占缓存行就可以避免这种现象，缺点在于浪费了空间不过现在内存大小已经很大了对于时间来说空间是可以牺牲的
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。