From d1643e41ef242ae656f667bf3c8b0324635cefd3 Mon Sep 17 00:00:00 2001
From: buzbee <buzbee@google.com>
Date: Wed, 5 Sep 2012 14:06:51 -0700
Subject: Basic block combine pass

Combine basic blocks terminated by instruction that we have since
proven not to throw.  This change is intended to relieve some of the
computational load for llvm by reducing the number of basic blocks
it has to contend with.

Also:
  Add stats to show how successful check elimination is.
  Restore mechanism to disable some expensive optimization passes when
  compiling large methods.

Change-Id: I7fae22160988cbefb90ea9fb1cc26d7364e8d229
---
 src/compiler/Dataflow.cc | 108 ++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 107 insertions(+), 1 deletion(-)

(limited to 'src/compiler/Dataflow.cc')

diff --git a/src/compiler/Dataflow.cc b/src/compiler/Dataflow.cc
index 896764969a..a5cdbdeaaa 100644
--- a/src/compiler/Dataflow.cc
+++ b/src/compiler/Dataflow.cc
@@ -1945,6 +1945,90 @@ bool nullCheckEliminationInit(struct CompilationUnit* cUnit,
   return true;
 }
 
+/* Collect stats on number of checks removed */
+bool countChecks( struct CompilationUnit* cUnit, struct BasicBlock* bb)
+{
+  if (bb->dataFlowInfo == NULL) return false;
+  for (MIR* mir = bb->firstMIRInsn; mir; mir = mir->next) {
+    if (mir->ssaRep == NULL) {
+      continue;
+    }
+    int dfAttributes = oatDataFlowAttributes[mir->dalvikInsn.opcode];
+    if (dfAttributes & DF_HAS_NULL_CHKS) {
+      cUnit->checkstats->nullChecks++;
+      if (mir->optimizationFlags & MIR_IGNORE_NULL_CHECK) {
+        cUnit->checkstats->nullChecksEliminated++;
+      }
+    }
+    if (dfAttributes & DF_HAS_RANGE_CHKS) {
+      cUnit->checkstats->rangeChecks++;
+      if (mir->optimizationFlags & MIR_IGNORE_RANGE_CHECK) {
+        cUnit->checkstats->rangeChecksEliminated++;
+      }
+    }
+  }
+  return false;
+}
+
+/* Combine any basic blocks terminated by instructions that we now know can't throw */
+bool combineBlocks(struct CompilationUnit* cUnit, struct BasicBlock* bb)
+{
+  // Loop here to allow combining a sequence of blocks
+  while (true) {
+    // Check termination conditions
+    if ((bb->firstMIRInsn == NULL)
+        || (bb->dataFlowInfo == NULL)
+        || (bb->blockType == kExceptionHandling)
+        || (bb->blockType == kExitBlock)
+        || (bb->blockType == kDead)
+        || ((bb->taken == NULL) || (bb->taken->blockType != kExceptionHandling))
+        || (bb->successorBlockList.blockListType != kNotUsed)
+        || ((int)bb->lastMIRInsn->dalvikInsn.opcode != kMirOpCheck)) {
+      break;
+    }
+
+    // Test the kMirOpCheck instruction
+    MIR* mir = bb->lastMIRInsn;
+    // Grab the attributes from the paired opcode
+    MIR* throwInsn = mir->meta.throwInsn;
+    int dfAttributes = oatDataFlowAttributes[throwInsn->dalvikInsn.opcode];
+    // Only null checks, and null checks eliminated?
+    if (((dfAttributes & DF_HAS_NULL_CHKS) == 0) || ((dfAttributes & DF_HAS_RANGE_CHKS) != 0)
+        || !(throwInsn->optimizationFlags & MIR_IGNORE_NULL_CHECK)) {
+      break;
+    }
+    // OK - got one.  Combine
+    BasicBlock* bbNext = bb->fallThrough;
+    DCHECK(!bbNext->catchEntry);
+    DCHECK_EQ(bbNext->predecessors->numUsed, 1U);
+    MIR* tMir = bb->lastMIRInsn->prev;
+    // Overwrite the kOpCheck insn with the paired opcode
+    DCHECK_EQ(bbNext->firstMIRInsn, throwInsn);
+    *bb->lastMIRInsn = *throwInsn;
+    bb->lastMIRInsn->prev = tMir;
+    // Use the successor info from the next block
+    bb->successorBlockList = bbNext->successorBlockList;
+    // Use the ending block linkage from the next block
+    bb->fallThrough = bbNext->fallThrough;
+    bb->taken->blockType = kDead;  // Kill the unused exception block
+    bb->taken = bbNext->taken;
+    // Include the rest of the instructions
+    bb->lastMIRInsn = bbNext->lastMIRInsn;
+
+    /*
+     * NOTE: we aren't updating all dataflow info here.  Should either make sure this pass
+     * happens after uses of iDominated, domFrontier or update the dataflow info here.
+     */
+
+    // Kill bbNext and remap now-dead id to parent
+    bbNext->blockType = kDead;
+    cUnit->blockIdMap.Overwrite(bbNext->id, bb->id);
+
+    // Now, loop back and see if we can keep going
+  }
+  return false;
+}
+
 /* Eliminate unnecessary null checks for a basic block. */
 bool eliminateNullChecks( struct CompilationUnit* cUnit, struct BasicBlock* bb)
 {
@@ -2049,7 +2133,7 @@ bool eliminateNullChecks( struct CompilationUnit* cUnit, struct BasicBlock* bb)
     }
 
     // Already nullchecked?
-    if (dfAttributes & DF_HAS_NULL_CHKS) {
+    if ((dfAttributes & DF_HAS_NULL_CHKS) && !(mir->optimizationFlags & MIR_IGNORE_NULL_CHECK)) {
       int srcIdx;
       if (dfAttributes & DF_NULL_CHK_1) {
         srcIdx = 1;
@@ -2091,6 +2175,28 @@ void oatMethodNullCheckElimination(CompilationUnit *cUnit)
   }
 }
 
+void oatMethodBasicBlockCombine(CompilationUnit* cUnit)
+{
+  oatDataFlowAnalysisDispatcher(cUnit, combineBlocks, kPreOrderDFSTraversal, false);
+}
+
+void oatDumpCheckStats(CompilationUnit *cUnit)
+{
+  Checkstats* stats = (Checkstats*)oatNew(cUnit, sizeof(Checkstats), true, kAllocDFInfo);
+  cUnit->checkstats = stats;
+  oatDataFlowAnalysisDispatcher(cUnit, countChecks, kAllNodes, false /* isIterative */);
+  if (stats->nullChecks > 0) {
+    LOG(INFO) << "Null Checks: " << PrettyMethod(cUnit->method_idx, *cUnit->dex_file) << " "
+              << stats->nullChecksEliminated << " of " << stats->nullChecks << " -> "
+              << ((float)stats->nullChecksEliminated/(float)stats->nullChecks) * 100.0 << "%";
+    }
+  if (stats->rangeChecks > 0) {
+    LOG(INFO) << "Range Checks: " << PrettyMethod(cUnit->method_idx, *cUnit->dex_file) << " "
+              << stats->rangeChecksEliminated << " of " << stats->rangeChecks << " -> "
+              << ((float)stats->rangeChecksEliminated/(float)stats->rangeChecks) * 100.0 << "%";
+  }
+}
+
 void oatMethodBasicBlockOptimization(CompilationUnit *cUnit)
 {
   if (!(cUnit->disableOpt & (1 << kBBOpt))) {
-- 
cgit v1.2.3-59-g8ed1b