rfactored split rvars have qualified names

@abadams

The following pipeline causes an error when passed to the Anderson2021 autoscheduler:

        if (true) {
            ImageParam im(Float(32), 2);

            Func max_fn{"max_fn"}, sum_fn{"sum_fn"}, output{"output"};
            Var u{"u"};
            RDom r(0, 8192);
            RVar ri{"ri"};

            max_fn(y) = Float(32).min();
            max_fn(y) = max(max_fn(y), im(r, y));

            sum_fn(y) += Halide::exp(im(r, y) - max_fn(y));
            sum_fn.update(0).split(r, r, ri, 8);
            sum_fn.update(0).rfactor(r, u);

            output(x, y) = sum_fn(x);

            output.set_estimates({{0, 8192}, {0, 32768}});

            Pipeline(output).apply_autoscheduler(target, params);
        }

This is in the context of test/autoschedulers/anderson2021/test.cpp. The error happens during schedule application / serialization. The factored RVar has the name r6$x.r6$x which is passed to var_name_match via dim_match. This produces the error:

Unhandled exception: Internal Error at /home/alex/Development/halide/src/Func.cpp:324 Condition failed: var.find('.') == string::npos: var_name_match expects unqualified names for the second argument. Name passed: r6$x.r6$x

I'm not sure if this is a bug with rfactor or with Anderson2021. Maybe @abadams can weigh in on this point? I didn't see the old rfactor implementation do anything to de-qualify the names.

Add test case for issue #8557

@jansel

This was minimized from a PyTorch test case from @jansel

First, a little background. A qualified name is one which contains a . character. An unqualified name does not. A Var is an unqualified name with twofold purpose: first, to bind names to the pure Dims of Funcs upon defintition; second, to resolve to (or "match") a (pure) Dim in the context of a scheduling directive. When used for this second purpose, a single Var may resolve to uncorrelated Dims of different funcs in different scheduling contexts.

Let us now review some salient facts for analyzing this issue as it applies to RVars:

An RVar is either one of two different things:
1. A handle to a dimension of an RDom. They are represented as a pointer to the RDom and a dimension index. When an update definition uses such an RVar, the entire RDom is added to the schedule. An update definition may only have a single RDom.
2. A name, like a Var. Such RVars are created directly by the user. In addition to being unqualified, their names must not contain the $ character.
A Var/RVar is resolved in the context of a Stage by searching for a Dim whose name either (a) matches the Var/RVar name exactly, in the case that the Dim name is unqualified, or (b) ends with the sequence .<name>. Note that this is not the same as the last .-separated component matching the Var.
A split directive takes an "old" Dim and replaces it with a pair of "outer" and "inner" Dims. These Dims are subject to Var/RVar resolution. Once the old Dim is resolved, names for the outer and inner Dims are determined by prepending the name of the old Dim, followed by a ., to the names of the outer and inner Vars/RVars, respectively. Splitting an RVar named r0$x into outer and inner RVars named ro and ri results in new dims named r0$x.ro and r0$x.ri, respectively.

As an aside, the names of the RVars in a newly constructed RDom are determined by first either (a) a non-unqualifying, user-specified prefix or (b) a uniquely generated prefix beginning with r and a number; this is followed by a $ and this prefix is applied to the sequence x, y, z, w, followed by the natural numbers beginning at 4. For example, a default-constructed RDom with six dimensions would have RVars named r0$x, r0$y, r0$z, r0$w, r0$4, r0$5. Had the user given the prefix "foo" as in case (1), the names would be foo$x, foo$y, and so forth.

The suspect behavior at the heart of this issue is that when rfactor() factors an RDom into its "preserved" and "intermediate" components, it builds two new RDoms from scratch. This is necessary so that the two definitions have separate RDoms (Fact 1i).

The names of the factored RVars in the existing implementation are inherited from the names of the Dims at the point in scheduling where factoring happened. However, if that Dim was the result of a split, the name might be qualified (Fact 3), which means it is impossible to manually create an RVar that references it (Fact 1ii). The dubious test in (Fact 2) is at the heart of why everything works anyway: the Dim name is not analyzed for .-separated components; an unstructured string suffix is checked.

Attempting to serialize a schedule involving an RVar with an invalid name is what leads to this bug.

One solution might be to give fresh names to the factored RDom's RVars. Unfortunately, this invalidates schedules, as existing RVars (of either type) no longer refer to the RVars of the RDoms in either the preserved or intermediate Funcs. That is, while the original RDom might have had RVars names r0$x and r0$y, the new RDoms will have one dimension each, named r1$x and r2$x (note this is not r2$y).

So we might try to work around this by rename()-ing the unqualified RVars back to their pre-factored Dim names. This works for the compiler, but as the Funcs are now partially scheduled, the autoscheduler refuses to proceed, issuing an error along the lines of:

Unhandled exception: Error: The Func "f" has scheduling directive(s) applied to it; you must remove these, or conditionalize them using `if (!auto_schedule)`, to use the autoscheduler on this pipeline.

At this point, I am not sure how best to proceed.

The "use fresh names and rename to the old dim names" approach is in the pytorch-bugfixes branch: https://github.com/halide/Halide/tree/pytorch-bugfixes

What's wrong with this approach:

Instead of letting the two new RDoms have the default names and adding rename directives, just construct the new RDoms with the desired unqualified names via the ReductionDomain constructor that takes an arbitrary vector of ReductionVariables.

Instead of letting the two new RDoms have the default names and adding rename directives, just construct the new RDoms with the desired unqualified names via the ReductionDomain constructor that takes an arbitrary vector of ReductionVariables.

Apparently in my last attempt to do this, I failed to correctly implement either the predicate fixup or dims list fixup. Not sure what went wrong, but appears to be working in my latest attempt. Just force-pushed my pytorch-bugfixes branch.

Add test case for issue #8557

Navigation Menu

Repository navigation

rfactored split rvars have qualified names #8557

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

rfactored split rvars have qualified names #8557

Description

Activity

alexreinking commented on Jan 22, 2025

alexreinking commented on Jan 27, 2025

alexreinking commented on Jan 27, 2025

abadams commented on Jan 27, 2025

alexreinking commented on Jan 28, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions