An Exact Method for Analysis of Value-based Array Data Dependences

dc.contributor.authorPugh, Williamen_US
dc.contributor.authorWonnacott, Daviden_US
dc.description.abstractStandard array data dependence testing algorithms give information about the aliasing of array references. If statement 1 writes a[5], and statement 2 later reads a[5], standard techniques described this as a flow dependence, even if there was an intervening write. We call a dependence between two references to the same memory location a memory-based dependence. In contrast, if there are no intervening writes, the references touch the same value and we call the dependence a value-based dependence. There has been a surge of recent work on value-based array data dependence analysis (also referred to as computation of array data-flow dependence information). In this paper, we describe a technique that is exact over programs without control flow (other than loops) and non-linear references. We compare our proposal with the technique proposed by Paul Feautrier, which is the other technique that is complete over the same domain as ours. We also compare our work with that of Tu and Padua, a representative approximate scheme for array privatization. (Also cross-referenced as UMIACS-TR-93-137)en_US
dc.format.extent263992 bytes
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3196en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-93-137en_US
dc.titleAn Exact Method for Analysis of Value-based Array Data Dependencesen_US
dc.typeTechnical Reporten_US


Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
257.8 KB
Postscript Files
Thumbnail Image
310.39 KB
Adobe Portable Document Format
Auto-generated copy of