CFG rework for explicit exception edges

Previously, basic blocks were terminated by any Dalvik opcode
which might throw, and the exception edges were represented
as a list of successor basic blocks.  This resulted in a
SSA renaming bug: any Dalvik register definition caused by
a throwing instruction (such as IGET) would incorrectly be considered
to be visible across the exception edges.  For the Art compiler (and JIT)
this was a benign bug.  But for llvm, it means an invalid CFG.

The other problem this CL is addressing is the llvm bitcode requirement
that all exception edges be explicit.  Because we can't use
the llvm bitcode "invoke" (it doesn't match our exception handling),
all exception edges must be represented as explicit branches in the
bitcode (further contributing to the llvm bitcode bloat).

We split all potentially throwing instructions into two parts: a
check prologue followed by the body.  If there are any catch blocks
associated with the potentially throwing instruction, we make a call
to the intrinisc dex_lang_catch_targets().  Though it should never
expand into actual code, this intrinsic returns a switch key that
feeds into an immediately-following switch statement.  That switch
statement will include edges to all necessary catch blocks, with the
default target referencing the block conaining the "work" portion of
the pair.

Included in this CL are also fixes for .dot file generation
(previously there was an issue with non-unique block names), and an
enhancement to include the block number on Phi incoming arcs.

Also reworked dissasembly to use StringPrintf.

Note: the insertion of new basic blocks following computation of
depth-first-search order badly degrades code layout.  DFS order
computation can be expensive, so I'll be looking for a workaround
in a future CL to avoid a full dfs order regeneration.

With this CL, the device boots, all target tests pass, all methods
are converted to Greenland Bitcode and all well-formed converted methods
pass llvm's function validation pass without error or warning.

We still have some cts failures related to the verifier's
instruction rewriting to THROW_VERIFICATION_ERROR.  In those cases
we can have a malformed graph - but we still must be able to convert
it to legal llvm bitcode.  If executed, it will throw.

We'll detect that situation and bitcast these mismatches away in a
subsequent CL.

Change-Id: I9fa359c912e25ca6a75e2f69d0975126d0687c33

1 files changed, 64 insertions, 57 deletions

diff --git a/src/compiler/Frontend.cc b/src/compiler/Frontend.cc
index b68233b4c0..6b45f0d2cd 100644
--- a/src/compiler/Frontend.cc
+++ b/src/compiler/Frontend.cc
@@ -54,6 +54,7 @@ static uint32_t kCompilerDebugFlags = 0 |     // Enable debug/testing modes
   //(1 << kDebugCountOpcodes) |
 #if defined(ART_USE_QUICK_COMPILER)
   //(1 << kDebugDumpBitcodeFile) |
+  //(1 << kDebugVerifyBitcode) |
 #endif
   0;
 
@@ -154,10 +155,8 @@ BasicBlock *splitBlock(CompilationUnit* cUnit, unsigned int codeOffset,
   }
 
   /* Handle the fallthrough path */
-  bottomBlock->needFallThroughBranch = origBlock->needFallThroughBranch;
   bottomBlock->fallThrough = origBlock->fallThrough;
   origBlock->fallThrough = bottomBlock;
-  origBlock->needFallThroughBranch = true;
   oatInsertGrowableList(cUnit, bottomBlock->predecessors,
                         (intptr_t)origBlock);
   if (bottomBlock->fallThrough) {
@@ -289,12 +288,12 @@ void oatDumpCFG(CompilationUnit* cUnit, const char* dirPrefix)
                                                               blockIdx);
     if (bb == NULL) break;
     if (bb->blockType == kEntryBlock) {
-      fprintf(file, "  entry [shape=Mdiamond];\n");
+      fprintf(file, "  entry_%d [shape=Mdiamond];\n", bb->id);
     } else if (bb->blockType == kExitBlock) {
-      fprintf(file, "  exit [shape=Mdiamond];\n");
+      fprintf(file, "  exit_%d [shape=Mdiamond];\n", bb->id);
     } else if (bb->blockType == kDalvikByteCode) {
-      fprintf(file, "  block%04x [shape=record,label = \"{ \\\n",
-              bb->startOffset);
+      fprintf(file, "  block%04x_%d [shape=record,label = \"{ \\\n",
+              bb->startOffset, bb->id);
       const MIR *mir;
         fprintf(file, "    {block id %d\\l}%s\\\n", bb->id,
                 bb->firstMIRInsn ? " | " : " ");
@@ -327,8 +326,8 @@ void oatDumpCFG(CompilationUnit* cUnit, const char* dirPrefix)
     }
 
     if (bb->successorBlockList.blockListType != kNotUsed) {
-      fprintf(file, "  succ%04x [shape=%s,label = \"{ \\\n",
-              bb->startOffset,
+      fprintf(file, "  succ%04x_%d [shape=%s,label = \"{ \\\n",
+              bb->startOffset, bb->id,
               (bb->successorBlockList.blockListType == kCatch) ?
                "Mrecord" : "record");
       GrowableListIterator iterator;
@@ -356,8 +355,8 @@ void oatDumpCFG(CompilationUnit* cUnit, const char* dirPrefix)
       fprintf(file, "  }\"];\n\n");
 
       oatGetBlockName(bb, blockName1);
-      fprintf(file, "  %s:s -> succ%04x:n [style=dashed]\n",
-              blockName1, bb->startOffset);
+      fprintf(file, "  %s:s -> succ%04x_%d:n [style=dashed]\n",
+              blockName1, bb->startOffset, bb->id);
 
       if (bb->successorBlockList.blockListType == kPackedSwitch ||
           bb->successorBlockList.blockListType == kSparseSwitch) {
@@ -374,8 +373,8 @@ void oatDumpCFG(CompilationUnit* cUnit, const char* dirPrefix)
           BasicBlock *destBlock = successorBlockInfo->block;
 
           oatGetBlockName(destBlock, blockName2);
-          fprintf(file, "  succ%04x:f%d:e -> %s:n\n", bb->startOffset,
-                  succId++, blockName2);
+          fprintf(file, "  succ%04x_%d:f%d:e -> %s:n\n", bb->startOffset,
+                  bb->id, succId++, blockName2);
         }
       }
     }
@@ -644,18 +643,20 @@ void processCanSwitch(CompilationUnit* cUnit, BasicBlock* curBlock,
 }
 
 /* Process instructions with the kThrow flag */
-void processCanThrow(CompilationUnit* cUnit, BasicBlock* curBlock, MIR* insn,
-                     int curOffset, int width, int flags,
-                     ArenaBitVector* tryBlockAddr, const u2* codePtr,
-                     const u2* codeEnd)
+BasicBlock* processCanThrow(CompilationUnit* cUnit, BasicBlock* curBlock,
+                            MIR* insn, int curOffset, int width, int flags,
+                            ArenaBitVector* tryBlockAddr, const u2* codePtr,
+                            const u2* codeEnd)
 {
   const DexFile::CodeItem* code_item = cUnit->code_item;
+  bool inTryBlock = oatIsBitSet(tryBlockAddr, curOffset);
 
   /* In try block */
-  if (oatIsBitSet(tryBlockAddr, curOffset)) {
+  if (inTryBlock) {
     CatchHandlerIterator iterator(*code_item, curOffset);
 
     if (curBlock->successorBlockList.blockListType != kNotUsed) {
+      LOG(INFO) << PrettyMethod(cUnit->method_idx, *cUnit->dex_file);
       LOG(FATAL) << "Successor block list already in use: "
                  << (int)curBlock->successorBlockList.blockListType;
     }
@@ -688,37 +689,46 @@ void processCanThrow(CompilationUnit* cUnit, BasicBlock* curBlock, MIR* insn,
     oatInsertGrowableList(cUnit, ehBlock->predecessors, (intptr_t)curBlock);
   }
 
-  /*
-   * Force the current block to terminate.
-   *
-   * Data may be present before codeEnd, so we need to parse it to know
-   * whether it is code or data.
-   */
-  if (codePtr < codeEnd) {
-    /* Create a fallthrough block for real instructions (incl. NOP) */
-    if (contentIsInsn(codePtr)) {
-      BasicBlock *fallthroughBlock = findBlock(cUnit,
-                                               curOffset + width,
-                                               /* split */
-                                               false,
-                                               /* create */
-                                               true,
-                                               /* immedPredBlockP */
-                                               NULL);
-      /*
-       * THROW is an unconditional branch.  NOTE:
-       * THROW_VERIFICATION_ERROR is also an unconditional
-       * branch, but we shouldn't treat it as such until we have
-       * a dead code elimination pass (which won't be important
-       * until inlining w/ constant propagation is implemented.
-       */
-      if (insn->dalvikInsn.opcode != Instruction::THROW) {
-        curBlock->fallThrough = fallthroughBlock;
-        oatInsertGrowableList(cUnit, fallthroughBlock->predecessors,
-                              (intptr_t)curBlock);
-      }
+  if (insn->dalvikInsn.opcode == Instruction::THROW){
+    if ((codePtr < codeEnd) && contentIsInsn(codePtr)) {
+      // Force creation of new block following THROW via side-effect
+      findBlock(cUnit, curOffset + width, /* split */ false,
+                /* create */ true, /* immedPredBlockP */ NULL);
+    }
+    if (!inTryBlock) {
+       // Don't split a THROW that can't rethrow - we're done.
+      return curBlock;
     }
   }
+
+  /*
+   * Split the potentially-throwing instruction into two parts.
+   * The first half will be a pseudo-op that captures the exception
+   * edges and terminates the basic block.  It always falls through.
+   * Then, create a new basic block that begins with the throwing instruction
+   * (minus exceptions).  Note: this new basic block must NOT be entered into
+   * the blockMap.  If the potentially-throwing instruction is the target of a
+   * future branch, we need to find the check psuedo half.  The new
+   * basic block containing the work portion of the instruction should
+   * only be entered via fallthrough from the block containing the
+   * pseudo exception edge MIR.  Note also that this new block is
+   * not automatically terminated after the work portion, and may
+   * contain following instructions.
+   */
+  BasicBlock *newBlock = oatNewBB(cUnit, kDalvikByteCode, cUnit->numBlocks++);
+  oatInsertGrowableList(cUnit, &cUnit->blockList, (intptr_t)newBlock);
+  newBlock->startOffset = insn->offset;
+  curBlock->fallThrough = newBlock;
+  oatInsertGrowableList(cUnit, newBlock->predecessors, (intptr_t)curBlock);
+  MIR* newInsn = (MIR*)oatNew(cUnit, sizeof(MIR), true, kAllocMIR);
+  *newInsn = *insn;
+  insn->dalvikInsn.opcode =
+      static_cast<Instruction::Code>(kMirOpCheck);
+  // Associate the two halves
+  insn->meta.throwInsn = newInsn;
+  newInsn->meta.throwInsn = insn;
+  oatAppendMIR(newBlock, newInsn);
+  return newBlock;
 }
 
 void oatInit(CompilationUnit* cUnit, const Compiler& compiler) {
@@ -763,15 +773,11 @@ CompiledMethod* oatCompileMethod(Compiler& compiler,
   cUnit->numRegs = code_item->registers_size_ - cUnit->numIns;
   cUnit->numOuts = code_item->outs_size_;
 #if defined(ART_USE_QUICK_COMPILER)
-  // TODO: fix bug and remove this workaround
-  std::string methodName = PrettyMethod(method_idx, dex_file);
-  if ((methodName.find("gdata2.AndroidGDataClient.createAndExecuteMethod")
-      != std::string::npos) || (methodName.find("hG.a") != std::string::npos)
-      || (methodName.find("hT.a(hV, java.lang.String, java.lang.String, java")
-      != std::string::npos) || (methodName.find("AndroidHttpTransport.exchange")
-      != std::string::npos)) {
-    LOG(INFO) << "Skipping bitcode generation for " << methodName;
-  } else {
+  DCHECK((cUnit->instructionSet == kThumb2) ||
+         (cUnit->instructionSet == kX86) ||
+         (cUnit->instructionSet == kMips));
+  if (cUnit->instructionSet == kThumb2) {
+    // TODO: remove this once x86 is tested
     cUnit->genBitcode = true;
   }
 #endif
@@ -791,6 +797,7 @@ CompiledMethod* oatCompileMethod(Compiler& compiler,
   }
 #if defined(ART_USE_QUICK_COMPILER)
   if (cUnit->genBitcode) {
+    //cUnit->enableDebug |= (1 << kDebugVerifyBitcode);
     //cUnit->printMe = true;
     //cUnit->enableDebug |= (1 << kDebugDumpBitcodeFile);
     // Disable non-safe optimizations for now
@@ -962,8 +969,8 @@ CompiledMethod* oatCompileMethod(Compiler& compiler,
         }
       }
     } else if (flags & Instruction::kThrow) {
-      processCanThrow(cUnit.get(), curBlock, insn, curOffset, width, flags,
-                      tryBlockAddr, codePtr, codeEnd);
+      curBlock = processCanThrow(cUnit.get(), curBlock, insn, curOffset,
+                                 width, flags, tryBlockAddr, codePtr, codeEnd);
     } else if (flags & Instruction::kSwitch) {
       processCanSwitch(cUnit.get(), curBlock, insn, curOffset, width, flags);
     }