Possible constructor inlining improvements

[basro]

Goal

The goal is to make this compile to code with 0 allocations:

for ( i in fibonacci().skip(4).take(10) ) {
	trace(i);
}

For this I would like these constructors to inline properly:

class Main {
	static function main() {
		var fib = new Fib();
		var take = new Take(fib, 10);
		
		take.next();
	}
}

// Iterator that takes a limited number of elements from another iterator.
class Take<T> {
	var from : Iterator<T>;
	var count : Int;

	public inline function new(from:Iterator<T>, count : Int) {
		this.from = from;
		this.count = count;
	}
	public inline function hasNext() return from.hasNext() && count > 0;
	public inline function next() {
		count--;
		return from.next();
	}
}

// Fibonnacci iterator
class Fib {
	var a = 0;
	var b = 1;

	public inline function new() {}
	public inline function hasNext() return true;
	public inline function next() {
		var r = a + b;
		a = b;
		b = r;
		return r;
	}
}

But currently only take iterator is inlined, fib is not.

Why it currently doesn't work

The inline constructors filter receives code with functions already inlined, but logically, before the constructors are inlined the call to Take's from.next() couldn't have been inlined.

For the main function the inline constructors filter receives this:

var fib = new Fib(); // Fib is considered for inlining
var take = new Take(fib, 10); // Take is considered for inlining, creates var take_from which aliases Fib.

take.count--;
take.from.next(); // take.from is alias of Fib but "next" is not one of it's inlined fields, accessing it causes Fib inlining to be cancelled.

The constructor inliner output is then:

var fib : Fib = new Fib();
var take_from : Iterator<Int> = fib;
var take_count : Int = 0;

take_count--;
take_from.next();

Proposal on how to make this work

I propose implementing a new filter which "Tightens" the types of local variables and then inlines method calls from the tightened local variables.

With "Tightening" the types I mean changing the local variable types to be as specific as possible.
For example in the output of the constructor inliner above, the variable take_from would be "tightened" from Iterator<Int> to Fib.
The type of expressions that depend on this variable would also get updated.

This filter would inline the take_from.next() call since it is now Fib.next() instead of Iteartor.next()

With this filter implemented the inline constructors filter can be altered so that if it inlined at least one constructor then the output goes through the tighten_and_inline filter, and then if the tighten_and_inline filter reports that it managed to inline a new function then the inline constructors filter is run again on that output. The loop ends when one of the filters failed to do any new inlining.

Possibly undesired side effects

Disable inlining tricks break

	var fib : Iterator<Int> = new Fib();
	fib.next(); // Function doesn't get inlined. Unrelated to inline constructor.

Casting to a less specific type as a trick to disable inlining would not work with this filter.

Performance

for( i in fibonacci().take(10).skip(4).map(i->i+1) ) trace(i);

Each of the .method there cause one extra pass of the constructor inliner, 4 passes total...
Might get slow.

The good news is that if you have multiple for loops:

for( i in fibonacci().take(10).skip(4).map(i->i+1) ) trace(i);
for( i in fibonacci().take(10).skip(4).map(i->i+1) ) trace(i);
for( i in fibonacci().take(10).skip(4).map(i->i+1) ) trace(i);

It's still only 4 passes.

Why this pitch

I'm interested in implementing this feature but Haxe compiler ocaml code doesn't roll of the tongue for me.

Perhaps the idea is bad and can be rejected early, would save me time.

If the idea seems good I'd humbly request a few tips on implementing the type "tightening" part of the filter, for which at the moment I have no clue of how to implement (I haven't spent much time trying to figure it out either, I want to see if this gets rejected first). Perhaps something like this already exists somewhere in the haxe compiler code.

[basro]

Here's what each filter pass would do to the example main function:

Input code for main

var fib = new Fib();
var take = new Take(fib, 10);

take.count--;
take.from.next();

apply inline constructors

var fib : Fib = new Fib();
var take_from : Iterator<Int> = fib; // Take gets inlined
var take_count : Int = 0;

take_count--;
take_from.next();

apply type tightening

var fib : Fib = new Fib();
var take_from : Fib = fib; // Iterator<Int> changes to Fib
var take_count : Int = 0;
take_count--;
take_from.next(); // take_from.next is now typed as Fib.next field

apply function inline pass

var fib : Fib = new Fib(); 
var take_from : Fib = fib;
var take_count : Int = 0;
take_count--;

var r = take_from.a + take_from.b; // take_from.next() gets inlined
take_from.a = take_from.b;
take_from.b = r;
r;

apply inline constructor pass 2

var fib_a : Int = 0; // new Fib() gets inlined
var fib_b : Int = 1;
var take_count : Int = 0;
take_count--;

var r = fib_a + fib_b;
fib_a = fib_b;
fib_b = r;
r;

tighten and inline make no changes and loop ends.

[nadako]

I guess if this "type tightening" is implemented, it'll also fix #3147? I can't say about the technical part, but I'm sure it would be a welcome addition \o/

[basro]

Some more thoughts:

Type tightening might be a lot easier if restricted to variables that are assigned only once.
That way it should be possible to just sequentially remap the types in code execution order and whenever an assignment to such a (single assignment) variable is encountered the type of the rvalue expression can be used directly without too much consideration.

Inline constructors already impose the restriction that object-aliasing variables can only be assigned once or else inlining is cancelled for the aliased object. So I think a restricted type tightening might work well in most cases too.

[basro]

Although the approach was different than what I suggested here #9599 achieves the goals in this issue so I'll close it.