mono interp_compute_dominance_frontier alloc 900m+ memory for 3k line method

[srxqds]

Description

I have a generated method with 3k lines. crash with Could not allocate 990414064 bytes

I have print the value in the method interp_compute_dominance_frontier

g_print ("interp_compute_dominance_frontier: %s %d %d %d\n", mono_method_get_full_name(td->method), bitsize, td->bblocks_count_no_eh, bitsize * td->bblocks_count_no_eh);

and print:

MonoPrintf interp_compute_dominance_frontier: void CsbFilePathConst:.cctor () 11132 88970 990414040

Reproduction Steps

you can download the bug.zip file and decompress it.
This cannot be run directly, but it should be enough to help analyze the problem.
bug.zip

and the CsbFilePathHelper.Cast source code show below:

public static class CsbFilePathHelper
{
internal static string Cast(ref Utf8JsonReader reader)
{
    // 防御一下错误数据
    if (reader.TokenType != JsonTokenType.String)
    {
        reader.Skip();
        return string.Empty;
    }
    return Cast(reader.GetString());     
}
}

Expected behavior

do not crash, work well

Actual behavior

crash

Regression?

I don't know

Known Workarounds

I have not trying.

Configuration

mono.browser.wasm 9.0.3 version

Other information

No response

[srxqds]

@BrzVlad Could you please help analyze this? This problem is urgent.

[MihuBot]

I'm a bot. Here is a possible related and/or duplicate issue (I may be wrong):

• [Wasm] Very large methods cause interpreter tiering to fail and allocates a lot of unmanaged memory #93192

[srxqds]

the td variable value shot:

the callstack:

[srxqds]

I trying print the dfontier memory using:

static void
interp_compute_dominance_frontier (TransformData *td)
{
	int bitsize = mono_bitset_alloc_size (td->bblocks_count_no_eh, 0);
	const char* cls_name = m_class_get_name(td->method->klass);
	int print_set = 0;
	if(!strcmp(cls_name, "CsbFilePathConst"))
	{
		print_set = 1;
		g_print ("interp_compute_dominance_frontier: %s %d %d %d\n", mono_method_get_full_name(td->method), bitsize, td->bblocks_count_no_eh, bitsize * td->bblocks_count_no_eh);
	}

	for (int i = 0; i < td->bblocks_count_no_eh; i++) {
		InterpBasicBlock *bb = td->bblocks [i];

		if (bb->in_count > 1) {
			for (int j = 0; j < bb->in_count; ++j) {
				InterpBasicBlock *p = bb->in_bb [j];
				if (!is_bblock_ssa_cfg (td, p))
				{
					if(print_set)
						g_print ("interp_compute_dominance_frontier: index %d, in_bb %d, is_bblock_ssa_cfg false\n", i, j);
					continue;
				}

				g_assert (p->dfs_index || p == td->entry_bb);

				while (p != td->idoms [bb->dfs_index]) {
					g_assert (bb->dfs_index < td->bblocks_count_no_eh);
					// mono_bitset_set_fast (p->dfrontier, bb->dfs_index);
					if(print_set)
					{
						g_print ("interp_compute_dominance_frontier: index %d, in_bb %d, InterpBasicBlock %p  dfs_index %d\n", i, j, p, bb->dfs_index);
					}
					p = td->idoms [p->dfs_index];
				}
			}	
		}
		else 
		{
			if(print_set)
			{
				g_print ("interp_compute_dominance_frontier: index %d, bb->in_count \n", i, bb->in_count);
			}
		}
	}
	// g_print ("interp_compute_dominance_frontier: %s.%s %d %d %d\n", m_class_get_name(td->method->klass), mono_method_get_name(td->method), td->bblocks_count_no_eh, bitsize * td->bblocks_count_no_eh);
	char *mem = (char *)mono_mempool_alloc0 (td->opt_mempool, bitsize * td->bblocks_count_no_eh);

	for (int i = 0; i < td->bblocks_count_no_eh; i++) {
		td->bblocks [i]->dfrontier = mono_bitset_mem_new (mem, td->bblocks_count_no_eh, 0);
		mem += bitsize;
	}

	for (int i = 0; i < td->bblocks_count_no_eh; i++) {
		InterpBasicBlock *bb = td->bblocks [i];

		if (bb->in_count > 1) {
			for (int j = 0; j < bb->in_count; ++j) {
				InterpBasicBlock *p = bb->in_bb [j];
				if (!is_bblock_ssa_cfg (td, p))
				{
					continue;
				}

				g_assert (p->dfs_index || p == td->entry_bb);

				while (p != td->idoms [bb->dfs_index]) {
					g_assert (bb->dfs_index < td->bblocks_count_no_eh);
					mono_bitset_set_fast (p->dfrontier, bb->dfs_index);
					p = td->idoms [p->dfs_index];
				}
			}	
		}
	}

	if (td->verbose_level) {
		InterpBasicBlock *bb;
		g_print ("\nBASIC BLOCK DFRONTIERS:\n");
		for (bb = td->entry_bb; bb != NULL; bb = bb->next_bb) {
			if (!is_bblock_ssa_cfg (td, bb))
				continue;
			g_print ("DFRONTIER (BB%d) = {", bb->index);
			int i;
			mono_bitset_foreach_bit (bb->dfrontier, i, td->bb_count) {
				g_print (" BB%d", td->bblocks [i]->index);
			}
			g_print (" }\n");
		}
	}
}

as the shot show:
the mono_bitset dfrontier only set with int bb->dfs_index value ,but it allocate #define MONO_BITSET_BITS_PER_CHUNK (8 * sizeof (gsize)) which is 64

it make a lot of memory waste?

It is enough allocate only 4 byte for write dfs_index?

could you help me or how to work around this problem. @BrzVlad

[dotnet-policy-service]

Tagging subscribers to this area: @BrzVlad, @kotlarmilos
See info in area-owners.md if you want to be subscribed.

[BrzVlad]

The interpreter always handled this pattern very bad because it doesn't have an inlining limit. This means that it will keep inlining in a huge method, as long as the method to inline satisfies basic conditions. In this case, this leads to excessive generated code. With recent changes, the problem got worse because SSA optimizations are more complex and use more memory. You could mitigate this by having latest dotnet version (9 or 10) and setting the env var: MONO_INTERPRETER_OPTIONS=-ssa

[srxqds]

The interpreter always handled this pattern very bad because it doesn't have an inlining limit. This means that it will keep inlining in a huge method, as long as the method to inline satisfies basic conditions. In this case, this leads to excessive generated code. With recent changes, the problem got worse because SSA optimizations are more complex and use more memory. You could mitigate this by having latest dotnet version (9 or 10) and setting the env var: MONO_INTERPRETER_OPTIONS=-ssa

This will result in no optimization at all, leading to poor performance.

could you try to optimize it such as decrease the bitset size？
if it work, the modify is simple but significant effect

this mono_bitset for p->dfrontier only use three place https://github.com/search?q=repo%3Adotnet%2Fruntime%20-%3Edfrontier&type=code`

only write for int value?