Deduplication of symbols by using dedup/linkonce features

[kotlarmilos]

Description

When Mono AOT compiler encounters a generic instance that is not handled by generic sharing, it will emit a code for the instance. If the same instance is encountered during compilation in multiple assemblies, the code will be emitted multiple times, increasing code size.

Solutions

There are at least two possible solutions to this problem.

Dedup by Mono AOT compiler

It compiles instances into a separate AOT image and consists of two phases. Dedup-skip flag is used when compiling assemblies, and it disables emitting code of dedup-able methods. Dedup-include flag is used when compiling dummy assembly where all assemblies are compiled together, and it enables emitting code of dedup-able methods only.

Linkonce by LLVM

If two functions have the same name and they are marked linkonce, then the linker is allowed to throw away all copies except one.

Experimental results

List of methods In Mono iOS sample app that can be deduplicated. Estimated size reduction is 400kb.
Proposed change for enabling deduplication in Mono iOS sample app.

Deduplication of symbols is currently enabled in WASM.

[ghost]

Tagging subscribers to 'arch-wasm': @lewing
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

When Mono AOT compiler encounters a generic instance that is not handled by generic sharing, it will emit a code for the instance. If the same instance is encountered during compilation in multiple assemblies, the code will be emitted multiple times, increasing code size.

Solutions

There are at least two possible solutions to this problem.

Dedup by Mono AOT compiler

It compiles instances into a separate AOT image and consists of two phases. Dedup-skip flag is used when compiling assemblies, and it disables emitting code of dedup-able methods. Dedup-include flag is used when compiling dummy assembly where all assemblies are compiled together, and it enables emitting code of dedup-able methods only.

Linkonce by LLVM

If two functions have the same name and they are marked linkonce, then the linker is allowed to throw away all copies except one.

Experimental results

List of methods In Mono iOS sample app that can be deduplicated. Estimated size reduction is 400kb.
Proposed change for enabling deduplication in Mono iOS sample app.

Deduplication of symbols is currently not enabled in WASM and iOS.

Tasks

List of tasks that needs to be addressed in order to enabled it in WASM and iOS:

• The existing implementation assumes that all code in an AOT image are grouped together in memory, but with the dedup change, some of the pointers in the code point to outside the AOT image
• During the compilation, emit_method_info_table can't find GOT offsets for dedup-able methods as they are not emitted
• During the compilation, emit_and_reloc_code that handles relocations is not invoked
• During the runtime, llvm_code_range is corrupted for assemblies where dedup-able methods are not emitted
• During the runtime, mono_aot_plt_resolve can't return the address of the PLT entry called by the code as it could point out of code range

Author:	kotlarmilos
Assignees:	vargaz, kotlarmilos
Labels:	arch-wasm, area-Codegen-AOT-mono, feature-request, os-ios
Milestone:	8.0.0

[kotlarmilos]

Update: The dedup feature can be enabled in HelloiOS app in non-LLVM debug configuration. To enable it in release mode and with LLVM, the updated list of tasks need to be resolved.

Current implementation doesn't cover cases where both shared method and its inflated instances could be deduplicated. During the compilation, the shared method is emitted in corresponding AOT image while inflated instances are emitted in dedup AOT image. During the runtime, the shared method can't be retrieved as it was searched in the dedup AOT image.

Here is an example. During the compilation, the following list of inflated instances emitted in the dedup AOT image.

(wrapper runtime-invoke) object <Module>:runtime_invoke_byte__this___int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_byte (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_int__this___int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_int__this___int_int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_int_int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_uint16__this___int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_uint16 (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_bool__this___int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_byte (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_sbyte__this___int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_sbyte (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_char__this___int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_uint16 (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_int16__this___int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_int16 (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_uint__this___int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_uint (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_long__this___int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_long (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_ulong__this___int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_long (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_intptr__this___int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_intptr (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_uintptr__this___int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_intptr (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_single__this___int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_single (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_double__this___int (object,intptr,intptr,intptr)
(wrapper runtime-invoke) object <Module>:runtime_invoke_void__this___int_double (object,intptr,intptr,intptr)

During the runtime, (wrapper runtime-invoke) void object:runtime_invoke_dynamic (intptr,intptr,intptr,intptr) was searched in the dedup AOT image as it is RUNTIME_INVOKE_WRAPPER, but not emitted in the dedup AOT image. It could be addressed by updating mono_aot_get_method method to handle such cases. Alternative approach could be adding a dedup flag in MonoMethod struct but it looks like inefficient approach.

Furthermore, In release configuration, during the runtime mono_jit_cleanup throws Could not find method 'GetPinnableReference' due to a type load error: Type System.ReadOnlySpan'1[T] is not a ByRefLike type so ref field, '_reference'. As it works without the dedup feature, it might happen due to inconsistent or missing data in the dedup AOT image.

HelloiOS with LLVM enabled throws while executing method wrappers. During the debugging, the implementation was changed to emit all methods in corresponding AOT images and to have an empty dedup AOT image linked into a binary. The same error occurred, which could lead to having an issue with segments offset of AOT images in the binary.

Further investigation is needed to narrow down the specific causes. /cc: @vargaz @lambdageek

[lambdageek]

Furthermore, In release configuration, during the runtime mono_jit_cleanup throws Could not find method 'GetPinnableReference' due to a type load error: Type System.ReadOnlySpan'1[T] is not a ByRefLike type so ref field, '_reference'. As it works without the dedup feature, it might happen due to inconsistent or missing data in the dedup AOT image.

You might be able to fix this by adding is_byreflike to MonoCachedClassInfo. Or we might need to fully load+init the ReadOnlySpan`1[T] class on some branch.

[kotlarmilos]

ReadOnlySpan`1[T] is a generic type and decode_cached_class_info returns FALSE. It works if added as an exception case, like the following.

if (m_class_is_valuetype (klass))
	if (class_has_isbyreflike_attribute (klass) || !strcmp (klass->name, "ReadOnlySpan`1"))
		klass->is_byreflike = 1;

What would be a good approach to add it?

[vargaz]

is_byreflike is computed when the class is created i.e. in mono_class_create_from_typedef () so it should be set correctly.

[kotlarmilos]

is_byreflike is computed when the class is created i.e. in mono_class_create_from_typedef () so it should be set correctly.

Let me check if for ReadOnlySpan`1[T].

HelloiOS with LLVM enabled throws while executing method wrappers. During the debugging, the implementation was changed to emit all methods in corresponding AOT images and to have an empty dedup AOT image linked into a binary. The same error occurred, which could lead to having an issue with segments offset of AOT images in the binary.

If LLVM is enabled the application throws in both release and debug configurations. When using debug configuration, NativeRuntimeEventSource constructor throws when initializing its attribute EventSource, as EventListener is NULL.

runtime/src/libraries/System.Private.CoreLib/src/System/Diagnostics/Tracing/EventSource.cs

Line 1566 in 8b2a920

EventListener.AddEventSource(this);

Similarly, when using release configuration, InternalWait throws as default is NULL.

runtime/src/libraries/System.Private.CoreLib/src/System/Runtime/CompilerServices/TaskAwaiter.cs

Line 140 in 8b2a920

bool taskCompleted = task.InternalWait(Timeout.Infinite, default);

In both cases, it fails when using default or global variable. The following direct call transformation is causing such issues with LLVM. @vargaz @lambdageek Any ideas why is it happening?

runtime/src/mono/mono/mini/aot-compiler.c

Lines 6512 to 6552 in 8b2a920

	// Don't compile inflated methods if we're doing dedup
	if (acfg->aot_opts.dedup && !mono_aot_can_dedup (cmethod)) {
	char *name = mono_aot_get_mangled_method_name (cmethod);
	mono_trace (G_LOG_LEVEL_DEBUG, MONO_TRACE_AOT, "DIRECT CALL: %s by %s", name, method ? mono_method_full_name (method, TRUE) : "");
	g_free (name);
	direct_call = TRUE;
	direct_call_target = callee_cfg->asm_symbol;
	patch_info->type = MONO_PATCH_INFO_NONE;
	acfg->stats.direct_calls ++;
	}
	}
	acfg->stats.all_calls ++;
	} else if (patch_info->type == MONO_PATCH_INFO_ICALL_ADDR_CALL) {
	if (!got_only && is_direct_callable (acfg, method, patch_info)) {
	if (!(patch_info->data.method->flags & METHOD_ATTRIBUTE_PINVOKE_IMPL))
	direct_pinvoke = lookup_icall_symbol_name_aot (patch_info->data.method);
	else
	direct_pinvoke = get_pinvoke_import (acfg, patch_info->data.method);
	if (direct_pinvoke && !never_direct_pinvoke (direct_pinvoke)) {
	direct_call = TRUE;
	g_assert (strlen (direct_pinvoke) < 1000);
	direct_call_target = g_strdup_printf ("%s%s", acfg->user_symbol_prefix, direct_pinvoke);
	}
	}
	} else if (patch_info->type == MONO_PATCH_INFO_JIT_ICALL_ADDR) {
	const char *sym = mono_find_jit_icall_info (patch_info->data.jit_icall_id)->c_symbol;
	if (!got_only && sym && acfg->aot_opts.direct_icalls) {
	/* Call to a C function implementing a jit icall */
	direct_call = TRUE;
	external_call = TRUE;
	g_assert (strlen (sym) < 1000);
	direct_call_target = g_strdup_printf ("%s%s", acfg->user_symbol_prefix, sym);
	}
	} else if (patch_info->type == MONO_PATCH_INFO_JIT_ICALL_ID) {
	MonoJitICallInfo * const info = mono_find_jit_icall_info (patch_info->data.jit_icall_id);
	const char * const sym = info->c_symbol;
	if (!got_only && sym && acfg->aot_opts.direct_icalls && info->func == info->wrapper) {
	/* Call to a jit icall without a wrapper */
	direct_call = TRUE;

Overall, with proper retrieval of is_byreflike and disabled direct call transformation, dedup can be enabled in HelloiOS application. Next steps include testing the dedup in MAUI application and testing CI lanes. /cc: @ivanpovazan @SamMonoRT

[ivanpovazan]

@kotlarmilos nice progress!
If I understand correctly, trying it out with MAUI is limited currently to Debug mode without LLVM, correct?

[kotlarmilos]

@kotlarmilos nice progress! If I understand correctly, trying it out with MAUI is limited currently to Debug mode without LLVM, correct?

With proper code changes it works in all configurations. We have to find appropriate fix for is_byreflike, but it might be separate issue. Here is a branch that can be used for a MAUI application: https://github.com/kotlarmilos/runtime/tree/improvement/dedup-ios