| 主权项 |
一种利用出入边关系的剖分信息构建超级块的方法，其特征在于包括如下步骤：1)定义基本块的边为执行流从一个基本块的出口点离开，由另一个基本块的入口点进入，继续执行操作的形式表示；基本块的出边为就当前基本块而言，执行流从当前基本块的出口点离开，进入下个基本块的边；基本块的入边为就当前基本块而言，执行流离开上个基本块，由当前基本块的入口点进入的边；出入边关系的剖分信息为执行流通过当前基本块时，所经过的当前基本块入边和出边的对应关系，以及这一过程的执行次数；剖分信息数据结构设计为以入边为第一索引，出边为第二索引的双重单向链表；2)实现一个剖分信息记录函数或独立线程，对当前基本块的出入边关系和这一过程的发生次数进行记录，并保存在当前基本块的剖分信息数据结构中；在动态二进制翻译器翻译某个基本块时，在基本块的开头插入指令，使此块在每次执行前，对一个记录此块的执行次数的统计变量加一；在翻译器执行当前基本块时，根据动态二进制翻译领域的链接技术，为上一基本块做链接时，在上一基本块的链接项中添加指令，使此链接项在之后命中后，调用剖分信息记录函数或激活剖分信息记录线程，为上一基本块记录出入边关系的剖分信息；在当前基本块第一次被执行后，执行流回到翻译器，翻译器调用剖分信息记录函数或激活剖分信息记录线程，初始化当前基本块的剖分信息数据结构；3)设定构建超级块的条件：①开始块的执行次数需高于事先设定的开始块执行次数下限，②各个超级块之间不能有重复的基本块存在，③每个基本块从当前入边进入并从相应出边离开的执行次数不能低于事先设定的构建边执行次数下限，④构建的超级块块序列所能包含的基本块个数不能超过某一上限；4)在采用动态构建时，某基本块一旦满足条件①②，则将此基本块作为开始块，在采用静态构建时，根据每个基本块的执行次数，将基本块按降序排列，从排序完的第一个基本块开始，逐个进行判断是否满足条件①②，将满足条件的基本块作为开始块；5)将开始块记录为块序列首个元素，从开始块的剖分信息中统计出每个出边的执行次数，选择次数最多者作为构建边；6)检查构建边是否满足条件③，如满足，将构建边所指向的基本块作为当前基本块，并将构建边作为当前基本块的选定入边；如不满足，停止此超级块构建过程，跳至步骤8)；7)检查当前基本块是否满足条件②以及块序列是否满足条件④，如满足，将当前基本块添加至块序列末尾，根据当前基本块的选定入边查找当前基本块的剖分信息，在选定入边对应的出边中选定执行次数最多的出边，作为继续构建超级块的构建边，返回步骤6)；8)在采用动态构建时，根据所得的块序列，完成重新组织和优化过程，并返回步骤4)继续构建下个超级块的块序列；在采用静态优化时，将块序列保存，返回步骤4)继续构建下个超级块的块序列，等遍历完所有块后，再根据获取的所有块序列，完成重新组织和优化过程。 |
