Generate selects for nested ternary operators

After an R8 update, the generated dex instructions are different
which means that the structure of the graph is different and we
weren't recognizing a possibility of select generation.

We now recognize it and can update the graph on the fly,
generating the corresponding selects.

Bug: 239385201
Fixes: 239385201
Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Change-Id: I07644f0a69369e809994b4dd39bdd95c2cc7dc6c

1 files changed, 39 insertions, 0 deletions

diff --git a/compiler/optimizing/select_generator.h b/compiler/optimizing/select_generator.h
index 30ac8a86eb..4f13917ba3 100644
--- a/compiler/optimizing/select_generator.h
+++ b/compiler/optimizing/select_generator.h
@@ -57,7 +57,9 @@
 #ifndef ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_
 #define ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_
 
+#include "base/scoped_arena_containers.h"
 #include "optimization.h"
+#include "optimizing/nodes.h"
 
 namespace art {
 
@@ -72,6 +74,43 @@ class HSelectGenerator : public HOptimization {
   static constexpr const char* kSelectGeneratorPassName = "select_generator";
 
  private:
+  bool TryGenerateSelectSimpleDiamondPattern(HBasicBlock* block,
+                                             ScopedArenaSafeMap<HInstruction*, HSelect*>* cache);
+
+  // When generating code for nested ternary operators (e.g. `return (x > 100) ? 100 : ((x < -100) ?
+  // -100 : x);`), a dexer can generate a double diamond pattern but it is not a clear cut one due
+  // to the merging of the blocks. `TryFixupDoubleDiamondPattern` recognizes that pattern and fixes
+  // up the graph to have a clean double diamond that `TryGenerateSelectSimpleDiamondPattern` can
+  // use to generate selects.
+  //
+  // In ASCII, it turns:
+  //
+  //      1 (outer if)
+  //     / \
+  //    2   3 (inner if)
+  //    |  / \
+  //    | 4  5
+  //     \/  |
+  //      6  |
+  //       \ |
+  //         7
+  //         |
+  //         8
+  // into:
+  //      1 (outer if)
+  //     / \
+  //    2   3 (inner if)
+  //    |  / \
+  //    | 4  5
+  //     \/ /
+  //      6
+  //      |
+  //      8
+  //
+  // In short, block 7 disappears and we merge 6 and 7. Now we have a diamond with {3,4,5,6}, and
+  // when that gets resolved we get another one with the outer if.
+  HBasicBlock* TryFixupDoubleDiamondPattern(HBasicBlock* block);
+
   DISALLOW_COPY_AND_ASSIGN(HSelectGenerator);
 };