ART: SBC: Support single exit loops with live_outs.

Support copying subgraphs with a single exit and live-outs -
values which are defined inside the subgraph and have uses outside.

Test: test-art-target, test-art-host.
Test: 530-checker-peel-unroll.

Change-Id: Id06a6f08d14c6e86f6437d662e24489f955e9edf

1 files changed, 30 insertions, 1 deletions

diff --git a/compiler/optimizing/superblock_cloner.h b/compiler/optimizing/superblock_cloner.h
index e0931674cb..f21172131b 100644
--- a/compiler/optimizing/superblock_cloner.h
+++ b/compiler/optimizing/superblock_cloner.h
@@ -218,7 +218,7 @@ class SuperblockCloner : public ValueObject {
 
  private:
   // Fills the 'exits' vector with the subgraph exits.
-  void SearchForSubgraphExits(ArenaVector<HBasicBlock*>* exits);
+  void SearchForSubgraphExits(ArenaVector<HBasicBlock*>* exits) const;
 
   // Finds and records information about the area in the graph for which control flow (back edges,
   // loops, dominators) needs to be adjusted.
@@ -240,6 +240,33 @@ class SuperblockCloner : public ValueObject {
   void ResolveDataFlow();
 
   //
+  // Helpers for live-outs processing and Subgraph-closed SSA.
+  //
+  //  - live-outs - values which are defined inside the subgraph and have uses outside.
+  //  - Subgraph-closed SSA - SSA form for which all the values defined inside the subgraph
+  //    have no outside uses except for the phi-nodes in the subgraph exits.
+  //
+  // Note: now if the subgraph has live-outs it is only clonable if it has a single exit; this
+  // makes the subgraph-closed SSA form construction much easier.
+  //
+  // TODO: Support subgraphs with live-outs and multiple exits.
+  //
+
+  // For each live-out value 'val' in the region puts a record <val, val> into the map.
+  // Returns whether all of the instructions in the subgraph are clonable.
+  bool CollectLiveOutsAndCheckClonable(HInstructionMap* live_outs_) const;
+
+  // Constructs Subgraph-closed SSA; precondition - a subgraph has a single exit.
+  //
+  // For each live-out 'val' in 'live_outs_' map inserts a HPhi 'phi' into the exit node, updates
+  // the record in the map to <val, phi> and replaces all outside uses with this phi.
+  void ConstructSubgraphClosedSSA();
+
+  // Fixes the data flow for the live-out 'val' by adding a 'copy_val' input to the corresponding
+  // (<val, phi>) phi after the cloning is done.
+  void FixSubgraphClosedSSAAfterCloning();
+
+  //
   // Helpers for CloneBasicBlock.
   //
 
@@ -316,6 +343,8 @@ class SuperblockCloner : public ValueObject {
   HLoopInformation* outer_loop_;
   HBasicBlockSet outer_loop_bb_set_;
 
+  HInstructionMap live_outs_;
+
   ART_FRIEND_TEST(SuperblockClonerTest, AdjustControlFlowInfo);
   ART_FRIEND_TEST(SuperblockClonerTest, IsGraphConnected);