Inlining doesn't work where expected

[m4tiz5zktonj]

I noticed, that sometimes inlinling doesn't work as I expect it. I created simple test functions that cover all (I hope) cases I have.

Some may be a variation of the forbidden cases described in the wiki, and I don't realize that yet. Some of them may be caused by the issues with the optimizer. I hope you can explain the results I see.

The examples have the following structure: functions inline* are annotated with (:inline) and expected to be inlined and removed from the code, functions function* call these inline*s and expected to contain the body of the inlined function, functions aux* are some helper functions, functions expected* are the expected result of the inlining operation for corresponding inline* and function* functions.

I tried to toggle prettierMonkeyC.iterateOptimizer, but it doesn't seem to affect the results.

---

import Toybox.Lang;

(:keep)
function function1(b as Boolean) as Number {
    // While inlining inline1: This function can only be inlined in statement, assignment, if or return contexts
    // While inlining inline1: Function didn't end with a return statement
    return inline1(b);
}
(:keep)
function function2(b as Boolean) as Number {
    // While inlining inline1: This function can only be inlined in statement, assignment, if or return contexts
    // While inlining inline1: Function didn't end with a return statement
    var x = inline1(b);
    return x;
}

(:inline)
function inline1(b as Boolean) as Number {
    if (b) {
        return 1;
    } else {
        return 0;
    }
}

(:keep)
function expected1(b as Boolean) as Number {
    if (b) {
        return 1;
    } else {
        return 0;
    }
}
(:keep)
function expected2(b as Boolean) as Number {
    // Either this or as in "expected1" after all other optimizations
    var x;
    if (b) {
        x = 1;
    } else {
        x = 0;
    }
    return x;
}

Generally, the optimizer can't inline a function unless it has a single return statement, and the return statement must be last, both in lexical order and in control flow order. This is because MonkeyC doesn't support goto, making it very hard to mimic the control flow produced by multiple returns.

I guess, it contradicts this requirement, but I don't understand, why it can't be inlined. Though inline1 has multiple return statements, it is pretty easy to do it manually.

I see the same results for switch with direct returns in all cases with default at the end in the inline* function.

---

import Toybox.Lang;

(:keep)
function function3(i as Number) as Number {
    // While inlining inline3: This function can only be inlined in statement, assignment, if or return contexts
    return inline3()[i];
}

(:inline)
function inline3() as Array<Number> {
    var a = [0] as Array<Number>;
    return a;
}

(:keep)
function expected3(i as Number) as Number {
    return ([0] as Array<Number>)[i];
}

Inlining works with direct return [0] as Array<Number>;. I'd expect iterateOptimizer to do the job on the second pass.

---

import Toybox.Lang;

(:keep)
function function4(b as Boolean, x as Number) as Float {
    // While inlining inline4: This function can only be inlined in statement, assignment, if or return contexts
    return b ? 0.0 : inline4(x as Number);
}

(:inline)
function inline4(x as Number?) as Float {
    return x != null ? x.toFloat() : 0.0;
}

(:keep)
function expected4(b as Boolean, x as Number) as Float {
    return b ? 0.0 : (x != null ? x.toFloat() : 0.0);
}

It works with inline4(x) instead of inline4(x as Number). Originally x is declared as Number? in function4, but it is guaranteed to be Number, if b is false, so I use cast as Number.

---

import Toybox.Application;
import Toybox.Lang;

class Class5 {
    private var s as String = inline5();

    // The inline function inline5 was not removed from the program
    (:inline)
    private function inline5() as String {
        return Application.loadResource(Rez.Strings.AppName) as String;
    }
}

class ExpectedClass5 {
    private var s as String = Application.loadResource(Rez.Strings.AppName) as String;
}

There are no While inlining ... message with the explanation for this case.

---

import Toybox.Lang;
import Toybox.System;

class Class61 {
    private static var x as Number = 0;

    (:keep)
    static function classMethod() as Number {
        return x;
    }
}

class Class62 {
    // The inline function classMethod was not removed from the program
    (:inline)
    static function classMethod() as Number {
        return Class61.classMethod();
    }
}

class Class63 {
    (:keep)
    function function6() as Number {
        return Class62.classMethod();
    }
}

class ExpectedClass63 {
    (:keep)
    function function6() as Number {
        return Class61.classMethod();
    }
}

It works as expected, if I rename Class61.classMethod() to something else.

---

import Toybox.Lang;
import Toybox.Time;
import Toybox.Time.Gregorian;

(:keep)
function function7() as Number {
    // While inlining inline7: This function can only be inlined in statement, assignment, if or return contexts
    return inline7(Time.now()).value();
}

(:inline)
function inline7(time as Moment) as Moment {
    return aux7(time);
}

(:keep)
function aux7(time as Moment) as Moment {
    var timeInfo = Gregorian.info(time, Time.FORMAT_SHORT);

    return Gregorian.moment({
        :year => timeInfo.year,
        :month => timeInfo.month as Number,
        :day => timeInfo.day,
        :hour => 0,
        :minute => 0,
        :second => 0,
    });
}

(:keep)
function expected7() as Number {
    return aux7(Time.now()).value();
}

It works, if I directly return result of inline7 function call from function7 (with updated return type in function7 declaration, ofc).

---

import Toybox.Lang;
import Toybox.System;

(:keep)
function function8(x as Number) as Void {
    // While inlining inline8: This function can only be inlined in statement, assignment, if or return contexts
    aux8(inline8(x));
}

(:inline)
function inline8(x as Number) as Number {
    var y = x;

    return x + y;
}

(:keep)
function aux8(x as Number) as Void {
    System.println(x);
}

(:keep)
function expected8(x as Number) as Void {
    // Either this or "aux8(x + x)" after all other optimizations

    var y = x;

    var z = x + y;

    aux8(z);
}

I see no reasons for it not to be inlined, especially with enabled iterateOptimizer.

---

Thank you!

[markw65]

Lots of questions!

So most of the answer is that the inliner was written fairly early on, before I had implemented any control flow analysis. So I used some simple heuristics to determine "inlinability".

With the more sophisticated control and data-flow analysis I do now, I could widen the range of suitable functions - but currently control and data-flow analysis is done per-function as I'm optimizing it; and we need information about the callee, not the caller's function. Still, I could cache information about the callee when I optimize it, and then use that cached information when trying to inline it.

There's a lot of different cases to cover, so I'll split my answer.

[markw65]

Why can't we inline the following in return context:

(:inline)
function inline1(b as Boolean) as Number {
    if (b) {
        return 1;
    } else {
        return 0;
    }
}

And the answer is because the last statement lexically is not a return (the last statement is actually the if). And the reason, as I said above, is that I use pretty simple heuristics for determining whether the control flow is suitable. As you say, this case is fine, but here's an example of what could go wrong:

(:inline)
function inline1(n as Number) as Number {
    if (n == 0) {
        return 1;
    } else if (n == 1) {
        return 0;
    }
}

function caller(b as Boolean, n as Number) as Number {
    if (b) {
        return inline1(n);
    }
    <Dangerous code that must never be executed when b is true>;
}

If I inline inline1 into caller, I get:

function caller(b as Boolean, n as Number) as Number {
    if (b) {
        if (n == 0) {
            return 1;
        } else if (n == 1) {
            return 0;
        }
    }
    <Dangerous code that must never be executed when b is true>;
}

And now when b is true, and n is 2, we execute the dangerous code.

OK, so Garmin's compiler would have complained about this, because inline1 can return null. But the user may not have the type checker enabled; or they could have declared inline1 as returning Number?

So I could fix this, by inserting return; after the inlined body - and now the behavior would be unchanged. But if I did that with your original example, Garmin's compiler would refuse to compile it because of the unreachable return; statement!

So again - with suitable control flow analysis, I could determine that your example is safe, and that mine is safe, but needs a trailing return;.

Alternatively, you could just rewrite your example as:

(:inline)
function inline1(b as Boolean) as Number {
    if (b) {
        return 1;
    } 
    return 0;
}

And it should now work in return context.

[markw65]

Why can't we inline the following in assignment context:

(:inline)
function inline1(b as Boolean) as Number {
    if (b) {
        return 1;
    } else {
        return 0;
    }
}

Again, as you say, for this example, inlining is easy - you just replace each return <E> with x = <E>;. But here's the problem:

(:inline)
function inline1(b as Boolean) as Number {
    if (b) {
        return 1;
    } 
    System.println("b was false");
    return 0;
}

If you try that substitution, not only do you execute the println when b is false, but you always end up with x set to false.

If MonkeyC had a goto, we could easily fix this, but it doesn't. This particular case could be fixed by putting the remainder of the function in an else - but that wouldn't work if the return was inside a switch, or a loop of some sort.

Of course, there is always a way to rewrite the code and inline it such that the result does the same as the non-inlined version. But it may involve new variables as flags, and could be way less efficient. So I just felt (and continue to feel!) that it's better to rewrite your inline function to conform to what the optimizer expects - a single return at the end of the function:

(:inline)
function inline1(b as Boolean) as Number {
    var x;
    if (b) {
        x = 1;
    } else {
        x = 0;
    }
    return x;
}

[markw65]

Why doesn't iterateOptimizer do what I expect?

You're right, it should. I added it to solve a particular issue where chains of unused functions (especially inline functions that called other inlined functions) didn't get removed. So it only triggers a new iteration when at least one entity is removed from the program - it doesn't care that the body of a function changed, unless it eliminates a reference to something.

So yes, those examples should probably work.

[markw65]

There are no While inlining ... message with the explanation for this case

The optimizer doesn't do any inlining for non-local variable initializers.

[markw65]

It works as expected, if I rename Class61.classMethod() to something else

Again, this is because I wrote the inlining pass before doing more general analysis. When it sees a call to Class61.classMethod(), it assumes that any of the methods named classMethod could be called. Given that it's a static method being called statically, I should really handle that one.

Even with more general x.classMethod() calls, the optimize and analysis passes actually do a much better job now of identifying which version of classMethod is called - but the cleanup pass that removes unused functions doesn't currently use that information.