Browse Prior Art Database

Data Dependence Analysis Using Value Numbering

IP.com Disclosure Number: IPCOM000241211D
Publication Date: 2015-Apr-03
Document File: 5 page(s) / 138K

Publishing Venue

The IP.com Prior Art Database

Abstract

The paper presents a method for efficient computation of data dependences using value numbering and induction information. This allows the treatment of a wide range of dependence problems and computes in polynomial complexity loop dependences, intra-iteration loop dependences and out-of-loop dependences for array, pointer, structure, vectorised and inline assembly code accesses. The method helps the compiler compute necessary data dependence information that enable a range of transformations as vectorization, instructions scheduling or software pipelining.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 33% of the total text.

Data Dependence Analysis

Using Value Numbering

Abstract

The paper presents a method for efficient computation of data dependences using value numbering and induction information. This allows the treatment of a wide range of dependence problems and computes in polynomial complexity loop dependences, intra-iteration loop dependences and out-of-loop dependences for array, pointer, structure, vectorised and inline assembly code accesses. The method helps the compiler compute necessary data dependence information that enable a range of transformations as vectorization, instructions scheduling or software pipelining.

Introduction

Data dependence analysis is an enabler for a multitude of compiler transformations, such as vectorization, instruction scheduling or software pipelining. This allows faster execution of loop and out of loop code. The common approaches for data dependence analysis are integer linear programming or value based array data analysis. An alternative is using value numbering analysis together with induction information allows. The algorithm analyzes data dependences between two memory accesses in polynomial time and can be applied both during high level and low level compiler transformations. This allows handling a wide range of cases of interest – scalar, vector, array, pointer, inline assembly and vector code data dependences – using information already existing in the compiler (induction and value numbering), without using integer linear programming or boundary checks.

Value numbering incorporates data flow information and allows handling out-of-loop, intra and inter-iteration dependences, while induction information is used to analyze inter-iteration behavior and distances. The algorithm computes equivalence/constant differences between various memory accesses on both array style and flat style memory accesses. For flat style memory accesses value numbering computes the distance between the accessed addresses. In the case of array style memory accesses, induction information together with value numbering analyzes the relation between indexes, the latter one also computing the distance between base addresses.

A special case is the one for data dependences particular to the first iteration of the loop (which change in following iterations), which are also computed. This helps optimizing the code after loop peeling or software pipelining without re-running data dependence analysis after the transformation that extracts the first iteration of the loop.

Algorithm for Data Dependence Analysis Using Value Numbering

The algorithm considers all memory accesses in a function / code region and gathers the following information for each accesses:

-          Loop iteration stride – the distance in bytes between the addresses accessed in consecutive iterations through the same access; a valid value for the field is UNKNOWN, which still allows the computation of intra-iteration data dependences

-          The flat expression describing the accessed mem...