1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
std::map<BasicBlock*,TreeNode*> bb_map;
std::map<BasicBlock*,unsigned int> nums_map;
// Spawn Random If
{
// Gen Random Tree
TreeNode tree;
genRandomTree(&tree, origBB_list.size());
tree.walk();
if( allocNode(&tree, 0, 0x7fffffff) ) { // 0x7fffffff
std::vector<BasicBlock*>::iterator iter= origBB_list.begin();
BasicBlock *head=createRandomBasicBlock(&tree, loopEntry->getParent(), switchVar, iter, &bb_map);
BranchInst::Create(head, loopEntry);
}
} // Spawn Random If
// 生成一颗不规则的二叉树 叶子节点的数量为基本块的数量
int llvm::FlatteningEnhanced::genRandomTree(TreeNode *node,int node_limit)
{
std::list<TreeNode*> son_list;
son_list.push_back(node);
// 当叶子节点数量达到node_limit时终止生成
while(son_list.size()!=node_limit)
{
// 从所有孩子节点中随机挑选一个孩子节点
std::list<TreeNode*>::iterator tmp = llvm::Utils::randomChooseElementFromList(&son_list);
TreeNode *node=*tmp;
node->expandNode();
son_list.push_back(node->left);
son_list.push_back(node->right);
son_list.erase(tmp);
}
return son_list.size();
}
// 在[l, r]的大区间上，为当前节点的所有子节点设定一段唯一的左闭右开的区间
bool llvm::FlatteningEnhanced::allocNode(TreeNode *node,unsigned int l,unsigned int r)
{
if(r-l<node->limit)
return false;
node->l=l;
node->r=r;
if(node->left==NULL && node->right==NULL)
return true;
unsigned int var;
if(r-l-node->limit==0)
var=0;
else
var=rand()%(r-l-node->limit);
unsigned int mid=l+node->left->limit+var;
if(!allocNode(node->left,l,mid) || !allocNode(node->right,mid,r))
return false;
return true;
}
// 把基本块排列到所有叶子节点上 并创建子分发块
BasicBlock * llvm::FlatteningEnhanced::createRandomBasicBlock(TreeNode *node,Function *f,Value *var,std::vector<BasicBlock*>::iterator &iter,std::map<BasicBlock*,TreeNode*> *bb_info)
{
// 若是叶子节点 则对该节点建立到基本块的映射
if(node->left==NULL && node->right==NULL)
{
BasicBlock *bb=*iter;
bb_info->insert(std::pair<BasicBlock*,TreeNode*>(bb,node));
iter++;
return bb;
}
// 若非叶子节点 建立一个分发块
BasicBlock *left_bb=createRandomBasicBlock(node->left,f,var,iter,bb_info);
BasicBlock *right_bb=createRandomBasicBlock(node->right,f,var,iter,bb_info);
BasicBlock *node_bb=BasicBlock::Create(f->getContext(),"knot",f);
if(node->left->r!=node->right->l) // 左闭右开区间断言
errs()<<"Error!\n";
// 在分发块末尾插入if语句 若switch变量小于 node->left->r 则跳转到node->left 否则跳转到node->right
LoadInst *load=new LoadInst(TYPE_I32, var, "", node_bb);
ICmpInst *condition=new ICmpInst(*node_bb, ICmpInst::ICMP_ULT, load, ConstantInt::get(TYPE_I32, node->left->r));
BranchInst::Create(left_bb,right_bb,(Value*)condition,node_bb);
return node_bb;
}
|
