主权项 |
1、一种基于数据流分析的访存合并优化方法,包括以下步骤:1)、利用编译器收集整个程序的访存操作信息,将所得信息存入一个映射表;2)、由编译器对程序中的所有基本块构造支配图和后支配图;3)、对程序中的所有读操作做反向数据流分析,更新基本块的输入数据集和输出数据集;4)、对程序中的所有写操作,进行正向数据流分析,更新基本块的输入数据集和输出数据集;5)、根据步骤3)和步骤4)所得到的基本块的输入数据集和输出数据集,对每一个访存操作,判断该访存操作所在基本块的输入数据集合中的访存操作是否可与该访存操作合并,并为输入数据集中所有可以与当前访存操作做合并的访存操作建立一个集合;6)、判断用于保存可合并的访存操作的集合是否为空,若为空,则跳转到步骤10),否则,执行下一步;7)、对步骤5)所得集合中的所有元素,分别计算各个元素对应的访存操作与当前访存操作之间的合并密度;8)、从步骤7)所得到的结果中,选择合并密度最大的访存操作,将该访存操作与当前访存操作进行合并,生成新的访存操作;9)、判断所合并的访存操作的类型,若访存操作为读操作,则将访存操作所在基本块的读操作替换为对临时寄存器的读操作,并跳转到步骤13),若访存操作为写操作,执行下一步;10)、访存操作为写操作,将访存操作所在基本块的写操作替换为对源操作数寄存器的写;11)、在写操作合并时,如果两个写操作的数据位置相邻,则到步骤13);否则,执行下一步;12)、两个写操作的数据位置不相邻,则遍历支配图中一个写操作原来所在基本块的所有祖先节点,寻找位于这些节点中的一个读操作,使得该读操作读取中间间隔部分的数据,如果找到该读操作,则在合并的写操作之前插入指令,将中间间隔部分的数据写入源操作数寄存器,如果找不到这样的读操作,则在支配图上该写操作原来所在基本块的父节点对应的基本块处,插入这样的读操作;13)、转步骤3);14)、结束。 |