diff --git a/tests/Android.bp b/tests/Android.bp
index 78a631f..8ca952d 100644
--- a/tests/Android.bp
+++ b/tests/Android.bp
@@ -25,34 +25,46 @@
     },
 }
 
+python_library_host {
+    name: "mini_cil_parser",
+    srcs: ["mini_parser.py"],
+}
+
+python_library_host {
+    name: "pysepolwrap",
+    srcs: [
+        "fc_sort.py",
+        "policy.py",
+    ],
+}
+
 python_binary_host {
     name: "treble_sepolicy_tests",
     srcs: [
-        "fc_sort.py",
-        "mini_parser.py",
-        "policy.py",
         "treble_sepolicy_tests.py",
     ],
+    libs: [
+        "mini_cil_parser",
+        "pysepolwrap",
+    ],
     data: [":libsepolwrap"],
 }
 
 python_binary_host {
     name: "sepolicy_tests",
     srcs: [
-        "fc_sort.py",
-        "policy.py",
         "sepolicy_tests.py",
     ],
+    libs: ["pysepolwrap"],
     data: [":libsepolwrap"],
 }
 
 python_binary_host {
     name: "searchpolicy",
     srcs: [
-        "fc_sort.py",
-        "policy.py",
         "searchpolicy.py",
     ],
+    libs: ["pysepolwrap"],
     required: ["libsepolwrap"],
 }
 
@@ -60,8 +72,8 @@
     name: "combine_maps",
     srcs: [
         "combine_maps.py",
-        "mini_parser.py",
     ],
+    libs: ["mini_cil_parser"],
 }
 
 python_binary_host {
diff --git a/tools/Android.bp b/tools/Android.bp
index 1ec129d..fcf375d 100644
--- a/tools/Android.bp
+++ b/tools/Android.bp
@@ -67,4 +67,6 @@
 python_binary_host {
     name: "sepolicy_generate_compat",
     srcs: ["sepolicy_generate_compat.py"],
+    libs: ["mini_cil_parser", "pysepolwrap"],
+    data: [":libsepolwrap"],
 }
diff --git a/tools/sepolicy_generate_compat.py b/tools/sepolicy_generate_compat.py
index ab9ed82..317a00e 100644
--- a/tools/sepolicy_generate_compat.py
+++ b/tools/sepolicy_generate_compat.py
@@ -15,19 +15,27 @@
 # limitations under the License.
 
 import argparse
+import distutils.ccompiler
 import glob
 import logging
+import mini_parser
 import os
+import policy
 import shutil
 import subprocess
 import tempfile
 import zipfile
 """This tool generates a mapping file for {ver} core sepolicy."""
 
+temp_dir = ''
 
-def check_run(cmd):
-    logging.debug('Running cmd: %s' % cmd)
-    subprocess.run(cmd, check=True)
+
+def check_run(cmd, cwd=None):
+    if cwd:
+        logging.debug('Running cmd at %s: %s' % (cwd, cmd))
+    else:
+        logging.debug('Running cmd: %s' % cmd)
+    subprocess.run(cmd, cwd=cwd, check=True)
 
 
 def check_output(cmd):
@@ -35,6 +43,15 @@
     return subprocess.run(cmd, check=True, stdout=subprocess.PIPE)
 
 
+def get_android_build_top():
+    ANDROID_BUILD_TOP = os.getenv('ANDROID_BUILD_TOP')
+    if not ANDROID_BUILD_TOP:
+        sys.exit(
+            'Error: Missing ANDROID_BUILD_TOP env variable. Please run '
+            '\'. build/envsetup.sh; lunch <build target>\'. Exiting script.')
+    return ANDROID_BUILD_TOP
+
+
 def fetch_artifact(branch, build, pattern, destination='.'):
     """Fetches build artifacts from Android Build server.
 
@@ -64,15 +81,20 @@
       img_path: string, path to system.img file
       ver: string, version of designated mapping file
       destination: string, destination to pull the mapping file to
+
+    Returns:
+      string, path to extracted mapping file
     """
 
     cmd = [
         'debugfs', '-R',
         'cat system/etc/selinux/mapping/%s.cil' % ver, img_path
     ]
-    with open(os.path.join(destination, '%s.cil' % ver), 'wb') as f:
+    path = os.path.join(destination, '%s.cil' % ver)
+    with open(path, 'wb') as f:
         logging.debug('Extracting %s.cil to %s' % (ver, destination))
         f.write(check_output(cmd).stdout)
+    return path
 
 
 def download_mapping_file(branch, build, ver, destination='.'):
@@ -83,24 +105,55 @@
       build: string, build ID or "latest"
       ver: string, version of designated mapping file (e.g. "32.0")
       destination: string, destination to pull build artifact to
+
+    Returns:
+      string, path to extracted mapping file
     """
-    temp_dir = tempfile.mkdtemp()
+    logging.info('Downloading %s mapping file from branch %s build %s...' %
+                 (ver, branch, build))
+    artifact_pattern = 'aosp_arm64-img-*.zip'
+    fetch_artifact(branch, build, artifact_pattern, temp_dir)
 
-    try:
-        artifact_pattern = 'aosp_arm64-img-*.zip'
-        fetch_artifact(branch, build, artifact_pattern, temp_dir)
+    # glob must succeed
+    zip_path = glob.glob(os.path.join(temp_dir, artifact_pattern))[0]
+    with zipfile.ZipFile(zip_path) as zip_file:
+        logging.debug('Extracting system.img to %s' % temp_dir)
+        zip_file.extract('system.img', temp_dir)
 
-        # glob must succeed
-        zip_path = glob.glob(os.path.join(temp_dir, artifact_pattern))[0]
-        with zipfile.ZipFile(zip_path) as zip_file:
-            logging.debug('Extracting system.img to %s' % temp_dir)
-            zip_file.extract('system.img', temp_dir)
+    system_img_path = os.path.join(temp_dir, 'system.img')
+    return extract_mapping_file_from_img(system_img_path, ver, destination)
 
-        system_img_path = os.path.join(temp_dir, 'system.img')
-        extract_mapping_file_from_img(system_img_path, ver, destination)
-    finally:
-        logging.info('Deleting temporary dir: {}'.format(temp_dir))
-        shutil.rmtree(temp_dir)
+
+def build_base_files(target_version):
+    """ Builds needed base policy files from the source code.
+
+    Args:
+      target_version: string, target version to gerenate the mapping file
+
+    Returns:
+      (string, string, string), paths to base policy, old policy, and pub policy
+      cil
+    """
+    logging.info('building base sepolicy files')
+    build_top = get_android_build_top()
+
+    cmd = [
+        'build/soong/soong_ui.bash',
+        '--make-mode',
+        'dist',
+        'base-sepolicy-files-for-mapping',
+        'TARGET_PRODUCT=aosp_arm64',
+        'TARGET_BUILD_VARIANT=userdebug',
+    ]
+    check_run(cmd, cwd=build_top)
+
+    dist_dir = os.path.join(build_top, 'out', 'dist')
+    base_policy_path = os.path.join(dist_dir, 'base_plat_sepolicy')
+    old_policy_path = os.path.join(dist_dir,
+                                   '%s_plat_sepolicy' % target_version)
+    pub_policy_cil_path = os.path.join(dist_dir, 'base_plat_pub_policy.cil')
+
+    return base_policy_path, old_policy_path, pub_policy_cil_path
 
 
 def get_args():
@@ -111,9 +164,13 @@
         help='Branch to pull build from. e.g. "sc-v2-dev"')
     parser.add_argument('--build', required=True, help='Build ID, or "latest"')
     parser.add_argument(
-        '--version',
+        '--target-version',
         required=True,
-        help='Version of designated mapping file. e.g. "32.0"')
+        help='Target version of designated mapping file. e.g. "32.0"')
+    parser.add_argument(
+        '--latest-version',
+        required=True,
+        help='Latest version for mapping of newer types. e.g. "31.0"')
     parser.add_argument(
         '-v',
         '--verbose',
@@ -131,7 +188,53 @@
         format='%(levelname)-8s [%(filename)s:%(lineno)d] %(message)s',
         level=(logging.WARNING, logging.INFO, logging.DEBUG)[verbosity])
 
-    download_mapping_file(args.branch, args.build, args.version)
+    global temp_dir
+    temp_dir = tempfile.mkdtemp()
+
+    try:
+        libpath = os.path.join(
+            os.path.dirname(os.path.realpath(__file__)), 'libsepolwrap' +
+            distutils.ccompiler.new_compiler().shared_lib_extension)
+        if not os.path.exists(libpath):
+            sys.exit(
+                'Error: libsepolwrap does not exist. Is this binary corrupted?\n'
+            )
+
+        build_top = get_android_build_top()
+        sepolicy_path = os.path.join(build_top, 'system', 'sepolicy')
+        target_compat_path = os.path.join(sepolicy_path, 'private', 'compat',
+                                          args.target_version)
+
+        # Step 1. Download system/etc/selinux/mapping/{ver}.cil, and remove types/typeattributes
+        mapping_file = download_mapping_file(args.branch, args.build,
+                                             args.target_version)
+        mapping_file_cil = mini_parser.MiniCilParser(mapping_file)
+        mapping_file_cil.types = set()
+        mapping_file_cil.typeattributes = set()
+
+        # Step 2. Build base policy files and parse latest mapping files
+        base_policy_path, old_policy_path, pub_policy_cil_path = build_base_files(
+            args.target_version)
+        base_policy = policy.Policy(base_policy_path, None, libpath)
+        old_policy = policy.Policy(old_policy_path, None, libpath)
+        pub_policy_cil = mini_parser.MiniCilParser(pub_policy_cil_path)
+
+        all_types = base_policy.GetAllTypes(False)
+        old_all_types = old_policy.GetAllTypes(False)
+        pub_types = pub_policy_cil.types
+
+        # Step 3. Find new types and removed types
+        new_types = pub_types & (all_types - old_all_types)
+        removed_types = (mapping_file_cil.pubtypes - mapping_file_cil.types) & (
+            old_all_types - all_types)
+
+        logging.info('new types: %s' % new_types)
+        logging.info('removed types: %s' % removed_types)
+
+        # TODO: Step 4. Map new types and removed types appropriately
+    finally:
+        logging.info('Deleting temporary dir: {}'.format(temp_dir))
+        shutil.rmtree(temp_dir)
 
 
 if __name__ == '__main__':