Run GVN earlier.

Rationale:
Running GVN earlier allows for better subsequent
instruction simplifation. For example, running GVN
before select generation also finds the MIN in:
   if (x > a[i])
     x = a[i];

Bug: b/74026074

Test: test-art-host,target

Change-Id: I633046375637c7809a3603fdf7c5cf77e8f21167

3 files changed, 36 insertions, 7 deletions

diff --git a/compiler/optimizing/loop_optimization.cc b/compiler/optimizing/loop_optimization.cc
index c0c721de63..1462404932 100644
--- a/compiler/optimizing/loop_optimization.cc
+++ b/compiler/optimizing/loop_optimization.cc
@@ -1353,6 +1353,11 @@ bool HLoopOptimization::VectorizeDef(LoopNode* node,
     HInstruction* index = instruction->InputAt(1);
     HInstruction* value = instruction->InputAt(2);
     HInstruction* offset = nullptr;
+    // For narrow types, explicit type conversion may have been
+    // optimized way, so set the no hi bits restriction here.
+    if (DataType::Size(type) <= 2) {
+      restrictions |= kNoHiBits;
+    }
     if (TrySetVectorType(type, &restrictions) &&
         node->loop_info->IsDefinedOutOfTheLoop(base) &&
         induction_range_.IsUnitStride(instruction, index, graph_, &offset) &&
diff --git a/compiler/optimizing/optimizing_compiler.cc b/compiler/optimizing/optimizing_compiler.cc
index 79165826d1..cadefc3b01 100644
--- a/compiler/optimizing/optimizing_compiler.cc
+++ b/compiler/optimizing/optimizing_compiler.cc
@@ -643,15 +643,13 @@ void OptimizingCompiler::RunOptimizations(HGraph* graph,
   MaybeRunInliner(graph, codegen, dex_compilation_unit, pass_observer, handles);
 
   OptimizationDef optimizations2[] = {
-    // SelectGenerator depends on the InstructionSimplifier removing
-    // redundant suspend checks to recognize empty blocks.
+    OptDef(OptimizationPass::kSideEffectsAnalysis,   "side_effects$before_gvn"),
+    OptDef(OptimizationPass::kGlobalValueNumbering),
     OptDef(OptimizationPass::kSelectGenerator),
-    // TODO: if we don't inline we can also skip fold2.
     OptDef(OptimizationPass::kConstantFolding,       "constant_folding$after_inlining"),
     OptDef(OptimizationPass::kInstructionSimplifier, "instruction_simplifier$after_inlining"),
     OptDef(OptimizationPass::kDeadCodeElimination,   "dead_code_elimination$after_inlining"),
-    OptDef(OptimizationPass::kSideEffectsAnalysis,   "side_effects$before_gvn"),
-    OptDef(OptimizationPass::kGlobalValueNumbering),
+    OptDef(OptimizationPass::kSideEffectsAnalysis,   "side_effects$before_licm"),
     OptDef(OptimizationPass::kInvariantCodeMotion),
     OptDef(OptimizationPass::kInductionVarAnalysis),
     OptDef(OptimizationPass::kBoundsCheckElimination),
diff --git a/compiler/optimizing/select_generator.cc b/compiler/optimizing/select_generator.cc
index 3f52bdd13c..f9acf5aa9a 100644
--- a/compiler/optimizing/select_generator.cc
+++ b/compiler/optimizing/select_generator.cc
@@ -16,6 +16,7 @@
 
 #include "select_generator.h"
 
+#include "base/scoped_arena_containers.h"
 #include "reference_type_propagation.h"
 
 namespace art {
@@ -90,9 +91,13 @@ static HPhi* GetSingleChangedPhi(HBasicBlock* block, size_t index1, size_t index
 }
 
 void HSelectGenerator::Run() {
+  // Select cache with local allocator.
+  ScopedArenaAllocator allocator(graph_->GetArenaStack());
+  ScopedArenaSafeMap<HInstruction*, HSelect*> cache(
+      std::less<HInstruction*>(), allocator.Adapter(kArenaAllocSelectGenerator));
+
   // Iterate in post order in the unlikely case that removing one occurrence of
   // the selection pattern empties a branch block of another occurrence.
-  // Otherwise the order does not matter.
   for (HBasicBlock* block : graph_->GetPostOrder()) {
     if (!block->EndsWithIf()) continue;
 
@@ -143,7 +148,8 @@ void HSelectGenerator::Run() {
     DCHECK(both_successors_return || phi != nullptr);
 
     // Create the Select instruction and insert it in front of the If.
-    HSelect* select = new (graph_->GetAllocator()) HSelect(if_instruction->InputAt(0),
+    HInstruction* condition = if_instruction->InputAt(0);
+    HSelect* select = new (graph_->GetAllocator()) HSelect(condition,
                                                            true_value,
                                                            false_value,
                                                            if_instruction->GetDexPc());
@@ -180,6 +186,26 @@ void HSelectGenerator::Run() {
 
     MaybeRecordStat(stats_, MethodCompilationStat::kSelectGenerated);
 
+    // Very simple way of finding common subexpressions in the generated HSelect statements
+    // (since this runs after GVN). Lookup by condition, and reuse latest one if possible
+    // (due to post order, latest select is most likely replacement). If needed, we could
+    // improve this by e.g. using the operands in the map as well.
+    auto it = cache.find(condition);
+    if (it == cache.end()) {
+      cache.Put(condition, select);
+    } else {
+      // Found cached value. See if latest can replace cached in the HIR.
+      HSelect* cached = it->second;
+      DCHECK_EQ(cached->GetCondition(), select->GetCondition());
+      if (cached->GetTrueValue() == select->GetTrueValue() &&
+          cached->GetFalseValue() == select->GetFalseValue() &&
+          select->StrictlyDominates(cached)) {
+       cached->ReplaceWith(select);
+       cached->GetBlock()->RemoveInstruction(cached);
+      }
+      it->second = select;  // always cache latest
+    }
+
     // No need to update dominance information, as we are simplifying
     // a simple diamond shape, where the join block is merged with the
     // entry block. Any following blocks would have had the join block