ART: Boolean simplifier

The optimization recognizes the negation pattern generated by 'javac'
and replaces it with a single condition. To this end, boolean values
are now consistently assumed to be represented by an integer.

This is a first optimization which deletes blocks from the HGraph and
does so by replacing the corresponding entries with null. Hence,
existing code can continue indexing the list of blocks with the block
ID, but must check for null when iterating over the list.

Change-Id: I7779da69cfa925c6521938ad0bcc11bc52335583

1 files changed, 22 insertions, 2 deletions

diff --git a/compiler/optimizing/nodes.h b/compiler/optimizing/nodes.h
index 07ff8ba010..7c84f959aa 100644
--- a/compiler/optimizing/nodes.h
+++ b/compiler/optimizing/nodes.h
@@ -128,6 +128,7 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
   void SetExitBlock(HBasicBlock* block) { exit_block_ = block; }
 
   void AddBlock(HBasicBlock* block);
+  void AddConstant(HConstant* instruction);
 
   // Try building the SSA form of this graph, with dominance computation and loop
   // recognition. Returns whether it was successful in doing all these steps.
@@ -154,6 +155,8 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
   // Inline this graph in `outer_graph`, replacing the given `invoke` instruction.
   void InlineInto(HGraph* outer_graph, HInvoke* invoke);
 
+  void MergeEmptyBranches(HBasicBlock* start_block, HBasicBlock* end_block);
+
   void SplitCriticalEdge(HBasicBlock* block, HBasicBlock* successor);
   void SimplifyLoop(HBasicBlock* header);
 
@@ -217,6 +220,8 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
   bool IsDebuggable() const { return debuggable_; }
 
   HNullConstant* GetNullConstant();
+  HIntConstant* GetIntConstant0();
+  HIntConstant* GetIntConstant1();
 
  private:
   HBasicBlock* FindCommonDominator(HBasicBlock* first, HBasicBlock* second) const;
@@ -267,6 +272,10 @@ class HGraph : public ArenaObject<kArenaAllocMisc> {
   // Cached null constant that might be created when building SSA form.
   HNullConstant* cached_null_constant_;
 
+  // Cached common constants often needed by optimization passes.
+  HIntConstant* cached_int_constant0_;
+  HIntConstant* cached_int_constant1_;
+
   ART_FRIEND_TEST(GraphTest, IfSuccessorSimpleJoinBlock1);
   DISALLOW_COPY_AND_ASSIGN(HGraph);
 };
@@ -300,9 +309,9 @@ class HLoopInformation : public ArenaObject<kArenaAllocMisc> {
     back_edges_.Delete(back_edge);
   }
 
-  bool IsBackEdge(HBasicBlock* block) {
+  bool IsBackEdge(const HBasicBlock& block) const {
     for (size_t i = 0, e = back_edges_.Size(); i < e; ++i) {
-      if (back_edges_.Get(i) == block) return true;
+      if (back_edges_.Get(i) == &block) return true;
     }
     return false;
   }
@@ -336,6 +345,7 @@ class HLoopInformation : public ArenaObject<kArenaAllocMisc> {
   const ArenaBitVector& GetBlocks() const { return blocks_; }
 
   void Add(HBasicBlock* block);
+  void Remove(HBasicBlock* block);
 
  private:
   // Internal recursive implementation of `Populate`.
@@ -391,6 +401,8 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> {
     return graph_->GetExitBlock() == this;
   }
 
+  bool IsSingleGoto() const;
+
   void AddBackEdge(HBasicBlock* back_edge) {
     if (loop_information_ == nullptr) {
       loop_information_ = new (graph_->GetArena()) HLoopInformation(this, graph_);
@@ -512,8 +524,16 @@ class HBasicBlock : public ArenaObject<kArenaAllocMisc> {
   // of `this` are moved to `other`.
   // Note that this method does not update the graph, reverse post order, loop
   // information, nor make sure the blocks are consistent (for example ending
+  // with a control flow instruction).
   void ReplaceWith(HBasicBlock* other);
 
+  // Disconnects `this` from all its predecessors, successors and the dominator.
+  // It assumes that `this` does not dominate any blocks.
+  // Note that this method does not update the graph, reverse post order, loop
+  // information, nor make sure the blocks are consistent (for example ending
+  // with a control flow instruction).
+  void DisconnectFromAll();
+
   void AddInstruction(HInstruction* instruction);
   void InsertInstructionBefore(HInstruction* instruction, HInstruction* cursor);
   // Replace instruction `initial` with `replacement` within this block.