{"action":"created","comment":{"url":"https://api.github.com/repos/halide/Halide/pulls/comments/88760524","pull_request_review_id":9327906,"id":88760524,"diff_hunk":"@@ -0,0 +1,523 @@\n+#include \"BalanceExpressionTrees.h\"\n+#include \"IRMutator.h\"\n+#include \"IREquality.h\"\n+#include \"Scope.h\"\n+#include <algorithm>\n+namespace Halide {\n+namespace Internal {\n+\n+using std::vector;\n+\n+namespace {\n+\n+typedef std::pair<Expr, int> RootWeightPair;\n+typedef std::map<Expr, int, IRDeepCompare> WeightedRoots;\n+class ExprHeights : public IRVisitor {\n+    using IRVisitor::visit;\n+    std::map<Expr, int, IRDeepCompare> m;\n+    Scope<int> var_heights;\n+public:\n+    // ExprHeights(Scope<int> var_heights) : var_heights(var_heights) {}\n+    void clear() { m.clear(); }\n+    void push(const std::string &name, int ht) {\n+        var_heights.push(name, ht);\n+    }\n+    void pop(const std::string &name) {\n+        var_heights.pop(name);\n+    }\n+    void push(Expr e) {\n+        internal_assert(e.type().is_vector()) << \"We are interested in the heights of only vector types\\n\";\n+        auto it = m.find(e);\n+        internal_assert(it == m.end())\n+            << \"Trying to push an expr that already exists in ExprHeights. Use the update method to update\\n\";\n+\n+        e.accept(this);\n+        return;\n+    }\n+    void push(Expr e, int h) {\n+        internal_assert(e.type().is_vector()) << \"We are interested in the heights of only vector types\\n\";\n+        m[e] = h;\n+        return;\n+    }\n+    void update_height(Expr e, int h) {\n+        push(e, h);\n+        return;\n+    }\n+    void erase(Expr e) {\n+        auto it = m.find(e);\n+        if (it != m.end()) {\n+            m.erase(it);\n+        }\n+    }\n+    int height(Expr e) {\n+        const Variable *var = e.as<Variable>();\n+        if (var) {\n+            internal_assert(var_heights.contains(var->name)) << \"Height of variable \" << var->name << \" not found in scope\\n\";\n+            return var_heights.get(var->name);\n+        }\n+        auto it = m.find(e);\n+        if (it != m.end()) {\n+            return it->second;\n+        } else {\n+            e.accept(this);\n+            return m[e];\n+        }\n+    }\n+    vector<int> height(const vector<Expr> &exprs) {\n+        vector<int> heights;\n+        for (Expr e: exprs) {\n+            if (e.type().is_vector()) {\n+                heights.push_back(height(e));\n+            }\n+        }\n+        return heights;\n+    }\n+    void set_containing_scope(const Scope<int> *s) {\n+        var_heights.set_containing_scope(s);\n+    }\n+    Scope<int> *get_var_heights() {\n+        return &var_heights;\n+    }\n+    template<typename T>\n+    void visit_binary(const T *op) {\n+        if (op->type.is_vector()) {\n+            IRVisitor::visit(op);\n+            m[op] = std::max(height(op->a), height(op->b)) + 1;\n+        }\n+    }\n+    template<typename T>\n+    void visit_leaf(const T *op) {\n+        if (op->type.is_vector()) {\n+            m[op] = 0;\n+        }\n+    }\n+    void visit(const Add *op) { visit_binary<Add>(op); }\n+    void visit(const Sub *op) { visit_binary<Sub>(op); }\n+    void visit(const Mul *op) { visit_binary<Mul>(op); }\n+    void visit(const Div *op) { visit_binary<Div>(op); }\n+    void visit(const Mod *op) { visit_binary<Mod>(op); }\n+    void visit(const Min *op) { visit_binary<Min>(op); }\n+    void visit(const Max *op) { visit_binary<Max>(op); }\n+    void visit(const EQ *op) { visit_binary<EQ>(op); }\n+    void visit(const NE *op) { visit_binary<NE>(op); }\n+    void visit(const LT *op) { visit_binary<LT>(op); }\n+    void visit(const LE *op) { visit_binary<LE>(op); }\n+    void visit(const GT *op) { visit_binary<GT>(op); }\n+    void visit(const GE *op) { visit_binary<GE>(op); }\n+    void visit(const And *op) { visit_binary<And>(op); }\n+    void visit(const Or *op) { visit_binary<Or>(op); }\n+\n+    void visit(const Load *op) { visit_leaf<Load>(op); }\n+    void visit(const IntImm *op) { visit_leaf<IntImm>(op); }\n+    void visit(const UIntImm *op) { visit_leaf<UIntImm>(op); }\n+    void visit(const FloatImm *op) { visit_leaf<FloatImm>(op); }\n+    void visit(const Ramp *op) { visit_leaf<Ramp>(op); }\n+    void visit(const Broadcast *op) { visit_leaf<Broadcast>(op); }\n+\n+    template <typename T>\n+    void visit_let(const T *op) {\n+        if (op->value.type().is_vector()) {\n+            Expr value = op->value;\n+            // First calculate the height of value.\n+            value.accept(this);\n+            int ht = height(value);\n+            m[value] = ht;\n+            var_heights.push(op->name, ht);\n+            op->body.accept(this);\n+            var_heights.pop(op->name);\n+        }\n+    }\n+\n+    void visit(const Let *op) { visit_let<Let>(op); }\n+    void visit(const LetStmt *op) { visit_let<LetStmt>(op); }\n+\n+    void visit(const Cast *op) {\n+        if (op->type.is_vector()) {\n+            IRVisitor::visit(op);\n+            // A number of HVX operations fold widening and narrowing\n+            // into themselves. e.g. widening adds. So count the cast\n+            // as adding no height.\n+            m[op] = height(op->value);\n+        }\n+    }\n+\n+    void visit(const Call *op) {\n+        if (op->type.is_vector()) {\n+            // ht(slice_vector(concat_vectors(x, ..)) = ht(concat_vectors(x, ...))\n+            if (op->is_intrinsic(Call::slice_vector)) {\n+                const Call *concat_v = op->args[0].as<Call>();\n+                if (concat_v && concat_v->is_intrinsic(Call::concat_vectors)) {\n+                    int ht = height(op->args[0]);\n+                    m[op] = ht;\n+                }\n+            }\n+            IRVisitor::visit(op);\n+            vector<int> heights = height(op->args);\n+            m[op] = *std::max_element(heights.begin(), heights.end());\n+        }\n+    }\n+\n+};\n+\n+class FindRoots : public IRVisitor {\n+    using IRVisitor::visit;\n+\n+    bool is_associative_or_cummutative(Expr a) {","path":"src/BalanceExpressionTrees.cpp","position":165,"original_position":165,"commit_id":"6ffd0454d4ec9d5cd13101d910907896d258cfa3","original_commit_id":"6ffd0454d4ec9d5cd13101d910907896d258cfa3","user":{"login":"steven-johnson","id":328955,"avatar_url":"https://avatars.githubusercontent.com/u/328955?v=3","gravatar_id":"","url":"https://api.github.com/users/steven-johnson","html_url":"https://github.com/steven-johnson","followers_url":"https://api.github.com/users/steven-johnson/followers","following_url":"https://api.github.com/users/steven-johnson/following{/other_user}","gists_url":"https://api.github.com/users/steven-johnson/gists{/gist_id}","starred_url":"https://api.github.com/users/steven-johnson/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/steven-johnson/subscriptions","organizations_url":"https://api.github.com/users/steven-johnson/orgs","repos_url":"https://api.github.com/users/steven-johnson/repos","events_url":"https://api.github.com/users/steven-johnson/events{/privacy}","received_events_url":"https://api.github.com/users/steven-johnson/received_events","type":"User","site_admin":false},"body":"Spelling: \"commutative\"","created_at":"2016-11-18T23:40:48Z","updated_at":"2016-11-18T23:40:48Z","html_url":"https://github.com/halide/Halide/pull/1627#discussion_r88760524","pull_request_url":"https://api.github.com/repos/halide/Halide/pulls/1627","_links":{"self":{"href":"https://api.github.com/repos/halide/Halide/pulls/comments/88760524"},"html":{"href":"https://github.com/halide/Halide/pull/1627#discussion_r88760524"},"pull_request":{"href":"https://api.github.com/repos/halide/Halide/pulls/1627"}}},"pull_request":{"url":"https://api.github.com/repos/halide/Halide/pulls/1627","id":93857602,"html_url":"https://github.com/halide/Halide/pull/1627","diff_url":"https://github.com/halide/Halide/pull/1627.diff","patch_url":"https://github.com/halide/Halide/pull/1627.patch","issue_url":"https://api.github.com/repos/halide/Halide/issues/1627","number":1627,"state":"open","locked":false,"title":"Expression Tree Balancing","user":{"login":"pranavb-ca","id":16598810,"avatar_url":"https://avatars.githubusercontent.com/u/16598810?v=3","gravatar_id":"","url":"https://api.github.com/users/pranavb-ca","html_url":"https://github.com/pranavb-ca","followers_url":"https://api.github.com/users/pranavb-ca/followers","following_url":"https://api.github.com/users/pranavb-ca/following{/other_user}","gists_url":"https://api.github.com/users/pranavb-ca/gists{/gist_id}","starred_url":"https://api.github.com/users/pranavb-ca/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/pranavb-ca/subscriptions","organizations_url":"https://api.github.com/users/pranavb-ca/orgs","repos_url":"https://api.github.com/users/pranavb-ca/repos","events_url":"https://api.github.com/users/pranavb-ca/events{/privacy}","received_events_url":"https://api.github.com/users/pranavb-ca/received_events","type":"User","site_admin":false},"body":"This patch adds a pass to balance expression trees.\r\n\r\nWe use this pass just before code generation for HVX. I am putting this\r\nin a file of its own so that it can be used for other targets that\r\nmay find this useful.\r\n\r\n@dsharletg, @ronlieb, @dpalermo : PTAL.","created_at":"2016-11-15T22:02:40Z","updated_at":"2016-11-18T23:40:48Z","closed_at":null,"merged_at":null,"merge_commit_sha":"20980d67cc93c12f7374e7f6cb312e29b96dd534","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/halide/Halide/pulls/1627/commits","review_comments_url":"https://api.github.com/repos/halide/Halide/pulls/1627/comments","review_comment_url":"https://api.github.com/repos/halide/Halide/pulls/comments{/number}","comments_url":"https://api.github.com/repos/halide/Halide/issues/1627/comments","statuses_url":"https://api.github.com/repos/halide/Halide/statuses/6ffd0454d4ec9d5cd13101d910907896d258cfa3","head":{"label":"halide:balance_expressions","ref":"balance_expressions","sha":"6ffd0454d4ec9d5cd13101d910907896d258cfa3","user":{"login":"halide","id":1548551,"avatar_url":"https://avatars.githubusercontent.com/u/1548551?v=3","gravatar_id":"","url":"https://api.github.com/users/halide","html_url":"https://github.com/halide","followers_url":"https://api.github.com/users/halide/followers","following_url":"https://api.github.com/users/halide/following{/other_user}","gists_url":"https://api.github.com/users/halide/gists{/gist_id}","starred_url":"https://api.github.com/users/halide/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/halide/subscriptions","organizations_url":"https://api.github.com/users/halide/orgs","repos_url":"https://api.github.com/users/halide/repos","events_url":"https://api.github.com/users/halide/events{/privacy}","received_events_url":"https://api.github.com/users/halide/received_events","type":"Organization","site_admin":false},"repo":{"id":5241312,"name":"Halide","full_name":"halide/Halide","owner":{"login":"halide","id":1548551,"avatar_url":"https://avatars.githubusercontent.com/u/1548551?v=3","gravatar_id":"","url":"https://api.github.com/users/halide","html_url":"https://github.com/halide","followers_url":"https://api.github.com/users/halide/followers","following_url":"https://api.github.com/users/halide/following{/other_user}","gists_url":"https://api.github.com/users/halide/gists{/gist_id}","starred_url":"https://api.github.com/users/halide/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/halide/subscriptions","organizations_url":"https://api.github.com/users/halide/orgs","repos_url":"https://api.github.com/users/halide/repos","events_url":"https://api.github.com/users/halide/events{/privacy}","received_events_url":"https://api.github.com/users/halide/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/halide/Halide","description":"a language for image processing and computational photography","fork":false,"url":"https://api.github.com/repos/halide/Halide","forks_url":"https://api.github.com/repos/halide/Halide/forks","keys_url":"https://api.github.com/repos/halide/Halide/keys{/key_id}","collaborators_url":"https://api.github.com/repos/halide/Halide/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/halide/Halide/teams","hooks_url":"https://api.github.com/repos/halide/Halide/hooks","issue_events_url":"https://api.github.com/repos/halide/Halide/issues/events{/number}","events_url":"https://api.github.com/repos/halide/Halide/events","assignees_url":"https://api.github.com/repos/halide/Halide/assignees{/user}","branches_url":"https://api.github.com/repos/halide/Halide/branches{/branch}","tags_url":"https://api.github.com/repos/halide/Halide/tags","blobs_url":"https://api.github.com/repos/halide/Halide/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/halide/Halide/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/halide/Halide/git/refs{/sha}","trees_url":"https://api.github.com/repos/halide/Halide/git/trees{/sha}","statuses_url":"https://api.github.com/repos/halide/Halide/statuses/{sha}","languages_url":"https://api.github.com/repos/halide/Halide/languages","stargazers_url":"https://api.github.com/repos/halide/Halide/stargazers","contributors_url":"https://api.github.com/repos/halide/Halide/contributors","subscribers_url":"https://api.github.com/repos/halide/Halide/subscribers","subscription_url":"https://api.github.com/repos/halide/Halide/subscription","commits_url":"https://api.github.com/repos/halide/Halide/commits{/sha}","git_commits_url":"https://api.github.com/repos/halide/Halide/git/commits{/sha}","comments_url":"https://api.github.com/repos/halide/Halide/comments{/number}","issue_comment_url":"https://api.github.com/repos/halide/Halide/issues/comments{/number}","contents_url":"https://api.github.com/repos/halide/Halide/contents/{+path}","compare_url":"https://api.github.com/repos/halide/Halide/compare/{base}...{head}","merges_url":"https://api.github.com/repos/halide/Halide/merges","archive_url":"https://api.github.com/repos/halide/Halide/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/halide/Halide/downloads","issues_url":"https://api.github.com/repos/halide/Halide/issues{/number}","pulls_url":"https://api.github.com/repos/halide/Halide/pulls{/number}","milestones_url":"https://api.github.com/repos/halide/Halide/milestones{/number}","notifications_url":"https://api.github.com/repos/halide/Halide/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/halide/Halide/labels{/name}","releases_url":"https://api.github.com/repos/halide/Halide/releases{/id}","deployments_url":"https://api.github.com/repos/halide/Halide/deployments","created_at":"2012-07-31T04:05:25Z","updated_at":"2016-11-18T20:23:35Z","pushed_at":"2016-11-18T23:00:33Z","git_url":"git://github.com/halide/Halide.git","ssh_url":"git@github.com:halide/Halide.git","clone_url":"https://github.com/halide/Halide.git","svn_url":"https://github.com/halide/Halide","homepage":"http://halide-lang.org","size":301006,"stargazers_count":1451,"watchers_count":1451,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":299,"mirror_url":null,"open_issues_count":233,"forks":299,"open_issues":233,"watchers":1451,"default_branch":"master"}},"base":{"label":"halide:master","ref":"master","sha":"8910b79a2d0b3fb6cb164d4c85aa340cbe57484e","user":{"login":"halide","id":1548551,"avatar_url":"https://avatars.githubusercontent.com/u/1548551?v=3","gravatar_id":"","url":"https://api.github.com/users/halide","html_url":"https://github.com/halide","followers_url":"https://api.github.com/users/halide/followers","following_url":"https://api.github.com/users/halide/following{/other_user}","gists_url":"https://api.github.com/users/halide/gists{/gist_id}","starred_url":"https://api.github.com/users/halide/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/halide/subscriptions","organizations_url":"https://api.github.com/users/halide/orgs","repos_url":"https://api.github.com/users/halide/repos","events_url":"https://api.github.com/users/halide/events{/privacy}","received_events_url":"https://api.github.com/users/halide/received_events","type":"Organization","site_admin":false},"repo":{"id":5241312,"name":"Halide","full_name":"halide/Halide","owner":{"login":"halide","id":1548551,"avatar_url":"https://avatars.githubusercontent.com/u/1548551?v=3","gravatar_id":"","url":"https://api.github.com/users/halide","html_url":"https://github.com/halide","followers_url":"https://api.github.com/users/halide/followers","following_url":"https://api.github.com/users/halide/following{/other_user}","gists_url":"https://api.github.com/users/halide/gists{/gist_id}","starred_url":"https://api.github.com/users/halide/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/halide/subscriptions","organizations_url":"https://api.github.com/users/halide/orgs","repos_url":"https://api.github.com/users/halide/repos","events_url":"https://api.github.com/users/halide/events{/privacy}","received_events_url":"https://api.github.com/users/halide/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/halide/Halide","description":"a language for image processing and computational photography","fork":false,"url":"https://api.github.com/repos/halide/Halide","forks_url":"https://api.github.com/repos/halide/Halide/forks","keys_url":"https://api.github.com/repos/halide/Halide/keys{/key_id}","collaborators_url":"https://api.github.com/repos/halide/Halide/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/halide/Halide/teams","hooks_url":"https://api.github.com/repos/halide/Halide/hooks","issue_events_url":"https://api.github.com/repos/halide/Halide/issues/events{/number}","events_url":"https://api.github.com/repos/halide/Halide/events","assignees_url":"https://api.github.com/repos/halide/Halide/assignees{/user}","branches_url":"https://api.github.com/repos/halide/Halide/branches{/branch}","tags_url":"https://api.github.com/repos/halide/Halide/tags","blobs_url":"https://api.github.com/repos/halide/Halide/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/halide/Halide/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/halide/Halide/git/refs{/sha}","trees_url":"https://api.github.com/repos/halide/Halide/git/trees{/sha}","statuses_url":"https://api.github.com/repos/halide/Halide/statuses/{sha}","languages_url":"https://api.github.com/repos/halide/Halide/languages","stargazers_url":"https://api.github.com/repos/halide/Halide/stargazers","contributors_url":"https://api.github.com/repos/halide/Halide/contributors","subscribers_url":"https://api.github.com/repos/halide/Halide/subscribers","subscription_url":"https://api.github.com/repos/halide/Halide/subscription","commits_url":"https://api.github.com/repos/halide/Halide/commits{/sha}","git_commits_url":"https://api.github.com/repos/halide/Halide/git/commits{/sha}","comments_url":"https://api.github.com/repos/halide/Halide/comments{/number}","issue_comment_url":"https://api.github.com/repos/halide/Halide/issues/comments{/number}","contents_url":"https://api.github.com/repos/halide/Halide/contents/{+path}","compare_url":"https://api.github.com/repos/halide/Halide/compare/{base}...{head}","merges_url":"https://api.github.com/repos/halide/Halide/merges","archive_url":"https://api.github.com/repos/halide/Halide/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/halide/Halide/downloads","issues_url":"https://api.github.com/repos/halide/Halide/issues{/number}","pulls_url":"https://api.github.com/repos/halide/Halide/pulls{/number}","milestones_url":"https://api.github.com/repos/halide/Halide/milestones{/number}","notifications_url":"https://api.github.com/repos/halide/Halide/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/halide/Halide/labels{/name}","releases_url":"https://api.github.com/repos/halide/Halide/releases{/id}","deployments_url":"https://api.github.com/repos/halide/Halide/deployments","created_at":"2012-07-31T04:05:25Z","updated_at":"2016-11-18T20:23:35Z","pushed_at":"2016-11-18T23:00:33Z","git_url":"git://github.com/halide/Halide.git","ssh_url":"git@github.com:halide/Halide.git","clone_url":"https://github.com/halide/Halide.git","svn_url":"https://github.com/halide/Halide","homepage":"http://halide-lang.org","size":301006,"stargazers_count":1451,"watchers_count":1451,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":299,"mirror_url":null,"open_issues_count":233,"forks":299,"open_issues":233,"watchers":1451,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/halide/Halide/pulls/1627"},"html":{"href":"https://github.com/halide/Halide/pull/1627"},"issue":{"href":"https://api.github.com/repos/halide/Halide/issues/1627"},"comments":{"href":"https://api.github.com/repos/halide/Halide/issues/1627/comments"},"review_comments":{"href":"https://api.github.com/repos/halide/Halide/pulls/1627/comments"},"review_comment":{"href":"https://api.github.com/repos/halide/Halide/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/halide/Halide/pulls/1627/commits"},"statuses":{"href":"https://api.github.com/repos/halide/Halide/statuses/6ffd0454d4ec9d5cd13101d910907896d258cfa3"}}}}
{"actor":{"display_login":"steven-johnson"}}