diff --git a/core/config.mk b/core/config.mk
index 450c06c..dbb40f5 100644
--- a/core/config.mk
+++ b/core/config.mk
@@ -571,6 +571,7 @@
 # ijar converts a .jar file to a smaller .jar file which only has its
 # interfaces.
 IJAR := $(HOST_OUT_EXECUTABLES)/ijar$(BUILD_EXECUTABLE_SUFFIX)
+DEXDUMP := $(HOST_OUT_EXECUTABLES)/dexdump2$(BUILD_EXECUTABLE_SUFFIX)
 
 # relocation packer
 RELOCATION_PACKER := prebuilts/misc/$(BUILD_OS)-$(HOST_PREBUILT_ARCH)/relocation_packer/relocation_packer
diff --git a/core/definitions.mk b/core/definitions.mk
index 5119d65..742a56c 100644
--- a/core/definitions.mk
+++ b/core/definitions.mk
@@ -1948,9 +1948,9 @@
 endef
 endif
 
-## Rule to creates a table of contents from a .jar file.
+## Rule to create a table of contents from a .jar file.
 ## Must be called with $(eval).
-# $1: A .jar file
+# $(1): A .jar file
 define _transform-jar-to-toc
 $1.toc: $1 | $(IJAR)
 	@echo Generating TOC: $$@
@@ -1959,11 +1959,40 @@
 endef
 
 ## Define a rule which generates .jar.toc and mark it as .KATI_RESTAT.
+# $(1): A .jar file
 define define-jar-to-toc-rule
 $(eval $(call _transform-jar-to-toc,$1))\
 $(eval .KATI_RESTAT: $1.toc)
 endef
 
+ifeq (,$(TARGET_BUILD_APPS))
+
+## Rule to create a table of contents from a .dex file.
+## Must be called with $(eval).
+# $(1): The directory which contains classes*.dex files
+define _transform-dex-to-toc
+$1/classes.dex.toc: PRIVATE_INPUT_DEX_FILES := $1/classes*.dex
+$1/classes.dex.toc: $1/classes.dex $(DEXDUMP)
+	@echo Generating TOC: $$@
+	$(hide) $(DEXDUMP) -l xml $$(PRIVATE_INPUT_DEX_FILES) > $$@.tmp
+	$$(call commit-change-for-toc,$$@)
+endef
+
+## Define a rule which generates .dex.toc and mark it as .KATI_RESTAT.
+# $(1): The directory which contains classes*.dex files
+define define-dex-to-toc-rule
+$(eval $(call _transform-dex-to-toc,$1))\
+$(eval .KATI_RESTAT: $1/classes.dex.toc)
+endef
+
+else
+
+# Turn off .toc optimization for apps build as we cannot build dexdump.
+define define-dex-to-toc-rule
+endef
+
+endif  # TARGET_BUILD_APPS
+
 
 # Invoke Jack to compile java from source to jack files without shrink or obfuscation.
 #
diff --git a/core/java.mk b/core/java.mk
index 9bdb77f..f6f52dc 100644
--- a/core/java.mk
+++ b/core/java.mk
@@ -658,6 +658,11 @@
 	@echo Building with Jack: $@
 	$(java-to-jack)
 
+# Update timestamps of .toc files for static java libraries so
+# dependents will be always rebuilt.
+$(built_dex).toc: $(full_classes_jack)
+	touch $@
+
 else #LOCAL_IS_STATIC_JAVA_LIBRARY
 $(built_dex_intermediate): PRIVATE_CLASSES_JACK := $(full_classes_jack)
 
@@ -671,6 +676,8 @@
 $(full_classes_jack): $(built_dex_intermediate)
 	$(hide) touch $@
 
+$(call define-dex-to-toc-rule, $(intermediates.COMMON))
+
 endif #LOCAL_IS_STATIC_JAVA_LIBRARY
 
 $(noshrob_classes_jack): PRIVATE_JACK_INTERMEDIATES_DIR := $(intermediates.COMMON)/jack-noshrob-rsc
diff --git a/core/java_common.mk b/core/java_common.mk
index 6694f16..f11e723 100644
--- a/core/java_common.mk
+++ b/core/java_common.mk
@@ -293,6 +293,10 @@
 
 full_shared_jack_libs := $(call jack-lib-files,$(LOCAL_JAVA_LIBRARIES),$(LOCAL_IS_HOST_MODULE))
 full_jack_lib_deps := $(call jack-lib-deps,$(LOCAL_JAVA_LIBRARIES),$(LOCAL_IS_HOST_MODULE))
+# Turn off .toc optimization for apps build as we cannot build dexdump.
+ifeq (,$(TARGET_BUILD_APPS))
+full_jack_lib_deps := $(patsubst %.jack, %.dex.toc, $(full_jack_lib_deps))
+endif
 
 else # LOCAL_IS_HOST_MODULE
 
diff --git a/core/prebuilt_internal.mk b/core/prebuilt_internal.mk
index 9ff348c..b0af228 100644
--- a/core/prebuilt_internal.mk
+++ b/core/prebuilt_internal.mk
@@ -328,6 +328,11 @@
         $(LOCAL_ADDITIONAL_DEPENDENCIES) $(JILL_JAR) $(JACK)
 	$(transform-jar-to-jack)
 
+# Update timestamps of .toc files for prebuilts so dependents will be
+# always rebuilt.
+$(intermediates.COMMON)/classes.dex.toc: $(intermediates.COMMON)/classes.jack
+	touch $@
+
 endif # JAVA_LIBRARIES
 
 $(built_module) : $(LOCAL_MODULE_MAKEFILE_DEP) $(LOCAL_ADDITIONAL_DEPENDENCIES)