autotrim: Rework autotrim dependency analyzer to limit memory consumption and improve accuracy.

2 files changed, 1411 insertions, 372 deletions

diff --git a/cli/cli_trim_auto_analyzer.cpp b/cli/cli_trim_auto_analyzer.cpp
index 41d90180..a9f030e4 100644
--- a/cli/cli_trim_auto_analyzer.cpp
+++ b/cli/cli_trim_auto_analyzer.cpp
@@ -36,140 +36,12 @@
 bool
 TraceAnalyzer::renderingHasSideEffect(void)
 {
-    return transformFeedbackActive || framebufferObjectActive;
-}
-
-/* Provide: Record that the given call affects the given resource
- * as a side effect. */
-void
-TraceAnalyzer::provide(std::string resource, trace::CallNo call_no)
-{
-    resources[resource].insert(call_no);
-}
-
-/* Like provide, but with a simply-formatted string, (appending an
- * integer to the given string). */
-void
-TraceAnalyzer::providef(std::string resource,
-                        int resource_no,
-                        trace::CallNo call_no)
-{
-    std::stringstream ss;
-    ss << resource << resource_no;
-    provide(ss.str(), call_no);
-}
-
-/* Link: Establish a dependency between resource 'resource' and
- * resource 'dependency'. This dependency is captured by name so
- * that if the list of calls that provide 'dependency' grows
- * before 'resource' is consumed, those calls will still be
- * captured. */
-void
-TraceAnalyzer::link(std::string resource, std::string dependency)
-{
-    dependencies[resource].insert(dependency);
-}
-
-/* Like link, but with a simply-formatted string, (appending an
- * integer to the given string). */
-void
-TraceAnalyzer::linkf(std::string resource, std::string dependency, int dep_no)
-{
-
-    std::stringstream ss;
-    ss << dependency << dep_no;
-    link(resource, ss.str());
-}
-
-/* Unlink: Remove dependency from 'resource' on 'dependency'. */
-void
-TraceAnalyzer::unlink(std::string resource, std::string dependency)
-{
-    dependencies[resource].erase(dependency);
-    if (dependencies[resource].size() == 0) {
-        dependencies.erase(resource);
-    }
-}
-
-/* Like unlink, but with a simply-formated string, (appending an
- * integer to the given string). */
-void
-TraceAnalyzer::unlinkf(std::string resource, std::string dependency, int dep_no)
-{
-
-    std::stringstream ss;
-    ss << dependency << dep_no;
-    unlink(resource, ss.str());
-}
-
-/* Unlink all: Remove dependencies from 'resource' to all other
- * resources. */
-void
-TraceAnalyzer::unlinkAll(std::string resource)
-{
-    dependencies.erase(resource);
-}
-
-/* Resolve: Recursively compute all calls providing 'resource',
- * (including linked dependencies of 'resource' on other
- * resources). */
-std::set<unsigned>
-TraceAnalyzer::resolve(std::string resource)
-{
-    std::set<std::string> *deps;
-    std::set<std::string>::iterator dep;
-
-    std::set<unsigned> *calls;
-    std::set<unsigned>::iterator call;
-
-    std::set<unsigned> result, deps_set;
-
-    /* Recursively chase dependencies. */
-    if (dependencies.count(resource)) {
-        deps = &dependencies[resource];
-        for (dep = deps->begin(); dep != deps->end(); dep++) {
-            deps_set = resolve(*dep);
-            for (call = deps_set.begin(); call != deps_set.end(); call++) {
-                result.insert(*call);
-            }
-        }
-    }
-
-    /* Also look for calls that directly provide 'resource' */
-    if (resources.count(resource)) {
-        calls = &resources[resource];
-        for (call = calls->begin(); call != calls->end(); call++) {
-            result.insert(*call);
-        }
-    }
-
-    return result;
-}
-
-/* Consume: Resolve all calls that provide the given resource, and
- * add them to the required list. Then clear the call list for
- * 'resource' along with any dependencies. */
-void
-TraceAnalyzer::consume(std::string resource)
-{
-
-    std::set<unsigned> calls;
-    std::set<unsigned>::iterator call;
-
-    calls = resolve(resource);
-
-    dependencies.erase(resource);
-    resources.erase(resource);
-
-    for (call = calls.begin(); call != calls.end(); call++) {
-        required.add(*call);
-    }
+    return transformFeedbackActive;
 }
 
 void
 TraceAnalyzer::stateTrackPreCall(trace::Call *call)
 {
-
     const char *name = call->name();
 
     if (strcmp(name, "glBegin") == 0) {
@@ -182,7 +54,8 @@ TraceAnalyzer::stateTrackPreCall(trace::Call *call)
         return;
     }
 
-    if (strcmp(name, "glActiveTexture") == 0) {
+    if (strcmp(name, "glActiveTexture") == 0 ||
+        strcmp(name, "glActiveTextureARB") == 0) {
         activeTextureUnit = static_cast<GLenum>(call->arg(0).toSInt());
         return;
     }
@@ -195,32 +68,69 @@ TraceAnalyzer::stateTrackPreCall(trace::Call *call)
         texture = call->arg(1).toUInt();
 
         if (texture == 0) {
+            unit_texture_map[target].erase(activeTextureUnit);
             texture_map.erase(target);
         } else {
+            unit_texture_map[target][activeTextureUnit] = texture;
             texture_map[target] = texture;
         }
 
         return;
     }
 
-    if (strcmp(name, "glUseProgram") == 0) {
+    if (STRNCMP_LITERAL(name, "glBindBuffer") == 0) {
+        const GLenum target = static_cast<GLenum>(call->arg(0).toSInt());
+        const GLuint buffer = call->sig->arg_names[1] == std::string("buffer") ?
+            call->arg(1).toUInt() : call->arg(2).toUInt();
+        const unsigned idx = call->sig->arg_names[1] != std::string("index") ? 0 :
+            call->arg(1).toUInt();
+
+        indexed_buffer_map[target][idx] = buffer;
+        buffer_map[target] = buffer;
+
+        return;
+    }
+
+    if (strcmp(name, "glUseProgram") == 0 ||
+        strcmp(name, "glUseProgramObjectARB") == 0) {
         activeProgram = call->arg(0).toUInt();
     }
 
-    if (strcmp(name, "glBindFramebuffer") == 0) {
-        GLenum target;
-        GLuint framebuffer;
+    if (STRNCMP_LITERAL(name, "glBindFramebuffer") == 0) {
+        const GLenum target = static_cast<GLenum>(call->arg(0).toSInt());
+        if (target == GL_FRAMEBUFFER || target == GL_DRAW_FRAMEBUFFER)
+            draw_framebuffer = call->arg(1).toUInt();
+        if (target == GL_FRAMEBUFFER || target == GL_READ_FRAMEBUFFER)
+            read_framebuffer = call->arg(1).toUInt();
+        return;
+    }
 
-        target = static_cast<GLenum>(call->arg(0).toSInt());
-        framebuffer = call->arg(1).toUInt();
+    if (STRNCMP_LITERAL(name, "glFramebufferTexture") == 0 &&
+        call->sig->arg_names[3] == std::string("texture")) {
+        const GLuint target = static_cast<GLenum>(call->arg(0).toSInt());
+        const GLuint framebuffer = target == GL_READ_FRAMEBUFFER ?
+            read_framebuffer : draw_framebuffer;
+        const GLenum att = static_cast<GLenum>(call->arg(1).toSInt());
 
-        if (target == GL_FRAMEBUFFER || target == GL_DRAW_FRAMEBUFFER) {
-            if (framebuffer == 0) {
-                framebufferObjectActive = false;
-            } else {
-                framebufferObjectActive = true;
-            }
-        }
+        if (const GLuint texture = call->arg(3).toSInt())
+            framebuffer_texture_map[framebuffer][att] = texture;
+        else
+            framebuffer_texture_map[framebuffer].erase(att);
+
+        return;
+    }
+
+    if (STRNCMP_LITERAL(name, "glFramebufferRenderbuffer") == 0 &&
+        call->sig->arg_names[3] == std::string("renderbuffer")) {
+        const GLenum target = static_cast<GLenum>(call->arg(0).toSInt());
+        const GLuint framebuffer = target == GL_READ_FRAMEBUFFER ?
+            read_framebuffer : draw_framebuffer;
+        const GLenum att = static_cast<GLenum>(call->arg(1).toSInt());
+
+        if (const GLuint rb = call->arg(3).toSInt())
+            framebuffer_renderbuffer_map[framebuffer][att] = rb;
+        else
+            framebuffer_renderbuffer_map[framebuffer].erase(att);
         return;
     }
 
@@ -229,6 +139,21 @@ TraceAnalyzer::stateTrackPreCall(trace::Call *call)
 
         insideNewEndList = list;
     }
+
+    if (STRNCMP_LITERAL(name, "glClientActiveTexture") == 0)
+        client_active_texture = call->arg(0).toUInt();
+
+    if (STRNCMP_LITERAL(name, "glBindRenderbuffer") == 0)
+        renderbuffer = call->arg(1).toSInt();
+
+    if (STRNCMP_LITERAL(name, "glMapBufferRange") == 0) {
+       const GLenum target = static_cast<GLenum>(call->arg(0).toSInt());
+       buffer_mapping_map[buffer_map[target]] =
+          std::make_pair(call->ret->toUIntPtr(), call->arg(2).toUInt());
+    }
+
+    if (STRNCMP_LITERAL(name, "glMatrixMode") == 0)
+       matrix_mode = static_cast<GLenum>(call->arg(0).toSInt());
 }
 
 void
@@ -253,21 +178,32 @@ TraceAnalyzer::stateTrackPostCall(trace::Call *call)
      * next frame. */
     if (call->flags & trace::CALL_FLAG_SWAP_RENDERTARGET &&
         call->flags & trace::CALL_FLAG_END_FRAME) {
-        dependencies.erase("framebuffer");
-        resources.erase("framebuffer");
+        winsys_framebuffer_calls = std::make_shared<const union_set<unsigned>>();
         return;
     }
 
     if (strcmp(name, "glEndList") == 0) {
         insideNewEndList = 0;
     }
+
+    if (STRNCMP_LITERAL(name, "glUnmapBuffer") == 0) {
+       const GLenum target = static_cast<GLenum>(call->arg(0).toSInt());
+       buffer_mapping_map.erase(buffer_map[target]);
+    }
 }
 
 bool
 TraceAnalyzer::callHasNoSideEffects(trace::Call *call, const char *name)
 {
     /* If call is flagged as no side effects, then we are done here. */
-    if (call->flags & trace::CALL_FLAG_NO_SIDE_EFFECTS) {
+    if (call->flags & trace::CALL_FLAG_NO_SIDE_EFFECTS ||
+        name == std::string("glReadPixels") ||
+        name == std::string("glFinish") ||
+        name == std::string("glFlush") ||
+        name == std::string("glWaitGL") ||
+        name == std::string("glClientWaitSync") ||
+        name == std::string("glGetShaderiv") ||
+        name ==  std::string("glGetShaderInfoLog")) {
         return true;
     }
 
@@ -278,145 +214,245 @@ TraceAnalyzer::callHasNoSideEffects(trace::Call *call, const char *name)
 bool
 TraceAnalyzer::recordTextureSideEffects(trace::Call *call, const char *name)
 {
+    if (name == std::string("glActiveTexture") ||
+        name == std::string("glActiveTextureARB")) {
+        active_texture_calls =
+            std::make_shared<const union_set<unsigned>>(call->no);
+        return true;
+    }
+
     if (strcmp(name, "glGenTextures") == 0) {
         const trace::Array *textures = call->arg(1).toArray();
         size_t i;
-        GLuint texture;
 
         if (textures) {
             for (i = 0; i < textures->size(); i++) {
-                texture = textures->values[i]->toUInt();
-                providef("texture-", texture, call->no);
+                const GLuint texture = textures->values[i]->toUInt();
+                texture_object_calls[texture] =
+                    std::make_shared<const union_set<unsigned>>(call->no);
             }
         }
         return true;
     }
 
-    /* FIXME: When we start tracking framebuffer objects as their own
-     * resources, we will want to link the FBO to the given texture
-     * resource, (and to this call). For now, just link render state
-     * to the texture, and force this call to be required. */
-    if (strcmp(name, "glFramebufferTexture2D") == 0) {
-        GLuint texture;
-
-        texture = call->arg(3).toUInt();
-
-        linkf("render-state", "texture-", texture);
-
-        provide("state", call->no);
-    }
-
     if (strcmp(name, "glBindTexture") == 0) {
-        GLenum target;
-        GLuint texture;
-
-        std::stringstream ss_target, ss_texture;
-
-        target = static_cast<GLenum>(call->arg(0).toSInt());
-        texture = call->arg(1).toUInt();
-
-        ss_target << "texture-unit-" << activeTextureUnit << "-target-" << target;
-        ss_texture << "texture-" << texture;
-
-        resources.erase(ss_target.str());
-        provide(ss_target.str(), call->no);
+        const GLenum target = static_cast<GLenum>(call->arg(0).toSInt());
 
-        unlinkAll(ss_target.str());
-        link(ss_target.str(), ss_texture.str());
-
-        /* FIXME: This really shouldn't be necessary. The effect
-         * this provide() has is that all glBindTexture calls will
-         * be preserved in the output trace (never trimmed). Carl
-         * has a trace ("btr") where a glBindTexture call should
-         * not be necessary at all, (it's immediately followed
-         * with a glBindTexture to a different texture and no
-         * intervening texture-related calls), yet this 'provide'
-         * makes the difference between a trim_stress test failing
-         * and passing.
-         *
-         * More investigation is necessary, but for now, be
-         * conservative and don't trim. */
-        provide("state", call->no);
+        texture_binding_calls[target][activeTextureUnit] =
+            std::make_shared<const union_set<unsigned>>(
+                union_set<unsigned>(call->no).add(active_texture_calls));
 
         return true;
     }
 
     /* FIXME: Need to handle glMultiTexImage and friends. */
     if (STRNCMP_LITERAL(name, "glTexImage") == 0 ||
-        STRNCMP_LITERAL(name, "glTexSubImage") == 0 ||
         STRNCMP_LITERAL(name, "glCopyTexImage") == 0 ||
-        STRNCMP_LITERAL(name, "glCopyTexSubImage") == 0 ||
         STRNCMP_LITERAL(name, "glCompressedTexImage") == 0 ||
+        STRNCMP_LITERAL(name, "glTexSubImage") == 0 ||
+        STRNCMP_LITERAL(name, "glCopyTexSubImage") == 0 ||
         STRNCMP_LITERAL(name, "glCompressedTexSubImage") == 0 ||
+        STRNCMP_LITERAL(name, "glTexParameter") == 0 ||
         strcmp(name, "glInvalidateTexImage") == 0 ||
         strcmp(name, "glInvalidateTexSubImage") == 0) {
+        const GLenum target = static_cast<GLenum>(call->arg(0).toSInt());
+        union_set<unsigned> framebuffer_calls;
+        union_set<unsigned> contents_calls;
+
+        if (STRNCMP_LITERAL(name, "glCopyTexImage") == 0 ||
+            STRNCMP_LITERAL(name, "glCopyTexSubImage") == 0) {
+            framebuffer_calls.add(framebuffer_binding_calls);
+
+            if (read_framebuffer) {
+                for (auto t : framebuffer_texture_map[read_framebuffer]) {
+                   if (texture_map[target] == 2098 && 0)
+                      std::cout << "contents_calls += TC[" << t.second << "] = "
+                                << size_unique(*texture_contents_calls[t.second]) << "\n";
+                    contents_calls.add(texture_contents_calls[t.second]);
+                    framebuffer_calls.add(texture_object_calls[t.second]);
+                }
+
+                for (auto t : framebuffer_renderbuffer_map[read_framebuffer]) {
+                   if (texture_map[target] == 2098 && 0)
+                      std::cout << "contents_calls += RC[" << t.second << "] = "
+                                << size_unique(*renderbuffer_contents_calls[t.second]) << "\n";
+                    contents_calls.add(renderbuffer_contents_calls[t.second]);
+                    framebuffer_calls.add(renderbuffer_object_calls[t.second]);
+                }
 
-        std::set<unsigned> *calls;
-        std::set<unsigned>::iterator c;
-        std::stringstream ss_target, ss_texture;
-
-        GLenum target = static_cast<GLenum>(call->arg(0).toSInt());
-
-        ss_target << "texture-unit-" << activeTextureUnit << "-target-" << target;
-        ss_texture << "texture-" << texture_map[target];
-
-        /* The texture resource depends on this call and any calls
-         * providing the given texture target. */
-        provide(ss_texture.str(), call->no);
-
-        if (resources.count(ss_target.str())) {
-            calls = &resources[ss_target.str()];
-            for (c = calls->begin(); c != calls->end(); c++) {
-                provide(ss_texture.str(), *c);
+            } else {
+               if (texture_map[target] == 2098 && 0)
+                  std::cout << "contents_calls += WC = "
+                            << size_unique(*winsys_framebuffer_calls) << "\n";
+                contents_calls.add(winsys_framebuffer_calls);
             }
         }
 
+        mutate_lazy(texture_object_calls[texture_map[target]],
+                    [&](union_set<unsigned> c) {
+                        return std::move(c.add(call->no)
+                                .add(active_texture_calls)
+                                .add(pixel_store_calls)
+                                .add(texture_binding_calls[target][activeTextureUnit])
+                                         .add(std::make_shared<const union_set<unsigned>>(framebuffer_calls)));
+                    });
+
+        if (STRNCMP_LITERAL(name, "glTexImage") == 0 ||
+            STRNCMP_LITERAL(name, "glCopyTexImage") == 0 ||
+            STRNCMP_LITERAL(name, "glCompressedTexImage") == 0 ||
+            strcmp(name, "glInvalidateTexImage") == 0) {
+            if (texture_map[target] == 2098 && 0)
+                std::cout << name << ": TC += " << size(*texture_object_calls[texture_map[target]])
+                          << "+" << size(contents_calls);
+            texture_contents_calls[texture_map[target]] =
+                std::make_shared<const union_set<unsigned>>(
+                    union_set<unsigned>(texture_object_calls[texture_map[target]])
+                    .add(std::make_shared<const union_set<unsigned>>(contents_calls)));
+            if (texture_map[target] == 2098 && 0)
+                std::cout << name << " = " << size(*texture_contents_calls[texture_map[target]]) << "\n";
+        } else {
+            if (texture_map[target] == 2098 && 0)
+                std::cout << name << ": TC += " << size(*texture_object_calls[texture_map[target]])
+                          << "+" << size(contents_calls) << "(" << size_unique(contents_calls) << ")";
+            mutate_lazy(texture_contents_calls[texture_map[target]],
+                        [&](union_set<unsigned> c) {
+                            return std::move(c.add(texture_object_calls[texture_map[target]])
+                                              .add(std::make_shared<const union_set<unsigned>>(contents_calls)));
+                        });
+            if (texture_map[target] == 2098 && 0)
+               std::cout << name << " = " << size(*texture_contents_calls[texture_map[target]])
+                          << "(" << size_unique(*texture_contents_calls[texture_map[target]]) << ")" << "\n";
+        }
+
         return true;
     }
 
     if (strcmp(name, "glEnable") == 0) {
-        GLenum cap;
-
-        cap = static_cast<GLenum>(call->arg(0).toSInt());
+        const GLenum cap = static_cast<GLenum>(call->arg(0).toSInt());
 
         if (cap == GL_TEXTURE_1D ||
             cap == GL_TEXTURE_2D ||
             cap == GL_TEXTURE_3D ||
             cap == GL_TEXTURE_CUBE_MAP)
-        {
-            std::stringstream ss;
-
-            ss << "texture-unit-" << activeTextureUnit << "-target-" << cap;
+            enabled_texture_units.insert(activeTextureUnit);
 
-            link("render-state", ss.str());
-        }
+        mutate(texture_enable_calls[activeTextureUnit][cap],
+               [&](const union_set<unsigned> &) {
+                   return std::move(union_set<unsigned>(call->no)
+                                    .add(active_texture_calls));
+               });
 
-        provide("state", call->no);
         return true;
     }
 
     if (strcmp(name, "glDisable") == 0) {
-        GLenum cap;
-
-        cap = static_cast<GLenum>(call->arg(0).toSInt());
+        const GLenum cap = static_cast<GLenum>(call->arg(0).toSInt());
 
         if (cap == GL_TEXTURE_1D ||
             cap == GL_TEXTURE_2D ||
             cap == GL_TEXTURE_3D ||
             cap == GL_TEXTURE_CUBE_MAP)
-        {
-            std::stringstream ss;
+            enabled_texture_units.erase(activeTextureUnit);
+
+        mutate(texture_enable_calls[activeTextureUnit][cap],
+               [&](const union_set<unsigned> &) {
+                   return std::move(union_set<unsigned>(call->no)
+                                    .add(active_texture_calls));
+               });
+
+        return true;
+    }
 
-            ss << "texture-unit-" << activeTextureUnit << "-target-" << cap;
+    /* No known texture-related side effects. Return false for more analysis. */
+    return false;
+}
 
-            unlink("render-state", ss.str());
+bool
+TraceAnalyzer::recordBufferSideEffects(trace::Call *call, const char *name)
+{
+    if (STRNCMP_LITERAL(name, "glGenBuffers") == 0) {
+        if (const trace::Array *buffers = call->arg(1).toArray()) {
+            for (size_t i = 0; i < buffers->size(); i++) {
+                const GLuint buf = buffers->values[i]->toUInt();
+                mutate_lazy(buffer_object_calls[buf],
+                            [&](union_set<unsigned> c) {
+                                return std::move(c.add(call->no));
+                            });
+            }
         }
+        return true;
+    }
 
-        provide("state", call->no);
+    if (STRNCMP_LITERAL(name, "glBindBuffer") == 0) {
+        const GLenum target = static_cast<GLenum>(call->arg(0).toSInt());
+        const unsigned idx = call->sig->arg_names[1] != std::string("index") ? 0 :
+            call->arg(1).toUInt();
+        buffer_binding_calls[target] =
+            std::make_shared<const union_set<unsigned>>(call->no);
+        indexed_buffer_binding_calls[target][idx] =
+            std::make_shared<const union_set<unsigned>>(call->no);
         return true;
     }
 
-    /* No known texture-related side effects. Return false for more analysis. */
+    if (STRNCMP_LITERAL(name, "glBufferData") == 0 ||
+        STRNCMP_LITERAL(name, "glBufferSubData") == 0 ||
+        STRNCMP_LITERAL(name, "glMapBufferRange") == 0 ||
+        STRNCMP_LITERAL(name, "glFlushMappedBufferRange") == 0) {
+        const GLenum target = static_cast<GLenum>(call->arg(0).toSInt());
+        mutate_lazy(buffer_object_calls[buffer_map[target]],
+                    [&](union_set<unsigned> c) {
+                        return std::move(c.add(call->no)
+                                         .add(buffer_binding_calls[target]));
+                    });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glInvalidateBufferData") == 0 ||
+        STRNCMP_LITERAL(name, "glInvalidateBufferSubData") == 0) {
+        const unsigned buffer = call->arg(0).toSInt();
+        mutate_lazy(buffer_object_calls[buffer],
+                    [&](union_set<unsigned> c) {
+                        return std::move(c.add(call->no));
+                    });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glUnmapBuffer") == 0) {
+       const GLenum target = static_cast<GLenum>(call->arg(0).toSInt());
+       const auto r = buffer_mapping_map[buffer_map[target]];
+       union_set<unsigned> calls = union_set<unsigned>(call->no)
+                                      .add(buffer_binding_calls[target]);
+
+       for (auto it = (memory_calls.upper_bound(r.first) == memory_calls.begin() ?
+                       memory_calls.begin() : std::prev(memory_calls.upper_bound(r.first)));
+            it != memory_calls.end() && it->first < r.first + r.second;) {
+          if (it->first + it->second.first > r.first &&
+              it->first < r.first + r.second)
+             calls.add(it->second.second);
+
+          if (it->first < r.first)
+             memory_calls.emplace(it->first,
+                                  std::make_pair(std::max(it->second.first, r.first - it->first),
+                                                 it->second.second));
+
+          if (it->first + it->second.first > r.first + r.second)
+             memory_calls.emplace(r.first + r.second,
+                                  std::make_pair(it->first + it->second.first - r.first - r.second,
+                                                 it->second.second));
+
+          memory_calls.erase(it++);
+       }
+
+       mutate_lazy(buffer_object_calls[buffer_map[target]],
+                   [&](union_set<unsigned> c) {
+                      return std::move(c.add(std::make_shared<const union_set<unsigned>>(calls)));
+                   });
+
+       return true;
+    }
+
+
+    /* No known buffer-related side effects. Return false for more analysis. */
     return false;
 }
 
@@ -425,94 +461,51 @@ TraceAnalyzer::recordShaderSideEffects(trace::Call *call, const char *name)
 {
     if (strcmp(name, "glCreateShader") == 0 ||
         strcmp(name, "glCreateShaderObjectARB") == 0) {
-
-        GLuint shader = call->ret->toUInt();
-        providef("shader-", shader, call->no);
+        const GLuint shader = call->ret->toUInt();
+        mutate(shader_object_calls[shader],
+               [&](union_set<unsigned> c) {
+                   return std::move(c.add(call->no));
+               });
         return true;
     }
 
     if (strcmp(name, "glShaderSource") == 0 ||
         strcmp(name, "glShaderSourceARB") == 0 ||
         strcmp(name, "glCompileShader") == 0 ||
-        strcmp(name, "glCompileShaderARB") == 0 ||
-        strcmp(name, "glGetShaderiv") == 0 ||
-        strcmp(name, "glGetShaderInfoLog") == 0) {
-
+        strcmp(name, "glCompileShaderARB") == 0) {
         GLuint shader = call->arg(0).toUInt();
-        providef("shader-", shader, call->no);
+        mutate(shader_object_calls[shader],
+               [&](union_set<unsigned> c) {
+                   return std::move(c.add(call->no));
+               });
         return true;
     }
 
     if (strcmp(name, "glCreateProgram") == 0 ||
         strcmp(name, "glCreateProgramObjectARB") == 0) {
-
         GLuint program = call->ret->toUInt();
-        providef("program-", program, call->no);
+        mutate(program_object_calls[program],
+               [&](union_set<unsigned> c) {
+                   return std::move(c.add(call->no));
+               });
         return true;
     }
 
     if (strcmp(name, "glAttachShader") == 0 ||
         strcmp(name, "glAttachObjectARB") == 0) {
-
-        GLuint program, shader;
-        std::stringstream ss_program, ss_shader;
-
-        program = call->arg(0).toUInt();
-        shader = call->arg(1).toUInt();
-
-        ss_program << "program-" << program;
-        ss_shader << "shader-" << shader;
-
-        link(ss_program.str(), ss_shader.str());
-        provide(ss_program.str(), call->no);
-
+        const GLuint program = call->arg(0).toUInt();
+        const GLuint shader = call->arg(1).toUInt();
+        mutate(program_object_calls[program],
+               [&](union_set<unsigned> c) {
+                   return std::move(c.add(shader_object_calls[shader])
+                                    .add(call->no));
+               });
         return true;
     }
 
     if (strcmp(name, "glDetachShader") == 0 ||
-        strcmp(name, "glDetachObjectARB") == 0) {
-
-        GLuint program, shader;
-        std::stringstream ss_program, ss_shader;
-
-        program = call->arg(0).toUInt();
-        shader = call->arg(1).toUInt();
-
-        ss_program << "program-" << program;
-        ss_shader << "shader-" << shader;
-
-        unlink(ss_program.str(), ss_shader.str());
-
-        return true;
-    }
-
-    if (strcmp(name, "glUseProgram") == 0 ||
-        strcmp(name, "glUseProgramObjectARB") == 0) {
-
-        GLuint program;
-
-        program = call->arg(0).toUInt();
-
-        unlinkAll("render-program-state");
-
-        if (program == 0) {
-            unlink("render-state", "render-program-state");
-            provide("state", call->no);
-        } else {
-            std::stringstream ss;
-
-            ss << "program-" << program;
-
-            link("render-state", "render-program-state");
-            link("render-program-state", ss.str());
-
-            provide(ss.str(), call->no);
-        }
-
-        return true;
-    }
-
-    if (strcmp(name, "glGetUniformLocation") == 0 ||
+        strcmp(name, "glDetachObjectARB") == 0 ||
+        strcmp(name, "glGetUniformLocation") == 0 ||
         strcmp(name, "glGetUniformLocationARB") == 0 ||
         strcmp(name, "glGetFragDataLocation") == 0 ||
         strcmp(name, "glGetFragDataLocationEXT") == 0 ||
@@ -520,11 +513,22 @@ TraceAnalyzer::recordShaderSideEffects(trace::Call *call, const char *name)
         strcmp(name, "glGetProgramResourceLocation") == 0 ||
         strcmp(name, "glGetProgramResourceLocationIndex") == 0 ||
         strcmp(name, "glGetVaryingLocationNV") == 0) {
+        const GLuint program = call->arg(0).toUInt();
+        mutate_lazy(program_object_calls[program],
+                    [&](union_set<unsigned> c) {
+                            return std::move(c.add(call->no));
+                    });
+        return true;
+    }
 
-        GLuint program = call->arg(0).toUInt();
-
-        providef("program-", program, call->no);
+    if (strcmp(name, "glUseProgram") == 0 ||
+        strcmp(name, "glUseProgramObjectARB") == 0) {
+        const GLuint program = call->arg(0).toUInt();
+        auto calls = union_set<unsigned>(call->no);
+        if (program)
+            calls.add(program_object_calls[program]);
 
+        program_binding_calls = std::make_shared<const union_set<unsigned>>(calls);
         return true;
     }
 
@@ -533,40 +537,33 @@ TraceAnalyzer::recordShaderSideEffects(trace::Call *call, const char *name)
      * dependence on the program we find there. */
     if (call->sig->num_args > 0 &&
         strcmp(call->sig->arg_names[0], "location") == 0) {
+        const unsigned location = call->arg(0).toSInt();
+        const unsigned count =
+                call->sig->arg_names[1] == std::string("count") ? call->arg(1).toUInt() :
+                call->sig->num_args - 1;
 
-        providef("program-", activeProgram, call->no);
+        for (unsigned l = location; l < location + count; l++)
+            program_object_uniform_calls[activeProgram][l] =
+               std::make_shared<const union_set<unsigned>>(union_set<unsigned>(call->no)
+                                                           .add(program_binding_calls));
 
         /* We can't easily tell if this uniform is being used to
          * associate a sampler in the shader with a texture
          * unit. The conservative option is to assume that it is
          * and create a link from the active program to any bound
-         * textures for the given unit number.
-         *
-         * FIXME: We should be doing the same thing for calls to
-         * glUniform1iv. */
+         * textures for the given unit number. */
         if (strcmp(name, "glUniform1i") == 0 ||
             strcmp(name, "glUniform1iARB") == 0) {
-
-            GLint max_unit = MAX(GL_MAX_TEXTURE_COORDS, GL_MAX_COMBINED_TEXTURE_IMAGE_UNITS);
-
-            GLint unit = call->arg(1).toSInt();
-            std::stringstream ss_program;
-            std::stringstream ss_texture;
+            const GLenum max_unit = GL_TEXTURE0 + MAX(GL_MAX_TEXTURE_COORDS,
+                                                      GL_MAX_COMBINED_TEXTURE_IMAGE_UNITS);
+            const GLenum unit = GL_TEXTURE0 + call->arg(1).toSInt();
 
             if (unit < max_unit) {
-
-                ss_program << "program-" << activeProgram;
-
-                ss_texture << "texture-unit-" << GL_TEXTURE0 + unit << "-target-";
-
                 /* We don't know what target(s) might get bound to
                  * this texture unit, so conservatively link to
                  * all. Only bound textures will actually get inserted
                  * into the output call stream. */
-                linkf(ss_program.str(), ss_texture.str(), GL_TEXTURE_1D);
-                linkf(ss_program.str(), ss_texture.str(), GL_TEXTURE_2D);
-                linkf(ss_program.str(), ss_texture.str(), GL_TEXTURE_3D);
-                linkf(ss_program.str(), ss_texture.str(), GL_TEXTURE_CUBE_MAP);
+                program_object_texture_units[activeProgram].insert(unit);
             }
         }
 
@@ -587,9 +584,11 @@ TraceAnalyzer::recordShaderSideEffects(trace::Call *call, const char *name)
         (call->sig->num_args > 0 &&
          (strcmp(call->sig->arg_names[0], "program") == 0 ||
           strcmp(call->sig->arg_names[0], "programObj") == 0))) {
-
-        GLuint program = call->arg(0).toUInt();
-        providef("program-", program, call->no);
+        const GLuint program = call->arg(0).toUInt();
+        mutate_lazy(program_object_calls[program],
+                    [&](union_set<unsigned> c) {
+                       return std::move(c.add(call->no));
+                    });
         return true;
     }
 
@@ -600,30 +599,76 @@ TraceAnalyzer::recordShaderSideEffects(trace::Call *call, const char *name)
 bool
 TraceAnalyzer::recordDrawingSideEffects(trace::Call *call, const char *name)
 {
+    if (name == std::string("glClear")) {
+        // XXX - Consider scissoring and other GL state.
+        const GLbitfield bufs = static_cast<GLenum>(call->arg(0).toSInt());
+
+        if (draw_framebuffer) {
+           for (auto t : framebuffer_texture_map[draw_framebuffer]) {
+                if ((t.first == GL_DEPTH_ATTACHMENT && (bufs & GL_DEPTH_BUFFER_BIT)) ||
+                    (t.first == GL_STENCIL_ATTACHMENT && (bufs & GL_STENCIL_BUFFER_BIT)) ||
+                    (t.first == GL_DEPTH_STENCIL_ATTACHMENT &&
+                     (bufs & GL_DEPTH_BUFFER_BIT) && (bufs & GL_STENCIL_BUFFER_BIT)) ||
+                    (t.first >= GL_COLOR_ATTACHMENT0 && t.first <= GL_COLOR_ATTACHMENT31 &&
+                     (bufs & GL_COLOR_BUFFER_BIT)))
+                    texture_contents_calls[t.second] =
+                        std::make_shared<const union_set<unsigned>>();
+            }
+
+            for (auto t : framebuffer_renderbuffer_map[draw_framebuffer]) {
+                if ((t.first == GL_DEPTH_ATTACHMENT && (bufs & GL_DEPTH_BUFFER_BIT)) ||
+                    (t.first == GL_STENCIL_ATTACHMENT && (bufs & GL_STENCIL_BUFFER_BIT)) ||
+                    (t.first == GL_DEPTH_STENCIL_ATTACHMENT &&
+                     (bufs & GL_DEPTH_BUFFER_BIT) && (bufs & GL_STENCIL_BUFFER_BIT)) ||
+                    (t.first >= GL_COLOR_ATTACHMENT0 && t.first <= GL_COLOR_ATTACHMENT31 &&
+                     (bufs & GL_COLOR_BUFFER_BIT)))
+                    renderbuffer_contents_calls[t.second] =
+                        std::make_shared<const union_set<unsigned>>();
+            }
+        } else {
+            if ((bufs & GL_DEPTH_BUFFER_BIT) && (bufs & GL_STENCIL_BUFFER_BIT) &&
+                (bufs & GL_COLOR_BUFFER_BIT))
+                winsys_framebuffer_calls =
+                    std::make_shared<const union_set<unsigned>>();
+        }
+    }
+
     /* Handle all rendering operations, (even though only glEnd is
      * flagged as a rendering operation we treat everything from
      * glBegin through glEnd as a rendering operation). */
     if (call->flags & trace::CALL_FLAG_RENDER ||
         insideBeginEnd) {
+        auto calls = std::make_shared<const union_set<unsigned>>(
+            pipeline_state_calls().add(call->no));
 
-        std::set<unsigned> calls;
-        std::set<unsigned>::iterator c;
+        for (auto t : framebuffer_texture_map[draw_framebuffer]) {
 
-        provide("framebuffer", call->no);
+            mutate_lazy(texture_contents_calls[t.second],
+                        [&](union_set<unsigned> s) {
+                            return std::move(s.add(calls));
+                        });
 
-        calls = resolve("render-state");
-
-        for (c = calls.begin(); c != calls.end(); c++) {
-            provide("framebuffer", *c);
         }
 
+        for (auto t : framebuffer_renderbuffer_map[draw_framebuffer])
+            mutate_lazy(renderbuffer_contents_calls[t.second],
+                        [&](union_set<unsigned> s) {
+                            return std::move(s.add(calls));
+                        });
+
+        if (!draw_framebuffer)
+            mutate_lazy(winsys_framebuffer_calls,
+                        [&](union_set<unsigned> s) {
+                            return std::move(s.add(calls));
+                        });
+
         /* In some cases, rendering has side effects beyond the
          * framebuffer update. */
         if (renderingHasSideEffect()) {
-            provide("state", call->no);
-            for (c = calls.begin(); c != calls.end(); c++) {
-                provide("state", *c);
-            }
+            mutate(global_state_calls,
+                   [&](union_set<unsigned> s) {
+                       return std::move(s.add(calls));
+                   });
         }
 
         return true;
@@ -640,6 +685,539 @@ TraceAnalyzer::recordDrawingSideEffects(trace::Call *call, const char *name)
     return false;
 }
 
+bool
+TraceAnalyzer::recordMatrixSideEffects(trace::Call *call, const char *name)
+{
+    /// XXX - Matrix stack
+
+    if (STRNCMP_LITERAL(name, "glMatrixMode") == 0) {
+        matrix_mode_calls = std::make_shared<const union_set<unsigned>>(call->no);
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glLoadMatrix") == 0 ||
+        STRNCMP_LITERAL(name, "glLoadIdentity") == 0 ||
+        STRNCMP_LITERAL(name, "glLoadTransposeMatrix") == 0 ||
+        STRNCMP_LITERAL(name, "glFrustum") == 0 ||
+        STRNCMP_LITERAL(name, "glOrtho") == 0) {
+        mutate(matrix_state_calls[matrix_mode],
+               [&](union_set<unsigned>) {
+                   return std::move(union_set<unsigned>(call->no)
+                                    .add(matrix_mode_calls));
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glMultMatrix") == 0 ||
+        STRNCMP_LITERAL(name, "glMultTransposeMatrix") == 0 ||
+        STRNCMP_LITERAL(name, "glRotate") == 0 ||
+        STRNCMP_LITERAL(name, "glScale") == 0 ||
+        STRNCMP_LITERAL(name, "glTranslate") == 0) {
+        mutate(matrix_state_calls[matrix_mode],
+               [&](union_set<unsigned> s) {
+                   return std::move(s.add(call->no)
+                                    .add(matrix_mode_calls));
+               });
+        return true;
+    }
+
+    /* No known drawing-related side effects. Return false for more analysis. */
+    return false;
+}
+
+bool
+TraceAnalyzer::recordStateSideEffects(trace::Call *call, const char *name)
+{
+    if (STRNCMP_LITERAL(name, "glClearColor") == 0) {
+        mutate(clear_color_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glClearDepth") == 0) {
+        mutate(clear_depth_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glClearStencil") == 0) {
+        mutate(clear_stencil_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glClientActiveTexture") == 0) {
+        mutate(client_active_texture_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glEnableClientState") == 0 ||
+        STRNCMP_LITERAL(name, "glDisableClientState") == 0) {
+        const GLenum target = static_cast<GLenum>(call->arg(0).toSInt());
+        const unsigned idx = target != GL_TEXTURE_COORD_ARRAY ? 0 :
+            client_active_texture;
+        mutate(client_state_enable_calls[target][idx],
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no)
+                            .add(client_active_texture_calls);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glEnableVertexAttribArray") == 0 ||
+        STRNCMP_LITERAL(name, "glDisableVertexAttribArray") == 0) {
+        const unsigned idx = static_cast<GLenum>(call->arg(0).toSInt());
+        mutate(vertex_attrib_array_enable_calls[idx],
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glVertexPointer") == 0) {
+        mutate(vertex_pointer_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no)
+                            .add(buffer_binding_calls[GL_ARRAY_BUFFER])
+                            .add(buffer_object_calls[buffer_map[GL_ARRAY_BUFFER]]);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glColorPointer") == 0) {
+        mutate(color_pointer_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no)
+                            .add(buffer_binding_calls[GL_ARRAY_BUFFER])
+                            .add(buffer_object_calls[buffer_map[GL_ARRAY_BUFFER]]);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glSecondaryColorPointer") == 0) {
+        mutate(secondary_color_pointer_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no)
+                            .add(buffer_binding_calls[GL_ARRAY_BUFFER])
+                            .add(buffer_object_calls[buffer_map[GL_ARRAY_BUFFER]]);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glNormalPointer") == 0) {
+        mutate(normal_pointer_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no)
+                            .add(buffer_binding_calls[GL_ARRAY_BUFFER])
+                            .add(buffer_object_calls[buffer_map[GL_ARRAY_BUFFER]]);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glTexCoordPointer") == 0) {
+        mutate(tex_coord_pointer_calls[client_active_texture],
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no)
+                            .add(buffer_binding_calls[GL_ARRAY_BUFFER])
+                            .add(buffer_object_calls[buffer_map[GL_ARRAY_BUFFER]])
+                            .add(client_active_texture_calls);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glEdgeFlagPointer") == 0) {
+        mutate(edge_flag_pointer_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no)
+                            .add(buffer_binding_calls[GL_ARRAY_BUFFER])
+                            .add(buffer_object_calls[buffer_map[GL_ARRAY_BUFFER]]);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glFogCoordPointer") == 0) {
+        mutate(fog_coord_pointer_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no)
+                            .add(buffer_binding_calls[GL_ARRAY_BUFFER])
+                            .add(buffer_object_calls[buffer_map[GL_ARRAY_BUFFER]]);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glIndexPointer") == 0) {
+        mutate(index_pointer_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no)
+                            .add(buffer_binding_calls[GL_ARRAY_BUFFER])
+                            .add(buffer_object_calls[buffer_map[GL_ARRAY_BUFFER]]);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glVertexAttribPointer") == 0) {
+        const unsigned idx = static_cast<GLenum>(call->arg(0).toSInt());
+        mutate(vertex_attrib_pointer_calls[idx],
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no)
+                            .add(buffer_binding_calls[GL_ARRAY_BUFFER])
+                            .add(buffer_object_calls[buffer_map[GL_ARRAY_BUFFER]]);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glColorMask") == 0) {
+        mutate(color_mask_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glDepthMask") == 0) {
+        mutate(depth_mask_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glStencilMask") == 0) {
+        mutate(stencil_mask_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glViewport") == 0) {
+        mutate(viewport_state_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glScissor") == 0) {
+        mutate(scissor_state_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glPolygonOffset") == 0) {
+        mutate(polygon_offset_state_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glPolygonMode") == 0) {
+        const GLenum face = static_cast<GLenum>(call->arg(0).toSInt());
+        mutate(face_polygon_mode_calls[face],
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glBlendEquation") == 0) {
+        mutate(blend_equation_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glBlendFunc") == 0) {
+        mutate(blend_func_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glFrontFace") == 0) {
+        mutate(front_face_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glCullFace") == 0) {
+        mutate(cull_face_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glDepthFunc") == 0) {
+        mutate(depth_func_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glStencilFuncSeparate") == 0) {
+        const GLenum face = static_cast<GLenum>(call->arg(0).toSInt());
+        mutate(face_stencil_func_calls[face],
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glStencilOpSeparate") == 0) {
+        const GLenum face = static_cast<GLenum>(call->arg(0).toSInt());
+        mutate(face_stencil_op_calls[face],
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glPixelStore") == 0) {
+        mutate(pixel_store_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glBindFramebuffer") == 0) {
+        const GLenum target = static_cast<GLenum>(call->arg(0).toSInt());
+        if (target == GL_FRAMEBUFFER || target == GL_DRAW_FRAMEBUFFER)
+            mutate(framebuffer_binding_calls,
+                   [&](union_set<unsigned>) {
+                       return union_set<unsigned>(call->no);
+                   });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glDrawBuffer") == 0) {
+        mutate(framebuffer_object_calls[draw_framebuffer],
+               [&](union_set<unsigned> c) {
+                   return std::move(c.add(call->no)
+                                    .add(framebuffer_binding_calls));
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glReadBuffer") == 0) {
+        mutate(framebuffer_object_calls[read_framebuffer],
+               [&](union_set<unsigned> c) {
+                   return std::move(c.add(call->no)
+                                    .add(framebuffer_binding_calls));
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glGenFramebuffers") == 0) {
+        if (const trace::Array *framebuffers = call->arg(1).toArray()) {
+            for (unsigned i = 0; i < framebuffers->size(); i++) {
+                const GLuint framebuffer = framebuffers->values[i]->toUInt();
+                framebuffer_object_calls[framebuffer] =
+                    std::make_shared<const union_set<unsigned>>(call->no);
+            }
+        }
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glFramebufferTexture") == 0 &&
+        call->sig->arg_names[3] == std::string("texture")) {
+        const GLuint target = static_cast<GLenum>(call->arg(0).toSInt());
+        const GLuint framebuffer = target == GL_READ_FRAMEBUFFER ?
+            read_framebuffer : draw_framebuffer;
+        const GLuint texture = call->arg(3).toSInt();
+        mutate_lazy(framebuffer_object_calls[framebuffer],
+                    [&](union_set<unsigned> c) {
+                        return std::move(c.add(call->no)
+                                .add(framebuffer_binding_calls)
+                                         .add(texture ? texture_object_calls[texture] : nullptr));
+                    });
+
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glGenRenderbuffers") == 0) {
+        if (const trace::Array *rbs = call->arg(1).toArray()) {
+            for (unsigned i = 0; i < rbs->size(); i++) {
+                const GLuint rb = rbs->values[i]->toUInt();
+                renderbuffer_object_calls[rb] =
+                    std::make_shared<const union_set<unsigned>>(call->no);
+            }
+        }
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glBindRenderbuffer") == 0) {
+        mutate(renderbuffer_binding_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glRenderbufferStorage") == 0) {
+        mutate(renderbuffer_object_calls[renderbuffer],
+               [&](union_set<unsigned> c) {
+                   return std::move(c.add(call->no)
+                                    .add(renderbuffer_binding_calls));
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glFramebufferRenderbuffer") == 0 &&
+        call->sig->arg_names[3] == std::string("renderbuffer")) {
+        const GLuint target = static_cast<GLenum>(call->arg(0).toSInt());
+        const GLuint framebuffer = target == GL_READ_FRAMEBUFFER ?
+            read_framebuffer : draw_framebuffer;
+        const GLuint rb = call->arg(3).toSInt();
+        mutate(framebuffer_object_calls[framebuffer],
+               [&](union_set<unsigned> c) {
+                   return std::move(c.add(call->no)
+                           .add(framebuffer_binding_calls)
+                                    .add(renderbuffer_object_calls[rb]));
+               });
+        return true;
+    }
+
+
+    if (STRNCMP_LITERAL(name, "glVertex2") == 0 ||
+        STRNCMP_LITERAL(name, "glVertex3") == 0 ||
+        STRNCMP_LITERAL(name, "glVertex4") == 0) {
+        mutate(current_vertex_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glNormal3") == 0) {
+        mutate(current_normal_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glFogCoord") == 0 &&
+        STRNCMP_LITERAL(name, "glFogCoordPointer") != 0) {
+        mutate(current_fog_coord_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glEdgeFlag") == 0 &&
+        STRNCMP_LITERAL(name, "glEdgeFlagPointer") != 0) {
+        mutate(current_edge_flag_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glColor3") == 0 ||
+        STRNCMP_LITERAL(name, "glColor4") == 0) {
+        mutate(current_color_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glSecondaryColor3") == 0 ||
+        STRNCMP_LITERAL(name, "glSecondaryColor4") == 0) {
+        mutate(current_secondary_color_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glIndex") == 0 &&
+        STRNCMP_LITERAL(name, "glIndexPointer") != 0) {
+        mutate(current_index_calls,
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    if (STRNCMP_LITERAL(name, "glTexCoord1") == 0 ||
+        STRNCMP_LITERAL(name, "glTexCoord2") == 0 ||
+        STRNCMP_LITERAL(name, "glTexCoord3") == 0 ||
+        STRNCMP_LITERAL(name, "glTexCoord4") == 0) {
+        mutate(current_tex_coord_calls[GL_TEXTURE0],
+               [&](union_set<unsigned>) {
+                   return union_set<unsigned>(call->no);
+               });
+        return true;
+    }
+
+    /* No known drawing-related side effects. Return false for more analysis. */
+    return false;
+}
+
+bool
+TraceAnalyzer::recordMemorySideEffects(trace::Call *call, const char *name)
+{
+   if (strcmp(name, "memcpy") == 0) {
+      const uintptr_t dst = call->arg(0).toUIntPtr();
+      const uintptr_t src = call->arg(1).toBlob() ? 0 : call->arg(1).toUIntPtr();
+      const size_t size = call->arg(2).toUInt();
+      union_set<unsigned> calls(call->no);
+
+      if (src) {
+              for (auto it = (memory_calls.upper_bound(src) == memory_calls.begin() ?
+                              memory_calls.begin() : std::prev(memory_calls.upper_bound(src)));
+                   it != memory_calls.end() && it->first < src + size; ++it) {
+                      if (it->first + it->second.first > src &&
+                          it->first < src + size)
+                              calls.add(it->second.second);
+              }
+      }
+
+      for (auto it = memory_calls.upper_bound(dst) == memory_calls.begin() ?
+              memory_calls.begin() : std::prev(memory_calls.upper_bound(dst));
+           it != memory_calls.end() && it->first < dst + size;) {
+         if (it->first < dst)
+            memory_calls.emplace(it->first,
+                                 std::make_pair(std::max(it->second.first, dst - it->first),
+                                                it->second.second));
+
+         if (it->first + it->second.first > dst + size)
+            memory_calls.emplace(dst + size,
+                                 std::make_pair(it->first + it->second.first - dst - size,
+                                                it->second.second));
+
+         memory_calls.erase(it++);
+      }
+
+      memory_calls.emplace(dst, std::make_pair(size, std::make_shared<const union_set<unsigned>>(calls)));
+
+      return true;
+   }
+
+   return false;
+}
+
 void
 TraceAnalyzer::recordSideEffects(trace::Call *call)
 {
@@ -656,14 +1234,19 @@ TraceAnalyzer::recordSideEffects(trace::Call *call)
      * lists will work, but does not trim out unused display
      * lists. */
     if (insideNewEndList != 0) {
-        provide("state", call->no);
+        mutate(global_state_calls,
+               [&](union_set<unsigned> s) {
+                   return std::move(s.add(call->no));
+               });
 
         /* Also, any texture bound inside a display list is
          * conservatively considered required. */
         if (strcmp(name, "glBindTexture") == 0) {
-            GLuint texture = call->arg(1).toUInt();
-
-            linkf("state", "texture-", texture);
+            const GLuint texture = call->arg(1).toUInt();
+            mutate(global_state_calls,
+                   [&](union_set<unsigned> s) {
+                       return std::move(s.add(texture_object_calls[texture]));
+                   });
         }
 
         return;
@@ -677,12 +1260,19 @@ TraceAnalyzer::recordSideEffects(trace::Call *call)
     }
 
     if (trimFlags & TRIM_FLAG_TEXTURES) {
-        
         if (recordTextureSideEffects(call, name)) {
             return;
         }
     }
 
+    if (recordBufferSideEffects(call, name)) {
+        return;
+    }
+
+    if (recordMatrixSideEffects(call, name)) {
+        return;
+    }
+
     if (trimFlags & TRIM_FLAG_SHADERS) {
 
         if (recordShaderSideEffects(call, name)) {
@@ -697,27 +1287,84 @@ TraceAnalyzer::recordSideEffects(trace::Call *call)
         }
     }
 
-    /* By default, assume this call affects the state somehow. */
-    resources["state"].insert(call->no);
-}
-
-void
-TraceAnalyzer::requireDependencies(trace::Call *call)
-{
+    if (recordStateSideEffects(call, name)) {
+        return;
+    }
 
-    /* Swap-buffers calls depend on framebuffer state. */
-    if (call->flags & trace::CALL_FLAG_SWAP_RENDERTARGET &&
-        call->flags & trace::CALL_FLAG_END_FRAME) {
-        consume("framebuffer");
+    if (recordMemorySideEffects(call, name)) {
+        return;
     }
 
-    /* By default, just assume this call depends on generic state. */
-    consume("state");
+    if (name != std::string("glDeleteSync") &&
+        name != std::string("glFenceSync") &&
+        name != std::string("glDebugMessageCallbackARB") &&
+        name != std::string("glS") &&
+        name != std::string("glXDestroyContext") &&
+        name != std::string("glXQueryCurrentRendererIntegerMESA") &&
+        name != std::string("glXChooseFBConfig") &&
+        name != std::string("glXGetVisualFromFBConfig") &&
+        name != std::string("glXCreateNewContext") &&
+        name != std::string("glXSwapIntervalSGI") &&
+        name != std::string("glLoadIdentity") &&
+        name != std::string("glDeleteBuffersARB") &&
+        name != std::string("glDeleteTextures") &&
+        name != std::string("glXMakeCurrent") &&
+        name != std::string("glXGetFBConfigAttrib") &&
+        name != std::string("glDeleteObjectARB") &&
+        name != std::string("glDeleteRenderbuffersEXT"))
+        std::cout << "UNHANDLED: " << name << std::endl;
+
+    /* By default, assume this call affects the state somehow. */
+    mutate_lazy(global_state_calls,
+                [&](union_set<unsigned> c) {
+                    return std::move(c.add(call->no));
+                });
 }
 
 TraceAnalyzer::TraceAnalyzer(TrimFlags trimFlagsOpt):
+    global_state_calls(std::make_shared<const union_set<unsigned>>()),
+    render_state_calls(std::make_shared<const union_set<unsigned>>()),
+    winsys_framebuffer_calls(std::make_shared<const union_set<unsigned>>()),
+    program_binding_calls(std::make_shared<const union_set<unsigned>>()),
+    active_texture_calls(std::make_shared<const union_set<unsigned>>()),
+    framebuffer_binding_calls(std::make_shared<const union_set<unsigned>>()),
+    renderbuffer_binding_calls(std::make_shared<const union_set<unsigned>>()),
+    pixel_store_calls(std::make_shared<const union_set<unsigned>>()),
+    current_vertex_calls(std::make_shared<const union_set<unsigned>>()),
+    current_color_calls(std::make_shared<const union_set<unsigned>>()),
+    current_secondary_color_calls(std::make_shared<const union_set<unsigned>>()),
+    current_normal_calls(std::make_shared<const union_set<unsigned>>()),
+    current_edge_flag_calls(std::make_shared<const union_set<unsigned>>()),
+    current_fog_coord_calls(std::make_shared<const union_set<unsigned>>()),
+    current_index_calls(std::make_shared<const union_set<unsigned>>()),
+    vertex_pointer_calls(std::make_shared<const union_set<unsigned>>()),
+    color_pointer_calls(std::make_shared<const union_set<unsigned>>()),
+    secondary_color_pointer_calls(std::make_shared<const union_set<unsigned>>()),
+    normal_pointer_calls(std::make_shared<const union_set<unsigned>>()),
+    edge_flag_pointer_calls(std::make_shared<const union_set<unsigned>>()),
+    fog_coord_pointer_calls(std::make_shared<const union_set<unsigned>>()),
+    index_pointer_calls(std::make_shared<const union_set<unsigned>>()),
+    client_active_texture_calls(std::make_shared<const union_set<unsigned>>()),
+    matrix_mode_calls(std::make_shared<const union_set<unsigned>>()),
+    clear_color_calls(std::make_shared<const union_set<unsigned>>()),
+    clear_depth_calls(std::make_shared<const union_set<unsigned>>()),
+    clear_stencil_calls(std::make_shared<const union_set<unsigned>>()),
+    depth_mask_calls(std::make_shared<const union_set<unsigned>>()),
+    color_mask_calls(std::make_shared<const union_set<unsigned>>()),
+    stencil_mask_calls(std::make_shared<const union_set<unsigned>>()),
+    viewport_state_calls(std::make_shared<const union_set<unsigned>>()),
+    scissor_state_calls(std::make_shared<const union_set<unsigned>>()),
+    polygon_offset_state_calls(std::make_shared<const union_set<unsigned>>()),
+    blend_equation_calls(std::make_shared<const union_set<unsigned>>()),
+    blend_func_calls(std::make_shared<const union_set<unsigned>>()),
+    front_face_calls(std::make_shared<const union_set<unsigned>>()),
+    cull_face_calls(std::make_shared<const union_set<unsigned>>()),
+    depth_func_calls(std::make_shared<const union_set<unsigned>>()),
+    matrix_mode(GL_MODELVIEW),
+    client_active_texture(GL_TEXTURE0),
+    draw_framebuffer(0),
+    read_framebuffer(0),
     transformFeedbackActive(false),
-    framebufferObjectActive(false),
     insideBeginEnd(false),
     insideNewEndList(0),
     activeTextureUnit(GL_TEXTURE0),
@@ -749,9 +1396,15 @@ TraceAnalyzer::analyze(trace::Call *call)
 void
 TraceAnalyzer::require(trace::Call *call)
 {
+    /* Swap-buffers calls depend on framebuffer state. */
+    if (call->flags & trace::CALL_FLAG_SWAP_RENDERTARGET &&
+        call->flags & trace::CALL_FLAG_END_FRAME) {
+        winsys_framebuffer_calls->consume(
+            [&](unsigned call) { required.add(call); });
+    }
 
-    /* First, find and insert all calls that this call depends on. */
-    requireDependencies(call);
+    /* By default, just assume this call depends on generic state. */
+    global_state_calls->consume([&](unsigned call) { required.add(call); });
 
     /* Then insert this call itself. */
     required.add(call->no);
diff --git a/cli/cli_trim_auto_analyzer.hpp b/cli/cli_trim_auto_analyzer.hpp
index c344fb6a..eb30ee49 100644
--- a/cli/cli_trim_auto_analyzer.hpp
+++ b/cli/cli_trim_auto_analyzer.hpp
@@ -24,6 +24,7 @@
  **************************************************************************/
 
 #include <set>
+#include <memory>
 
 #include <GL/gl.h>
 #include <GL/glext.h>
@@ -52,48 +53,433 @@ enum {
     TRIM_FLAG_DRAWING			= (1 << 3),
 };
 
+template<typename T>
+struct union_set {
+    union_set() {}
+    union_set(const union_set &x) : s(x.s), sps(x.sps) {}
+    union_set(union_set &&x) : s(std::move(x.s)), sps(std::move(x.sps)) {}
+
+    template<typename S>
+    union_set(const S &x) {
+        add(x);
+    }
+
+    union_set &
+    add(const std::shared_ptr<const union_set> &sp) & {
+        if (sp) {
+            if (sp->s.size() + sp->sps.size() <= 4) {
+                s.insert(sp->s.begin(), sp->s.end());
+                sps.insert(sp->sps.begin(), sp->sps.end());
+            } else {
+                sps.emplace(sp);
+            }
+        }
+        return *this;
+    }
+
+    union_set &
+    add(const T &x) & {
+        s.insert(x);
+        return *this;
+    }
+
+    template<typename S>
+    union_set &&
+    add(const S &sp) && {
+        add(sp);
+        return std::move(*this);
+    }
+
+    union_set &
+    clear() & {
+        s.clear();
+        sps.clear();
+        return *this;
+    }
+
+    union_set &&
+    clear() && {
+        clear();
+        return std::move(*this);
+    }
+
+    template<typename F>
+    void
+    consume(const F &f) const {
+        for (const auto &x : s)
+            f(x);
+        const_cast<union_set *>(this)->s.clear();
+
+        std::set<std::shared_ptr<const union_set>> &sps =
+            const_cast<union_set *>(this)->sps;
+
+        while (!sps.empty()) {
+            const auto sp = *sps.begin();
+            sps.erase(sps.begin());
+            sps.insert(sp->sps.begin(), sp->sps.end());
+            const_cast<union_set *>(sp.get())->sps.clear();
+
+            for (const auto &x : sp->s)
+                f(x);
+            const_cast<union_set *>(sp.get())->s.clear();
+        }
+    }
+
+    template<typename F>
+    void
+    traverse(const F &f, std::set<const union_set *> &seen) const {
+        if (!seen.count(this)) {
+            seen.insert(this);
+
+            for (const auto &x : s)
+                f(x);
+
+            for (const auto &sp : sps)
+                sp->traverse(f, seen);
+        }
+    }
+
+    template<typename F>
+    void
+    traverse(const F &f) const {
+        std::set<const union_set *> seen;
+        traverse(f, seen);
+    }
+
+private:
+    std::set<T> s;
+    std::set<std::shared_ptr<const union_set>> sps;
+};
+
+template<typename T>
+unsigned
+size(const union_set<T> &s) {
+    unsigned n = 0;
+    s.traverse([&](const T &) { n++; });
+    return n;
+}
+
+template<typename T>
+unsigned
+size_unique(const union_set<T> &s) {
+    std::set<T> xs;
+    s.traverse([&](const T &x) { xs.insert(x); });
+    return xs.size();
+}
+
+template<typename T, typename F>
+void
+mutate(std::shared_ptr<const T> &sp, const F &f) {
+    if (!sp)
+        sp = std::make_shared<const T>(f(T()));
+    else if (sp.use_count() == 1)
+        sp = std::make_shared<const T>(f(std::move(const_cast<T &>(*sp))));
+    else
+        sp = std::make_shared<const T>(f(*sp));
+}
+
+template<typename T, typename F>
+void
+mutate_lazy(std::shared_ptr<const T> &sp, const F &f) {
+    if (!sp)
+        sp = std::make_shared<const T>(f(T()));
+    else if (sp.use_count() == 1)
+        sp = std::make_shared<const T>(f(std::move(const_cast<T &>(*sp))));
+    else
+        sp = std::make_shared<const T>(f(T(sp)));
+}
+
+bool debugging();
+
+template<typename T>
+void
+dump(const union_set<T> &s) {
+    std::cout << "DUMP: ";
+    s.traverse([](unsigned x) {
+            std::cout << x << ", ";
+        });
+    std::cout << std::endl;
+}
+
+template<typename T>
+bool
+contains(const union_set<T> &s, T x) {
+        bool found = false;
+        s.traverse([&](const T &y) {
+                        found |= (y == x);
+                });
+        return found;
+}
+
 class TraceAnalyzer {
 private:
-    std::map<std::string, std::set<unsigned> > resources;
-    std::map<std::string, std::set<std::string> > dependencies;
+    std::shared_ptr<const union_set<unsigned>> global_state_calls;
 
-    std::map<GLenum, unsigned> texture_map;
+    std::shared_ptr<const union_set<unsigned>> render_state_calls;
+    std::shared_ptr<const union_set<unsigned>> winsys_framebuffer_calls;
+    std::shared_ptr<const union_set<unsigned>> program_binding_calls;
+    std::map<unsigned, std::shared_ptr<const union_set<unsigned>>>
+       framebuffer_object_calls;
+    std::map<unsigned, std::shared_ptr<const union_set<unsigned>>>
+       renderbuffer_object_calls;
+    std::map<unsigned, std::shared_ptr<const union_set<unsigned>>>
+       renderbuffer_contents_calls;
 
-    trace::FastCallSet required;
+    std::map<GLenum, std::map<GLenum,
+             std::shared_ptr<const union_set<unsigned>>>> texture_binding_calls;
+    std::map<GLenum, std::map<GLenum,
+             std::shared_ptr<const union_set<unsigned>>>> texture_enable_calls;
+
+    std::shared_ptr<const union_set<unsigned>> active_texture_calls;
+    std::map<GLenum, std::map<unsigned,
+             std::shared_ptr<const union_set<unsigned>>>> indexed_buffer_binding_calls;
+    std::map<GLenum,
+             std::shared_ptr<const union_set<unsigned>>> buffer_binding_calls;
+    std::shared_ptr<const union_set<unsigned>> framebuffer_binding_calls;
+    std::shared_ptr<const union_set<unsigned>> renderbuffer_binding_calls;
+    std::shared_ptr<const union_set<unsigned>> pixel_store_calls;
+
+    std::shared_ptr<const union_set<unsigned>> current_vertex_calls;
+    std::shared_ptr<const union_set<unsigned>> current_color_calls;
+    std::shared_ptr<const union_set<unsigned>> current_secondary_color_calls;
+    std::shared_ptr<const union_set<unsigned>> current_normal_calls;
+    std::map<GLenum,
+             std::shared_ptr<const union_set<unsigned>>> current_tex_coord_calls;
+    std::shared_ptr<const union_set<unsigned>> current_edge_flag_calls;
+    std::shared_ptr<const union_set<unsigned>> current_fog_coord_calls;
+    std::shared_ptr<const union_set<unsigned>> current_index_calls;
+
+    std::shared_ptr<const union_set<unsigned>> vertex_pointer_calls;
+    std::shared_ptr<const union_set<unsigned>> color_pointer_calls;
+    std::shared_ptr<const union_set<unsigned>> secondary_color_pointer_calls;
+    std::shared_ptr<const union_set<unsigned>> normal_pointer_calls;
+    std::map<GLenum,
+             std::shared_ptr<const union_set<unsigned>>> tex_coord_pointer_calls;
+    std::shared_ptr<const union_set<unsigned>> edge_flag_pointer_calls;
+    std::shared_ptr<const union_set<unsigned>> fog_coord_pointer_calls;
+    std::shared_ptr<const union_set<unsigned>> index_pointer_calls;
+
+    std::map<GLenum, std::map<unsigned,
+                              std::shared_ptr<const union_set<unsigned>>>>
+        client_state_enable_calls;
+    std::map<unsigned, std::shared_ptr<const union_set<unsigned>>>
+        vertex_attrib_array_enable_calls;
+    std::map<unsigned, std::shared_ptr<const union_set<unsigned>>>
+        vertex_attrib_pointer_calls;
+    std::shared_ptr<const union_set<unsigned>> client_active_texture_calls;
+
+    std::map<unsigned, std::shared_ptr<const union_set<unsigned>>> program_object_calls;
+    std::map<unsigned, std::map<unsigned,
+                                std::shared_ptr<const union_set<unsigned>>>> program_object_uniform_calls;
+    std::map<unsigned, std::shared_ptr<const union_set<unsigned>>> texture_object_calls;
+    std::map<unsigned, std::shared_ptr<const union_set<unsigned>>> texture_contents_calls;
+    std::map<unsigned, std::shared_ptr<const union_set<unsigned>>> buffer_object_calls;
+    std::map<unsigned, std::shared_ptr<const union_set<unsigned>>> shader_object_calls;
+
+    std::map<GLenum, std::shared_ptr<const union_set<unsigned>>> matrix_state_calls;
+    std::shared_ptr<const union_set<unsigned>> matrix_mode_calls;
+
+    std::shared_ptr<const union_set<unsigned>> clear_color_calls;
+    std::shared_ptr<const union_set<unsigned>> clear_depth_calls;
+    std::shared_ptr<const union_set<unsigned>> clear_stencil_calls;
+
+    std::shared_ptr<const union_set<unsigned>> depth_mask_calls;
+    std::shared_ptr<const union_set<unsigned>> color_mask_calls;
+    std::shared_ptr<const union_set<unsigned>> stencil_mask_calls;
+    std::shared_ptr<const union_set<unsigned>> viewport_state_calls;
+    std::shared_ptr<const union_set<unsigned>> scissor_state_calls;
+    std::shared_ptr<const union_set<unsigned>> polygon_offset_state_calls;
+    std::map<GLenum, std::shared_ptr<const union_set<unsigned>>> face_polygon_mode_calls;
+    std::shared_ptr<const union_set<unsigned>> blend_equation_calls;
+    std::shared_ptr<const union_set<unsigned>> blend_func_calls;
+    std::shared_ptr<const union_set<unsigned>> front_face_calls;
+    std::shared_ptr<const union_set<unsigned>> cull_face_calls;
+
+    std::shared_ptr<const union_set<unsigned>> depth_func_calls;
+    std::map<GLenum, std::shared_ptr<const union_set<unsigned>>>
+       face_stencil_func_calls;
+    std::map<GLenum, std::shared_ptr<const union_set<unsigned>>>
+       face_stencil_op_calls;
 
+    std::map<uintptr_t, std::pair<size_t, std::shared_ptr<const union_set<unsigned>>>> memory_calls;
+
+    std::shared_ptr<const union_set<unsigned>>
+    bound_indexed_buffer_object_calls(GLenum target, unsigned idx) const
+    {
+        const unsigned buffer = indexed_buffer_map.at(target).at(idx);
+        auto calls = *indexed_buffer_binding_calls.at(target).at(idx);
+        if (buffer_object_calls.count(buffer))
+            calls.add(buffer_object_calls.at(buffer));
+        return std::make_shared<const union_set<unsigned>>(calls);
+    }
+
+    std::shared_ptr<const union_set<unsigned>>
+    bound_texture_object_calls(GLenum target, unsigned unit) const
+    {
+        const GLuint texture = unit_texture_map.at(target).at(unit);
+        return std::make_shared<const union_set<unsigned>>(
+            union_set<unsigned>(*texture_binding_calls.at(target).at(unit))
+                 .add(texture_object_calls.at(texture))
+                 .add(texture_contents_calls.at(texture)));
+    }
+
+    std::set<unsigned>
+    all_enabled_texture_units() const
+    {
+        std::set<unsigned> result = enabled_texture_units;
+        if (activeProgram && program_object_texture_units.count(activeProgram))
+            result.insert(program_object_texture_units.at(activeProgram).begin(),
+                          program_object_texture_units.at(activeProgram).end());
+        return result;
+    }
+
+    union_set<unsigned>
+    pipeline_state_calls() const {
+        union_set<unsigned> result = render_state_calls;
+
+        for (auto u : all_enabled_texture_units()) {
+            for (const auto &t : unit_texture_map) {
+                if (t.second.count(u))
+                    result.add(bound_texture_object_calls(t.first, u));
+            }
+        }
+
+        for (const auto &p : texture_enable_calls) {
+            for (const auto &q : p.second)
+                result.add(q.second);
+        }
+
+        for (const auto &p : indexed_buffer_binding_calls) {
+            for (const auto &q : p.second)
+                result.add(bound_indexed_buffer_object_calls(p.first, q.first));
+        }
+
+        for (const auto &p : matrix_state_calls)
+            result.add(p.second);
+
+        if (activeProgram && program_object_uniform_calls.count(activeProgram)) {
+            for (const auto &p : program_object_uniform_calls.at(activeProgram))
+                result.add(p.second);
+        }
+
+        result.add(program_binding_calls);
+        result.add(clear_color_calls);
+        result.add(clear_depth_calls);
+        result.add(clear_stencil_calls);
+
+        for (const auto &p : client_state_enable_calls) {
+            for (const auto &q : p.second)
+                result.add(q.second);
+        }
+
+        for (const auto &p : vertex_attrib_array_enable_calls)
+            result.add(p.second);
+
+        for (const auto &p : vertex_attrib_pointer_calls)
+            result.add(p.second);
+
+        result.add(vertex_pointer_calls);
+        result.add(color_pointer_calls);
+        result.add(secondary_color_pointer_calls);
+        result.add(normal_pointer_calls);
+
+        for (const auto &p : tex_coord_pointer_calls)
+            result.add(p.second);
+
+        result.add(edge_flag_pointer_calls);
+        result.add(fog_coord_pointer_calls);
+        result.add(index_pointer_calls);
+
+        result.add(depth_mask_calls);
+        result.add(color_mask_calls);
+        result.add(stencil_mask_calls);
+        result.add(viewport_state_calls);
+        result.add(scissor_state_calls);
+        result.add(polygon_offset_state_calls);
+
+        for (const auto &p : face_polygon_mode_calls)
+            result.add(p.second);
+
+        result.add(blend_equation_calls);
+        result.add(blend_func_calls);
+        result.add(front_face_calls);
+        result.add(cull_face_calls);
+        result.add(depth_func_calls);
+        result.add(framebuffer_binding_calls);
+        result.add(renderbuffer_binding_calls);
+
+        if (framebuffer_object_calls.count(draw_framebuffer))
+            result.add(framebuffer_object_calls.at(draw_framebuffer));
+
+        for (const auto &p : face_stencil_func_calls)
+            result.add(p.second);
+
+        for (const auto &p : face_stencil_op_calls)
+            result.add(p.second);
+
+        if (draw_framebuffer) {
+            for (const auto &t : framebuffer_texture_map.at(draw_framebuffer))
+                result.add(texture_object_calls.at(t.second));
+
+            for (const auto &t : framebuffer_renderbuffer_map.at(draw_framebuffer))
+                result.add(renderbuffer_object_calls.at(t.second));
+        }
+
+        result.add(current_vertex_calls);
+        result.add(current_color_calls);
+        result.add(current_secondary_color_calls);
+        result.add(current_normal_calls);
+
+        for (const auto &p : current_tex_coord_calls)
+            result.add(p.second);
+
+        result.add(current_edge_flag_calls);
+        result.add(current_fog_coord_calls);
+        result.add(current_index_calls);
+
+        return result;
+    }
+
+    std::map<unsigned, std::set<unsigned>> program_object_texture_units;
+    std::set<unsigned> enabled_texture_units;
+    std::map<GLenum, unsigned> texture_map;
+    std::map<GLenum, std::map<unsigned, unsigned>> unit_texture_map;
+    std::map<GLenum, unsigned> buffer_map;
+    std::map<unsigned, std::pair<uintptr_t, size_t>> buffer_mapping_map;
+    std::map<GLenum, std::map<unsigned, unsigned>> indexed_buffer_map;
+    std::map<unsigned, std::map<GLenum, unsigned>> framebuffer_texture_map;
+    std::map<unsigned, std::map<GLenum, unsigned>> framebuffer_renderbuffer_map;
+
+    GLenum matrix_mode;
+    GLenum client_active_texture;
+    GLenum draw_framebuffer;
+    GLenum read_framebuffer;
+    GLuint renderbuffer;
     bool transformFeedbackActive;
-    bool framebufferObjectActive;
     bool insideBeginEnd;
     GLuint insideNewEndList;
     GLenum activeTextureUnit;
     GLuint activeProgram;
-    unsigned int trimFlags;
 
-    void provide(std::string resource, trace::CallNo call_no);
-    void providef(std::string resource, int resource_no, trace::CallNo call_no);
-
-    void link(std::string resource, std::string dependency);
-    void linkf(std::string resource, std::string dependency, int dep_no);
+    trace::FastCallSet required;
 
-    void unlink(std::string resource, std::string dependency);
-    void unlinkf(std::string resource, std::string dependency, int dep_no);
-    void unlinkAll(std::string resource);
+    unsigned int trimFlags;
 
     void stateTrackPreCall(trace::Call *call);
 
     void recordSideEffects(trace::Call *call);
     bool callHasNoSideEffects(trace::Call *call, const char *name);
     bool recordTextureSideEffects(trace::Call *call, const char *name);
+    bool recordBufferSideEffects(trace::Call *call, const char *name);
     bool recordShaderSideEffects(trace::Call *call, const char *name);
     bool recordDrawingSideEffects(trace::Call *call, const char *name);
+    bool recordMatrixSideEffects(trace::Call *call, const char *name);
+    bool recordStateSideEffects(trace::Call *call, const char *name);
+    bool recordMemorySideEffects(trace::Call *call, const char *name);
 
     void stateTrackPostCall(trace::Call *call);
 
     bool renderingHasSideEffect(void);
-    std::set<unsigned> resolve(std::string resource);
-
-    void consume(std::string resource);
-    void requireDependencies(trace::Call *call);
 
 public:
     TraceAnalyzer(TrimFlags trimFlags = -1);