Update lpython to use optimization passes

[Smit-create]

LFortran supports optimization passes like loop_unroll, fma, etc. which are already supported in libasr. We should update LPython to make use of these optimization passes.

cc @czgdp1807

[certik]

The new pass manager will allow it, we just have to integrate it.

[czgdp1807]

LPython already uses the passes which you have mentioned. The interface to input the list of passes is exactly the same for LPython and LFortran. Use command line argument, —pass.

[czgdp1807]

In addition also see, asr_to_llvm.cpp in both the compilers. They both call the pass manager to apply same set of passes.

[Smit-create]

On the main branch, I get:

% lpython --show-asr expr.py --indent --pass=fma
Pass must be one of: do_loops, global_stmts, implied_do_loops, array_op, class_constructor, print_arr, arr_slice, unused_functions

On updating the bin/lpython to use fma, I get:

LFortranException: Module 'lfortran_intrinsic_optimization' not declared in the current source and the modfile was not found

[czgdp1807]

Here's what I get,

(lp) 16:48:31:~/lpython_project/lpython % lpython --pass=fma --show-asr tests/expr16.py
(TranslationUnit (SymbolTable 1 {main_program: (Program (SymbolTable 3 {}) main_program [] []), test_issue_455: (Function (SymbolTable 2 {_lpython_return_variable: (Variable 2 _lpython_return_variable ReturnVar () () Default (Real 8 []) Source Public Required .false.), data: (Variable 2 data In () () Default (List (Integer 4 [])) Source Public Required .false.), i: (Variable 2 i Local () () Default (Integer 4 []) Source Public Required .false.), sum: (Variable 2 sum Local () () Default (Real 8 []) Source Public Required .false.)}) test_issue_455 [(Var 2 data)] [(= (Var 2 sum) (RealConstant   0.00000000000000000e+00 (Real 8 [])) ()) (DoLoop ((Var 2 i) (IntegerConstant 0 (Integer 4 [])) (IntegerBinOp (ListLen (Var 2 data) (Integer 4 []) ()) Sub (IntegerConstant 1 (Integer 4 [])) (Integer 4 []) ()) (IntegerConstant 1 (Integer 4 []))) [(= (Var 2 sum) (RealBinOp (Var 2 sum) Add (Cast (ListItem (Var 2 data) (Var 2 i) (Integer 4 []) ()) IntegerToReal (Real 8 []) ()) (Real 8 []) ()) ())]) (= (Var 2 _lpython_return_variable) (Var 2 sum) ()) (Return)] (Var 2 _lpython_return_variable) Source Public Implementation ())}) [])
(lp) 16:49:16:~/lpython_project/lpython % lpython --version
LPython version: 0.2.0-1263-gacac3ba17
Platform: macOS ARM
Default target: arm64-apple-darwin21.5.0

Commit on main branch - acac3ba

[czgdp1807]

The exception you get is outdated, because this is what I get if I pass an unsupported pass,

(lp) 16:51:47:~/lpython_project/lpython % lpython --pass=fma1 --show-asr tests/expr16.py
fma1 isn't supported yet. Only the following passes are supported:- 
arr_slice
array_op
class_constructor
dead_code_removal
div_to_mul
do_loops
flip_sign
fma
forall
global_stmts
implied_do_loops
inline_function_calls
loop_unroll
loop_vectorise
print_arr
select_case
sign_from_value
unused_functions

[Smit-create]

Oh, I see. I forgot to fetch the latest main. But still there is an exception:

LFortranException: Module 'lfortran_intrinsic_optimization' not declared in the current source and the modfile was not found

[Thirumalai-Shaktivel]

On the main branch, I get:

% lpython --show-asr expr.py --indent --pass=fma
Pass must be one of: do_loops, global_stmts, implied_do_loops, array_op, class_constructor, print_arr, arr_slice, unused_functions

On updating the bin/lpython to use fma, I get:

LFortranException: Module 'lfortran_intrinsic_optimization' not declared in the current source and the modfile was not found

Hi @Smit-create, I was also getting the same message as yours.

$ lpython --show-asr tests/expr16.py --pass=fma   
Pass must be one of: do_loops, global_stmts, implied_do_loops, array_op, class_constructor, print_arr, arr_slice, unused_functions

So, after updating the lpython main branch using

$ git pull lpython main:main 
$ git clean -dfx
$ ./build0.sh; ./build1.sh

I got the output similar to @czgdp1807.

$ lpython --pass=fma1 --show-asr tests/expr16.py
fma1 isn't supported yet. Only the following passes are supported:- 
arr_slice
array_op
class_constructor
dead_code_removal
div_to_mul
do_loops
flip_sign
fma
forall
global_stmts
implied_do_loops
inline_function_calls
loop_unroll
loop_vectorise
print_arr
select_case
sign_from_value
unused_functions
$ lpython --show-asr tests/expr16.py --pass=fma
(TranslationUnit (SymbolTable 1 {main_program: (Program (SymbolTable 3 {}) main_program [] []), test_issue_455: (Function (SymbolTable 2 {_lpython_return_variable: (Variable 2 _lpython_return_variable ReturnVar () () Default (Real 8 []) Source Public Required .false.), data: (Variable 2 data In () () Default (List (Integer 4 [])) Source Public Required .false.), i: (Variable 2 i Local () () Default (Integer 4 []) Source Public Required .false.), sum: (Variable 2 sum Local () () Default (Real 8 []) Source Public Required .false.)}) test_issue_455 [(Var 2 data)] [(= (Var 2 sum) (RealConstant   0.00000000000000000e+00 (Real 8 [])) ()) (DoLoop ((Var 2 i) (IntegerConstant 0 (Integer 4 [])) (IntegerBinOp (ListLen (Var 2 data) (Integer 4 []) ()) Sub (IntegerConstant 1 (Integer 4 [])) (Integer 4 []) ()) (IntegerConstant 1 (Integer 4 []))) [(= (Var 2 sum) (RealBinOp (Var 2 sum) Add (Cast (ListItem (Var 2 data) (Var 2 i) (Integer 4 []) ()) IntegerToReal (Real 8 []) ()) (Real 8 []) ()) ())]) (= (Var 2 _lpython_return_variable) (Var 2 sum) ()) (Return)] (Var 2 _lpython_return_variable) Source Public Implementation ())}) [])

[Smit-create]

lfortran_intrinsic_optimization

Does this error have a dependency on this file? https://gitlab.com/lfortran/lfortran/-/blob/master/src/runtime/builtin/lfortran_intrinsic_optimization.f90 I don't have that locally, so that might be the reason for this failure?

[czgdp1807]

The error you are getting is because the following function is tuned for LFortran,

https://github.com/lfortran/lfortran/blob/ecd48b8676f50372c60f3d846b54bce648472802/src/libasr/pass/pass_utils.h#L56-L59

which is called from the below line,

https://github.com/lfortran/lfortran/blob/ecd48b8676f50372c60f3d846b54bce648472802/src/libasr/pass/fma.cpp#L119-L121

Now, to generalise these utility functions for LCompilers there are two options with us,

1. Compile modules in every LCompiler - On the basis of my understanding, LPython as of now re-compiles a module every time we import it. Or in other words there are no .mod files generated for intrinsic modules while building LPython. On the contrary, when we build LFortran then all the intrinsic modules are pre-compiled and saved into .mod files. Whenever we use them the .mod file is deserialised and inserted into the global scope of ASR. So, either make LPython work in a similar fashion so that we can write the fallback implementations of each of these optimisations in a python module, save it in a .mod file and re-use them in whatever way we want.

lpython/src/lpython/semantics/python_ast_to_asr.cpp

Lines 126 to 127 in acac3ba

	Result<ASR::TranslationUnit_t*> r2 = python_ast_to_asr(al, *ast,
	diagnostics, false, false, false, path_used);

2. Insert fallback implementations directly in the ASR - So, I added loop_vectorise implementation recently into LPython. In this we don't attempt to load it from a python module but we ourselves create a fallback implementation with the help of ASR APIs and insert it into the global scope. We can follow this approach in all the LCompilers as well.

lpython/src/libasr/pass/pass_utils.cpp

Lines 479 to 481 in acac3ba

	ASR::symbol_t* insert_fallback_vector_copy(Allocator& al, ASR::TranslationUnit_t& unit,
	SymbolTable*& global_scope, std::vector<ASR::ttype_t*>& types,
	std::string prefix) {

The above function is called in get_vector_copy as follows,

lpython/src/libasr/pass/pass_utils.cpp

Lines 537 to 547 in acac3ba

	ASR::stmt_t* get_vector_copy(ASR::symbol_t* array0, ASR::symbol_t* array1, ASR::expr_t* start,
	ASR::expr_t* end, ASR::expr_t* step, ASR::expr_t* vector_length,
	Allocator& al, ASR::TranslationUnit_t& unit,
	SymbolTable*& global_scope, Location& loc) {
	ASR::ttype_t* array0_type = ASRUtils::symbol_type(array0);
	ASR::ttype_t* array1_type = ASRUtils::symbol_type(array1);
	ASR::ttype_t* index_type = ASRUtils::expr_type(start);
	std::vector<ASR::ttype_t*> types = {array0_type, array1_type, index_type};
	ASR::symbol_t *v = insert_fallback_vector_copy(al, unit, global_scope,
	types,
	"vector_copy_");

I am fine either of the approaches. We just have to follow a single approach across all the LCompilers because libasr is a shared portion of the code and once an ASR is generated you never know from which language it was created (unless you are willing to use hackish string checks).

Personal opinion - I would like to follow point 2 as I already did with loop_vectorise (after discussing with @certik) because it provides us flexibility and scalability for a variety of type combinations (infinite in theory). The first approach would require us to write fallback implementations for a very large number of type combinations and that too for each of the optimisations we want to add which is ad-hoc I believe.

[certik]

Let's brainstorm this more. We want to be able to reuse these passes for all frontends.

[czgdp1807]

I and @certik discussed this yesterday. We arrived at the conclusion to use idea in point number 2 of #723 (comment). The reason to go for this approach is because of the scalability advantage it provides which is a major overhead if we implement all the fallback implementations of optimisations manually by writing modules, etc. In addition, the ASR remains compact because we generate fallback implementations only for those combination of types which are in the user code (and not for every combination of types beforehand).

In future, we will abstract the code in order to generate subroutines, functions using ASR APIs easier.