版权声明：本文为CSDN博主「ashimida@」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/lidan113lidan/article/details/122953830?更多内容可关注微信公众号?
?
一、shrink-wrapping基本概念
? pro/epilogue是函数开始/结束时编译器为其插入的指令序列, shrink-warpping是针对pro/epilogue插入位置的优化,包括两个步骤:
1. 将pro/epilogue收缩到其实际需要的当前函数最小cfg子集中(此过程是在try_shrink_wrapping函数中完成的，后续称之为shrink-wrapping):
? ? pro/epilogue未必总是要发送到函数的开始和结束的，比如函数的某个流程中可能没有使用pro/epilogue中保护的寄存器，那么此流程就无需保护, 如下面的函数:
int main(int x)
{
if(x) return x; //1)
__asm__ ("":::"x20", "x21"); //2) 实际上这里可能是一个复杂的操作，使用了各种寄存器
return 0;
}
//aarch64-linux-gnu-gcc main.c -O2 -S -o main.s -fomit-frame-pointer
// 生成的汇编代码
1 main:
2 cbnz w0, .L4
3 stp x20, x21, [sp, -16]!
4 ldp x20, x21, [sp], 16
5 ret
6 .L4:
7 ret? 此函数在2) 处使用了callee-saved寄存器x20/x21, 那么在函数pro/epilogue中就需要save/restore此两个寄存器。但实际上如果在源码1)处发现x非0是可以直接ret返回的，这个流程中并没有使用x20/x21寄存器，无需执行pro/epilogue中save/restore x20/x21的代码。 从汇编代码中可以看出最终生成的汇编代码中若发现x0非0则直接跳转到.L4, 只有w0为0才会执行pro/epilogue.
? shrink-wrapping的第一个作用就是识别出CFG中那些不需要pro/epilogue的流程，只将pro/epilogue发送到其需要的最小cfg之内, 对于不需要pro/epilogue的路径使用simple_return直接返回。
2. 在1的基础上将pro/epilogue拆分为一个个更细的部分(components), 其中的每一部分最终只在其真正需要的基本块前后发射(后续称之为 shrink-wrapping separate):
? pro/epilogue指令序列的这种细分是平台相关的，在aarch64平台上(components)是根据寄存器来分的，即如果某个基本块(bb)中使用了某个寄存器，则才会在此bb前后发送pro/epilogue中此寄存器相关的save/restore指令 (多个bb均使用某些寄存器的情况还会继续优化，这里只简单举例):
int main(int x) {
if (x) {
__asm__ ("":::"x19", "x20"); //这里的作用是确保可以正确触发shrink-wrapping过程，原理参考aarch64函数栈分析
__asm__ ("#shrink-wrapping 1\n\t":::"x21", "x22"); // case 1
return x;
}
__asm__ ("#shirnk-warpping 2\n\t":::"x23", "x24"); // case 2
return 0;
}
//aarch64-linux-gnu-gcc main.c -O2 -S -o main.s -fomit-frame-pointer
//生成的汇编代码
1 main:
2 stp x19, x20, [sp, -48]! //作为stp!中使用的寄存器，无法做shrink-warpping
3 cbnz w0, .L6
4 stp x23, x24, [sp, 32]
5 #shirnk-warpping 2 //1) x23/x24寄存器只在 case 2中被用到过, shrink-wrapping separate将其save/restore限制在 case 2中
6 ldp x23, x24, [sp, 32]
7 mov w0, 0
8 .L1:
9 ldp x19, x20, [sp], 48
10 ret
11 .L6:
12 stp x21, x22, [sp, 16]
13 #shrink-wrapping 1 //2) x12/x22 寄存器只在 case 1中被用到过, shrink-wrapping separate将其save/restore限制在 case 1中
14 ldp x21, x22, [sp, 16]
15 b .L1 ? shring-wrapping seperate的原理也并不复杂，在gcc aarch64中:
- 首先按照寄存器划分出一个个components,通常一个函数中每个需要保存到栈中的寄存器都是一个components (见aarch64_get_separate_components)
- 分析每个bb中的指令序列，并确定此bb中使用了哪些寄存器，同时分析bb之间的关系，确定每个bb前后最终要插入哪些components相关的pro/epilogue指令。
- 为每个bb插入其需要的components的pro/epilogue指令(每个寄存器在pro/epilogue中的操作就是简单的 save/restore，这里并不需要做复杂的分析，只需为每个寄存器发送save/restore指令即可，见aarch64_emit_prologue_components)
- 重新生成pro/epilogue，此时根据寄存器排除掉已经作为 components 发送到各个bb中的寄存器相关的save/restore指令，只发射没有拆分的指令.
小结:
? 所以shrink-wrapping实际上恰如其名,?确实就是起到了一个"收缩包装"的效果，pro/epilogue作为函数的包装，将其收缩到需要的最小集中；同时还按照寄存器对pro/epilogue最进一步拆分，一个bb使用到了某个寄存器就发送此寄存器相关的pro/epilogue。
二、shrink-wrapping 相关源码:
? 在gcc中shrink-wrapping属于prologue/epilogue过程的一部分，其代码在pass_thread_prologue_and_epilogue中实现:
//pass_thread_prologue_and_epilogue => rest_of_handle_thread_prologue_and_epilogue => thread_prologue_and_epilogue_insns
void
thread_prologue_and_epilogue_insns (void)
{
......
rtx_insn *split_prologue_seq = make_split_prologue_seq ();
rtx_insn *prologue_seq = make_prologue_seq ();
rtx_insn *epilogue_seq = make_epilogue_seq ();
try_shrink_wrapping (&entry_edge, prologue_seq); //prologue/epilogue插入位置的优化
try_shrink_wrapping_separate (entry_edge->dest); //prologue/epilogue中的语句如果可以拆分，则拆分发射到各个bb中
if (crtl->shrink_wrapped_separate) //拆分后重新生成的pro/epilogue中不再包含已经发射到各个bb前后的指令了
{
split_prologue_seq = make_split_prologue_seq ();
prologue_seq = make_prologue_seq ();
epilogue_seq = make_epilogue_seq ();
}
.......
}1.try_shrink_warpping:
? try_shrink_wrapping 负责整体优化prologue/epilogue的插入位置, 其函数定义如下:
/*
* entry_edge传入的是函数入口
* prologue_seq传入此函数的prologue指令序列
最终entry_edge返回此函数prologue最终要插入的边位置.
*/
void try_shrink_wrapping (edge *entry_edge, rtx_insn *prologue_seq)
{
/* 若平台不支持 simple_return 则无法使用shrink-wrapping, 因为不包装的部分必须使用simple_return返回
若编译器指定了-fno-shrink-wrapping 则也可以禁止此功能. */
if (!SHRINK_WRAPPING_ENABLED)
return;
/* 若当前函数需要插入mcount桩,则不会shrink wrap*/
if (crtl->profile && !targetm.profile_before_prologue ())
return;
if (crtl->calls_eh_return) /* 函数调用了异常则此函数不做 shrink-wrap */
return;
bool empty_prologue = true;
/* 若prologue序列为空则函数不做shrink-wrap */
for (rtx_insn *insn = prologue_seq; insn; insn = NEXT_INSN (insn))
if (!(NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_PROLOGUE_END))
{
empty_prologue = false;
break;
}
if (empty_prologue)
return;
......
}? 这里通过注释来大体描述try_shrink_wrapping 的过程(见try_shrink_wrapping):
- try_shrink_wrapping函数负责执行shrink-wrapping, 以确保prologue/epilogue只在其需要函数部分被发射.
- 在shirink-wrapping的过程中不会复制prologue,整个prologue最终在函数中只能出现0次或一次。确定了prologue插入位置后，若一些bb在有prologue和没有prologue时都可达，那么此bb需要被复制一份，对于两个要分开。
- 不需要执行prologue就可以直接退出的路径会使用一个simple_return代替epilogue返回. 如果多个路径中都需要prologue，那么prologue会被放到其最靠前的公共路径中.
- 如下面的例子中, 若BB 3需要prologue,则CFG变化如下:
/* B: begin, R: return, S:simple_return */
B B
| |
2 2
|\ |\ //此时prologue插入到2=>3的边中
| 3 becomes | 3
|/ | \
4 7 4
|\ |\ |\
| 5 | 8 | 5
|/ |/ |/
6 9 6
| | |
R S R- 另一个例子，如果复制了循环中的某个基本块(如下面只有BB 3中需要prologue):
B 3<-- B ->3<--
| | | | | | |
| v | becomes | | v |
2---4--- 2---5-- 4--- //BB 4 复制为BB5, prologue插入到5=>3的边中
| | |
R S R? try_shrink_wrapping 返回的entry_edge是最终prologue要插入到的边, 其可能会被此函数改变.
2.try_shrink_wrapping_separate
? 此函数负责shrink-wrapping平台相关的各个component,其定义如下:
void try_shrink_wrapping_separate (basic_block first_bb)
{
if (HAVE_cc0)
return;
/* 若关闭了shrink-wrapping[-separate],开启了速度优先或者平台不支持separate函数则直接返回 */
if (!(SHRINK_WRAPPING_ENABLED
&& flag_shrink_wrap_separate
&& optimize_function_for_speed_p (cfun)
&& targetm.shrink_wrap.get_separate_components))
return;
if (cfun->calls_alloca /* 特殊函数不做shrink-wrapping separate */
|| cfun->calls_setjmp
|| cfun->can_throw_non_call_exceptions
|| crtl->calls_eh_return
|| crtl->has_nonlocal_goto
|| crtl->saves_all_registers)
return;
/* 平台相关函数, 此函数决定平台如何划分prologue中的component,
对于aarch64来说调用的是 aarch64_get_separate_components, 其以寄存器为单位划分component */
sbitmap components = targetm.shrink_wrap.get_separate_components ();
if (!components)
return;
......
/* 对函数中的每个bb分别调用平台相关函数 components_for_bb, 确定此bb中使用了哪些components,
aarch64中调用函数 aarch64_components_for_bb */
init_separate_shrink_wrap (components);
......
/* 从first_bb开始, 分析最终每个bb中要插入哪些 components */
EXECUTE_IF_SET_IN_BITMAP (components, 0, j, sbi)
place_prologue_for_one_component (j, first_bb);
/* 这里为每个bb插入对应compnents的prologue和epilogue代码
* emit_common_heads_for_components 是在bb的头部插入
* emit_common_tails_for_components 是在bb的尾部插入
* insert_prologue_epilogue_for_components 是在边上插入
这三个函数的差别在于插入位置的分析，对于每一个具体的插入，这三个函数中都会先调用:
- emit_prologue_components 插入此component的prologue(aarch64_emit_prologue_components)
- emit_epilogue_components 插入此component的epilogue(aarch64_emit_epilogue_components)
*/
else {
emit_common_heads_for_components (components); /* 在bb的开始发射,这里比较的是bb的所有前驱和自身 */
......
emit_common_tails_for_components (components); /* 在bb结束发射,这里比较的是bb的所有后继和自身 */
......
insert_prologue_epilogue_for_components (components); /* 在边指令中发射的部分 */
/* 标记components这个bitmap中所有的寄存器都已经被拆分到各个bb中了,
后续thread_prologue_and_epilogue_insns重新生成pro/epilouge时会排除此部分 */
targetm.shrink_wrap.set_handled_components (components);
crtl->shrink_wrapped_separate = true; /* 标记此函数需要重新生成prologue/epilogue */
}
.......
}2.1 targetm.shrink_wrap.get_separate_components
? 其中 targetm.shrink_wrap.get_separate_components 返回在当前平台中可以被shrink-warpped的components, 其返回的是一个bitmap。在aarch64平台其调用的是 aarch64_get_separate_components，其将每个寄存器均作为一个component,其返回的是当前cfun中所有需要分析的寄存器(components)，此函数定义如下：
/* 确定当前分析的函数中需要并可以参与shrink-wrapping的寄存器, 将结构构件成一个sbitmap返回. */
static sbitmap aarch64_get_separate_components (void)
{
sbitmap components = sbitmap_alloc (LAST_SAVED_REGNUM + 1); /* 为每个寄存器(这里到64)都在bitmap中分配一个位置 */
bitmap_clear (components);
/* 遍历所有在栈中需要保存的寄存器, 尝试将其加入到 components bitmap中进行shrink-wrapping。
当前函数中哪些寄存器需要在栈中保存是在aarch64_layout_frame中确定的，见后续分析[TODO] */
for (unsigned regno = 0; regno <= LAST_SAVED_REGNUM; regno++)
if (aarch64_register_saved_on_entry (regno))
{
......
bitmap_set_bit (components, regno);
}
/* 如果需要栈帧，则x29不能被收缩包装*/
if (frame_pointer_needed)
bitmap_clear_bit (components, HARD_FRAME_POINTER_REGNUM);
/* 被stp/ldp ! 指令选中的寄存器不可以做 shrink-wrapping */
unsigned reg1 = cfun->machine->frame.wb_candidate1;
unsigned reg2 = cfun->machine->frame.wb_candidate2;
if (reg2 != INVALID_REGNUM)
bitmap_clear_bit (components, reg2);
if (reg1 != INVALID_REGNUM)
bitmap_clear_bit (components, reg1);
/* LR实际上就是X30,理论上是可以shrink-wrapping的,但这里先禁止了 */
bitmap_clear_bit (components, LR_REGNUM);
bitmap_clear_bit (components, SP_REGNUM); /* SP不在R30之内，不参与shrink-wrapping */
return components;
}2.2 init_separate_shrink_wrap
? 其中init_separate_shrink_wrap负责分析函数中的每一个bb, 确定每一个bb中使用了哪些components，定义如下:
struct sw {
sbitmap needs_components; /* 代表其对应bb中使用了哪些components */
sbitmap has_components; /* 代表其对应bb中需要插入哪些component对应的指令 */
sbitmap head_components;
sbitmap tail_components;
gcov_type own_cost;
gcov_type total_cost;
};
static void init_separate_shrink_wrap (sbitmap components)
{
basic_block bb;
FOR_ALL_BB_FN (bb, cfun) /* 遍历所有bb */
{
bb->aux = xcalloc (1, sizeof (struct sw));
/* 确定此bb中使用了哪些components */
SW (bb)->needs_components = targetm.shrink_wrap.components_for_bb (bb);
......
}
}? 在aarch64中 targetm.shrink_wrap.components_for_bb最终调用aarch64_components_for_bb来确定每个bb中使用了哪些components:
static sbitmap aarch64_components_for_bb (basic_block bb)
{
bitmap in = DF_LIVE_IN (bb);
bitmap gen = &DF_LIVE_BB_INFO (bb)->gen;
bitmap kill = &DF_LIVE_BB_INFO (bb)->kill;
bool simd_function = aarch64_simd_decl_p (cfun->decl);
sbitmap components = sbitmap_alloc (LAST_SAVED_REGNUM + 1);
bitmap_clear (components);
/* 通常非callee used(也就是除了callee中使用了不需要恢复的)寄存器，只要在BB的 IN/GEN/KILL集合中,就会加入到此bb的components中. */
for (unsigned regno = 0; regno <= LAST_SAVED_REGNUM; regno++)
if ((!call_used_regs[regno] || (simd_function && FP_SIMD_SAVED_REGNUM_P (regno)))
&& (bitmap_bit_p (in, regno) || bitmap_bit_p (gen, regno) || bitmap_bit_p (kill, regno)))
{
unsigned regno2, offset, offset2;
bitmap_set_bit (components, regno); /* 将此寄存器加入components中 */
/* 若有一个相邻寄存器,则相邻寄存器也加入以增加LDP/STP利用几率 */
......
}
return components;
}2.3 emit_prologue/epilogue_components
init_separate_shrink_wrap负责确定每个bb中使用了哪些components, place_prologue_for_one_component 负责分析每个bb最终需要插入哪些components，最终:
- emit_common_heads_for_components
- emit_common_tails_for_components
- insert_prologue_epilogue_for_components
三个函数中分别在bb的开头/结尾以及边指令上插入components对应的pro/epilogue, 插入函数为:
- aarch64_emit_prologue_components: 负责向指令序列插入components对应的prologue
- aarch64_emit_epilogue_components: 负责向指令序列插入components对应的epilogue
二者定义如下:
static void aarch64_emit_prologue_components (sbitmap components)
{
aarch64_process_components (components, true);
}
static void aarch64_emit_epilogue_components (sbitmap components)
{
aarch64_process_components (components, false);
}
/* 发射ldx/stx指令,发射components中标记为1的寄存器对应的prologue/epilogue指令 */
static void aarch64_process_components (sbitmap components, bool prologue_p)
{
rtx ptr_reg = gen_rtx_REG (Pmode, frame_pointer_needed ? HARD_FRAME_POINTER_REGNUM : STACK_POINTER_REGNUM);
unsigned last_regno = SBITMAP_SIZE (components);
unsigned regno = aarch64_get_next_set_bit (components, R0_REGNUM);
rtx_insn *insn = NULL;
while (regno != last_regno) /* 遍历 components中所有寄存器 */
{
machine_mode mode = aarch64_reg_save_mode (cfun->decl, regno);
rtx reg = gen_rtx_REG (mode, regno);
poly_int64 offset = cfun->machine->frame.reg_offset[regno];
if (!frame_pointer_needed)
offset += cfun->machine->frame.frame_size - cfun->machine->frame.hard_fp_offset;
rtx addr = plus_constant (Pmode, ptr_reg, offset);
rtx mem = gen_frame_mem (mode, addr);
rtx set = prologue_p ? gen_rtx_SET (mem, reg) : gen_rtx_SET (reg, mem);
unsigned regno2 = aarch64_get_next_set_bit (components, regno + 1);
if (regno2 == last_regno)
{
/* 若只剩下一个寄存器了，则发送ldr/str指令 */
insn = emit_insn (set);
......
}
poly_int64 offset2 = cfun->machine->frame.reg_offset[regno2];
......
/* 若是指令对,则发送ldp/stp指令 */
if (prologue_p)
insn = emit_insn (aarch64_gen_store_pair (mode, mem, reg, mem2, reg2));
else
insn = emit_insn (aarch64_gen_load_pair (mode, reg, mem, reg2, mem2));
......
regno = aarch64_get_next_set_bit (components, regno2 + 1);
}
}2.4 targetm.shrink_wrap.set_handled_components
? set_handled_components负责标记哪些component已经在真正需要的bb中发射了，这些components在函数的pro/epilogue中不必再次发射了。在aarch64中对应函数为? aarch64_set_handled_components:
static void aarch64_set_handled_components (sbitmap components)
{
/* components中的部分已经在bb中发射过了，这里将其标记在reg_is_wrapped_separately中，后续重新生成pro/epilogue时不必再次发射 */
for (unsigned regno = 0; regno <= LAST_SAVED_REGNUM; regno++)
if (bitmap_bit_p (components, regno))
cfun->machine->reg_is_wrapped_separately[regno] = true;
}2.5 重新生成pro/epilogue
? components中已经发射到bb中的指令序列在pro/epilogue中无需再次发射，故此时需要重新生成pro/epilogue:
//pass_thread_prologue_and_epilogue => rest_of_handle_thread_prologue_and_epilogue => thread_prologue_and_epilogue_insns
void thread_prologue_and_epilogue_insns (void)
{
......
rtx_insn *split_prologue_seq = make_split_prologue_seq ();
rtx_insn *prologue_seq = make_prologue_seq ();
rtx_insn *epilogue_seq = make_epilogue_seq ();
try_shrink_wrapping (&entry_edge, prologue_seq); //prologue/epilogue插入位置的优化
try_shrink_wrapping_separate (entry_edge->dest); //prologue/epilogue中的语句如果可以拆分，则拆分发射到各个bb中
if (crtl->shrink_wrapped_separate) /* 重新生成的pro/epilogue */
{
split_prologue_seq = make_split_prologue_seq ();
prologue_seq = make_prologue_seq ();
epilogue_seq = make_epilogue_seq ();
}
.......
}? 这里以prologue为例(epilogue最终对应函数为aarch64_restore_callee_saves):
//make_prologue_seq => targetm.gen_prologue => aarch64_expand_prologue => aarch64_save_callee_saves
static void aarch64_save_callee_saves (machine_mode mode, poly_int64 start_offset,
unsigned start, unsigned limit, bool skip_wb)
{
rtx_insn *insn;
unsigned regno;
unsigned regno2;
/* 遍历[regno,limit]中所有需要被callee save 的寄存器并发射讲这些寄存器保存到对应栈地址的指令,
如果能凑成两个寄存器就发送如ldp的指令对, 否则直接发送mov reg mem;
*/
for (regno = aarch64_next_callee_save (start, limit);
regno <= limit;
regno = aarch64_next_callee_save (regno + 1, limit))
{
rtx reg, mem;
poly_int64 offset;
int offset_diff;
......
/* 作为components已经被处理过的寄存器对应的prologue指令不必重新发送 */
if (cfun->machine->reg_is_wrapped_separately[regno])
continue;
......
if (regno2 <= limit
&& !cfun->machine->reg_is_wrapped_separately[regno2]
&& known_eq (GET_MODE_SIZE (mode), offset_diff))
{
......
insn = emit_insn (aarch64_gen_store_pair (mode, mem, reg, mem2, reg2));
......
}
else
insn = emit_move_insn (mem, reg);
}
}小结:
? aarch64中整个shrink-wrapping separate的过程可以总结为:
- 按照寄存器将pro/epilogue划分为一个个components相关的(aarch64_get_separate_components)
- 确定函数中每个bb中使用了哪些components(aarch64_components_for_bb)
- 优化并确定每个bb最终需要为哪些components插入指令
- 将每个components对应的指令插入到需要的bb中(aarch64_process_components)
- 标记这些components对应的指令已经生成完毕(aarch64_set_handled_components)
- 重新生成pro/epilogue,此过程中会忽略已经发射过的components对应的指令(aarch64_save_callee_saves/aarch64_restore_callee_saves)