Closure Conversion - index out of bounds

[NeuralCoder3]

The error

array.h:99: const T& thorin::ArrayRef<T>::operator[](size_t) const [with T = const thorin::Def*; size_t = long unsigned int]: Assertion `i < size() && "index out of bounds"' failed

is triggered in some examples when trying to use closure conversion.

Example Thorin file:
https://github.com/NeuralCoder3/thorin2/blob/autodiff/enzyme/brussel.thorin
Commit 84af1a0

Stacktrace

libc.so.6![Unknown/Just-In-Time compiled code] (Unbekannte Quelle:0)
libc.so.6!raise (Unbekannte Quelle:0)
libc.so.6!abort (Unbekannte Quelle:0)
libc.so.6![Unknown/Just-In-Time compiled code] (Unbekannte Quelle:0)
libc.so.6!__assert_fail (Unbekannte Quelle:0)
libthorin_clos.so!thorin::ArrayRef<thorin::Def const*>::operator[](const thorin::ArrayRef<thorin::Def const*> * const this, size_t i) (thorin/thorin/util/array.h:99)
libthorin_clos.so!operator()<unsigned long>(const struct {...} * const __closure, unsigned long j) (thorin/dialects/clos/phase/clos_conv.cpp:35)
libthorin_clos.so!std::__invoke_impl<const thorin::Def*, thorin::clos::ctype(thorin::World&, thorin::Defs, const thorin::Def*)::<lambda(auto:57)>::<lambda(auto:58)>&, long unsigned int>(std::__invoke_other, struct {...} &)(struct {...} & __f) (/usr/include/c++/12.1.1/bits/invoke.h:61)
libthorin_clos.so!std::__invoke_r<const thorin::Def*, thorin::clos::ctype(thorin::World&, thorin::Defs, const thorin::Def*)::<lambda(auto:57)>::<lambda(auto:58)>&, long unsigned int>(struct {...} &)(struct {...} & __fn) (/usr/include/c++/12.1.1/bits/invoke.h:114)
libthorin_clos.so!std::_Function_handler<const thorin::Def*(long unsigned int), thorin::clos::ctype(thorin::World&, thorin::Defs, const thorin::Def*)::<lambda(auto:57)>::<lambda(auto:58)> >::_M_invoke(const std::_Any_data &, unsigned long &&)(const std::_Any_data & __functor,  __args#0) (/usr/include/c++/12.1.1/bits/std_function.h:290)
libthorin_clos.so!std::function<thorin::Def const* (unsigned long)>::operator()(unsigned long) const(const std::function<const thorin::Def*(long unsigned int)> * const this,  __args#0) (/usr/include/c++/12.1.1/bits/std_function.h:591)
libthorin_clos.so!thorin::clos::clos_insert_env(unsigned long, thorin::Def const*, std::function<thorin::Def const* (unsigned long)>)(size_t i, const thorin::Def * env, std::function<const thorin::Def*(long unsigned int)> f) (thorin/dialects/clos/phase/clos_conv.cpp:21)
libthorin_clos.so!operator()<unsigned long>(const struct {...} * const __closure, unsigned long i) (thorin/dialects/clos/phase/clos_conv.cpp:35)
libthorin_clos.so!std::__invoke_impl<const thorin::Def*, thorin::clos::ctype(thorin::World&, thorin::Defs, const thorin::Def*)::<lambda(auto:57)>&, long unsigned int>(std::__invoke_other, struct {...} &)(struct {...} & __f) (/usr/include/c++/12.1.1/bits/invoke.h:61)
libthorin_clos.so!std::__invoke_r<const thorin::Def*, thorin::clos::ctype(thorin::World&, thorin::Defs, const thorin::Def*)::<lambda(auto:57)>&, long unsigned int>(struct {...} &)(struct {...} & __fn) (/usr/include/c++/12.1.1/bits/invoke.h:114)
libthorin_clos.so!std::_Function_handler<const thorin::Def*(long unsigned int), thorin::clos::ctype(thorin::World&, thorin::Defs, const thorin::Def*)::<lambda(auto:57)> >::_M_invoke(const std::_Any_data &, unsigned long &&)(const std::_Any_data & __functor,  __args#0) (/usr/include/c++/12.1.1/bits/std_function.h:290)
libthorin_clos.so!std::function<thorin::Def const* (unsigned long)>::operator()(unsigned long) const(const std::function<const thorin::Def*(long unsigned int)> * const this,  __args#0) (/usr/include/c++/12.1.1/bits/std_function.h:591)
libthorin_clos.so!thorin::Array<thorin::Def const*>::Array(unsigned long, std::function<thorin::Def const* (unsigned long)>)(thorin::Array<thorin::Def const*> * const this, size_t size, std::function<const thorin::Def*(long unsigned int)> f) (thorin/thorin/util/array.h:288)
libthorin_clos.so!thorin::clos::ctype(thorin::World & w, thorin::Defs doms, const thorin::Def * env_type) (thorin/dialects/clos/phase/clos_conv.cpp:34)
libthorin_clos.so!thorin::clos::ctype(thorin::World & w, thorin::Defs doms, const thorin::Def * env_type) (thorin/dialects/clos/phase/clos_conv.cpp:30)
libthorin_clos.so!thorin::clos::ClosConv::closure_type(thorin::clos::ClosConv * const this, const thorin::Pi * pi, thorin::Def2Def & subst, const thorin::Def * env_type) (thorin/dialects/clos/phase/clos_conv.cpp:280)
libthorin_clos.so!thorin::clos::ClosConv::rewrite(thorin::clos::ClosConv * const this, const thorin::Def * def, thorin::Def2Def & subst) (thorin/dialects/clos/phase/clos_conv.cpp:188)
libthorin_clos.so!thorin::clos::ClosConv::rewrite(thorin::clos::ClosConv * const this, const thorin::Def * def, thorin::Def2Def & subst) (thorin/dialects/clos/phase/clos_conv.cpp:227)
libthorin_clos.so!operator()<unsigned long>(const struct {...} * const __closure, unsigned long i) (thorin/dialects/clos/phase/clos_conv.cpp:244)
libthorin_clos.so!std::__invoke_impl<const thorin::Def*, thorin::clos::ClosConv::rewrite(const thorin::Def*, thorin::Def2Def&)::<lambda(auto:62)>&, long unsigned int>(std::__invoke_other, struct {...} &)(struct {...} & __f) (/usr/include/c++/12.1.1/bits/invoke.h:61)
libthorin_clos.so!std::__invoke_r<const thorin::Def*, thorin::clos::ClosConv::rewrite(const thorin::Def*, thorin::Def2Def&)::<lambda(auto:62)>&, long unsigned int>(struct {...} &)(struct {...} & __fn) (/usr/include/c++/12.1.1/bits/invoke.h:114)
libthorin_clos.so!std::_Function_handler<const thorin::Def*(long unsigned int), thorin::clos::ClosConv::rewrite(const thorin::Def*, thorin::Def2Def&)::<lambda(auto:62)> >::_M_invoke(const std::_Any_data &, unsigned long &&)(const std::_Any_data & __functor,  __args#0) (/usr/include/c++/12.1.1/bits/std_function.h:290)
libthorin_clos.so!std::function<thorin::Def const* (unsigned long)>::operator()(unsigned long) const(const std::function<const thorin::Def*(long unsigned int)> * const this,  __args#0) (/usr/include/c++/12.1.1/bits/std_function.h:591)
libthorin_clos.so!thorin::Array<thorin::Def const*>::Array(unsigned long, std::function<thorin::Def const* (unsigned long)>)(thorin::Array<thorin::Def const*> * const this, size_t size, std::function<const thorin::Def*(long unsigned int)> f) (thorin/thorin/util/array.h:288)
libthorin_clos.so!thorin::clos::ClosConv::rewrite(thorin::clos::ClosConv * const this, const thorin::Def * def, thorin::Def2Def & subst) (thorin/dialects/clos/phase/clos_conv.cpp:244)
libthorin_clos.so!thorin::clos::ClosConv::rewrite_body(thorin::clos::ClosConv * const this, thorin::Lam * new_lam, thorin::Def2Def & subst) (thorin/dialects/clos/phase/clos_conv.cpp:164)
libthorin_clos.so!thorin::clos::ClosConv::start(thorin::clos::ClosConv * const this) (thorin/dialects/clos/phase/clos_conv.cpp:131)
libthorin.so!thorin::Phase::run(thorin::Phase * const this) (thorin/thorin/phase/phase.cpp:10)
libthorin_clos.so!ClosConvWrapper::prepare(ClosConvWrapper * const this) (thorin/dialects/clos/clos.cpp:29)
libthorin.so!thorin::PassMan::run(thorin::PassMan * const this) (thorin/thorin/pass/pass.cpp:56)
libthorin.so!thorin::PassManPhase::start(thorin::PassManPhase * const this) (thorin/thorin/phase/phase.h:141)
libthorin.so!thorin::Phase::run(thorin::Phase * const this) (thorin/thorin/phase/phase.cpp:10)
libthorin.so!thorin::Pipeline::start(thorin::Pipeline * const this) (thorin/thorin/phase/phase.cpp:31)
libthorin.so!thorin::Phase::run(thorin::Phase * const this) (thorin/thorin/phase/phase.cpp:10)
libthorin.so!thorin::optimize(thorin::World & world, thorin::PipelineBuilder & builder) (thorin/thorin/pass/optimize.cpp:60)
main(int argc, char ** argv) (thorin/cli/main.cpp:139)

Possibly related to #117, #118

[leissa]

Example file links to 404. Do you have an update?

[NeuralCoder3]

Example file links to 404. Do you have an update?

Here is the file from when the issue was opened:
https://github.com/NeuralCoder3/thorin2/blob/84af1a073ab4e1a848def18cce2e6afc7fe567f1/enzyme/brussel.thorin

Here is the file currently: (Nothing big regarding this issue should have changed)
https://github.com/NeuralCoder3/thorin2/blob/84af1a073ab4e1a848def18cce2e6afc7fe567f1/enzyme/brussel.thorin
(the enzyme folder was moved into the eval folder)

[leissa]

I have to double-check with @f-fries but I think the problem is that the whole clos dialect assumes that the first argument is a mem. Otherwise, things go south as in your example.

[leissa]

This is indeed the problem. I opened a new issue #126 as it really is an enhancement and closing this here for now.

[NeuralCoder3]

This is indeed the problem. I opened a new issue #126 as it really is an enhancement and closing this here for now.

Therefore, one needs a pass that reorders mem to the front and propagates it to functions without mem (higher order arguments and others) in order to generate the code.
Or would it be easier to adapt closure conversion?

[leissa]

I think it makes everyone's life easier if we can just assume that the first argument is mem if present at all. But we should also enhance the closure conversion to also cope with functions without mem. I think it's cool to have this explicitly annotated on the type that a function is pure and it would be a pity if we would enforce impure functions.

[f-fries]

It might still be a good idea to uniformly add mems before/during closure conversion as @NeuralCoder3 has suggested.
Closure conversion actually introduces new side-effects (environment allocation etc).
So some pure functions would get a "pure closure" while others would end up with an "impure closure" with a different type.