Future value based single assignment program representations and optimizations

An optimizing compiler internal representation fundamentally affects the clarity, efficiency and feasibility of optimization algorithms employed by the compiler. Static Single Assignment (SSA) as a state-of-the-art program representation has great advantages though still can be improved. This dissertation explores the domain of single assignment beyond SSA, and presents two novel program representations: Future Gated Single Assignment (FGSA) and Recursive Future Predicated Form (RFPF). Both FGSA and RFPF embed control flow and data flow information, enabling efficient traversal program information and thus leading to better and simpler optimizations. We introduce future value concept, the designing base of both FGSA and RFPF, which permits a consumer instruction to be encountered before the producer of its source operand(s) in a control flow setting. We show that FGSA is efficiently computable by using a series T1/T2/TR transformation, yielding an expected linear time algorithm for combining together the construction of the pruned single assignment form and live analysis for both reducible and irreducible graphs. As a result, the approach results in an average reduction of 7.7%, with a maximum of 67% in the number of gating functions compared to the pruned SSA form on the SPEC2000 benchmark suite. We present a solid and near optimal framework to perform inverse transformation from single assignment programs. We demonstrate the importance of unrestricted code motion and present RFPF. We develop algorithms which enable instruction movement in acyclic, as well as cyclic regions, and show the ease to perform optimizations such as Partial Redundancy Elimination on RFPF.

Quickbird satellite imagery for riparian management : characterizing riparian filter strips and detecting concentrated flow in an agricultural watershed

Riparian ecology plays an important part in the filtration of sediments from upland agricultural lands. The focus of this work makes use of multispectral high spatial resolution remote sensing imagery (Quickbird by Digital Globe) and geographic information systems (GIS) to characterize significant riparian attributes in the USDA’s experimental watershed, Goodwin Creek, located in northern Mississippi. Significant riparian filter characteristics include the width of the strip, vegetation properties, soil properties, topography, and upland land use practices. The land use and vegetation classes are extracted from the remotely sensed image with a supervised maximum likelihood classification algorithm. Accuracy assessments resulted in an acceptable overall accuracy of 84 percent. In addition to sensing riparian vegetation characteristics, this work addresses the issue of concentrated flow bypassing a riparian filter. Results indicate that Quickbird multispectral remote sensing and GIS data are capable of determining riparian impact on filtering sediment. Quickbird imagery is a practical solution for land managers to monitor the effectiveness of riparian filtration in an agricultural watershed.