1 files changed, 91 insertions, 5 deletions

diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 19787c3170..649038b532 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -112,6 +112,7 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
       : arena_(arena),
         blocks_(arena, kDefaultNumberOfBlocks),
         reverse_post_order_(arena, kDefaultNumberOfBlocks),
+        linear_order_(arena, kDefaultNumberOfBlocks),
         entry_block_(nullptr),
         exit_block_(nullptr),
         maximum_number_of_out_vregs_(0),
@@ -216,6 +217,10 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
     return reverse_post_order_;
   }
 
+  const GrowableArray<HBasicBlock*>& GetLinearOrder() const {
+    return linear_order_;
+  }
+
   bool HasArrayAccesses() const {
     return has_array_accesses_;
   }
@@ -248,7 +253,7 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
                               ArenaBitVector* visited,
                               ArenaBitVector* visiting);
   void RemoveInstructionsAsUsersFromDeadBlocks(const ArenaBitVector& visited) const;
-  void RemoveDeadBlocks(const ArenaBitVector& visited) const;
+  void RemoveDeadBlocks(const ArenaBitVector& visited);
 
   template <class InstType, typename ValueType>
   InstType* CreateConstant(ValueType value, ArenaSafeMap<ValueType, InstType*>* cache);
@@ -262,6 +267,9 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
   // List of blocks to perform a reverse post order tree traversal.
   GrowableArray<HBasicBlock*> reverse_post_order_;
 
+  // List of blocks to perform a linear order tree traversal.
+  GrowableArray<HBasicBlock*> linear_order_;
+
   HBasicBlock* entry_block_;
   HBasicBlock* exit_block_;
 
@@ -293,6 +301,7 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
   ArenaSafeMap<int32_t, HIntConstant*> cached_int_constants_;
   ArenaSafeMap<int64_t, HLongConstant*> cached_long_constants_;
 
+  friend class SsaLivenessAnalysis;  // For the linear order.
   ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1);
   DISALLOW_COPY_AND_ASSIGN(HGraph);
 };
@@ -676,6 +685,7 @@ class HLoopInformationOutwardIterator : public ValueObject {
   M(ArrayGet, Instruction)                                              \
   M(ArrayLength, Instruction)                                           \
   M(ArraySet, Instruction)                                              \
+  M(BooleanNot, UnaryOperation)                                         \
   M(BoundsCheck, Instruction)                                           \
   M(BoundType, Instruction)                                             \
   M(CheckCast, Instruction)                                             \
@@ -2643,6 +2653,33 @@ class HNot : public HUnaryOperation {
   DISALLOW_COPY_AND_ASSIGN(HNot);
 };
 
+class HBooleanNot : public HUnaryOperation {
+ public:
+  explicit HBooleanNot(HInstruction* input)
+      : HUnaryOperation(Primitive::Type::kPrimBoolean, input) {}
+
+  bool CanBeMoved() const OVERRIDE { return true; }
+  bool InstructionDataEquals(HInstruction* other) const OVERRIDE {
+    UNUSED(other);
+    return true;
+  }
+
+  int32_t Evaluate(int32_t x) const OVERRIDE {
+    DCHECK(IsUint<1>(x));
+    return !x;
+  }
+
+  int64_t Evaluate(int64_t x ATTRIBUTE_UNUSED) const OVERRIDE {
+    LOG(FATAL) << DebugName() << " cannot be used with 64-bit values";
+    UNREACHABLE();
+  }
+
+  DECLARE_INSTRUCTION(BooleanNot);
+
+ private:
+  DISALLOW_COPY_AND_ASSIGN(HBooleanNot);
+};
+
 class HTypeConversion : public HExpression<1> {
  public:
   // Instantiate a type conversion of `input` to `result_type`.
@@ -3432,8 +3469,11 @@ class HMonitorOperation : public HTemplateInstruction<1> {
 
 class MoveOperands : public ArenaObject<kArenaAllocMisc> {
  public:
-  MoveOperands(Location source, Location destination, HInstruction* instruction)
-      : source_(source), destination_(destination), instruction_(instruction) {}
+  MoveOperands(Location source,
+               Location destination,
+               Primitive::Type type,
+               HInstruction* instruction)
+      : source_(source), destination_(destination), type_(type), instruction_(instruction) {}
 
   Location GetSource() const { return source_; }
   Location GetDestination() const { return destination_; }
@@ -3481,11 +3521,17 @@ class MoveOperands : public ArenaObject<kArenaAllocMisc> {
     return source_.IsInvalid();
   }
 
+  bool Is64BitMove() const {
+    return Primitive::Is64BitType(type_);
+  }
+
   HInstruction* GetInstruction() const { return instruction_; }
 
  private:
   Location source_;
   Location destination_;
+  // The type this move is for.
+  Primitive::Type type_;
   // The instruction this move is assocatied with. Null when this move is
   // for moving an input in the expected locations of user (including a phi user).
   // This is only used in debug mode, to ensure we do not connect interval siblings
@@ -3500,7 +3546,10 @@ class HParallelMove : public HTemplateInstruction<0> {
   explicit HParallelMove(ArenaAllocator* arena)
       : HTemplateInstruction(SideEffects::None()), moves_(arena, kDefaultNumberOfMoves) {}
 
-  void AddMove(Location source, Location destination, HInstruction* instruction) {
+  void AddMove(Location source,
+               Location destination,
+               Primitive::Type type,
+               HInstruction* instruction) {
     DCHECK(source.IsValid());
     DCHECK(destination.IsValid());
     if (kIsDebugBuild) {
@@ -3526,7 +3575,7 @@ class HParallelMove : public HTemplateInstruction<0> {
             << "Same destination for two moves in a parallel move.";
       }
     }
-    moves_.Add(MoveOperands(source, destination, instruction));
+    moves_.Add(MoveOperands(source, destination, type, instruction));
   }
 
   MoveOperands* MoveOperandsAt(size_t index) const {
@@ -3642,6 +3691,43 @@ class HPostOrderIterator : public ValueObject {
   DISALLOW_COPY_AND_ASSIGN(HPostOrderIterator);
 };
 
+class HLinearPostOrderIterator : public ValueObject {
+ public:
+  explicit HLinearPostOrderIterator(const HGraph& graph)
+      : order_(graph.GetLinearOrder()), index_(graph.GetLinearOrder().Size()) {}
+
+  bool Done() const { return index_ == 0; }
+
+  HBasicBlock* Current() const { return order_.Get(index_ -1); }
+
+  void Advance() {
+    --index_;
+    DCHECK_GE(index_, 0U);
+  }
+
+ private:
+  const GrowableArray<HBasicBlock*>& order_;
+  size_t index_;
+
+  DISALLOW_COPY_AND_ASSIGN(HLinearPostOrderIterator);
+};
+
+class HLinearOrderIterator : public ValueObject {
+ public:
+  explicit HLinearOrderIterator(const HGraph& graph)
+      : order_(graph.GetLinearOrder()), index_(0) {}
+
+  bool Done() const { return index_ == order_.Size(); }
+  HBasicBlock* Current() const { return order_.Get(index_); }
+  void Advance() { ++index_; }
+
+ private:
+  const GrowableArray<HBasicBlock*>& order_;
+  size_t index_;
+
+  DISALLOW_COPY_AND_ASSIGN(HLinearOrderIterator);
+};
+
 // 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.