diff --git a/core/base_rules.mk b/core/base_rules.mk
index a0a3582..42dfc1b 100644
--- a/core/base_rules.mk
+++ b/core/base_rules.mk
@@ -221,6 +221,33 @@
 LOCAL_INTERMEDIATE_TARGETS += $(LOCAL_BUILT_MODULE)
 
 ###########################################################
+## Create .toc files from shared objects to reduce unnecessary rebuild
+# .toc files have the list of external dynamic symbols without their addresses.
+# For ninja build, .toc files will be updated only when the content of .toc
+# files are changed. As .KATI_RESTAT is specified to .toc files, dependent
+# binaries of a .toc file will be rebuilt only when the content of
+# the .toc file is changed.
+###########################################################
+ifeq ($(LOCAL_MODULE_CLASS),SHARED_LIBRARIES)
+LOCAL_INTERMEDIATE_TARGETS += $(LOCAL_BUILT_MODULE).toc
+$(LOCAL_BUILT_MODULE).toc: $(LOCAL_BUILT_MODULE)
+ifeq ($(BUILDING_WITH_NINJA),true)
+	$(call $(PRIVATE_2ND_ARCH_VAR_PREFIX)$(PRIVATE_PREFIX)transform-shared-lib-to-toc,$<,$@.tmp)
+	$(hide) if cmp -s $@.tmp $@ ; then \
+		  rm $@.tmp ; \
+		else \
+		  mv $@.tmp $@ ; \
+		fi
+else
+	@# make doesn't support restat. We always update .toc files so the dependents will always be updated too.
+	$(call $(PRIVATE_2ND_ARCH_VAR_PREFIX)$(PRIVATE_PREFIX)transform-shared-lib-to-toc,$<,$@)
+endif
+
+# Kati adds restat=1 to ninja. GNU make does nothing for this.
+.KATI_RESTAT: $(LOCAL_BUILT_MODULE).toc
+endif
+
+###########################################################
 ## logtags: Add .logtags files to global list
 ###########################################################
 
diff --git a/core/binary.mk b/core/binary.mk
index e9b2265..d3b536d 100644
--- a/core/binary.mk
+++ b/core/binary.mk
@@ -1175,6 +1175,7 @@
     $(addprefix $($(LOCAL_2ND_ARCH_VAR_PREFIX)$(my_prefix)OUT_INTERMEDIATE_LIBRARIES)/, \
       $(addsuffix $(so_suffix), \
         $(my_shared_libraries)))
+built_shared_library_tocs := $(addsuffix .toc, $(built_shared_libraries))
 
 # Add the NDK libraries to the built module dependency
 my_system_shared_libraries_fullpath := \
@@ -1188,6 +1189,8 @@
     $(addprefix $($(LOCAL_2ND_ARCH_VAR_PREFIX)$(my_prefix)OUT_INTERMEDIATE_LIBRARIES)/, \
       $(addsuffix $(so_suffix), \
         $(installed_shared_library_module_names)))
+built_shared_library_tocs := $(addsuffix .toc, $(built_shared_libraries))
+my_system_shared_libraries_fullpath :=
 endif
 
 built_static_libraries := \
@@ -1282,7 +1285,8 @@
 ###########################################################
 # all_libraries is used for the dependencies on LOCAL_BUILT_MODULE.
 all_libraries := \
-    $(built_shared_libraries) \
+    $(built_shared_library_tocs) \
+    $(my_system_shared_libraries_fullpath) \
     $(built_static_libraries) \
     $(built_whole_libraries)
 
diff --git a/core/combo/HOST_CROSS_windows-x86.mk b/core/combo/HOST_CROSS_windows-x86.mk
index c5a713c..c2a65bc 100644
--- a/core/combo/HOST_CROSS_windows-x86.mk
+++ b/core/combo/HOST_CROSS_windows-x86.mk
@@ -40,6 +40,13 @@
 $(combo_var_prefix)CC := $(TOOLS_PREFIX)gcc
 $(combo_var_prefix)CXX := $(TOOLS_PREFIX)g++
 $(combo_var_prefix)AR := $(TOOLS_PREFIX)ar
+$(combo_var_prefix)NM := $(TOOLS_PREFIX)nm
+$(combo_var_prefix)OBJDUMP := $(TOOLS_PREFIX)objdump
+
+define $(combo_var_prefix)transform-shared-lib-to-toc
+$(hide) $($(PRIVATE_2ND_ARCH_VAR_PREFIX)$(PRIVATE_PREFIX)OBJDUMP) -x $(1) | grep "^Name" | cut -f3 -d" " > $(2)
+$(hide) $($(PRIVATE_2ND_ARCH_VAR_PREFIX)$(PRIVATE_PREFIX)NM) -g -f p $(1) | cut -f1-2 -d" " >> $(2)
+endef
 
 $(combo_var_prefix)GLOBAL_LDFLAGS += \
     --enable-stdcall-fixup
diff --git a/core/combo/HOST_darwin-x86.mk b/core/combo/HOST_darwin-x86.mk
index 85c883c..fc56e52 100644
--- a/core/combo/HOST_darwin-x86.mk
+++ b/core/combo/HOST_darwin-x86.mk
@@ -36,6 +36,10 @@
 $(combo_2nd_arch_prefix)HOST_CC  := $($(combo_2nd_arch_prefix)HOST_TOOLCHAIN_PREFIX)-gcc
 $(combo_2nd_arch_prefix)HOST_CXX := $($(combo_2nd_arch_prefix)HOST_TOOLCHAIN_PREFIX)-g++
 
+define $(combo_var_prefix)transform-shared-lib-to-toc
+$(call _gen_toc_command_for_macho,$(1),$(2))
+endef
+
 # gcc location for clang; to be updated when clang is updated
 # HOST_TOOLCHAIN_ROOT is a Darwin-specific define
 $(combo_2nd_arch_prefix)HOST_TOOLCHAIN_FOR_CLANG := $($(combo_2nd_arch_prefix)HOST_TOOLCHAIN_ROOT)
diff --git a/core/combo/HOST_darwin-x86_64.mk b/core/combo/HOST_darwin-x86_64.mk
index 93a1b3e..251455f 100644
--- a/core/combo/HOST_darwin-x86_64.mk
+++ b/core/combo/HOST_darwin-x86_64.mk
@@ -36,6 +36,10 @@
 HOST_CC  := $(HOST_TOOLCHAIN_PREFIX)-gcc
 HOST_CXX := $(HOST_TOOLCHAIN_PREFIX)-g++
 
+define $(combo_var_prefix)transform-shared-lib-to-toc
+$(call _gen_toc_command_for_macho,$(1),$(2))
+endef
+
 # gcc location for clang; to be updated when clang is updated
 # HOST_TOOLCHAIN_ROOT is a Darwin-specific define
 HOST_TOOLCHAIN_FOR_CLANG := $(HOST_TOOLCHAIN_ROOT)
diff --git a/core/combo/HOST_linux-x86.mk b/core/combo/HOST_linux-x86.mk
index 4caf607..b5efc71 100644
--- a/core/combo/HOST_linux-x86.mk
+++ b/core/combo/HOST_linux-x86.mk
@@ -23,6 +23,12 @@
 $(combo_2nd_arch_prefix)HOST_CC  := $($(combo_2nd_arch_prefix)HOST_TOOLCHAIN_PREFIX)gcc
 $(combo_2nd_arch_prefix)HOST_CXX := $($(combo_2nd_arch_prefix)HOST_TOOLCHAIN_PREFIX)g++
 $(combo_2nd_arch_prefix)HOST_AR  := $($(combo_2nd_arch_prefix)HOST_TOOLCHAIN_PREFIX)ar
+$(combo_2nd_arch_prefix)HOST_READELF  := $($(combo_2nd_arch_prefix)HOST_TOOLCHAIN_PREFIX)readelf
+$(combo_2nd_arch_prefix)HOST_NM  := $($(combo_2nd_arch_prefix)HOST_TOOLCHAIN_PREFIX)nm
+
+define $(combo_var_prefix)transform-shared-lib-to-toc
+$(call _gen_toc_command_for_elf,$(1),$(2))
+endef
 
 # gcc location for clang; to be updated when clang is updated
 $(combo_2nd_arch_prefix)HOST_TOOLCHAIN_FOR_CLANG := prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8
diff --git a/core/combo/HOST_linux-x86_64.mk b/core/combo/HOST_linux-x86_64.mk
index 3708137..9a77324 100644
--- a/core/combo/HOST_linux-x86_64.mk
+++ b/core/combo/HOST_linux-x86_64.mk
@@ -23,6 +23,12 @@
 HOST_CC  := $(HOST_TOOLCHAIN_PREFIX)gcc
 HOST_CXX := $(HOST_TOOLCHAIN_PREFIX)g++
 HOST_AR  := $(HOST_TOOLCHAIN_PREFIX)ar
+HOST_READELF  := $(HOST_TOOLCHAIN_PREFIX)readelf
+HOST_NM  := $(HOST_TOOLCHAIN_PREFIX)nm
+
+define $(combo_var_prefix)transform-shared-lib-to-toc
+$(call _gen_toc_command_for_elf,$(1),$(2))
+endef
 
 # gcc location for clang; to be updated when clang is updated
 HOST_TOOLCHAIN_FOR_CLANG := prebuilts/gcc/linux-x86/host/x86_64-linux-glibc2.15-4.8
diff --git a/core/combo/TARGET_linux-arm.mk b/core/combo/TARGET_linux-arm.mk
index 5f0f1d2..485e48c 100644
--- a/core/combo/TARGET_linux-arm.mk
+++ b/core/combo/TARGET_linux-arm.mk
@@ -63,6 +63,11 @@
 $(combo_2nd_arch_prefix)TARGET_LD := $($(combo_2nd_arch_prefix)TARGET_TOOLS_PREFIX)ld
 $(combo_2nd_arch_prefix)TARGET_READELF := $($(combo_2nd_arch_prefix)TARGET_TOOLS_PREFIX)readelf
 $(combo_2nd_arch_prefix)TARGET_STRIP := $($(combo_2nd_arch_prefix)TARGET_TOOLS_PREFIX)strip
+$(combo_2nd_arch_prefix)TARGET_NM := $($(combo_2nd_arch_prefix)TARGET_TOOLS_PREFIX)nm
+
+define $(combo_var_prefix)transform-shared-lib-to-toc
+$(call _gen_toc_command_for_elf,$(1),$(2))
+endef
 
 $(combo_2nd_arch_prefix)TARGET_NO_UNDEFINED_LDFLAGS := -Wl,--no-undefined
 
diff --git a/core/combo/TARGET_linux-arm64.mk b/core/combo/TARGET_linux-arm64.mk
index b213ea7..1eb3240 100644
--- a/core/combo/TARGET_linux-arm64.mk
+++ b/core/combo/TARGET_linux-arm64.mk
@@ -63,6 +63,11 @@
 TARGET_LD := $(TARGET_TOOLS_PREFIX)ld
 TARGET_READELF := $(TARGET_TOOLS_PREFIX)readelf
 TARGET_STRIP := $(TARGET_TOOLS_PREFIX)strip
+TARGET_NM := $(TARGET_TOOLS_PREFIX)nm
+
+define $(combo_var_prefix)transform-shared-lib-to-toc
+$(call _gen_toc_command_for_elf,$(1),$(2))
+endef
 
 TARGET_NO_UNDEFINED_LDFLAGS := -Wl,--no-undefined
 
diff --git a/core/combo/TARGET_linux-mips.mk b/core/combo/TARGET_linux-mips.mk
index 8e117eb..be05302 100644
--- a/core/combo/TARGET_linux-mips.mk
+++ b/core/combo/TARGET_linux-mips.mk
@@ -63,6 +63,11 @@
 $(combo_2nd_arch_prefix)TARGET_LD := $($(combo_2nd_arch_prefix)TARGET_TOOLS_PREFIX)ld
 $(combo_2nd_arch_prefix)TARGET_READELF := $($(combo_2nd_arch_prefix)TARGET_TOOLS_PREFIX)readelf
 $(combo_2nd_arch_prefix)TARGET_STRIP := $($(combo_2nd_arch_prefix)TARGET_TOOLS_PREFIX)strip
+$(combo_2nd_arch_prefix)TARGET_NM := $($(combo_2nd_arch_prefix)TARGET_TOOLS_PREFIX)nm
+
+define $(combo_var_prefix)transform-shared-lib-to-toc
+$(call _gen_toc_command_for_elf,$(1),$(2))
+endef
 
 $(combo_2nd_arch_prefix)TARGET_NO_UNDEFINED_LDFLAGS := -Wl,--no-undefined
 
diff --git a/core/combo/TARGET_linux-mips64.mk b/core/combo/TARGET_linux-mips64.mk
index 565083a..9704b6b 100644
--- a/core/combo/TARGET_linux-mips64.mk
+++ b/core/combo/TARGET_linux-mips64.mk
@@ -63,6 +63,11 @@
 TARGET_LD := $(TARGET_TOOLS_PREFIX)ld
 TARGET_READELF := $(TARGET_TOOLS_PREFIX)readelf
 TARGET_STRIP := $(TARGET_TOOLS_PREFIX)strip
+TARGET_NM := $(TARGET_TOOLS_PREFIX)nm
+
+define $(combo_var_prefix)transform-shared-lib-to-toc
+$(call _gen_toc_command_for_elf,$(1),$(2))
+endef
 
 TARGET_NO_UNDEFINED_LDFLAGS := -Wl,--no-undefined
 
diff --git a/core/combo/TARGET_linux-x86.mk b/core/combo/TARGET_linux-x86.mk
index 5fff641..c4cb0f8 100644
--- a/core/combo/TARGET_linux-x86.mk
+++ b/core/combo/TARGET_linux-x86.mk
@@ -56,6 +56,11 @@
 $(combo_2nd_arch_prefix)TARGET_LD := $($(combo_2nd_arch_prefix)TARGET_TOOLS_PREFIX)ld
 $(combo_2nd_arch_prefix)TARGET_READELF := $($(combo_2nd_arch_prefix)TARGET_TOOLS_PREFIX)readelf
 $(combo_2nd_arch_prefix)TARGET_STRIP := $($(combo_2nd_arch_prefix)TARGET_TOOLS_PREFIX)strip
+$(combo_2nd_arch_prefix)TARGET_NM := $($(combo_2nd_arch_prefix)TARGET_TOOLS_PREFIX)nm
+
+define $(combo_var_prefix)transform-shared-lib-to-toc
+$(call _gen_toc_command_for_elf,$(1),$(2))
+endef
 
 ifneq ($(wildcard $($(combo_2nd_arch_prefix)TARGET_CC)),)
 $(combo_2nd_arch_prefix)TARGET_LIBGCC := \
diff --git a/core/combo/TARGET_linux-x86_64.mk b/core/combo/TARGET_linux-x86_64.mk
index cacfae1..b7ec50b 100644
--- a/core/combo/TARGET_linux-x86_64.mk
+++ b/core/combo/TARGET_linux-x86_64.mk
@@ -56,6 +56,11 @@
 TARGET_LD := $(TARGET_TOOLS_PREFIX)ld
 TARGET_READELF := $(TARGET_TOOLS_PREFIX)readelf
 TARGET_STRIP := $(TARGET_TOOLS_PREFIX)strip
+TARGET_NM := $(TARGET_TOOLS_PREFIX)nm
+
+define $(combo_var_prefix)transform-shared-lib-to-toc
+$(call _gen_toc_command_for_elf,$(1),$(2))
+endef
 
 ifneq ($(wildcard $(TARGET_CC)),)
 TARGET_LIBGCC := \
diff --git a/core/config.mk b/core/config.mk
index 5678a83..9c275f7 100644
--- a/core/config.mk
+++ b/core/config.mk
@@ -281,6 +281,18 @@
 endif
 TARGET_CPU_ABI2 := $(strip $(TARGET_CPU_ABI2))
 
+# Commands to generate .toc file common to ELF .so files.
+define _gen_toc_command_for_elf
+$(hide) $($(PRIVATE_2ND_ARCH_VAR_PREFIX)$(PRIVATE_PREFIX)READELF) -d $(1) | grep SONAME > $(2)
+$(hide) $($(PRIVATE_2ND_ARCH_VAR_PREFIX)$(PRIVATE_PREFIX)NM) -gD -f p $(1) | cut -f1-2 -d" " >> $(2)
+endef
+
+# Commands to generate .toc file from Darwin dynamic library.
+define _gen_toc_command_for_macho
+$(hide) otool -l $(1) | grep LC_ID_DYLIB -A 5 > $(2)
+$(hide) nm -gP $(1) | cut -f1-2 -d" " | grep -v U$$ >> $(2)
+endef
+
 combo_target := HOST_
 combo_2nd_arch_prefix :=
 include $(BUILD_SYSTEM)/combo/select.mk
diff --git a/core/definitions.mk b/core/definitions.mk
index 5a6a411..1c8f41a 100644
--- a/core/definitions.mk
+++ b/core/definitions.mk
@@ -1516,7 +1516,6 @@
 $(transform-o-to-shared-lib-inner)
 endef
 
-
 ###########################################################
 ## Commands for filtering a target executable or library
 ###########################################################