Implement LICM in optimizing compiler.

Change-Id: I9c8afb0a58ef45e568576015473cbfd5f011c242

1 files changed, 44 insertions, 3 deletions

diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 3e4028ed7f..dfb03c31cc 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -899,8 +899,8 @@ class HInstruction : public ArenaObject<kArenaAllocMisc> {
   void ReplaceWith(HInstruction* instruction);
   void ReplaceInput(HInstruction* replacement, size_t index);
 
-  // Insert `this` instruction in `cursor`'s graph, just before `cursor`.
-  void InsertBefore(HInstruction* cursor);
+  // Move `this` instruction before `cursor`.
+  void MoveBefore(HInstruction* cursor);
 
 #define INSTRUCTION_TYPE_CHECK(type, super)                                    \
   bool Is##type() const { return (As##type() != nullptr); }                    \
@@ -2562,6 +2562,12 @@ class HLoadClass : public HExpression<0> {
     return MustGenerateClinitCheck() || !is_referrers_class_;
   }
 
+  bool CanThrow() const OVERRIDE {
+    // May call runtime and and therefore can throw.
+    // TODO: finer grain decision.
+    return !is_referrers_class_;
+  }
+
   DECLARE_INSTRUCTION(LoadClass);
 
  private:
@@ -2726,12 +2732,14 @@ class HThrow : public HTemplateInstruction<1> {
 
   bool NeedsEnvironment() const OVERRIDE { return true; }
 
+  bool CanThrow() const OVERRIDE { return true; }
+
   uint32_t GetDexPc() const { return dex_pc_; }
 
   DECLARE_INSTRUCTION(Throw);
 
  private:
-  uint32_t dex_pc_;
+  const uint32_t dex_pc_;
 
   DISALLOW_COPY_AND_ASSIGN(HThrow);
 };
@@ -3063,6 +3071,39 @@ class HPostOrderIterator : public ValueObject {
   DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator);
 };
 
+// Iterator over the blocks that art part of the loop. Includes blocks part
+// of an inner loop. The order in which the blocks are iterated is on their
+// block id.
+class HBlocksInLoopIterator : public ValueObject {
+ public:
+  explicit HBlocksInLoopIterator(const HLoopInformation& info)
+      : blocks_in_loop_(info.GetBlocks()),
+        blocks_(info.GetHeader()->GetGraph()->GetBlocks()),
+        index_(0) {
+    if (!blocks_in_loop_.IsBitSet(index_)) {
+      Advance();
+    }
+  }
+
+  bool Done() const { return index_ == blocks_.Size(); }
+  HBasicBlock* Current() const { return blocks_.Get(index_); }
+  void Advance() {
+    ++index_;
+    for (size_t e = blocks_.Size(); index_ < e; ++index_) {
+      if (blocks_in_loop_.IsBitSet(index_)) {
+        break;
+      }
+    }
+  }
+
+ private:
+  const BitVector& blocks_in_loop_;
+  const GrowableArray<HBasicBlock*>& blocks_;
+  size_t index_;
+
+  DISALLOW_COPY_AND_ASSIGN(HBlocksInLoopIterator);
+};
+
 }  // namespace art
 
 #endif  // ART_COMPILER_OPTIMIZING_NODES_H_