{"action":"created","comment":{"url":"https://api.github.com/repos/MiniJavaInScala/mjis/pulls/comments/23120165","id":23120165,"diff_hunk":"@@ -0,0 +1,99 @@\n+package mjis\n+\n+import mjis.asm._\n+\n+import scala.collection.mutable\n+\n+/** Creates Mov instructions for the contents of block.phi. */\n+class PhiCodeGenerator(block: AsmBasicBlock) {\n+  // A phi permutation interpreted as a graph looks as follows: Each node has indegree <= 1\n+  // (because each register is written to at most once) and arbitrary outdegree.\n+  // Each of the connected subgraphs is thus either acyclic (and therefore a tree) or contains\n+  // exactly one cycle (else there would be a node with indegree >= 2).\n+  // Each of the nodes in the cycle can optionally be the root of a tree.\n+\n+  // Inverse of the Phi map: source operand -> list of registers its value is written to\n+  private val invertedPhi: Map[Operand, mutable.Iterable[RegisterOperand]] = block.phi.groupBy(_._2).mapValues(_.map(_._1))\n+\n+  // Cycles\n+  private val cycles = mutable.Set[List[RegisterOperand]]()\n+\n+  // Roots of standalone trees\n+  private val roots = mutable.Set[Operand]()\n+\n+  private def buildCyclesAndRoots() = {\n+    val visited = mutable.Set[RegisterOperand]()\n+    block.phi.keys.foreach(buildCyclesAndRootsRec(_, Nil, visited))\n+  }\n+\n+  @annotation.tailrec\n+  private def buildCyclesAndRootsRec(reg: RegisterOperand, stack: List[RegisterOperand],\n+       visited: mutable.Set[RegisterOperand]): Unit = {\n+    if (visited(reg)) {\n+      if (stack.nonEmpty && stack.contains(reg)) {\n+        // found cycle\n+        cycles += reg :: stack.takeWhile(_ != reg)\n+      }\n+    } else {\n+      visited += reg\n+      block.phi.get(reg) match {\n+        case None =>\n+          // no predecessor -> root of a tree\n+          roots += reg\n+        case Some(r : RegisterOperand) =>\n+          buildCyclesAndRootsRec(r, reg :: stack, visited)\n+        case Some(op) =>\n+          // non-register operand -> has no predecessor -> root of a tree\n+          roots += op\n+      }\n+    }\n+  }\n+\n+  /** Writes the acyclic register permutation (= tree) starting at `rootOp`, skipping the successor\n+    * `cycleSuccessor` of `rootOp`. */\n+  private def getInstructionsForTree(rootOp: Operand, cycleSuccessor: RegisterOperand): Seq[Instruction] = {\n+    val workList = mutable.ListBuffer[RegisterOperand]()","path":"src/main/scala/mjis/PhiCodeGenerator.scala","position":55,"original_position":55,"commit_id":"d44c364eec4d389a3c70df09e403c731ab61b8cd","original_commit_id":"d44c364eec4d389a3c70df09e403c731ab61b8cd","user":{"login":"Kha","id":109126,"avatar_url":"https://avatars.githubusercontent.com/u/109126?v=3","gravatar_id":"","url":"https://api.github.com/users/Kha","html_url":"https://github.com/Kha","followers_url":"https://api.github.com/users/Kha/followers","following_url":"https://api.github.com/users/Kha/following{/other_user}","gists_url":"https://api.github.com/users/Kha/gists{/gist_id}","starred_url":"https://api.github.com/users/Kha/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/Kha/subscriptions","organizations_url":"https://api.github.com/users/Kha/orgs","repos_url":"https://api.github.com/users/Kha/repos","events_url":"https://api.github.com/users/Kha/events{/privacy}","received_events_url":"https://api.github.com/users/Kha/received_events","type":"User","site_admin":false},"body":"`Queue`?","created_at":"2015-01-17T01:01:56Z","updated_at":"2015-01-17T01:01:56Z","html_url":"https://github.com/MiniJavaInScala/mjis/pull/260#discussion_r23120165","pull_request_url":"https://api.github.com/repos/MiniJavaInScala/mjis/pulls/260","_links":{"self":{"href":"https://api.github.com/repos/MiniJavaInScala/mjis/pulls/comments/23120165"},"html":{"href":"https://github.com/MiniJavaInScala/mjis/pull/260#discussion_r23120165"},"pull_request":{"href":"https://api.github.com/repos/MiniJavaInScala/mjis/pulls/260"}}},"pull_request":{"url":"https://api.github.com/repos/MiniJavaInScala/mjis/pulls/260","id":27528964,"html_url":"https://github.com/MiniJavaInScala/mjis/pull/260","diff_url":"https://github.com/MiniJavaInScala/mjis/pull/260.diff","patch_url":"https://github.com/MiniJavaInScala/mjis/pull/260.patch","issue_url":"https://api.github.com/repos/MiniJavaInScala/mjis/issues/260","number":260,"state":"open","locked":false,"title":"Allow more complex dependency graphs in Phi generation","user":{"login":"jspam","id":496373,"avatar_url":"https://avatars.githubusercontent.com/u/496373?v=3","gravatar_id":"","url":"https://api.github.com/users/jspam","html_url":"https://github.com/jspam","followers_url":"https://api.github.com/users/jspam/followers","following_url":"https://api.github.com/users/jspam/following{/other_user}","gists_url":"https://api.github.com/users/jspam/gists{/gist_id}","starred_url":"https://api.github.com/users/jspam/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jspam/subscriptions","organizations_url":"https://api.github.com/users/jspam/orgs","repos_url":"https://api.github.com/users/jspam/repos","events_url":"https://api.github.com/users/jspam/events{/privacy}","received_events_url":"https://api.github.com/users/jspam/received_events","type":"User","site_admin":false},"body":"","created_at":"2015-01-16T19:14:53Z","updated_at":"2015-01-17T01:01:56Z","closed_at":null,"merged_at":null,"merge_commit_sha":"79321e12062850ca3686d74467fd7fcdd03e02b8","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/MiniJavaInScala/mjis/pulls/260/commits","review_comments_url":"https://api.github.com/repos/MiniJavaInScala/mjis/pulls/260/comments","review_comment_url":"https://api.github.com/repos/MiniJavaInScala/mjis/pulls/comments/{number}","comments_url":"https://api.github.com/repos/MiniJavaInScala/mjis/issues/260/comments","statuses_url":"https://api.github.com/repos/MiniJavaInScala/mjis/statuses/d44c364eec4d389a3c70df09e403c731ab61b8cd","head":{"label":"jspam:098-evil-phis","ref":"098-evil-phis","sha":"d44c364eec4d389a3c70df09e403c731ab61b8cd","user":{"login":"jspam","id":496373,"avatar_url":"https://avatars.githubusercontent.com/u/496373?v=3","gravatar_id":"","url":"https://api.github.com/users/jspam","html_url":"https://github.com/jspam","followers_url":"https://api.github.com/users/jspam/followers","following_url":"https://api.github.com/users/jspam/following{/other_user}","gists_url":"https://api.github.com/users/jspam/gists{/gist_id}","starred_url":"https://api.github.com/users/jspam/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jspam/subscriptions","organizations_url":"https://api.github.com/users/jspam/orgs","repos_url":"https://api.github.com/users/jspam/repos","events_url":"https://api.github.com/users/jspam/events{/privacy}","received_events_url":"https://api.github.com/users/jspam/received_events","type":"User","site_admin":false},"repo":{"id":25473363,"name":"mjis","full_name":"jspam/mjis","owner":{"login":"jspam","id":496373,"avatar_url":"https://avatars.githubusercontent.com/u/496373?v=3","gravatar_id":"","url":"https://api.github.com/users/jspam","html_url":"https://github.com/jspam","followers_url":"https://api.github.com/users/jspam/followers","following_url":"https://api.github.com/users/jspam/following{/other_user}","gists_url":"https://api.github.com/users/jspam/gists{/gist_id}","starred_url":"https://api.github.com/users/jspam/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jspam/subscriptions","organizations_url":"https://api.github.com/users/jspam/orgs","repos_url":"https://api.github.com/users/jspam/repos","events_url":"https://api.github.com/users/jspam/events{/privacy}","received_events_url":"https://api.github.com/users/jspam/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/jspam/mjis","description":"A compiler for MiniJava, written in Scala","fork":true,"url":"https://api.github.com/repos/jspam/mjis","forks_url":"https://api.github.com/repos/jspam/mjis/forks","keys_url":"https://api.github.com/repos/jspam/mjis/keys{/key_id}","collaborators_url":"https://api.github.com/repos/jspam/mjis/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/jspam/mjis/teams","hooks_url":"https://api.github.com/repos/jspam/mjis/hooks","issue_events_url":"https://api.github.com/repos/jspam/mjis/issues/events{/number}","events_url":"https://api.github.com/repos/jspam/mjis/events","assignees_url":"https://api.github.com/repos/jspam/mjis/assignees{/user}","branches_url":"https://api.github.com/repos/jspam/mjis/branches{/branch}","tags_url":"https://api.github.com/repos/jspam/mjis/tags","blobs_url":"https://api.github.com/repos/jspam/mjis/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/jspam/mjis/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/jspam/mjis/git/refs{/sha}","trees_url":"https://api.github.com/repos/jspam/mjis/git/trees{/sha}","statuses_url":"https://api.github.com/repos/jspam/mjis/statuses/{sha}","languages_url":"https://api.github.com/repos/jspam/mjis/languages","stargazers_url":"https://api.github.com/repos/jspam/mjis/stargazers","contributors_url":"https://api.github.com/repos/jspam/mjis/contributors","subscribers_url":"https://api.github.com/repos/jspam/mjis/subscribers","subscription_url":"https://api.github.com/repos/jspam/mjis/subscription","commits_url":"https://api.github.com/repos/jspam/mjis/commits{/sha}","git_commits_url":"https://api.github.com/repos/jspam/mjis/git/commits{/sha}","comments_url":"https://api.github.com/repos/jspam/mjis/comments{/number}","issue_comment_url":"https://api.github.com/repos/jspam/mjis/issues/comments/{number}","contents_url":"https://api.github.com/repos/jspam/mjis/contents/{+path}","compare_url":"https://api.github.com/repos/jspam/mjis/compare/{base}...{head}","merges_url":"https://api.github.com/repos/jspam/mjis/merges","archive_url":"https://api.github.com/repos/jspam/mjis/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/jspam/mjis/downloads","issues_url":"https://api.github.com/repos/jspam/mjis/issues{/number}","pulls_url":"https://api.github.com/repos/jspam/mjis/pulls{/number}","milestones_url":"https://api.github.com/repos/jspam/mjis/milestones{/number}","notifications_url":"https://api.github.com/repos/jspam/mjis/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/jspam/mjis/labels{/name}","releases_url":"https://api.github.com/repos/jspam/mjis/releases{/id}","created_at":"2014-10-20T15:40:07Z","updated_at":"2014-12-23T10:55:48Z","pushed_at":"2015-01-16T22:18:41Z","git_url":"git://github.com/jspam/mjis.git","ssh_url":"git@github.com:jspam/mjis.git","clone_url":"https://github.com/jspam/mjis.git","svn_url":"https://github.com/jspam/mjis","homepage":"https://github.com/MiniJavaInScala/mjis","size":13289,"stargazers_count":0,"watchers_count":0,"language":"Scala","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"MiniJavaInScala:master","ref":"master","sha":"41cb8ba6b09ed5706761977f4e0db6e8344690b5","user":{"login":"MiniJavaInScala","id":9319912,"avatar_url":"https://avatars.githubusercontent.com/u/9319912?v=3","gravatar_id":"","url":"https://api.github.com/users/MiniJavaInScala","html_url":"https://github.com/MiniJavaInScala","followers_url":"https://api.github.com/users/MiniJavaInScala/followers","following_url":"https://api.github.com/users/MiniJavaInScala/following{/other_user}","gists_url":"https://api.github.com/users/MiniJavaInScala/gists{/gist_id}","starred_url":"https://api.github.com/users/MiniJavaInScala/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MiniJavaInScala/subscriptions","organizations_url":"https://api.github.com/users/MiniJavaInScala/orgs","repos_url":"https://api.github.com/users/MiniJavaInScala/repos","events_url":"https://api.github.com/users/MiniJavaInScala/events{/privacy}","received_events_url":"https://api.github.com/users/MiniJavaInScala/received_events","type":"Organization","site_admin":false},"repo":{"id":25466807,"name":"mjis","full_name":"MiniJavaInScala/mjis","owner":{"login":"MiniJavaInScala","id":9319912,"avatar_url":"https://avatars.githubusercontent.com/u/9319912?v=3","gravatar_id":"","url":"https://api.github.com/users/MiniJavaInScala","html_url":"https://github.com/MiniJavaInScala","followers_url":"https://api.github.com/users/MiniJavaInScala/followers","following_url":"https://api.github.com/users/MiniJavaInScala/following{/other_user}","gists_url":"https://api.github.com/users/MiniJavaInScala/gists{/gist_id}","starred_url":"https://api.github.com/users/MiniJavaInScala/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MiniJavaInScala/subscriptions","organizations_url":"https://api.github.com/users/MiniJavaInScala/orgs","repos_url":"https://api.github.com/users/MiniJavaInScala/repos","events_url":"https://api.github.com/users/MiniJavaInScala/events{/privacy}","received_events_url":"https://api.github.com/users/MiniJavaInScala/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/MiniJavaInScala/mjis","description":"A compiler for MiniJava, written in Scala","fork":false,"url":"https://api.github.com/repos/MiniJavaInScala/mjis","forks_url":"https://api.github.com/repos/MiniJavaInScala/mjis/forks","keys_url":"https://api.github.com/repos/MiniJavaInScala/mjis/keys{/key_id}","collaborators_url":"https://api.github.com/repos/MiniJavaInScala/mjis/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/MiniJavaInScala/mjis/teams","hooks_url":"https://api.github.com/repos/MiniJavaInScala/mjis/hooks","issue_events_url":"https://api.github.com/repos/MiniJavaInScala/mjis/issues/events{/number}","events_url":"https://api.github.com/repos/MiniJavaInScala/mjis/events","assignees_url":"https://api.github.com/repos/MiniJavaInScala/mjis/assignees{/user}","branches_url":"https://api.github.com/repos/MiniJavaInScala/mjis/branches{/branch}","tags_url":"https://api.github.com/repos/MiniJavaInScala/mjis/tags","blobs_url":"https://api.github.com/repos/MiniJavaInScala/mjis/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/MiniJavaInScala/mjis/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/MiniJavaInScala/mjis/git/refs{/sha}","trees_url":"https://api.github.com/repos/MiniJavaInScala/mjis/git/trees{/sha}","statuses_url":"https://api.github.com/repos/MiniJavaInScala/mjis/statuses/{sha}","languages_url":"https://api.github.com/repos/MiniJavaInScala/mjis/languages","stargazers_url":"https://api.github.com/repos/MiniJavaInScala/mjis/stargazers","contributors_url":"https://api.github.com/repos/MiniJavaInScala/mjis/contributors","subscribers_url":"https://api.github.com/repos/MiniJavaInScala/mjis/subscribers","subscription_url":"https://api.github.com/repos/MiniJavaInScala/mjis/subscription","commits_url":"https://api.github.com/repos/MiniJavaInScala/mjis/commits{/sha}","git_commits_url":"https://api.github.com/repos/MiniJavaInScala/mjis/git/commits{/sha}","comments_url":"https://api.github.com/repos/MiniJavaInScala/mjis/comments{/number}","issue_comment_url":"https://api.github.com/repos/MiniJavaInScala/mjis/issues/comments/{number}","contents_url":"https://api.github.com/repos/MiniJavaInScala/mjis/contents/{+path}","compare_url":"https://api.github.com/repos/MiniJavaInScala/mjis/compare/{base}...{head}","merges_url":"https://api.github.com/repos/MiniJavaInScala/mjis/merges","archive_url":"https://api.github.com/repos/MiniJavaInScala/mjis/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/MiniJavaInScala/mjis/downloads","issues_url":"https://api.github.com/repos/MiniJavaInScala/mjis/issues{/number}","pulls_url":"https://api.github.com/repos/MiniJavaInScala/mjis/pulls{/number}","milestones_url":"https://api.github.com/repos/MiniJavaInScala/mjis/milestones{/number}","notifications_url":"https://api.github.com/repos/MiniJavaInScala/mjis/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/MiniJavaInScala/mjis/labels{/name}","releases_url":"https://api.github.com/repos/MiniJavaInScala/mjis/releases{/id}","created_at":"2014-10-20T13:08:36Z","updated_at":"2015-01-14T23:38:47Z","pushed_at":"2015-01-14T23:38:47Z","git_url":"git://github.com/MiniJavaInScala/mjis.git","ssh_url":"git@github.com:MiniJavaInScala/mjis.git","clone_url":"https://github.com/MiniJavaInScala/mjis.git","svn_url":"https://github.com/MiniJavaInScala/mjis","homepage":"https://github.com/MiniJavaInScala/mjis","size":13905,"stargazers_count":3,"watchers_count":3,"language":"Scala","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":5,"mirror_url":null,"open_issues_count":12,"forks":5,"open_issues":12,"watchers":3,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/MiniJavaInScala/mjis/pulls/260"},"html":{"href":"https://github.com/MiniJavaInScala/mjis/pull/260"},"issue":{"href":"https://api.github.com/repos/MiniJavaInScala/mjis/issues/260"},"comments":{"href":"https://api.github.com/repos/MiniJavaInScala/mjis/issues/260/comments"},"review_comments":{"href":"https://api.github.com/repos/MiniJavaInScala/mjis/pulls/260/comments"},"review_comment":{"href":"https://api.github.com/repos/MiniJavaInScala/mjis/pulls/comments/{number}"},"commits":{"href":"https://api.github.com/repos/MiniJavaInScala/mjis/pulls/260/commits"},"statuses":{"href":"https://api.github.com/repos/MiniJavaInScala/mjis/statuses/d44c364eec4d389a3c70df09e403c731ab61b8cd"}}}}