PointerArgProcess 函数指针参数处理算法

2020-10-19

New PointerAnalysis算法步骤详细说明（修改后的PointerArgProcess）

1、每次以Function为处理单位，从Top Function（默认main）开始，依次处理IR中与Top Function相关所有Function。

2、 OptGetElementPtrInst(func)：对Function中两个连续getelementptr做合并操作。

3、getTargetedCallInst(func, call_list)：遍历Function中CallInst，并用call_list记录CallInst。

4、processTargetedCallInst(call_list)：依次遍历处理call_list中的每一条CallInst指令。并用new_callInst替换old_callInst。

（函数参数替换与创建指令）
5、SplitInstPointerArg(call_inst)：目标是将函数的PointerArg分解Globalvariable、AllcaInst、Argument和非PointerType的变量。

5.1、AnalysisPointerArg(call_inst)：分析CallInst的PointerArg，以及 GetelementptrInst、SelectInst、PHINode等指令，并记录memory和offset。

5.2、CreateMidFunction(call_inst)：
先利用func_arg_vec_创建MidF，此时MidF函数参数和 body都需要修改。
其次为MidFunction AddNewInst，遍历process_inst_list_处理， 将相关的GetelementptrInst、SelectInst、PHINode等指令添加进MidFunction中。

5.3、getReplacedArg(call_inst, del_arg_index)：记录CallInst中PointerArg为Inst的参数，准备删除。

5.4、DelFunctionArg(MidF, del_arg_index)：删除MidF中useless pointer_argument by del_arg_index。生成NewFunction。

5.5、创建New_CallInst，并代替Old_CallInst，删除Old_CallInst，删除MidFunction。

5.6、MarkGlobalVariable(call_new, NewF)：record the characteristic of global in function

5.7、addFuncUmap(OldF, NewF)：unordered_map<Function*, list<Function*> > func_umap_，如果OldF对应list为空，NewF加入list，否则NewF与list中Function逐个比较FunctionType。（如果Type一致，再比较Function添加的全局变量是否一致。）当确定NewF在list已经存在，将其删除。

（目的：Global变量不允许出现在函数参数，将其转至函数内部）
6、delGlobalArg(call_inst): 当函数参数存在全局变量指针，利用delGlobalArg函数进行替换删除处理。

（函数参数独立性分析processNonUniquePointer）
7、processNonUniquePointer(call_inst)：为保证函数参数直接相互独立，需要对不独立的参数进行替换删除，并生成NewFunc。（replace all uses of repetitive arg in body，delete the repetitive arguments & create new function with new CallInst。）

8、processUselessFunc()：利用del_list_，删除被new_Function替换且无调用的old_function。

9、PointerArgProcessMain()处理完毕。

2020-10-15：对算法设计细节流程：（仅供参考）

对select、phi指令进行添加，算法进行改进工作

（1）处理callInst指令中pointer参数：callInst（%a, %b, %c, %d, %e,……）

（2）%a往前搜索规则终止规则：Value为port、globalvariable、alloca。
搜索的指令为：getelementptr、bitcast、select、phi。

（3）举个栗子：

Orderset_argument: %M1, %I1, %I2, %M2

%1 : %M1, %I1
%2:%M1, %I2
%3:%M2, %I1
%x: %1, %2, %3
%y: %1, %x

Func_Mid(%x, %y ,%M1, %I1, %I2, %M2)

Func(%M1, %I1, %I2, %M2)

具体算法流程：

process_inst_set(Instruction*)：需要copy指令集合。
List(Instruction*) copy指令处理顺序
func_arg_vec(Value*)：原始参数所有value + 拆解的memory和offset。
arg_map(value*，int)：记录NewFunc的是否存在该value，与value在NewFunc中的index。
其中value为AllocaInst、GlobalVariable、Argument、(Inst’s op->getType()->isPointerTy() == false)

callInst（%1，……）

首先判断callInst是否需要处理条件：含有不是port、globalvariable、alloca的指针。

当%1%为函数参数时，判断%1：port、globalvariable、alloca。

1.1当%1为port、globalvariable、alloca， arg_map记录%1在函数参数的index_num。

1.2当%1不为port、globalvariable、alloca的指针参数。并用del_num记录。
判断%1是否在process_inst_set中。
1.2.1 当%1存在于process_inst_set中，不用处理。
1.2.2 当%1不存在于process_inst_set中，process_inst_set添加%1。依次处理%1的operands。
当operand为port、globalvariable、alloca、非pointer Type：
当operand存在于arg_map中，不用处理。
当不存在arg_map中，将其添加进入arg_map和func_arg_vec。

else：
当operand存在于process_inst_set中，不用处理。
当operand不存在于process_inst_set中，operand添加进process_inst_set中，继而处理operand这条指令。

1.3 memory到callInst中pointer参数之间的指令全部标记处理完毕。利用process_inst_set、func_arg_vec(Value*)、arg_map（value*，int）创建MidFunc（原始参数+func_arg_vec中参数）
1.3.1 利用func_arg_vec(Value*)创建MidFunc FunctionType。生成MidFunc函数。
注意：进行OldF 的ArgAttr相关属性copy到 Mid的问题，

1.3.2 利用process_inst_list_，准备将Instruction重新create到MidFunc函数中。
1.3.3 依次遍历处理process_inst_list_中的Instruction。
inst_map(Instruction*, Instruction*)：OldF 中inst与MidF 中inst的map。

举例子：
%1 = memory + offset
通过memory、offset的index找到对应MidFunc中的argument。从而create MidFunc中的%Mid_1。需要建立%1与%Mid_1的联系。inst_map[%1] = %Mid_1。

%3 = %1 + %2 + offset
通过offset的index找到对应MidFunc中的argument。再从inst_map中寻找%1、%2对应的%Mid_1、%Mid_2。从而生成inst_map[%3] = %Mid_3。

vec_temp中所有的Value在arg_map或者inst_map中都能找到时，对该Instruction进行create。

1.4 当所有指令都在MidFunc中create完毕后，删除callInst中del_num记录的指针参数。生成NewFunc，并重新创建NewFunc对应的callInst_new。

指针算法前期汇报总结：

目前函数指针参数处理情况总结：
（1）函数参数中指向数组类型的指针参数 分解为memory+offset。
支持变量类型：数组类型。
将一维或多维数组类型变量的首地址或者偏移地址传递给函数。
C程序：
int array[5]= {0,1,2,3,4};
int *q = &array [0]; // 数组类型变量的首地址 array[5] + 0
int *p = q + index; // 数组类型变量的偏移地址 array[5] + index
A(q, p); //函数A参数分解为A (array[5] , 0, array[5], index)

后期待优化：offset为const 变量，可以不用通过函数参数传递。

（2）函数间传递全局变量
（由于传值无需处理，只针对传指针情况）
函数参数中的指针变量为：直接或间接指向全局变量的指针
支持全局变量类型：基本类型、数组类型。
全局变量为基本类型时，对指针参数的user用全局变量替换，再删除指针参数。
全局变量为一维或多维数组时，先对指针参数分解为memory + offset，再对user用全局变量替换，最后删除指针参数。

C程序：
int global_x = 5；
int global_array[5] = {1,2,3,4,5};
main () {
int *q = &global_x;
int *p = & global_array [0];
int *m = p + index;
A(q, p, m); //A(0, index)
}

（3）确保函数参数之间相互独立
（由于函数参数指针指向全局变量已处理完毕，只针对指向局部变量的指针参数。）
函数参数为直接指向局部变量的指针
支持变量类型：基本类型、数组类型。
C程序：
Main () {
int x = 5;
int *x_pointer = &x;
int array[5]= {0,1,2,3,4};
int *q = &array [0];
int *p = q + index;
Func(x_pointer，&x，*q， *p); // Func(x_pointer, array[5], 0, index);
}

一、函数指针参数处理算法大纲：
1、 以Function为处理单位，深度优先、自上向下处理Function。
2、 遍历Function和Global进行pointToAnalysis分析，随时得到Value *a对应memory。
3、 遍历Function每条CallInst，List记录CallInst指令，map记录需要处理memory。
4、 遍历Function指令，对memory相关指令进行标记。
5、 依次处理每条CallInst，进行函数参数替换与创建指令和函数参数独立性分析处理。
6、 最后删除被new_Function替换且无调用的old_function。

二、Global作为函参问题：
目标：memory dependency 要求函参之间相互独立，函数参数（port）与函数内global必须独立。
解决方法：Global变量不允许出现在函数参数，将其转至函数内部。

全局变量不适合作为函数参数原因
（1） Jpeg中全局变量九十个，处理十分麻烦。
（2） 处理sum函数时，需要先将sum函数内所有的全局变量统计，并与参数比对，是否与参数重叠

举例说明：函数间global传递.cpp

三、函数参数处理流程说明：
（1）：Sum (*a, *b,……)

（2）：Sum (*a, *memory_a, offset, ……, *b, *memory_b, offset, ……)

（3）：当memory_a为global变量，b不是global变量时：
Sum (offset, ……, *memory_b, offset, ……)

当memory_a和b都不是global变量时：
Sum (*memory_a, offset, ……, *memory_b, offset, ……)

（4）：Sum (memory_a, offset, ……, memory_b, offset, ……)中，独立性分析得出memory_a与memory_b指向同一memory，则memory_a 替换memory_b
Sum (*memory_a, offset, ……, offset, ……)

举例说明：函数传递两个数组.cpp

四、如何防止创建冗余函数说明：
背景：对三中的sum函数创建sum_1时，下次根据CallInst指令再创建sum_2时，sum_2等于sum_1，则不需要创建sum_2。

unordered_map<Function*, list<Function*> > func_umap_；
处理OldF并生成NewF时：
（1）当OldF对应list为空，NewF加入list
（2）当OldF对应list不为空，NewF逐个比较list中Function。
比较方法：（1）比较FunctionType和（2）比较Function添加全局变量（指令不好比较）
比较结果：当确定NewF在list已经存在，将其删除。否则加入list。

五、处理C程序情况罗列说明：
数据类型支持：基本类型（字符型、整型、浮点型）、数组

PointerArgProcess使用场景：将变量的首地址或者偏移地址传递给函数。