Write a Blog >>
Mon 19 Jun 2017 11:15 - 11:40 at Aula Master - Compiler Optimizations Chair(s): Uday Bondhugula

List comprehensions provide a powerful abstraction mechanism for expressing computations over ordered collections of data declaratively without having to use explicit iteration constructs. This paper puts forth effectful comprehensions as an elegant way to describe list comprehensions that incorporate loop carried state. This is motivated by operations such as compression/decompression and serialization/deserialization that are common in log/data processing pipelines and require loop-carried state when processing an input stream of data.

We build on the underlying theory of symbolic transducers to fuse pipelines of effectful comprehensions into a single representation, from which efficient code can be generated. Using background theory reasoning with an SMT solver our fusion and subsequent reachability based branch elimination algorithms can significantly reduce the complexity of the fused pipelines. Our implementation shows significant speedups over reasonable hand-written code (3.4X, on average) and traditionally fused version of the pipeline (2.6X, on average) for a variety of examples, including scenarios for extracting fields with regular expressions, processing XML with XPath, and running queries over encoded data.

Mon 19 Jun

Displayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change

10:50 - 12:30
Compiler OptimizationsPLDI Research Papers at Aula Master
Chair(s): Uday Bondhugula Indian Institute of Science
10:50
25m
Talk
Cache Locality Optimization for Recursive Programs
PLDI Research Papers
Jonathan Lifflander , Sriram Krishnamoorthy Pacific Northwest National Laboratories
11:15
25m
Talk
Fusing Effectful Comprehensions
PLDI Research Papers
Olli Saarikivi , Margus Veanes Microsoft Research, Todd Mytkowicz , Madan Musuvathi Microsoft Research
11:40
25m
Talk
Generalizations of the Theory and Deployment of Triangular Inequality for Compiler-Based Strength Reduction
PLDI Research Papers
Yufei Ding North Carolina State University, Lin Ning North Carolina State University, Hui Guan North Carolina State University, Xipeng Shen North Carolina State University
Media Attached
12:05
25m
Talk
ALIVE-INFER: Data-Driven Precondition Inference for Peephole Optimizations in LLVM
PLDI Research Papers
David Menendez Rutgers University, Santosh Nagarakatte Rutgers University, USA
Media Attached