Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

hir: Compile MatchExpr to if statements #2004

Open
wants to merge 1 commit into
base: master
Choose a base branch
from

Conversation

goar5670
Copy link
Contributor

@goar5670 goar5670 commented Mar 18, 2023

The main purpose of this commit is to refactor the old switch-based logic we
had for compiling match expressions and use an if-statement-based approach.

So, naturally, the old logic was removed in this commit. That includes
sort_tuple_patterns, simplify_tuple_match, PatternMerge and patterns_mergeable.

In the new approach, each arm is transformed into an if statement. And for
any if statement, there are two main components: the condition and the then_block.

The entity responsible for handling the condition is CompileMatchArmCondition.
It's a class that traverses down the arm pattern and the match scrutinee expression
simultaneously. Whenever it meets a base-case in the pattern (i.e. expression or identifier
but identifiers are not handled for now), it takes the respective field of the scrutinee
and returns a backend comparison expression for them.

As for the then_block, it's compiled by SimplifyMatchExpr::compile_case_expr.
This function transforms the HIR::Expr match case final expression
into a backend block so it can be used easily inside the if_statement. In case
the expr is of type BlockExpr, then we can easily compile it using CompileBlock::compile.
Otherwise, we'll have to create a new block and add the expression as a statement.

Now we have the means of creating the if statements. All that's left is to glue the
multiple match arms (if_statements) together, and that's where
SimplifyMatchExpr::simplify_remaining_cases comes in. It compiles the condition and
then_block with the help of the functions mentioned earlier. As for the else_block,
it should contain the if_statements for the remaining match arms. So
simplify_remaining_cases calculates the else_block recursively by calling itself.
After that it returns the compiled if_statement with the condition, then_block, and
else_block.

@goar5670 goar5670 changed the title hir: Lower MatchExpr to if statement instead of switch expression hir: Lower MatchExpr to if statement instead of switch expression [WIP] Mar 18, 2023
@goar5670 goar5670 force-pushed the dev2 branch 5 times, most recently from 8cfab5f to 3b46d00 Compare March 18, 2023 22:44
@goar5670 goar5670 changed the title hir: Lower MatchExpr to if statement instead of switch expression [WIP] hir: Lower MatchExpr to if statement instead of switch expression Mar 18, 2023
@goar5670 goar5670 changed the title hir: Lower MatchExpr to if statement instead of switch expression hir: Compile MatchExpr to if statements Mar 18, 2023
@philberty philberty requested review from dafaust and philberty March 18, 2023 22:48
@goar5670 goar5670 force-pushed the dev2 branch 2 times, most recently from b4183e6 to 98d4024 Compare March 18, 2023 23:31
@goar5670
Copy link
Contributor Author

@philberty do you have any idea why it's failing? I think it's overflowing somewhere but I can't figure it out.

@CohenArthur
Copy link
Member

For reference this is the assert that fails:

template <typename storage>
inline wi::storage_ref
wi::int_traits < generic_wide_int <storage> >::
decompose (HOST_WIDE_INT *, unsigned int precision,
	   const generic_wide_int <storage> &x)
{
  gcc_checking_assert (precision == x.get_precision ());
  return wi::storage_ref (x.get_val (), x.get_len (), precision);
}

@goar5670 goar5670 force-pushed the dev2 branch 3 times, most recently from 2b6d3d1 to 76f307c Compare April 1, 2023 18:00
@goar5670
Copy link
Contributor Author

goar5670 commented Apr 1, 2023

Btw, this implementation also handles the path-to-tuple scrutinee and nested tuples. Added tests for that.

The main purpose of this commit is to refactor the old switch-based logic we
had for compiling match expressions and use an if-statement-based approach.

So, naturally, the old logic was removed in this commit. That includes
sort_tuple_patterns, simplify_tuple_match, PatternMerge and patterns_mergeable.

In the new approach, each arm is transformed into an if statement. And for
any if statement, there are two main components: the condition and the then_block.

The entity responsible for handling the condition is CompileMatchArmCondition.
It's a class that traverses down the arm pattern and the match scrutinee expression
simultaneously. Whenever it meets a base-case in the pattern (i.e. expression or identifier
but identifiers are not handled for now), it takes the respective field of the scrutinee
and returns a backend comparison expression for them.

As for the then_block, it's compiled by SimplifyMatchExpr::compile_case_expr.
This function transforms the HIR::Expr match case final expression
into a backend block so it can be used easily inside the if_statement. In case
the expr is of type BlockExpr, then we can easily compile it using CompileBlock::compile.
Otherwise, we'll have to create a new block and add the expression as a statement.

Now we have the means of creating the if statements. All that's left is to glue the
multiple match arms (if_statements) together, and that's where
SimplifyMatchExpr::simplify_remaining_cases comes in. It compiles the condition and
then_block with the help of the functions mentioned earlier. As for the else_block,
it should contain the if_statements for the remaining match arms. So
simplify_remaining_cases calculates the else_block recursively by calling itself.
After that it returns the compiled if_statement with the condition, then_block, and
else_block.

gcc/rust/ChangeLog:

	* backend/rust-compile-expr.cc (patterns_mergeable): Removed.
	(struct PatternMerge): Removed.
	(sort_tuple_patterns): Removed.
	(simplify_tuple_match): Removed.
	(check_match_scrutinee): Renamed to ..
	(check_match_expr_type): this
	(CompileExpr::visit): Refactored MatchExpr compilation to an
	if-statement-based approach.
	(SimplifyMatchExpr::go): New function. The entry point for compiling
	a match expression into an if statement
	(SimplifyMatchExpr::compile_case_expr): New function. Compiles the match
	case expr.
	(SimplifyMatchExpr::simplify_remaining_cases): New function. Contains the
	main logic for compiling match expressions.
	* backend/rust-compile-expr.h (class SimplifyMatchExpr): New class.
	* backend/rust-compile-pattern.cc (CompilePatternCaseLabelExpr::visit):
	Mostly renamed to...
	(CompileMatchArmCondition::visit): this. Added a tuple visit.
	* backend/rust-compile-pattern.h (class CompilePatternCaseLabelExpr):
	Mostly renamed to...
	(class CompileMatchArmCondition): this.

gcc/testsuite/ChangeLog:
	* rust/execute/torture/match_tuple2.rs: New test.
	* rust/execute/torture/match_tuple3.rs: New test.

Signed-off-by: Mahmoud Mohamed <mahadelr19@gmail.com>
@powerboat9
Copy link
Collaborator

@goar5670 are you still working on this? No pressure/implied obligation intended

@philberty
Copy link
Member

I think we should think about finishing this work off soon. GCC auto optimizes cases to switch blocks too and lets not worry about pattern exhaustiveness checks for now.

@powerboat9
Copy link
Collaborator

I think some of this has been superseded -- @goar5670 thoughts? I think the tests look like they'd be good to have, and you might have some input on the current match expression code.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Status: Todo
Development

Successfully merging this pull request may close these issues.

5 participants