[GSoC 2021] Rewrite Rules Evaluation

Detailed Description

The Halide compiler uses a Term Rewriting System (see Section 2.1 here) in order to simplify complex expressions. Some basic examples include:


x / 1 -> x
x + 0 -> x

We have a list of thousands of verifiably correct rules that are not currently used in the compiler. This project would evaluate how useful these rewrite rules are, for both compile time and code execution time, individually and as sets of rules (as some rules may enable others to be used).

Some relevant metrics that we would like information on:

• Reduction in compile time
• Reduction in execution time
• Reduction in memory usage at execution time

Expected Outcomes

• Measurements that illustrate how useful subsets of the given rewrite rules are
• A subset of the given rewrite rules that have a positive impact on compile time and/or code execution time added to the Halide compiler

Stretch goal(s):

• A metric (or metrics) for determining how useful a rewrite rule is, preferably in a reusable form.

Required Skills

Some C++ experience is required for this project. Halide experience will be useful but not required.

• C++14
• Some experience with template metaprogramming

Difficulty Level

Medium

Mentors

• @rootjalex (Alexander Root)
• @abadams (Andrew Adams)