-
LoopStack: a Lightweight Tensor Algebra Compiler Stack
Authors:
Bram Wasti,
José Pablo Cambronero,
Benoit Steiner,
Hugh Leather,
Aleksandar Zlateski
Abstract:
We present LoopStack, a domain specific compiler stack for tensor operations, composed of a frontend, LoopTool, and an efficient optimizing code generator, LoopNest. This stack enables us to compile entire neural networks and generate code targeting the AVX2, AVX512, NEON, and NEONfp16 instruction sets while incorporating optimizations often missing from other machine learning compiler backends. W…
▽ More
We present LoopStack, a domain specific compiler stack for tensor operations, composed of a frontend, LoopTool, and an efficient optimizing code generator, LoopNest. This stack enables us to compile entire neural networks and generate code targeting the AVX2, AVX512, NEON, and NEONfp16 instruction sets while incorporating optimizations often missing from other machine learning compiler backends. We evaluate our stack on a collection of full neural networks and commonly used network blocks as well as individual operators, and show that LoopStack generates machine code that matches and frequently exceeds the performance of in state-of-the-art machine learning frameworks in both cases. We also show that for a large collection of schedules LoopNest's compilation is orders of magnitude faster than LLVM, while resulting in equal or improved run time performance. Additionally, LoopStack has a very small memory footprint - a binary size of 245KB, and under 30K lines of effective code makes it ideal for use on mobile and embedded devices.
△ Less
Submitted 1 May, 2022;
originally announced May 2022.
-
Searching for Replacement Classes
Authors:
Malavika Samak,
Jose Pablo Cambronero,
Martin C. Rinard
Abstract:
Software developers must often replace existing components in their systems to adapt to evolving environments or tooling. While traditional code search systems are effective at retrieving components with related functionality, it is much more challenging to retrieve components that can be used to directly replace existing functionality, as replacements must account for more fundamental program pro…
▽ More
Software developers must often replace existing components in their systems to adapt to evolving environments or tooling. While traditional code search systems are effective at retrieving components with related functionality, it is much more challenging to retrieve components that can be used to directly replace existing functionality, as replacements must account for more fundamental program properties such as type compatibility. To address this problem, we introduce ClassFinder, a system which given a query class Q, and a search corpus S, returns a ranked subset of classes that can replace Q and its functionality. ClassFinder produces afield and method mapping between the classes that can provide useful hints to a developer and can be used to effectively refine the ranking of candidate replacement classes. Our technique leverages the complementary strengths of a distributed embeddings-based search and type-based analysis, using the former to prune down candidates for an optimization-based approach based on the latter. ClassFinder retrieves replacement classes, along with a type-aware field/method mapping between classes. We evaluate ClassFinder on a search space of ~600thousand open sourceJava classes. Querying ClassFinder with 24 known Java classes provided meaningful replacement classes and mappings, in many cases producing complete mappings with functionally identical replacement classes.
△ Less
Submitted 11 October, 2021;
originally announced October 2021.
-
Inferring Drop-in Binary Parsers from Program Executions
Authors:
Thurston H. Y. Dang,
Jose P. Cambronero,
Martin C. Rinard
Abstract:
We present BIEBER (Byte-IdEntical Binary parsER), the first system to model and regenerate a full working parser from instrumented program executions. To achieve this, BIEBER exploits the regularity (e.g., header fields and array-like data structures) that is commonly found in file formats. Key generalization steps derive strided loops that parse input file data and rewrite concrete loop bounds wi…
▽ More
We present BIEBER (Byte-IdEntical Binary parsER), the first system to model and regenerate a full working parser from instrumented program executions. To achieve this, BIEBER exploits the regularity (e.g., header fields and array-like data structures) that is commonly found in file formats. Key generalization steps derive strided loops that parse input file data and rewrite concrete loop bounds with expressions over input file header bytes. These steps enable BIEBER to generalize parses of specific input files to obtain parsers that operate over input files of arbitrary size. BIEBER also incrementally and efficiently infers a decision tree that reads file header bytes to route input files of different types to inferred parsers of the appropriate type. The inferred parsers and decision tree are expressed in an IR; separate backends (C and Perl in our prototype) can translate the IR into the same language as the original program (for a safer drop-in replacement), or automatically port to a different language. An empirical evaluation shows that BIEBER can successfully regenerate parsers for six file formats (waveform audio [1654 files], MT76x0 .BIN firmware containers [5 files], OS/2 1.x bitmap images [9 files], Windows 3.x bitmaps [9971 files], Windows 95/NT4 bitmaps [133 files], and Windows 98/2000 bitmaps [859 files]), correctly parsing 100% (>= 99.98% when using standard held-out cross-validation) of the corresponding corpora. The regenerated parsers contain automatically inserted safety checks that eliminate common classes of errors such as memory errors. We find that BIEBER can help reverse-engineer file formats, because it automatically identifies predicates for the decision tree that relate to key semantics of the file format. We also discuss how BIEBER helped us detect and fix two new bugs in stb_image as well as independently rediscover and fix a known bug.
△ Less
Submitted 19 April, 2021;
originally announced April 2021.
-
Characterizing Developer Use of Automatically Generated Patches
Authors:
José Pablo Cambronero,
Jiasi Shen,
Jürgen Cito,
Elena Glassman,
Martin Rinard
Abstract:
We present a study that characterizes the way developers use automatically generated patches when fixing software defects. Our study tasked two groups of developers with repairing defects in C programs. Both groups were provided with the defective line of code. One was also provided with five automatically generated and validated patches, all of which modified the defective line of code, and one o…
▽ More
We present a study that characterizes the way developers use automatically generated patches when fixing software defects. Our study tasked two groups of developers with repairing defects in C programs. Both groups were provided with the defective line of code. One was also provided with five automatically generated and validated patches, all of which modified the defective line of code, and one of which was correct. Contrary to our initial expectations, the group with access to the generated patches did not produce more correct patches and did not produce patches in less time. We characterize the main behaviors observed in experimental subjects: a focus on understanding the defect and the relationship of the patches to the original source code. Based on this characterization, we highlight various potentially productive directions for future developer-centric automatic patch generation systems.
△ Less
Submitted 22 November, 2019; v1 submitted 15 July, 2019;
originally announced July 2019.