rho-devel · ArunChauhan · Jun 10, 2016 · Jun 11, 2016
diff --git a/src/include/rho/jit/Optimization.hpp b/src/include/rho/jit/Optimization.hpp
@@ -26,6 +26,8 @@
 
 #include "rho/jit/llvm.hpp"
 
+#include "llvm/Analysis/PostDominators.h"
+
 namespace rho {
 namespace JIT {
 
@@ -67,9 +69,20 @@ class RemoveRedundantCallsToSetVisibility : public llvm::BasicBlockPass {
       RemoveRedundantCallsToSetVisibility&& other) = default;
   ~RemoveRedundantCallsToSetVisibility() = default;
 
-  // Eliminates redundant calls to rho_runtime_setVisibility.  Any call that is
-  // postdominated by another is redundant.
-  bool runOnBasicBlock(llvm::BasicBlock& basic_block) override;
+  // Eliminates redundant calls to kSetVisibilityFuncName and returns true if
+  // basic_block was changed.
+  bool runOnBasicBlock(llvm::BasicBlock& basic_block) override {
+    return RemoveRedundantCalls(basic_block) > 1;
+  }
+
+  // Eliminates redundant calls to kSetVisibilityFuncName.  Any call that is
+  // postdominated by another is redundant, thus all except the last one are
+  // removed.  Returns the total number of calls (not just redundant ones) found
+  // in the basic_block.  The returned value is useful in determining if the
+  // basic blocks post-dominated by basic_block should be cleared of all the
+  // calls to kSetVisibilityFuncName.  If keep_one is false then it removes all
+  // the calls, including the last one.
+  int RemoveRedundantCalls(llvm::BasicBlock& basic_block, bool keep_one = true);
 
  private:
   static char pass_id;  // LLVM uses the address of this variable as the ID.

diff --git a/src/main/jit/Optimization.cpp b/src/main/jit/Optimization.cpp
@@ -23,27 +23,63 @@
 
 #include "rho/jit/Optimization.hpp"
 
+#include <deque>
+#include <set>
 #include <string>
+#include <tuple>
 #include <vector>
 
 #include "rho/jit/llvm.hpp"
 
 namespace rho {
 namespace JIT {
 namespace {
-const std::string kSetVisibilityFuncName("rho_runtime_setVisibility");
+inline bool IsSetVisibilityFunction(const llvm::CallInst* call_instr) {
+  return call_instr->getCalledFunction()->getName() ==
+         "rho_runtime_setVisibility";
+}
 }  // namespace
 
 //------------------------------------------------------------------------------
 // Implementation of BasicFunctionPass.
 
 bool BasicFunctionPass::runOnFunction(llvm::Function& function) {
+  using TreeNode = llvm::DomTreeNodeBase<llvm::BasicBlock>;
+  using QEntry = std::pair<TreeNode*, bool>;
+  using NodeQ = std::deque<QEntry>;
+
+  llvm::PostDominatorTree post_domtree;
+  post_domtree.runOnFunction(function);
+  std::set<llvm::BasicBlock*> covered_blocks;
   RemoveRedundantCallsToSetVisibility optimize_set_visibility;
-  bool changed = false;
+  NodeQ nodes;
+  for (const auto root : post_domtree.DT->getRoots()) {
+    nodes.push_back(QEntry(post_domtree.DT->getNode(root),
+                           /* keep_one= */ true));
+  }
+
+  // Traverse the postdom tree to remove all post-dominated calls.
+  while (!nodes.empty()) {
+    TreeNode* node;
+    bool keep_one;
+    std::tie(node, keep_one) = nodes.front();
+    covered_blocks.insert(node->getBlock());
+    nodes.pop_front();
+    bool keep_one_in_children = optimize_set_visibility.RemoveRedundantCalls(
+                                    *node->getBlock(), keep_one) == 0 &&
+                                keep_one;
+    for (auto child : node->getChildren()) {
+      nodes.push_back(QEntry(child, keep_one_in_children));
+    }
+  }
+
+  // Remove reundancies in any remaining basic blocks, not in the postdom tree.
+  bool changed = covered_blocks.size() > 0;
C06D
   for (auto& block : function.getBasicBlockList()) {
-    bool block_changed = optimize_set_visibility.runOnBasicBlock(block);
-    changed = changed || block_changed;
+    if (covered_blocks.find(&block) != covered_blocks.end()) continue;
+    changed = optimize_set_visibility.runOnBasicBlock(block) || changed;
   }
+
   return changed;
 }
 
@@ -53,27 +89,23 @@ char BasicFunctionPass::pass_id = 0;
 //------------------------------------------------------------------------------
 // Impelementation of RemoveRedundantCallsToSetVisibility.
 
-bool RemoveRedundantCallsToSetVisibility::runOnBasicBlock(
-    llvm::BasicBlock& block) {
-  // Collect all calls to kSetVisibilityFuncName.
-  std::vector<llvm::CallInst*> calls_to_delete;  // Pointed insts not owned.
-  for (llvm::Instruction& instr : block) {
-    llvm::CallInst* call_inst = llvm::dyn_cast<llvm::CallInst>(&instr);
-    if (call_inst != nullptr &&
-        call_inst->getCalledFunction()->getName() == kSetVisibilityFuncName) {
-      calls_to_delete.emplace_back(call_inst);
-    }
-  }
-  // Finally, remove all calls, except the last one.
-  if (calls_to_delete.size() > 1) {
-    calls_to_delete.pop_back();
-    for (llvm::CallInst* call_to_delete : calls_to_delete) {
-      call_to_delete->eraseFromParent();
+int RemoveRedundantCallsToSetVisibility::RemoveRedundantCalls(
+    llvm::BasicBlock& block, bool keep_one) {
+  int count = 0;
+  auto iter = block.rbegin();
+  while (iter != block.rend()) {
+    llvm::CallInst* call_inst = llvm::dyn_cast<llvm::CallInst>(&*iter);
+    if (call_inst != nullptr && IsSetVisibilityFunction(call_inst)) {
+      ++count;
+      if (!keep_one) {
+        iter->removeFromParent();
+        continue;
+      }
+      keep_one = false;  // Don't skip any call henceforth.
     }
-    return true;
-  } else {
-    return false;
+    ++iter;
   }
+  return count;
 }
 
 // LLVM uses the address of the following variable, the value is unimportant.