Create separate Android.mk for main build targets

The runtime, compiler, dex2oat, and oatdump now are in seperate trees
to prevent dependency creep.  They can now be individually built
without rebuilding the rest of the art projects. dalvikvm and jdwpspy
were already this way. Builds in the art directory should behave as
before, building everything including tests.

Change-Id: Ic6b1151e5ed0f823c3dd301afd2b13eb2d8feb81

1 files changed, 499 insertions, 0 deletions

diff --git a/compiler/dex/quick/local_optimizations.cc b/compiler/dex/quick/local_optimizations.cc
new file mode 100644
index 0000000..ac654d8
--- /dev/null
+++ b/compiler/dex/quick/local_optimizations.cc
@@ -0,0 +1,499 @@
+/*
+ * Copyright (C) 2011 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "dex/compiler_internals.h"
+
+namespace art {
+
+#define DEBUG_OPT(X)
+
+/* Check RAW, WAR, and RAW dependency on the register operands */
+#define CHECK_REG_DEP(use, def, check) ((def & check->use_mask) || \
+                                        ((use | def) & check->def_mask))
+
+/* Scheduler heuristics */
+#define MAX_HOIST_DISTANCE 20
+#define LDLD_DISTANCE 4
+#define LD_LATENCY 2
+
+static bool IsDalvikRegisterClobbered(LIR* lir1, LIR* lir2)
+{
+  int reg1Lo = DECODE_ALIAS_INFO_REG(lir1->alias_info);
+  int reg1Hi = reg1Lo + DECODE_ALIAS_INFO_WIDE(lir1->alias_info);
+  int reg2Lo = DECODE_ALIAS_INFO_REG(lir2->alias_info);
+  int reg2Hi = reg2Lo + DECODE_ALIAS_INFO_WIDE(lir2->alias_info);
+
+  return (reg1Lo == reg2Lo) || (reg1Lo == reg2Hi) || (reg1Hi == reg2Lo);
+}
+
+/* Convert a more expensive instruction (ie load) into a move */
+void Mir2Lir::ConvertMemOpIntoMove(LIR* orig_lir, int dest, int src)
+{
+  /* Insert a move to replace the load */
+  LIR* move_lir;
+  move_lir = OpRegCopyNoInsert(dest, src);
+  /*
+   * Insert the converted instruction after the original since the
+   * optimization is scannng in the top-down order and the new instruction
+   * will need to be re-checked (eg the new dest clobbers the src used in
+   * this_lir).
+   */
+  InsertLIRAfter(orig_lir, move_lir);
+}
+
+/*
+ * Perform a pass of top-down walk, from the second-last instruction in the
+ * superblock, to eliminate redundant loads and stores.
+ *
+ * An earlier load can eliminate a later load iff
+ *   1) They are must-aliases
+ *   2) The native register is not clobbered in between
+ *   3) The memory location is not written to in between
+ *
+ * An earlier store can eliminate a later load iff
+ *   1) They are must-aliases
+ *   2) The native register is not clobbered in between
+ *   3) The memory location is not written to in between
+ *
+ * A later store can be eliminated by an earlier store iff
+ *   1) They are must-aliases
+ *   2) The memory location is not written to in between
+ */
+void Mir2Lir::ApplyLoadStoreElimination(LIR* head_lir, LIR* tail_lir)
+{
+  LIR* this_lir;
+
+  if (head_lir == tail_lir) return;
+
+  for (this_lir = PREV_LIR(tail_lir); this_lir != head_lir; this_lir = PREV_LIR(this_lir)) {
+
+    if (is_pseudo_opcode(this_lir->opcode)) continue;
+
+    int sink_distance = 0;
+
+    uint64_t target_flags = GetTargetInstFlags(this_lir->opcode);
+
+    /* Skip non-interesting instructions */
+    if ((this_lir->flags.is_nop == true) ||
+        (target_flags & IS_BRANCH) ||
+        ((target_flags & (REG_DEF0 | REG_DEF1)) == (REG_DEF0 | REG_DEF1)) ||  // Skip wide loads.
+        ((target_flags & (REG_USE0 | REG_USE1 | REG_USE2)) ==
+         (REG_USE0 | REG_USE1 | REG_USE2)) ||  // Skip wide stores.
+        !(target_flags & (IS_LOAD | IS_STORE))) {
+      continue;
+    }
+
+    int native_reg_id;
+    if (cu_->instruction_set == kX86) {
+      // If x86, location differs depending on whether memory/reg operation.
+      native_reg_id = (GetTargetInstFlags(this_lir->opcode) & IS_STORE) ? this_lir->operands[2]
+          : this_lir->operands[0];
+    } else {
+      native_reg_id = this_lir->operands[0];
+    }
+    bool is_this_lir_load = GetTargetInstFlags(this_lir->opcode) & IS_LOAD;
+    LIR* check_lir;
+    /* Use the mem mask to determine the rough memory location */
+    uint64_t this_mem_mask = (this_lir->use_mask | this_lir->def_mask) & ENCODE_MEM;
+
+    /*
+     * Currently only eliminate redundant ld/st for constant and Dalvik
+     * register accesses.
+     */
+    if (!(this_mem_mask & (ENCODE_LITERAL | ENCODE_DALVIK_REG))) continue;
+
+    uint64_t stop_def_reg_mask = this_lir->def_mask & ~ENCODE_MEM;
+    uint64_t stop_use_reg_mask;
+    if (cu_->instruction_set == kX86) {
+      stop_use_reg_mask = (IS_BRANCH | this_lir->use_mask) & ~ENCODE_MEM;
+    } else {
+      /*
+       * Add pc to the resource mask to prevent this instruction
+       * from sinking past branch instructions. Also take out the memory
+       * region bits since stop_mask is used to check data/control
+       * dependencies.
+       */
+        stop_use_reg_mask = (GetPCUseDefEncoding() | this_lir->use_mask) & ~ENCODE_MEM;
+    }
+
+    for (check_lir = NEXT_LIR(this_lir); check_lir != tail_lir; check_lir = NEXT_LIR(check_lir)) {
+
+      /*
+       * Skip already dead instructions (whose dataflow information is
+       * outdated and misleading).
+       */
+      if (check_lir->flags.is_nop || is_pseudo_opcode(check_lir->opcode)) continue;
+
+      uint64_t check_mem_mask = (check_lir->use_mask | check_lir->def_mask) & ENCODE_MEM;
+      uint64_t alias_condition = this_mem_mask & check_mem_mask;
+      bool stop_here = false;
+
+      /*
+       * Potential aliases seen - check the alias relations
+       */
+      uint64_t check_flags = GetTargetInstFlags(check_lir->opcode);
+      // TUNING: Support instructions with multiple register targets.
+      if ((check_flags & (REG_DEF0 | REG_DEF1)) == (REG_DEF0 | REG_DEF1)) {
+        stop_here = true;
+      } else if (check_mem_mask != ENCODE_MEM && alias_condition != 0) {
+        bool is_check_lir_load = check_flags & IS_LOAD;
+        if  (alias_condition == ENCODE_LITERAL) {
+          /*
+           * Should only see literal loads in the instruction
+           * stream.
+           */
+          DCHECK(!(check_flags & IS_STORE));
+          /* Same value && same register type */
+          if (check_lir->alias_info == this_lir->alias_info &&
+              SameRegType(check_lir->operands[0], native_reg_id)) {
+            /*
+             * Different destination register - insert
+             * a move
+             */
+            if (check_lir->operands[0] != native_reg_id) {
+              ConvertMemOpIntoMove(check_lir, check_lir->operands[0], native_reg_id);
+            }
+            check_lir->flags.is_nop = true;
+          }
+        } else if (alias_condition == ENCODE_DALVIK_REG) {
+          /* Must alias */
+          if (check_lir->alias_info == this_lir->alias_info) {
+            /* Only optimize compatible registers */
+            bool reg_compatible = SameRegType(check_lir->operands[0], native_reg_id);
+            if ((is_this_lir_load && is_check_lir_load) ||
+                (!is_this_lir_load && is_check_lir_load)) {
+              /* RAR or RAW */
+              if (reg_compatible) {
+                /*
+                 * Different destination register -
+                 * insert a move
+                 */
+                if (check_lir->operands[0] !=
+                  native_reg_id) {
+                  ConvertMemOpIntoMove(check_lir, check_lir->operands[0], native_reg_id);
+                }
+                check_lir->flags.is_nop = true;
+              } else {
+                /*
+                 * Destinaions are of different types -
+                 * something complicated going on so
+                 * stop looking now.
+                 */
+                stop_here = true;
+              }
+            } else if (is_this_lir_load && !is_check_lir_load) {
+              /* WAR - register value is killed */
+              stop_here = true;
+            } else if (!is_this_lir_load && !is_check_lir_load) {
+              /* WAW - nuke the earlier store */
+              this_lir->flags.is_nop = true;
+              stop_here = true;
+            }
+          /* Partial overlap */
+          } else if (IsDalvikRegisterClobbered(this_lir, check_lir)) {
+            /*
+             * It is actually ok to continue if check_lir
+             * is a read. But it is hard to make a test
+             * case for this so we just stop here to be
+             * conservative.
+             */
+            stop_here = true;
+          }
+        }
+        /* Memory content may be updated. Stop looking now. */
+        if (stop_here) {
+          break;
+        /* The check_lir has been transformed - check the next one */
+        } else if (check_lir->flags.is_nop) {
+          continue;
+        }
+      }
+
+
+      /*
+       * this and check LIRs have no memory dependency. Now check if
+       * their register operands have any RAW, WAR, and WAW
+       * dependencies. If so, stop looking.
+       */
+      if (stop_here == false) {
+        stop_here = CHECK_REG_DEP(stop_use_reg_mask, stop_def_reg_mask, check_lir);
+      }
+
+      if (stop_here == true) {
+        if (cu_->instruction_set == kX86) {
+          // Prevent stores from being sunk between ops that generate ccodes and
+          // ops that use them.
+          uint64_t flags = GetTargetInstFlags(check_lir->opcode);
+          if (sink_distance > 0 && (flags & IS_BRANCH) && (flags & USES_CCODES)) {
+            check_lir = PREV_LIR(check_lir);
+            sink_distance--;
+          }
+        }
+        DEBUG_OPT(dump_dependent_insn_pair(this_lir, check_lir, "REG CLOBBERED"));
+        /* Only sink store instructions */
+        if (sink_distance && !is_this_lir_load) {
+          LIR* new_store_lir =
+              static_cast<LIR*>(arena_->NewMem(sizeof(LIR), true, ArenaAllocator::kAllocLIR));
+          *new_store_lir = *this_lir;
+          /*
+           * Stop point found - insert *before* the check_lir
+           * since the instruction list is scanned in the
+           * top-down order.
+           */
+          InsertLIRBefore(check_lir, new_store_lir);
+          this_lir->flags.is_nop = true;
+        }
+        break;
+      } else if (!check_lir->flags.is_nop) {
+        sink_distance++;
+      }
+    }
+  }
+}
+
+/*
+ * Perform a pass of bottom-up walk, from the second instruction in the
+ * superblock, to try to hoist loads to earlier slots.
+ */
+void Mir2Lir::ApplyLoadHoisting(LIR* head_lir, LIR* tail_lir)
+{
+  LIR* this_lir, *check_lir;
+  /*
+   * Store the list of independent instructions that can be hoisted past.
+   * Will decide the best place to insert later.
+   */
+  LIR* prev_inst_list[MAX_HOIST_DISTANCE];
+
+  /* Empty block */
+  if (head_lir == tail_lir) return;
+
+  /* Start from the second instruction */
+  for (this_lir = NEXT_LIR(head_lir); this_lir != tail_lir; this_lir = NEXT_LIR(this_lir)) {
+
+    if (is_pseudo_opcode(this_lir->opcode)) continue;
+
+    uint64_t target_flags = GetTargetInstFlags(this_lir->opcode);
+    /* Skip non-interesting instructions */
+    if ((this_lir->flags.is_nop == true) ||
+        ((target_flags & (REG_DEF0 | REG_DEF1)) == (REG_DEF0 | REG_DEF1)) ||
+        !(target_flags & IS_LOAD)) {
+      continue;
+    }
+
+    uint64_t stop_use_all_mask = this_lir->use_mask;
+
+    if (cu_->instruction_set != kX86) {
+      /*
+       * Branches for null/range checks are marked with the true resource
+       * bits, and loads to Dalvik registers, constant pools, and non-alias
+       * locations are safe to be hoisted. So only mark the heap references
+       * conservatively here.
+       */
+      if (stop_use_all_mask & ENCODE_HEAP_REF) {
+        stop_use_all_mask |= GetPCUseDefEncoding();
+      }
+    }
+
+    /* Similar as above, but just check for pure register dependency */
+    uint64_t stop_use_reg_mask = stop_use_all_mask & ~ENCODE_MEM;
+    uint64_t stop_def_reg_mask = this_lir->def_mask & ~ENCODE_MEM;
+
+    int next_slot = 0;
+    bool stop_here = false;
+
+    /* Try to hoist the load to a good spot */
+    for (check_lir = PREV_LIR(this_lir); check_lir != head_lir; check_lir = PREV_LIR(check_lir)) {
+
+      /*
+       * Skip already dead instructions (whose dataflow information is
+       * outdated and misleading).
+       */
+      if (check_lir->flags.is_nop) continue;
+
+      uint64_t check_mem_mask = check_lir->def_mask & ENCODE_MEM;
+      uint64_t alias_condition = stop_use_all_mask & check_mem_mask;
+      stop_here = false;
+
+      /* Potential WAR alias seen - check the exact relation */
+      if (check_mem_mask != ENCODE_MEM && alias_condition != 0) {
+        /* We can fully disambiguate Dalvik references */
+        if (alias_condition == ENCODE_DALVIK_REG) {
+          /* Must alias or partually overlap */
+          if ((check_lir->alias_info == this_lir->alias_info) ||
+            IsDalvikRegisterClobbered(this_lir, check_lir)) {
+            stop_here = true;
+          }
+        /* Conservatively treat all heap refs as may-alias */
+        } else {
+          DCHECK_EQ(alias_condition, ENCODE_HEAP_REF);
+          stop_here = true;
+        }
+        /* Memory content may be updated. Stop looking now. */
+        if (stop_here) {
+          prev_inst_list[next_slot++] = check_lir;
+          break;
+        }
+      }
+
+      if (stop_here == false) {
+        stop_here = CHECK_REG_DEP(stop_use_reg_mask, stop_def_reg_mask,
+                     check_lir);
+      }
+
+      /*
+       * Store the dependent or non-pseudo/indepedent instruction to the
+       * list.
+       */
+      if (stop_here || !is_pseudo_opcode(check_lir->opcode)) {
+        prev_inst_list[next_slot++] = check_lir;
+        if (next_slot == MAX_HOIST_DISTANCE) break;
+      }
+
+      /* Found a new place to put the load - move it here */
+      if (stop_here == true) {
+        DEBUG_OPT(dump_dependent_insn_pair(check_lir, this_lir "HOIST STOP"));
+        break;
+      }
+    }
+
+    /*
+     * Reached the top - use head_lir as the dependent marker as all labels
+     * are barriers.
+     */
+    if (stop_here == false && next_slot < MAX_HOIST_DISTANCE) {
+      prev_inst_list[next_slot++] = head_lir;
+    }
+
+    /*
+     * At least one independent instruction is found. Scan in the reversed
+     * direction to find a beneficial slot.
+     */
+    if (next_slot >= 2) {
+      int first_slot = next_slot - 2;
+      int slot;
+      LIR* dep_lir = prev_inst_list[next_slot-1];
+      /* If there is ld-ld dependency, wait LDLD_DISTANCE cycles */
+      if (!is_pseudo_opcode(dep_lir->opcode) &&
+        (GetTargetInstFlags(dep_lir->opcode) & IS_LOAD)) {
+        first_slot -= LDLD_DISTANCE;
+      }
+      /*
+       * Make sure we check slot >= 0 since first_slot may be negative
+       * when the loop is first entered.
+       */
+      for (slot = first_slot; slot >= 0; slot--) {
+        LIR* cur_lir = prev_inst_list[slot];
+        LIR* prev_lir = prev_inst_list[slot+1];
+
+        /* Check the highest instruction */
+        if (prev_lir->def_mask == ENCODE_ALL) {
+          /*
+           * If the first instruction is a load, don't hoist anything
+           * above it since it is unlikely to be beneficial.
+           */
+          if (GetTargetInstFlags(cur_lir->opcode) & IS_LOAD) continue;
+          /*
+           * If the remaining number of slots is less than LD_LATENCY,
+           * insert the hoisted load here.
+           */
+          if (slot < LD_LATENCY) break;
+        }
+
+        // Don't look across a barrier label
+        if ((prev_lir->opcode == kPseudoTargetLabel) ||
+            (prev_lir->opcode == kPseudoSafepointPC) ||
+            (prev_lir->opcode == kPseudoBarrier)) {
+          break;
+        }
+
+        /*
+         * Try to find two instructions with load/use dependency until
+         * the remaining instructions are less than LD_LATENCY.
+         */
+        bool prev_is_load = is_pseudo_opcode(prev_lir->opcode) ? false :
+            (GetTargetInstFlags(prev_lir->opcode) & IS_LOAD);
+        if (((cur_lir->use_mask & prev_lir->def_mask) && prev_is_load) || (slot < LD_LATENCY)) {
+          break;
+        }
+      }
+
+      /* Found a slot to hoist to */
+      if (slot >= 0) {
+        LIR* cur_lir = prev_inst_list[slot];
+        LIR* new_load_lir =
+          static_cast<LIR*>(arena_->NewMem(sizeof(LIR), true, ArenaAllocator::kAllocLIR));
+        *new_load_lir = *this_lir;
+        /*
+         * Insertion is guaranteed to succeed since check_lir
+         * is never the first LIR on the list
+         */
+        InsertLIRBefore(cur_lir, new_load_lir);
+        this_lir->flags.is_nop = true;
+      }
+    }
+  }
+}
+
+void Mir2Lir::ApplyLocalOptimizations(LIR* head_lir, LIR* tail_lir)
+{
+  if (!(cu_->disable_opt & (1 << kLoadStoreElimination))) {
+    ApplyLoadStoreElimination(head_lir, tail_lir);
+  }
+  if (!(cu_->disable_opt & (1 << kLoadHoisting))) {
+    ApplyLoadHoisting(head_lir, tail_lir);
+  }
+}
+
+/*
+ * Nop any unconditional branches that go to the next instruction.
+ * Note: new redundant branches may be inserted later, and we'll
+ * use a check in final instruction assembly to nop those out.
+ */
+void Mir2Lir::RemoveRedundantBranches()
+{
+  LIR* this_lir;
+
+  for (this_lir = first_lir_insn_; this_lir != last_lir_insn_; this_lir = NEXT_LIR(this_lir)) {
+
+    /* Branch to the next instruction */
+    if (IsUnconditionalBranch(this_lir)) {
+      LIR* next_lir = this_lir;
+
+      while (true) {
+        next_lir = NEXT_LIR(next_lir);
+
+        /*
+         * Is the branch target the next instruction?
+         */
+        if (next_lir == this_lir->target) {
+          this_lir->flags.is_nop = true;
+          break;
+        }
+
+        /*
+         * Found real useful stuff between the branch and the target.
+         * Need to explicitly check the last_lir_insn_ here because it
+         * might be the last real instruction.
+         */
+        if (!is_pseudo_opcode(next_lir->opcode) ||
+          (next_lir == last_lir_insn_))
+          break;
+      }
+    }
+  }
+}
+
+}  // namespace art