1 /*
2  * Copyright (C) 2016 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 /*
18  * This optimization recognizes the common diamond selection pattern and
19  * replaces it with an instance of the HSelect instruction.
20  *
21  * Recognized patterns:
22  *
23  *          If [ Condition ]
24  *            /          \
25  *      false branch  true branch
26  *            \          /
27  *     Phi [FalseValue, TrueValue]
28  *
29  * and
30  *
31  *             If [ Condition ]
32  *               /          \
33  *     false branch        true branch
34  *     return FalseValue   return TrueValue
35  *
36  * The pattern will be simplified if `true_branch` and `false_branch` each
37  * contain at most one instruction without any side effects.
38  *
39  * Blocks are merged into one and Select replaces the If and the Phi.
40  *
41  * For the first pattern it simplifies to:
42  *
43  *              true branch
44  *              false branch
45  *              Select [FalseValue, TrueValue, Condition]
46  *
47  * For the second pattern it simplifies to:
48  *
49  *              true branch
50  *              false branch
51  *              return Select [FalseValue, TrueValue, Condition]
52  *
53  * Note: In order to recognize no side-effect blocks, this optimization must be
54  * run after the instruction simplifier has removed redundant suspend checks.
55  */
56 
57 #ifndef ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_
58 #define ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_
59 
60 #include "base/macros.h"
61 #include "base/scoped_arena_containers.h"
62 #include "optimization.h"
63 #include "optimizing/nodes.h"
64 
65 namespace art HIDDEN {
66 
67 class HSelectGenerator : public HOptimization {
68  public:
69   HSelectGenerator(HGraph* graph,
70                    OptimizingCompilerStats* stats,
71                    const char* name = kSelectGeneratorPassName);
72 
73   bool Run() override;
74 
75   static constexpr const char* kSelectGeneratorPassName = "select_generator";
76 
77  private:
78   bool TryGenerateSelectSimpleDiamondPattern(HBasicBlock* block,
79                                              ScopedArenaSafeMap<HInstruction*, HSelect*>* cache);
80 
81   // When generating code for nested ternary operators (e.g. `return (x > 100) ? 100 : ((x < -100) ?
82   // -100 : x);`), a dexer can generate a double diamond pattern but it is not a clear cut one due
83   // to the merging of the blocks. `TryFixupDoubleDiamondPattern` recognizes that pattern and fixes
84   // up the graph to have a clean double diamond that `TryGenerateSelectSimpleDiamondPattern` can
85   // use to generate selects.
86   //
87   // In ASCII, it turns:
88   //
89   //      1 (outer if)
90   //     / \
91   //    2   3 (inner if)
92   //    |  / \
93   //    | 4  5
94   //     \/  |
95   //      6  |
96   //       \ |
97   //         7
98   //         |
99   //         8
100   // into:
101   //      1 (outer if)
102   //     / \
103   //    2   3 (inner if)
104   //    |  / \
105   //    | 4  5
106   //     \/ /
107   //      6
108   //      |
109   //      8
110   //
111   // In short, block 7 disappears and we merge 6 and 7. Now we have a diamond with {3,4,5,6}, and
112   // when that gets resolved we get another one with the outer if.
113   HBasicBlock* TryFixupDoubleDiamondPattern(HBasicBlock* block);
114 
115   DISALLOW_COPY_AND_ASSIGN(HSelectGenerator);
116 };
117 
118 }  // namespace art
119 
120 #endif  // ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_
121