diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..415166b
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+*.pyc
+*.*~
diff --git a/Android.bp b/Android.bp
index 61c7605..545cc80 100644
--- a/Android.bp
+++ b/Android.bp
@@ -35,21 +35,36 @@
 
 se_cil_compat_map {
     name: "26.0.cil",
-    srcs: [
-        ":26.0.board.compat.map",
-    ],
+    bottom_half: [":26.0.board.compat.map"],
+    top_half: "27.0.cil",
 }
 
 se_cil_compat_map {
     name: "27.0.cil",
-    srcs: [
-        ":27.0.board.compat.map",
-    ],
+    bottom_half: [":27.0.board.compat.map"],
+    top_half: "28.0.cil",
 }
 
 se_cil_compat_map {
     name: "28.0.cil",
-    srcs: [
-        ":28.0.board.compat.map",
-    ],
+    bottom_half: [":28.0.board.compat.map"],
+    // top_half: "29.0.cil",
+}
+
+se_cil_compat_map {
+    name: "26.0.ignore.cil",
+    bottom_half: ["private/compat/26.0/26.0.ignore.cil"],
+    top_half: "27.0.ignore.cil",
+}
+
+se_cil_compat_map {
+    name: "27.0.ignore.cil",
+    bottom_half: ["private/compat/27.0/27.0.ignore.cil"],
+    top_half: "28.0.ignore.cil",
+}
+
+se_cil_compat_map {
+    name: "28.0.ignore.cil",
+    bottom_half: ["private/compat/28.0/28.0.ignore.cil"],
+    // top_half: "29.0.ignore.cil",
 }
diff --git a/build/soong/cil_compat_map.go b/build/soong/cil_compat_map.go
index 8f55797..2402d75 100644
--- a/build/soong/cil_compat_map.go
+++ b/build/soong/cil_compat_map.go
@@ -21,10 +21,28 @@
 	"android/soong/android"
 	"fmt"
 	"io"
+
+	"github.com/google/blueprint/proptools"
+	"github.com/google/blueprint"
 )
 
 var (
 	pctx = android.NewPackageContext("android/soong/selinux")
+
+	combine_maps = pctx.HostBinToolVariable("combine_maps", "combine_maps")
+	combineMapsCmd = "${combine_maps} -t ${topHalf} -b ${bottomHalf} -o $out"
+	combineMapsRule = pctx.StaticRule(
+		"combineMapsRule",
+		blueprint.RuleParams{
+			Command: combineMapsCmd,
+			CommandDeps: []string{"${combine_maps}"},
+		},
+		"topHalf",
+		"bottomHalf",
+	)
+
+	String = proptools.String
+	TopHalfDepTag = dependencyTag{name: "top"}
 )
 
 func init() {
@@ -40,18 +58,43 @@
 }
 
 type cilCompatMapProperties struct {
-	// list of source (.cil) files used to build an sepolicy compatibility mapping
-	// file. srcs may reference the outputs of other modules that produce source
-	// files like genrule or filegroup using the syntax ":module". srcs has to be
-	// non-empty.
-	Srcs []string
+	// se_cil_compat_map module representing a compatibility mapping file for
+	// platform versions (x->y). Bottom half represents a mapping (y->z).
+	// Together the halves are used to generate a (x->z) mapping.
+	Top_half *string
+	// list of source (.cil) files used to build an the bottom half of sepolicy
+	// compatibility mapping file. bottom_half may reference the outputs of
+	// other modules that produce source files like genrule or filegroup using
+	// the syntax ":module". srcs has to be non-empty.
+	Bottom_half []string
 }
 
 type cilCompatMap struct {
 	android.ModuleBase
 	properties cilCompatMapProperties
 	// (.intermediate) module output path as installation source.
-	installSource android.OptionalPath
+	installSource android.Path
+}
+
+type CilCompatMapGenerator interface {
+	GeneratedMapFile() android.Path
+}
+
+type dependencyTag struct {
+	blueprint.BaseDependencyTag
+	name string
+}
+
+func expandTopHalf(ctx android.ModuleContext) android.OptionalPath {
+	var topHalf android.OptionalPath
+	ctx.VisitDirectDeps(func(dep android.Module) {
+		depTag := ctx.OtherModuleDependencyTag(dep)
+		switch depTag {
+		case TopHalfDepTag:
+			topHalf = android.OptionalPathForPath(dep.(CilCompatMapGenerator).GeneratedMapFile())
+		}
+	})
+	return topHalf
 }
 
 func expandSeSources(ctx android.ModuleContext, srcFiles []string) android.Paths {
@@ -81,29 +124,52 @@
 }
 
 func (c *cilCompatMap) GenerateAndroidBuildActions(ctx android.ModuleContext) {
-	srcFiles := expandSeSources(ctx, c.properties.Srcs)
+	srcFiles := expandSeSources(ctx, c.properties.Bottom_half)
+
 	for _, src := range srcFiles {
 		if src.Ext() != ".cil" {
-			ctx.PropertyErrorf("srcs", "%s has to be a .cil file.", src.String())
+			ctx.PropertyErrorf("bottom_half", "%s has to be a .cil file.", src.String())
 		}
 	}
 
-	out := android.PathForModuleGen(ctx, c.Name())
+	bottomHalf := android.PathForModuleGen(ctx, "bottom_half")
 	ctx.Build(pctx, android.BuildParams{
 		Rule:   android.Cat,
-		Output: out,
+		Output: bottomHalf,
 		Inputs: srcFiles,
 	})
-	c.installSource = android.OptionalPathForPath(out)
+
+	topHalf := expandTopHalf(ctx)
+	if (topHalf.Valid()) {
+		out := android.PathForModuleGen(ctx, c.Name())
+		ctx.ModuleBuild(pctx, android.ModuleBuildParams{
+			Rule: combineMapsRule,
+			Output: out,
+			Implicits: []android.Path{
+				topHalf.Path(),
+				bottomHalf,
+			},
+			Args: map[string]string{
+				"topHalf": topHalf.String(),
+				"bottomHalf": bottomHalf.String(),
+			},
+		})
+		c.installSource = out
+	} else {
+		c.installSource = bottomHalf
+	}
 }
 
 func (c *cilCompatMap) DepsMutator(ctx android.BottomUpMutatorContext) {
-	android.ExtractSourcesDeps(ctx, c.properties.Srcs)
+	android.ExtractSourcesDeps(ctx, c.properties.Bottom_half)
+	if (c.properties.Top_half != nil) {
+		ctx.AddDependency(c, TopHalfDepTag, String(c.properties.Top_half))
+	}
 }
 
 func (c *cilCompatMap) AndroidMk() android.AndroidMkData {
 	ret := android.AndroidMkData{
-		OutputFile: c.installSource,
+		OutputFile: android.OptionalPathForPath(c.installSource),
 		Class:      "ETC",
 	}
 	ret.Extra = append(ret.Extra, func(w io.Writer, outputFile android.Path) {
@@ -111,3 +177,9 @@
 	})
 	return ret
 }
+
+var _ CilCompatMapGenerator = (*cilCompatMap)(nil)
+
+func (c *cilCompatMap) GeneratedMapFile() android.Path {
+	return c.installSource
+}
diff --git a/private/compat/26.0/26.0.ignore.cil b/private/compat/26.0/26.0.ignore.cil
index 5f4950c..7e3fdbc 100644
--- a/private/compat/26.0/26.0.ignore.cil
+++ b/private/compat/26.0/26.0.ignore.cil
@@ -1,9 +1,11 @@
 ;; new_objects - a collection of types that have been introduced that have no
 ;;   analogue in older policy.  Thus, we do not need to map these types to
 ;;   previous ones.  Add here to pass checkapi tests.
+(type new_objects)
 (typeattribute new_objects)
 (typeattributeset new_objects
-  ( activity_task_service
+  ( new_objects
+    activity_task_service
     adb_service
     adbd_exec
     app_binding_service
@@ -182,8 +184,9 @@
 ;; private_objects - a collection of types that were labeled differently in
 ;;     older policy, but that should not remain accessible to vendor policy.
 ;;     Thus, these types are also not mapped, but recorded for checkapi tests
+(type priv_objects)
 (typeattribute priv_objects)
 (typeattributeset priv_objects
-     ( adbd_tmpfs
-       untrusted_app_27_tmpfs
-     ))
+  ( priv_objects
+    adbd_tmpfs
+    untrusted_app_27_tmpfs))
diff --git a/private/compat/27.0/27.0.ignore.cil b/private/compat/27.0/27.0.ignore.cil
index 891f1a3..7d5017d 100644
--- a/private/compat/27.0/27.0.ignore.cil
+++ b/private/compat/27.0/27.0.ignore.cil
@@ -1,9 +1,11 @@
 ;; new_objects - a collection of types that have been introduced that have no
 ;;   analogue in older policy.  Thus, we do not need to map these types to
 ;;   previous ones.  Add here to pass checkapi tests.
+(type new_objects)
 (typeattribute new_objects)
 (typeattributeset new_objects
-  ( activity_task_service
+  ( new_objects
+    activity_task_service
     adb_service
     app_binding_service
     atrace
@@ -160,5 +162,8 @@
 ;; private_objects - a collection of types that were labeled differently in
 ;;     older policy, but that should not remain accessible to vendor policy.
 ;;     Thus, these types are also not mapped, but recorded for checkapi tests
+(type priv_objects)
 (typeattribute priv_objects)
-(typeattributeset priv_objects (untrusted_app_27_tmpfs))
+(typeattributeset priv_objects
+  ( priv_objects
+    untrusted_app_27_tmpfs))
diff --git a/private/compat/28.0/28.0.ignore.cil b/private/compat/28.0/28.0.ignore.cil
index 4310f03..63cfcb8 100644
--- a/private/compat/28.0/28.0.ignore.cil
+++ b/private/compat/28.0/28.0.ignore.cil
@@ -1,9 +1,11 @@
 ;; new_objects - a collection of types that have been introduced that have no
 ;;   analogue in older policy.  Thus, we do not need to map these types to
 ;;   previous ones.  Add here to pass checkapi tests.
+(type new_objects)
 (typeattribute new_objects)
 (typeattributeset new_objects
-  ( activity_task_service
+  ( new_objects
+    activity_task_service
     adb_service
     app_binding_service
     biometric_service
diff --git a/tests/Android.bp b/tests/Android.bp
index abb5e35..670d29d 100644
--- a/tests/Android.bp
+++ b/tests/Android.bp
@@ -63,3 +63,11 @@
     required: ["libsepolwrap"],
     defaults: ["py2_only"],
 }
+
+python_binary_host {
+    name: "combine_maps",
+    srcs: [
+        "combine_maps.py",
+        "mini_parser.py",
+    ],
+}
diff --git a/tests/combine_maps.py b/tests/combine_maps.py
new file mode 100644
index 0000000..a2bf38d
--- /dev/null
+++ b/tests/combine_maps.py
@@ -0,0 +1,66 @@
+# Copyright 2018 - The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+"""Tool to combine SEPolicy mapping file.
+
+Say, x, y, z are platform SEPolicy versions such that x > y > z. Then given two
+mapping files from x to y (top) and y to z (bottom), it's possible to construct
+a mapping file from x to z. We do the following to combine two maps.
+1. Add all new types declarations from top to bottom.
+2. Say, a new type "bar" in top is mapped like this "foo_V_v<-bar", then we map
+"bar" to whatever "foo" is mapped to in the bottom map. We do this for all new
+types in the top map.
+
+More generally, we can correctly construct x->z from x->y' and y"->z as long as
+y">y'.
+
+This file contains the implementation of combining two mapping files.
+"""
+import argparse
+import re
+from mini_parser import MiniCilParser
+
+def Combine(top, bottom):
+    bottom.types.update(top.types)
+
+    for top_ta in top.typeattributesets:
+        top_type_set = top.typeattributesets[top_ta]
+        if len(top_type_set) == 1:
+            continue
+
+        m = re.match(r"(\w+)_\d+_\d+", top_ta)
+        # Typeattributes in V.v.cil have _V_v suffix, but not in V.v.ignore.cil
+        bottom_type = m.group(1) if m else top_ta
+
+        for bottom_ta in bottom.rTypeattributesets[bottom_type]:
+            bottom.typeattributesets[bottom_ta].update(top_type_set)
+
+    return bottom
+
+if __name__ == "__main__":
+    parser = argparse.ArgumentParser()
+    parser.add_argument("-t", "--top-map", dest="top_map",
+                        required=True, help="top map file")
+    parser.add_argument("-b", "--bottom-map", dest="bottom_map",
+                        required=True, help="bottom map file")
+    parser.add_argument("-o", "--output-file", dest="output_file",
+                        required=True, help="output map file")
+    args = parser.parse_args()
+
+    top_map_cil = MiniCilParser(args.top_map)
+    bottom_map_cil = MiniCilParser(args.bottom_map)
+    result = Combine(top_map_cil, bottom_map_cil)
+
+    with open(args.output_file, "w") as output:
+        output.write(result.unparse())
diff --git a/tests/mini_parser.py b/tests/mini_parser.py
index 9182c5d..cba9e39 100644
--- a/tests/mini_parser.py
+++ b/tests/mini_parser.py
@@ -12,6 +12,7 @@
     def __init__(self, policyFile):
         self.types = set() # types declared in mapping
         self.pubtypes = set()
+        self.expandtypeattributes = {}
         self.typeattributes = set() # attributes declared in mapping
         self.typeattributesets = {} # sets defined in mapping
         self.rTypeattributesets = {} # reverse mapping of above sets
@@ -27,6 +28,32 @@
         if m:
             self.apiLevel = m.group(1)
 
+    def unparse(self):
+        def wrapParens(stmt):
+            return "(" + stmt + ")"
+
+        def joinWrapParens(entries):
+            return wrapParens(" ".join(entries))
+
+        result = ""
+        for ty in sorted(self.types):
+            result += joinWrapParens(["type", ty]) + "\n"
+
+        for ta in sorted(self.typeattributes):
+            result += joinWrapParens(["typeattribute", ta]) + "\n"
+
+        for eta in sorted(self.expandtypeattributes.items(),
+                          key=lambda x: x[0]):
+            result += joinWrapParens(
+                    ["expandtypeattribute", wrapParens(eta[0]), eta[1]]) + "\n"
+
+        for tas in sorted(self.typeattributesets.items(), key=lambda x: x[0]):
+            result += joinWrapParens(
+                    ["typeattributeset", tas[0],
+                     joinWrapParens(sorted(tas[1]))]) + "\n"
+
+        return result
+
     def _getNextStmt(self, infile):
         parens = 0
         s = ""
@@ -55,6 +82,11 @@
         self.types.add(m.group(1))
         return
 
+    def _parseExpandtypeattribute(self, stmt):
+        m = re.match(r"expandtypeattribute\s+\((.+)\)\s+(true|false)", stmt)
+        self.expandtypeattributes[m.group(1)] = m.group(2)
+        return
+
     def _parseTypeattribute(self, stmt):
         m = re.match(r"typeattribute\s+(.+)", stmt)
         self.typeattributes.add(m.group(1))
@@ -73,7 +105,7 @@
         for t in tas:
             if self.rTypeattributesets.get(t) is None:
                 self.rTypeattributesets[t] = set()
-            self.rTypeattributesets[t].update(set(ta))
+            self.rTypeattributesets[t].update([ta])
 
         # check to see if this typeattributeset is a versioned public type
         pub = re.match(r"(\w+)_\d+_\d+", ta)
@@ -88,6 +120,8 @@
             self._parseTypeattribute(stmt)
         elif re.match(r"typeattributeset\s+.+", stmt):
             self._parseTypeattributeset(stmt)
+        elif re.match(r"expandtypeattribute\s+.+", stmt):
+            self._parseExpandtypeattribute(stmt)
         return
 
 if __name__ == '__main__':
diff --git a/tests/treble_sepolicy_tests.py b/tests/treble_sepolicy_tests.py
index 05549a1..f2d600a 100644
--- a/tests/treble_sepolicy_tests.py
+++ b/tests/treble_sepolicy_tests.py
@@ -240,8 +240,8 @@
     if len(violators) > 0:
         ret += "SELinux: The following public types were found added to the "
         ret += "policy without an entry into the compatibility mapping file(s) "
-        ret += "found in private/compat/" + compatMapping.apiLevel + "/"
-        ret +=  compatMapping.apiLevel + "[.ignore].cil\n"
+        ret += "found in private/compat/V.v/V.v[.ignore].cil, where V.v is the "
+        ret += "latest API level.\n"
         ret += " ".join(str(x) for x in sorted(violators)) + "\n"
     return ret
 
@@ -263,7 +263,8 @@
     if len(violators) > 0:
         ret += "SELinux: The following formerly public types were removed from "
         ret += "policy without a declaration in the compatibility mapping "
-        ret += "file(s) found in prebuilts/api/" + compatMapping.apiLevel + "/\n"
+        ret += "found in private/compat/V.v/V.v[.ignore].cil, where V.v is the "
+        ret += "latest API level.\n"
         ret += " ".join(str(x) for x in sorted(violators)) + "\n"
     return ret
 
diff --git a/treble_sepolicy_tests_for_release.mk b/treble_sepolicy_tests_for_release.mk
index 1ab29b5..e7c73c9 100644
--- a/treble_sepolicy_tests_for_release.mk
+++ b/treble_sepolicy_tests_for_release.mk
@@ -51,8 +51,9 @@
 # targeting the $(version) SELinux release.  This ensures that our policy will build
 # when used on a device that has non-platform policy targetting the $(version) release.
 $(version)_compat := $(intermediates)/$(version)_compat
-$(version)_mapping.cil := $(LOCAL_PATH)/private/compat/$(version)/$(version).cil
-$(version)_mapping.ignore.cil := $(LOCAL_PATH)/private/compat/$(version)/$(version).ignore.cil
+$(version)_mapping.cil := $(call intermediates-dir-for,ETC,$(version).cil)/$(version).cil
+$(version)_mapping.ignore.cil := \
+    $(call intermediates-dir-for,ETC,$(version).ignore.cil)/$(version).ignore.cil
 $(version)_prebuilts_dir := $(LOCAL_PATH)/prebuilts/api/$(version)
 
 # vendor_sepolicy.cil and plat_pub_versioned.cil are the new design to replace