174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil/*
274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * Copyright (C) 2016 The Android Open Source Project
374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *
474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * Licensed under the Apache License, Version 2.0 (the "License");
574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * you may not use this file except in compliance with the License.
674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * You may obtain a copy of the License at
774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *
874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *      http://www.apache.org/licenses/LICENSE-2.0
974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *
1074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * Unless required by applicable law or agreed to in writing, software
1174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * distributed under the License is distributed on an "AS IS" BASIS,
1274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
1374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * See the License for the specific language governing permissions and
1474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * limitations under the License.
1574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil */
1674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil
1774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil/*
1874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * This optimization recognizes the common diamond selection pattern and
1974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * replaces it with an instance of the HSelect instruction.
2074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *
2174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * Recognized pattern:
2274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *
2374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *          If [ Condition ]
2474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *            /          \
2574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *      false branch  true branch
2674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *            \          /
2774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *     Phi [FalseValue, TrueValue]
2874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *
2974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * The pattern will be simplified if `true_branch` and `false_branch` each
3074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * contain at most one instruction without any side effects.
3174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *
3274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * Blocks are merged into one and Select replaces the If and the Phi:
3374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *              true branch
3474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *              false branch
3574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *              Select [FalseValue, TrueValue, Condition]
3674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil *
3774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * Note: In order to recognize no side-effect blocks, this optimization must be
3874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil * run after the instruction simplifier has removed redundant suspend checks.
3974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil */
4074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil
4174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil#ifndef ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_
4274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil#define ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_
4374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil
4474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil#include "optimization.h"
4574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil
4674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdilnamespace art {
4774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil
4874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdilclass HSelectGenerator : public HOptimization {
4974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil public:
5038e9e8046ea2196284bdb4638771c31108a30a4aJean-Philippe Halimi  HSelectGenerator(HGraph* graph, OptimizingCompilerStats* stats)
5138e9e8046ea2196284bdb4638771c31108a30a4aJean-Philippe Halimi    : HOptimization(graph, kSelectGeneratorPassName, stats) {}
5274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil
5374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil  void Run() OVERRIDE;
5474eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil
5574eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil  static constexpr const char* kSelectGeneratorPassName = "select_generator";
5674eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil
5774eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil private:
5874eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil  DISALLOW_COPY_AND_ASSIGN(HSelectGenerator);
5974eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil};
6074eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil
6174eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil}  // namespace art
6274eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil
6374eb1b264691c4eb399d0858015a7fc13c476ac6David Brazdil#endif  // ART_COMPILER_OPTIMIZING_SELECT_GENERATOR_H_
64