Sparse Code Generation for Imperfectly Nested Loops with Dependences

Standard restructuring compiler tools are based on polyhedral algebra and cannot be used to analyze or restructure sparse matrix codes. Wehave recently shown that tools based on relational algebra can be used to generate an efficient sparse matrix program from the corresponding dense matrix program and a specification of the sparse matrix format. This work was restricted to DO-ALL loops and loops with reductions. In this paper, we extend this approachto loops with dependences. Although our results are restricted to Compressed Hyperplane Storage formats, they apply to both perfectly nested loops and imperfectly nested loops