000189648 001__ 189648
000189648 005__ 20181203023301.0
000189648 0247_ $$2doi$$a10.1145/2480359.2429128
000189648 022__ $$a0362-1340
000189648 02470 $$2ISI$$a000318629900042
000189648 037__ $$aARTICLE
000189648 245__ $$aOptimizing Data Structures in High-Level Programs New Directions for Extensible Compilers based on Staging
000189648 260__ $$bAssoc Computing Machinery$$c2013$$aNew York
000189648 269__ $$a2013
000189648 300__ $$a14
000189648 336__ $$aJournal Articles
000189648 520__ $$aHigh level data structures are a cornerstone of modern programming and at the same time stand in the way of compiler optimizations. In order to reason about user or library-defined data structures, compilers need to be extensible. Common mechanisms to extend compilers fall into two categories. Frontend macros, staging or partial evaluation systems can be used to programmatically remove abstraction and specialize programs before they enter the compiler. Alternatively, some compilers allow extending the internal workings by adding new transformation passes at different points in the compile chain or adding new intermediate representation (IR) types. None of these mechanisms alone is sufficient to handle the challenges posed by high level data structures. This paper shows a novel way to combine them to yield benefits that are greater than the sum of the parts. Instead of using staging merely as a front end, we implement internal compiler passes using staging as well. These internal passes delegate back to program execution to construct the transformed IR. Staging is known to simplify program generation, and in the same way it can simplify program transformation. Defining a transformation as a staged IR interpreter is simpler than implementing a low-level IR to IR transformer. With custom IR nodes, many optimizations that are expressed as rewritings from IR nodes to staged program fragments can be combined into a single pass, mitigating phase ordering problems. Speculative rewriting can preserve optimistic assumptions around loops. We demonstrate several powerful program optimizations using this architecture that are particularly geared towards data structures: a novel loop fusion and deforestation algorithm, array of struct to struct of array conversion, object flattening and code generation for heterogeneous parallel devices. We validate our approach using several non trivial case studies that exhibit order of magnitude speedups in experiments.
000189648 6531_ $$aDesign
000189648 6531_ $$aLanguages
000189648 6531_ $$aPerformance
000189648 6531_ $$aStaging
000189648 6531_ $$aCode Generation
000189648 6531_ $$aData Structures
000189648 6531_ $$aExtensible Compilers
000189648 700__ $$0243345$$g185682$$uEPFL, Zurich, Switzerland$$aRompf, Tiark
000189648 700__ $$aSujeeth, Arvind K.
000189648 700__ $$0246589$$g164625$$uEPFL, Zurich, Switzerland$$aAmin, Nada
000189648 700__ $$aBrown, Kevin J.
000189648 700__ $$0243781$$g202774$$uEPFL, Zurich, Switzerland$$aJovanovic, Vojin
000189648 700__ $$aLee, Hyoukjoong
000189648 700__ $$0246590$$g170823$$uEPFL, Zurich, Switzerland$$aJonnalagedda, Manohar
000189648 700__ $$aOlukotun, Kunle
000189648 700__ $$aOdersky, Martin$$uEPFL, Zurich, Switzerland$$g126003$$0241835
000189648 773__ $$j48$$tAcm Sigplan Notices$$k1$$q497-510
000189648 909C0 $$xU10409$$0252187$$pLAMP
000189648 909CO $$pIC$$particle$$ooai:infoscience.tind.io:189648
000189648 917Z8 $$x166927
000189648 937__ $$aEPFL-ARTICLE-189648
000189648 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000189648 980__ $$aARTICLE