Abstract: The authors present a basic-block reordering method that detects typical structures in the control-flow graph. It utilizes the architecture-specific branch cost model and execution possibilities of control-flow edges to estimate the possible layout costs of specific sub-structures. The layout with the minimal cost estimation would be chosen. The authors further investigate a novel approach to apply neural network to predict execution possibility for each edge. A set of programs are chosen to record particular static information of the edges in the typical structures. The data include the knowledge about the relationship between static program features and dynamic behaviors. It is fed to train an improved back propagation neural network (RPROP). The algorithm is implemented based on a simple pipeline UniCore microprocessor. Experiment result shows that it improves programs?performance about 8% , which indicates that the execution possibility of edges may be predicted using machine learning techniques.

Key words: artificial neural network, basic-block reordering, structural analysis, compiler optimization

摘要： 基于程序的控制流动信息和体系结构跳转代价模型, 使用人工神经网络预测控制流边的执行概率, 利用子结构分析技术开展基本块重排。程序的控制流边信息被选择作为神经网络的训练数据, 这些信息包含了该边的静态特征和动态行为之间的联系。基于弹性反馈反向传播( RPROP) 神经 网络, 在 UniCore 处理器上实现了采用子结构分析的基本块重排算法。评测结果表明, 此算法可获得与利用剖视信息的优化算法相同的程序性能优化效果, 不依赖于剖视信息的特性, 可很好地扩展该基本块重排算法的应用范围。

关键词: 人工神经网络, 基本块重排, 子结构分析, 编译优化