N - DAG优化

Description

大家都学过了代码优化，其中有一个DAG优化，这次我们就练习这个操作。

Input

输入第一行为一个整数ｎ(n < 100)，表示该组输入的表达式的个数

之后ｎ行为表达式，每个变量为一个字母，表达式仅包括二元运算 + - * /

例如：A=B+C

Output

 通过构造DAG图，进行代码优化，只需要保留AB，删除无用变量，删除变量时，尽量保留最早出现的变量。

PS:保证AB的值不同

Sample

Input 

3
A=B+C
B=B+B
A=C+C

Output 

B=B+B
A=C+C

#include <bits/stdc++.h>

using namespace std;
int cnt,n; // cnt 为当前结点的个数，n为输入的表达式个数
char s[10]; //临时输入
char ans[101][101]; // 最后输出的优化后的表达式
bool flas[101]; //用于记录那些表达式最后可以输出

struct st{
    char id; // 结点的值
    int left = -1; // left 和 right 都是存放的标号，即左/右子树所在的标号
    int right = -1;
    vector<char>var;
}node[101];

// i 是第i个结点，c是当前查找的符号
bool find_var(int i, char c)
{
    // 一个结点可能有多个标记
    int len = node[i].var.size();
    for(int k = 0; k < len; k ++)
    {
        if(node[i].var[k] == c)
        {
            // 找到
            return true;
        }
    }
    return false;
}
// 建立结点
// add_node 返回的值时该结点的标号，也就是位置
int add_node(char c)
{
    // 遍历当前已经建立的结点
    for(int i = cnt - 1; i >= 0; i --)
    {
        // 如果该结点建立过，或者和其他结点在同一个上面
        // 这个时候已经变量就会得到合并
        if(node[i].id == c || find_var(i,c))
        {
            return i;
        }
    }
    // 没有找到该结点，则需要新建立
    node[cnt].id = c;
    return cnt ++;
}

//添加表达式
void add_operator(char c, char op, int l, int r)
{
    for(int i = cnt - 1; i >= 0; i --)
    {
        //如果该表达式已经存在，将该表达式左边的值放到结点的var中即可。
        if(op == node[i].id && node[i].left == l && node[i].right == r)
        {
            node[i].var.push_back(c);
            return ;
        }
    }
    // 如果没有，则需要把整个表达式都加进去
    // 形状是结点为操作符，左右结点为操作数，结果存到父节点的var中
    node[cnt].id = op;
    node[cnt].left = l;
    node[cnt].right = r;
    node[cnt].var.push_back(c);
    cnt ++;
}
// 保留变量标记
void dfs(int i){
    // 如果保留的变量需要使用该表达式，则标记为1，保留下来
    if(node[i].left != -1)
    {
        flas[i] = 1;
        dfs(node[i].left);
        dfs(node[i].right);
    }
}
// ok函数
char ok(int i)
{
    int len = node[i].var.size();
    for(int k = 0; k < len; k++)
    {
        // 遍历i结点这个地方是不是有A||B，如果有的话，就说明这个值就没用了，用A||B就行
        if(node[i].var[k] == 'A' || node[i].var[k] == 'B')
        {
            return node[i].var[k];
        }
    }
    // 如果没有那就暂时保存这个值
    return node[i].var[0];
}
int main()
{
    cnt = 0;
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> s;
        // 使用add_node建立结点
        int l = add_node(s[2]);
        int r = add_node(s[4]);
        // 将表达式构成树
        // 左右的l、r 使用的就是两个变量存在的标号
        add_operator(s[0],s[3],l,r);
    }
    for(int i = 0; i < cnt; i ++)
    {
        // 保留有左子树的,有左子树情况就是一个表达式的表示
        if(node[i].left != -1){
            // 搞定复写的另一种，比如c = d + d,a = d + d,b = e + c
            // 这时候确定存在ans[i][0]的是a，而不是c
            ans[i][0] = ok(i);
            ans[i][1] = '=';
            // node[i] 是由其左右结点运算得来的
            st ll = node[node[i].left];
            st rr = node[node[i].right];
            // 如果这个结点的左子树不是空的，那操作数就是ok(node[i].left)
            //就是判断c = d + d,a = d + d,b = e + c是否将c换成a
            // 如果是空的，那就是左子树本身的值，即ll.id
            ans[i][2] = ll.left != -1 ? ok(node[i].left) : ll.id;
            ans[i][3] = node[i].id;
            ans[i][4] = rr.left != -1 ? ok(node[i].right) : rr.id;
            ans[i][5] = '\0';
        }
    }
    // 保留所需要变量
    // 题目中要求保留A、B
    for(int i = cnt - 1; i >= 0; i --)
    {
        // 把A能用的表达式或者值进行标记
        if(ans[i][0] == 'A')
        {
            dfs(i);
            break;
        }
    }
     for(int i = cnt - 1; i >= 0; i --)
    {
        // 把B能用的表达式或者值进行标记
        if(ans[i][0] == 'B')
        {
            dfs(i);
            break;
        }
    }
    for(int i = 0; i < cnt; i ++)
    {
        if(flas[i])
        {
            puts(ans[i]);
        }
    }
    return 0;
}

优化原因

• 逐条语句进行的代码生成策略经常产生含有大量冗余指令和次最优解结构的目标代码。
• 代码优化就是被优化程序进行一种语义保持的变换

优化位置

• 中间代码优化（与机器无关）
• 目标代码优化（与机器有关）

优化分类

• 局部优化
• 循环优化
• 全局优化

优化技术

• 删除公共子表达式：t1 = 4 * i和t2 = 4 * i的右侧是公共的，优化为t1 = 4 * i和t2 = t1
• 复写传播：t1 = f[t2]、t3 = t2、t4 = f[t3]优化为t1 = f[t2]、t3 = t2、t4 = f[t2]
• 删除无用表达式：把上面的t3 = t2删掉（事实上，复写传播的目的正是使某些变量的复制变为无用）
• 强度削弱：t1 = 4 * i，i的值每次循环减1，优化为t1 = t1 - 4，将强度较高乘法运算优化为强度较低的加法运算
• 删除归纳变量：若存在线性关系t1 = 4 * i和t2 = 4 * j，则i > j优化为t1 > t2

流图构造

——— 根据中间代码构造流图需要三步：

1. 找入口语句（程序的第一句 + 转移语句的目标句 + 转移语句的下一句）
2. 根据入口语句划分基本块
3. 画图

——— 例题练手 >_<：

(1) read x
(2) read y
(3) r = x mod y
(4) if r = 0 goto (8)
(5) x = y
(6) y = r
(7) goto (3)
(8) write y
(9) end

1. 找入口语句：(1) (3) (5) (8)
2. 划分基本块：(1)(2); (3)(4); (5)(6)(7); (8)(9)
3. 画图
   

DAG优化

(1) T0 = 3.14
(2) T1 = 2 * T0
(3) T2 = R + r
(4) A = T1 * T2
(5) B = A
(6) T3 = 2 * T0
(7) T4 = R + r
(8) T5 = T3 * T4
(9) T6 = R - r
(10) B = T5 * T6

(1) T0 = 3.14
(2) T1 = 6.28
(3) T3 = 6.28
(4) T2 = R + r
(5) T4 = T2
(6) A = 6.28 * T2
(7) T5 = A
(8) T6 = R - r
(9) B = A * T6

$END$

如下图：
第一次重构，T1 =6.28并没有因为复写传播而去掉，
下一次优化，就会被去掉，T1直接用6.28表示
T2 =R+r
A = 6.28 * T2
T6 =R - r
B = A * T6

Ps：完成复写传播的消除，就会产生无用代码，伴随着删除无用代码的操作