trim: Move TraceAnalyzer out of cli_trim.cpp into its own file.

This class had long since outgrown where it was living at the top of
cli_trim.cpp. Thanks to José for recommending this.

4 files changed, 784 insertions, 653 deletions

diff --git a/cli/CMakeLists.txt b/cli/CMakeLists.txt
index ed998810..5df363ab 100644
--- a/cli/CMakeLists.txt
+++ b/cli/CMakeLists.txt
@@ -11,6 +11,7 @@ add_executable (apitrace
     cli_retrace.cpp
     cli_trace.cpp
     cli_trim.cpp
+    trace_analyzer.cpp
 )
 
 target_link_libraries (apitrace
diff --git a/cli/cli_trim.cpp b/cli/cli_trim.cpp
index f7bc92ba..c2bb887c 100644
--- a/cli/cli_trim.cpp
+++ b/cli/cli_trim.cpp
@@ -29,22 +29,17 @@
 #include <limits.h> // for CHAR_MAX
 #include <getopt.h>
 
-#include <GL/gl.h>
-#include <GL/glext.h>
-
 #include <set>
 
 #include "cli.hpp"
 
 #include "os_string.hpp"
 
+#include "trace_analyzer.hpp"
 #include "trace_callset.hpp"
 #include "trace_parser.hpp"
 #include "trace_writer.hpp"
 
-#define MAX(a, b) ((a) > (b) ? (a) : (b))
-#define STRNCMP_LITERAL(var, literal) strncmp((var), (literal), sizeof (literal) -1)
-
 static const char *synopsis = "Create a new trace by trimming an existing trace.";
 
 static void
@@ -157,653 +152,6 @@ struct stringCompare {
     }
 };
 
-class TraceAnalyzer {
-    /* Maps for tracking resource dependencies between calls. */
-    std::map<std::string, std::set<unsigned> > resources;
-    std::map<std::string, std::set<std::string> > dependencies;
-
-    /* Maps for tracking OpenGL state. */
-    std::map<GLenum, unsigned> texture_map;
-
-    /* The final set of calls required. This consists of calls added
-     * explicitly with the require() method as well as all calls
-     * implicitly required by those through resource dependencies. */
-    std::set<unsigned> required;
-
-    bool transformFeedbackActive;
-    bool framebufferObjectActive;
-    bool insideBeginEnd;
-    GLuint insideNewEndList;
-    GLuint activeProgram;
-    GLenum activeTextureUnit;
-
-    /* Rendering often has no side effects, but it can in some cases,
-     * (such as when transform feedback is active, or when rendering
-     * targets a framebuffer object). */
-    bool renderingHasSideEffect() {
-        return transformFeedbackActive || framebufferObjectActive;
-    }
-
-    /* Provide: Record that the given call affects the given resource
-     * as a side effect. */
-    void 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 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 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 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 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 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 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> 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 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.insert(*call);
-        }
-    }
-
-    void stateTrackPreCall(trace::Call *call) {
-
-        const char *name = call->name();
-
-        if (strcmp(name, "glBegin") == 0) {
-            insideBeginEnd = true;
-            return;
-        }
-
-        if (strcmp(name, "glBeginTransformFeedback") == 0) {
-            transformFeedbackActive = true;
-            return;
-        }
-
-        if (strcmp(name, "glActiveTexture") == 0) {
-            activeTextureUnit = static_cast<GLenum>(call->arg(0).toSInt());
-            return;
-        }
-
-        if (strcmp(name, "glBindTexture") == 0) {
-            GLenum target;
-            GLuint texture;
-
-            target = static_cast<GLenum>(call->arg(0).toSInt());
-            texture = call->arg(1).toUInt();
-
-            if (texture == 0) {
-                texture_map.erase(target);
-            } else {
-                texture_map[target] = texture;
-            }
-
-            return;
-        }
-
-        if (strcmp(name, "glUseProgram") == 0) {
-            activeProgram = call->arg(0).toUInt();
-        }
-
-        if (strcmp(name, "glBindFramebuffer") == 0) {
-            GLenum target;
-            GLuint framebuffer;
-
-            target = static_cast<GLenum>(call->arg(0).toSInt());
-            framebuffer = call->arg(1).toUInt();
-
-            if (target == GL_FRAMEBUFFER || target == GL_DRAW_FRAMEBUFFER) {
-                if (framebuffer == 0) {
-                    framebufferObjectActive = false;
-                } else {
-                    framebufferObjectActive = true;
-                }
-            }
-            return;
-        }
-
-        if (strcmp(name, "glNewList") == 0) {
-            GLuint list = call->arg(0).toUInt();
-
-            insideNewEndList = list;
-        }
-    }
-
-    void stateTrackPostCall(trace::Call *call) {
-
-        const char *name = call->name();
-
-        if (strcmp(name, "glEnd") == 0) {
-            insideBeginEnd = false;
-            return;
-        }
-
-        if (strcmp(name, "glEndTransformFeedback") == 0) {
-            transformFeedbackActive = false;
-            return;
-        }
-
-        /* If this swapbuffers was included in the trace then it will
-         * have already consumed all framebuffer dependencies. If not,
-         * then clear them now so that they don't carry over into the
-         * next frame. */
-        if (call->flags & trace::CALL_FLAG_SWAP_RENDERTARGET &&
-            call->flags & trace::CALL_FLAG_END_FRAME) {
-            dependencies.erase("framebuffer");
-            resources.erase("framebuffer");
-            return;
-        }
-
-        if (strcmp(name, "glEndList") == 0) {
-            insideNewEndList = 0;
-        }
-    }
-
-    void recordSideEffects(trace::Call *call) {
-
-        const char *name = call->name();
-
-        /* Handle display lists before any other processing. */
-
-        /* FIXME: If we encode the list of commands that are executed
-         * immediately (as opposed to those that are compiled into a
-         * display list) then we could generate a "display-list-X"
-         * resource just as we do for "texture-X" resources and only
-         * emit it in the trace if a glCallList(X) is emitted. For
-         * now, simply punt and include anything within glNewList and
-         * glEndList in the trim output. This guarantees that display
-         * lists will work, but does not trim out unused display
-         * lists. */
-        if (insideNewEndList != 0) {
-            provide("state", 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);
-            }
-
-            return;
-        }
-
-        /* If call is flagged as no side effects, then we are done here. */
-        if (call->flags & trace::CALL_FLAG_NO_SIDE_EFFECTS) {
-            return;
-        }
-
-        /* Similarly, swap-buffers calls don't have interesting side effects. */
-        if (call->flags & trace::CALL_FLAG_SWAP_RENDERTARGET &&
-            call->flags & trace::CALL_FLAG_END_FRAME) {
-            return;
-        }
-
-        if (strcmp(name, "glGenTextures") == 0) {
-            const trace::Array *textures = dynamic_cast<const trace::Array *>(&call->arg(1));
-            size_t i;
-            GLuint texture;
-
-            if (textures) {
-                for (i = 0; i < textures->size(); i++) {
-                    texture = textures->values[i]->toUInt();
-                    providef("texture-", texture, call->no);
-                }
-            }
-            return;
-        }
-
-        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);
-
-            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);
-
-            return;
-        }
-
-        /* FIXME: Need to handle glMultTexImage 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, "glCompressedTexSubImage") == 0 ||
-            strcmp(name, "glInvalidateTexImage") == 0 ||
-            strcmp(name, "glInvalidateTexSubImage") == 0) {
-
-            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);
-                }
-            }
-
-            return;
-        }
-
-        if (strcmp(name, "glEnable") == 0) {
-            GLenum cap;
-
-            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;
-
-                link("render-state", ss.str());
-            }
-
-            provide("state", call->no);
-            return;
-        }
-
-        if (strcmp(name, "glDisable") == 0) {
-            GLenum cap;
-
-            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;
-
-                unlink("render-state", ss.str());
-            }
-
-            provide("state", call->no);
-            return;
-        }
-
-        if (strcmp(name, "glCreateShader") == 0 ||
-            strcmp(name, "glCreateShaderObjectARB") == 0) {
-
-            GLuint shader = call->ret->toUInt();
-            providef("shader-", shader, call->no);
-            return;
-        }
-
-        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) {
-
-            GLuint shader = call->arg(0).toUInt();
-            providef("shader-", shader, call->no);
-            return;
-        }
-
-        if (strcmp(name, "glCreateProgram") == 0 ||
-            strcmp(name, "glCreateProgramObjectARB") == 0) {
-
-            GLuint program = call->ret->toUInt();
-            providef("program-", program, call->no);
-            return;
-        }
-
-        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);
-
-            return;
-        }
-
-        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;
-        }
-
-        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;
-        }
-
-        if (strcmp(name, "glGetUniformLocation") == 0 ||
-            strcmp(name, "glGetUniformLocationARB") == 0 ||
-            strcmp(name, "glGetFragDataLocation") == 0 ||
-            strcmp(name, "glGetFragDataLocationEXT") == 0 ||
-            strcmp(name, "glGetSubroutineUniformLocation") == 0 ||
-            strcmp(name, "glGetProgramResourceLocation") == 0 ||
-            strcmp(name, "glGetProgramResourceLocationIndex") == 0 ||
-            strcmp(name, "glGetVaryingLocationNV") == 0) {
-
-            GLuint program = call->arg(0).toUInt();
-
-            providef("program-", program, call->no);
-
-            return;
-        }
-
-        /* For any call that accepts 'location' as its first argument,
-         * perform a lookup in our location->program map and add a
-         * dependence on the program we find there. */
-        if (call->sig->num_args > 0 &&
-            strcmp(call->sig->arg_names[0], "location") == 0) {
-
-            providef("program-", activeProgram, call->no);
-
-            /* 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. */
-            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;
-
-                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);
-                }
-            }
-
-            return;
-        }
-
-        /* FIXME: We cut a huge swath by assuming that any unhandled
-         * call that has a first argument named "program" should not
-         * be included in the trimmed output unless the program of
-         * that number is also included.
-         *
-         * This heuristic is correct for many cases, but we should
-         * actually carefully verify if this includes some calls
-         * inappropriately, or if it misses some.
-         */
-        if (strcmp(name, "glLinkProgram") == 0 ||
-            strcmp(name, "glLinkProgramARB") == 0 ||
-            (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);
-            return;
-        }
-
-        /* 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) {
-
-            std::set<unsigned> calls;
-            std::set<unsigned>::iterator c;
-
-            provide("framebuffer", call->no);
-
-            calls = resolve("render-state");
-
-            for (c = calls.begin(); c != calls.end(); c++) {
-                provide("framebuffer", *c);
-            }
-
-            /* 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);
-                }
-            }
-
-            return;
-        }
-
-        /* By default, assume this call affects the state somehow. */
-        resources["state"].insert(call->no);
-    }
-
-    void requireDependencies(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) {
-            consume("framebuffer");
-        }
-
-        /* By default, just assume this call depends on generic state. */
-        consume("state");
-    }
-
-
-public:
-    TraceAnalyzer(): transformFeedbackActive(false),
-                     framebufferObjectActive(false),
-                     insideBeginEnd(false),
-                     insideNewEndList(0),
-                     activeTextureUnit(GL_TEXTURE0)
-    {}
-
-    ~TraceAnalyzer() {}
-
-    /* Analyze this call by tracking state and recording all the
-     * resources provided by this call as side effects.. */
-    void analyze(trace::Call *call) {
-
-        stateTrackPreCall(call);
-
-        recordSideEffects(call);
-
-        stateTrackPostCall(call);
-    }
-
-    /* Require this call and all of its dependencies to be included in
-     * the final trace. */
-    void require(trace::Call *call) {
-
-        /* First, find and insert all calls that this call depends on. */
-        requireDependencies(call);
-
-        /* Then insert this call itself. */
-        required.insert(call->no);
-    }
-
-    /* Return a set of all the required calls, (both those calls added
-     * explicitly with require() and those implicitly depended
-     * upon. */
-    std::set<unsigned> *get_required(void) {
-        return &required;
-    }
-};
-
 struct trim_options {
     /* Calls to be included in trace. */
     trace::CallSet calls;
diff --git a/cli/trace_analyzer.cpp b/cli/trace_analyzer.cpp
new file mode 100644
index 00000000..afca8026
--- /dev/null
+++ b/cli/trace_analyzer.cpp
@@ -0,0 +1,696 @@
+/**************************************************************************
+ * Copyright 2012 Intel corporation
+ *
+ * All Rights Reserved.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ *
+ **************************************************************************/
+
+#include <sstream>
+
+#include "trace_analyzer.hpp"
+
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+#define STRNCMP_LITERAL(var, literal) strncmp((var), (literal), sizeof (literal) -1)
+
+/* Rendering often has no side effects, but it can in some cases,
+* (such as when transform feedback is active, or when rendering
+* targets a framebuffer object). */
+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.insert(*call);
+    }
+}
+
+void
+TraceAnalyzer::stateTrackPreCall(trace::Call *call)
+{
+
+    const char *name = call->name();
+
+    if (strcmp(name, "glBegin") == 0) {
+        insideBeginEnd = true;
+        return;
+    }
+
+    if (strcmp(name, "glBeginTransformFeedback") == 0) {
+        transformFeedbackActive = true;
+        return;
+    }
+
+    if (strcmp(name, "glActiveTexture") == 0) {
+        activeTextureUnit = static_cast<GLenum>(call->arg(0).toSInt());
+        return;
+    }
+
+    if (strcmp(name, "glBindTexture") == 0) {
+        GLenum target;
+        GLuint texture;
+
+        target = static_cast<GLenum>(call->arg(0).toSInt());
+        texture = call->arg(1).toUInt();
+
+        if (texture == 0) {
+            texture_map.erase(target);
+        } else {
+            texture_map[target] = texture;
+        }
+
+        return;
+    }
+
+    if (strcmp(name, "glUseProgram") == 0) {
+        activeProgram = call->arg(0).toUInt();
+    }
+
+    if (strcmp(name, "glBindFramebuffer") == 0) {
+        GLenum target;
+        GLuint framebuffer;
+
+        target = static_cast<GLenum>(call->arg(0).toSInt());
+        framebuffer = call->arg(1).toUInt();
+
+        if (target == GL_FRAMEBUFFER || target == GL_DRAW_FRAMEBUFFER) {
+            if (framebuffer == 0) {
+                framebufferObjectActive = false;
+            } else {
+                framebufferObjectActive = true;
+            }
+        }
+        return;
+    }
+
+    if (strcmp(name, "glNewList") == 0) {
+        GLuint list = call->arg(0).toUInt();
+
+        insideNewEndList = list;
+    }
+}
+
+void
+TraceAnalyzer::stateTrackPostCall(trace::Call *call)
+{
+
+    const char *name = call->name();
+
+    if (strcmp(name, "glEnd") == 0) {
+        insideBeginEnd = false;
+        return;
+    }
+
+    if (strcmp(name, "glEndTransformFeedback") == 0) {
+        transformFeedbackActive = false;
+        return;
+    }
+
+    /* If this swapbuffers was included in the trace then it will
+     * have already consumed all framebuffer dependencies. If not,
+     * then clear them now so that they don't carry over into the
+     * next frame. */
+    if (call->flags & trace::CALL_FLAG_SWAP_RENDERTARGET &&
+        call->flags & trace::CALL_FLAG_END_FRAME) {
+        dependencies.erase("framebuffer");
+        resources.erase("framebuffer");
+        return;
+    }
+
+    if (strcmp(name, "glEndList") == 0) {
+        insideNewEndList = 0;
+    }
+}
+
+void
+TraceAnalyzer::recordSideEffects(trace::Call *call)
+{
+
+    const char *name = call->name();
+
+    /* Handle display lists before any other processing. */
+
+    /* FIXME: If we encode the list of commands that are executed
+     * immediately (as opposed to those that are compiled into a
+     * display list) then we could generate a "display-list-X"
+     * resource just as we do for "texture-X" resources and only
+     * emit it in the trace if a glCallList(X) is emitted. For
+     * now, simply punt and include anything within glNewList and
+     * glEndList in the trim output. This guarantees that display
+     * lists will work, but does not trim out unused display
+     * lists. */
+    if (insideNewEndList != 0) {
+        provide("state", 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);
+        }
+
+        return;
+    }
+
+    /* If call is flagged as no side effects, then we are done here. */
+    if (call->flags & trace::CALL_FLAG_NO_SIDE_EFFECTS) {
+        return;
+    }
+
+    /* Similarly, swap-buffers calls don't have interesting side effects. */
+    if (call->flags & trace::CALL_FLAG_SWAP_RENDERTARGET &&
+        call->flags & trace::CALL_FLAG_END_FRAME) {
+        return;
+    }
+
+    if (strcmp(name, "glGenTextures") == 0) {
+        const trace::Array *textures = dynamic_cast<const trace::Array *>(&call->arg(1));
+        size_t i;
+        GLuint texture;
+
+        if (textures) {
+            for (i = 0; i < textures->size(); i++) {
+                texture = textures->values[i]->toUInt();
+                providef("texture-", texture, call->no);
+            }
+        }
+        return;
+    }
+
+    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);
+
+        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);
+
+        return;
+    }
+
+    /* FIXME: Need to handle glMultTetImage 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, "glCompressedTexSubImage") == 0 ||
+        strcmp(name, "glInvalidateTexImage") == 0 ||
+        strcmp(name, "glInvalidateTexSubImage") == 0) {
+
+        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);
+            }
+        }
+
+        return;
+    }
+
+    if (strcmp(name, "glEnable") == 0) {
+        GLenum cap;
+
+        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;
+
+            link("render-state", ss.str());
+        }
+
+        provide("state", call->no);
+        return;
+    }
+
+    if (strcmp(name, "glDisable") == 0) {
+        GLenum cap;
+
+        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;
+
+            unlink("render-state", ss.str());
+        }
+
+        provide("state", call->no);
+        return;
+    }
+
+    if (strcmp(name, "glCreateShader") == 0 ||
+        strcmp(name, "glCreateShaderObjectARB") == 0) {
+
+        GLuint shader = call->ret->toUInt();
+        providef("shader-", shader, call->no);
+        return;
+    }
+
+    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) {
+
+        GLuint shader = call->arg(0).toUInt();
+        providef("shader-", shader, call->no);
+        return;
+    }
+
+    if (strcmp(name, "glCreateProgram") == 0 ||
+        strcmp(name, "glCreateProgramObjectARB") == 0) {
+
+        GLuint program = call->ret->toUInt();
+        providef("program-", program, call->no);
+        return;
+    }
+
+    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);
+
+        return;
+    }
+
+    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;
+    }
+
+    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;
+    }
+
+    if (strcmp(name, "glGetUniformLocation") == 0 ||
+        strcmp(name, "glGetUniformLocationARB") == 0 ||
+        strcmp(name, "glGetFragDataLocation") == 0 ||
+        strcmp(name, "glGetFragDataLocationEXT") == 0 ||
+        strcmp(name, "glGetSubroutineUniformLocation") == 0 ||
+        strcmp(name, "glGetProgramResourceLocation") == 0 ||
+        strcmp(name, "glGetProgramResourceLocationIndex") == 0 ||
+        strcmp(name, "glGetVaryingLocationNV") == 0) {
+
+        GLuint program = call->arg(0).toUInt();
+
+        providef("program-", program, call->no);
+
+        return;
+    }
+
+    /* For any call that accepts 'location' as its first argument,
+     * perform a lookup in our location->program map and add a
+     * dependence on the program we find there. */
+    if (call->sig->num_args > 0 &&
+        strcmp(call->sig->arg_names[0], "location") == 0) {
+
+        providef("program-", activeProgram, call->no);
+
+        /* 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. */
+        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;
+
+            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);
+            }
+        }
+
+        return;
+    }
+
+    /* FIXME: We cut a huge swath by assuming that any unhandled
+     * call that has a first argument named "program" should not
+     * be included in the trimmed output unless the program of
+     * that number is also included.
+     *
+     * This heuristic is correct for many cases, but we should
+     * actually carefully verify if this includes some calls
+     * inappropriately, or if it misses some.
+     */
+    if (strcmp(name, "glLinkProgram") == 0 ||
+        strcmp(name, "glLinkProgramARB") == 0 ||
+        (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);
+        return;
+    }
+
+    /* 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) {
+
+        std::set<unsigned> calls;
+        std::set<unsigned>::iterator c;
+
+        provide("framebuffer", call->no);
+
+        calls = resolve("render-state");
+
+        for (c = calls.begin(); c != calls.end(); c++) {
+            provide("framebuffer", *c);
+        }
+
+        /* 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);
+            }
+        }
+
+        return;
+    }
+
+    /* By default, assume this call affects the state somehow. */
+    resources["state"].insert(call->no);
+}
+
+void
+TraceAnalyzer::requireDependencies(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) {
+        consume("framebuffer");
+    }
+
+    /* By default, just assume this call depends on generic state. */
+    consume("state");
+}
+
+TraceAnalyzer::TraceAnalyzer(): transformFeedbackActive(false),
+                               framebufferObjectActive(false),
+                               insideBeginEnd(false),
+                               insideNewEndList(0),
+                               activeTextureUnit(GL_TEXTURE0)
+{
+    /* Nothing needed. */
+}
+
+TraceAnalyzer::~TraceAnalyzer()
+{
+    /* Nothing needed. */
+}
+
+/* Analyze this call by tracking state and recording all the
+ * resources provided by this call as side effects.. */
+void
+TraceAnalyzer::analyze(trace::Call *call)
+{
+
+    stateTrackPreCall(call);
+
+    recordSideEffects(call);
+
+    stateTrackPostCall(call);
+}
+
+/* Require this call and all of its dependencies to be included in
+ * the final trace. */
+void
+TraceAnalyzer::require(trace::Call *call)
+{
+
+    /* First, find and insert all calls that this call depends on. */
+    requireDependencies(call);
+
+    /* Then insert this call itself. */
+    required.insert(call->no);
+}
+
+/* Return a set of all the required calls, (both those calls added
+ * explicitly with require() and those implicitly depended
+ * upon. */
+std::set<unsigned>  *
+TraceAnalyzer::get_required(void)
+{
+    return &required;
+}
diff --git a/cli/trace_analyzer.hpp b/cli/trace_analyzer.hpp
new file mode 100644
index 00000000..6619c573
--- /dev/null
+++ b/cli/trace_analyzer.hpp
@@ -0,0 +1,86 @@
+/**************************************************************************
+ * Copyright 2012 Intel corporation
+ *
+ * All Rights Reserved.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ *
+ **************************************************************************/
+
+#include <set>
+
+#include <GL/gl.h>
+#include <GL/glext.h>
+
+#include "trace_callset.hpp"
+#include "trace_parser.hpp"
+
+class TraceAnalyzer {
+private:
+    std::map<std::string, std::set<unsigned> > resources;
+    std::map<std::string, std::set<std::string> > dependencies;
+
+    std::map<GLenum, unsigned> texture_map;
+
+    std::set<unsigned> required;
+
+    bool transformFeedbackActive;
+    bool framebufferObjectActive;
+    bool insideBeginEnd;
+    GLuint insideNewEndList;
+    GLenum activeTextureUnit;
+    GLuint activeProgram;
+
+    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);
+
+    void unlink(std::string resource, std::string dependency);
+    void unlinkf(std::string resource, std::string dependency, int dep_no);
+    void unlinkAll(std::string resource);
+
+    void stateTrackPreCall(trace::Call *call);
+    void recordSideEffects(trace::Call *call);
+    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();
+    ~TraceAnalyzer();
+
+    /* Analyze this call by tracking state and recording all the
+     * resources provided by this call as side effects.. */
+    void analyze(trace::Call *call);
+
+    /* Require this call and all of its dependencies to be included in
+     * the final trace. */
+    void require(trace::Call *call);
+
+    /* Return a set of all the required calls, (both those calls added
+     * explicitly with require() and those implicitly depended
+     * upon. */
+    std::set<unsigned> *get_required(void);
+};