Home | History | Annotate | Download | only in optimizing 
      1 /*
      2  * Copyright (C) 2014 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 #include "optimization.h"
     18 
     19 #ifdef ART_ENABLE_CODEGEN_arm
     20 #include "instruction_simplifier_arm.h"
     21 #endif
     22 #ifdef ART_ENABLE_CODEGEN_arm64
     23 #include "instruction_simplifier_arm64.h"
     24 #endif
     25 #ifdef ART_ENABLE_CODEGEN_mips
     26 #include "instruction_simplifier_mips.h"
     27 #include "pc_relative_fixups_mips.h"
     28 #endif
     29 #ifdef ART_ENABLE_CODEGEN_x86
     30 #include "pc_relative_fixups_x86.h"
     31 #include "instruction_simplifier_x86.h"
     32 #endif
     33 #if defined(ART_ENABLE_CODEGEN_x86) || defined(ART_ENABLE_CODEGEN_x86_64)
     34 #include "x86_memory_gen.h"
     35 #endif
     36 #ifdef ART_ENABLE_CODEGEN_x86_64
     37 #include "instruction_simplifier_x86_64.h"
     38 #endif
     39 
     40 #include "bounds_check_elimination.h"
     41 #include "cha_guard_optimization.h"
     42 #include "code_sinking.h"
     43 #include "constant_folding.h"
     44 #include "constructor_fence_redundancy_elimination.h"
     45 #include "dead_code_elimination.h"
     46 #include "dex/code_item_accessors-inl.h"
     47 #include "driver/compiler_options.h"
     48 #include "driver/dex_compilation_unit.h"
     49 #include "gvn.h"
     50 #include "induction_var_analysis.h"
     51 #include "inliner.h"
     52 #include "instruction_simplifier.h"
     53 #include "intrinsics.h"
     54 #include "licm.h"
     55 #include "load_store_analysis.h"
     56 #include "load_store_elimination.h"
     57 #include "loop_optimization.h"
     58 #include "scheduler.h"
     59 #include "select_generator.h"
     60 #include "sharpening.h"
     61 #include "side_effects_analysis.h"
     62 
     63 // Decide between default or alternative pass name.
     64 
     65 namespace art {
     66 
     67 const char* OptimizationPassName(OptimizationPass pass) {
     68   switch (pass) {
     69     case OptimizationPass::kSideEffectsAnalysis:
     70       return SideEffectsAnalysis::kSideEffectsAnalysisPassName;
     71     case OptimizationPass::kInductionVarAnalysis:
     72       return HInductionVarAnalysis::kInductionPassName;
     73     case OptimizationPass::kLoadStoreAnalysis:
     74       return LoadStoreAnalysis::kLoadStoreAnalysisPassName;
     75     case OptimizationPass::kGlobalValueNumbering:
     76       return GVNOptimization::kGlobalValueNumberingPassName;
     77     case OptimizationPass::kInvariantCodeMotion:
     78       return LICM::kLoopInvariantCodeMotionPassName;
     79     case OptimizationPass::kLoopOptimization:
     80       return HLoopOptimization::kLoopOptimizationPassName;
     81     case OptimizationPass::kBoundsCheckElimination:
     82       return BoundsCheckElimination::kBoundsCheckEliminationPassName;
     83     case OptimizationPass::kLoadStoreElimination:
     84       return LoadStoreElimination::kLoadStoreEliminationPassName;
     85     case OptimizationPass::kConstantFolding:
     86       return HConstantFolding::kConstantFoldingPassName;
     87     case OptimizationPass::kDeadCodeElimination:
     88       return HDeadCodeElimination::kDeadCodeEliminationPassName;
     89     case OptimizationPass::kInliner:
     90       return HInliner::kInlinerPassName;
     91     case OptimizationPass::kSelectGenerator:
     92       return HSelectGenerator::kSelectGeneratorPassName;
     93     case OptimizationPass::kInstructionSimplifier:
     94       return InstructionSimplifier::kInstructionSimplifierPassName;
     95     case OptimizationPass::kCHAGuardOptimization:
     96       return CHAGuardOptimization::kCHAGuardOptimizationPassName;
     97     case OptimizationPass::kCodeSinking:
     98       return CodeSinking::kCodeSinkingPassName;
     99     case OptimizationPass::kConstructorFenceRedundancyElimination:
    100       return ConstructorFenceRedundancyElimination::kCFREPassName;
    101     case OptimizationPass::kScheduling:
    102       return HInstructionScheduling::kInstructionSchedulingPassName;
    103 #ifdef ART_ENABLE_CODEGEN_arm
    104     case OptimizationPass::kInstructionSimplifierArm:
    105       return arm::InstructionSimplifierArm::kInstructionSimplifierArmPassName;
    106 #endif
    107 #ifdef ART_ENABLE_CODEGEN_arm64
    108     case OptimizationPass::kInstructionSimplifierArm64:
    109       return arm64::InstructionSimplifierArm64::kInstructionSimplifierArm64PassName;
    110 #endif
    111 #ifdef ART_ENABLE_CODEGEN_mips
    112     case OptimizationPass::kPcRelativeFixupsMips:
    113       return mips::PcRelativeFixups::kPcRelativeFixupsMipsPassName;
    114     case OptimizationPass::kInstructionSimplifierMips:
    115       return mips::InstructionSimplifierMips::kInstructionSimplifierMipsPassName;
    116 #endif
    117 #ifdef ART_ENABLE_CODEGEN_x86
    118     case OptimizationPass::kPcRelativeFixupsX86:
    119       return x86::PcRelativeFixups::kPcRelativeFixupsX86PassName;
    120     case OptimizationPass::kInstructionSimplifierX86:
    121       return x86::InstructionSimplifierX86::kInstructionSimplifierX86PassName;
    122 #endif
    123 #ifdef ART_ENABLE_CODEGEN_x86_64
    124     case OptimizationPass::kInstructionSimplifierX86_64:
    125       return x86_64::InstructionSimplifierX86_64::kInstructionSimplifierX86_64PassName;
    126 #endif
    127 #if defined(ART_ENABLE_CODEGEN_x86) || defined(ART_ENABLE_CODEGEN_x86_64)
    128     case OptimizationPass::kX86MemoryOperandGeneration:
    129       return x86::X86MemoryOperandGeneration::kX86MemoryOperandGenerationPassName;
    130 #endif
    131     case OptimizationPass::kNone:
    132       LOG(FATAL) << "kNone does not represent an actual pass";
    133       UNREACHABLE();
    134   }
    135 }
    136 
    137 #define X(x) if (pass_name == OptimizationPassName((x))) return (x)
    138 
    139 OptimizationPass OptimizationPassByName(const std::string& pass_name) {
    140   X(OptimizationPass::kBoundsCheckElimination);
    141   X(OptimizationPass::kCHAGuardOptimization);
    142   X(OptimizationPass::kCodeSinking);
    143   X(OptimizationPass::kConstantFolding);
    144   X(OptimizationPass::kConstructorFenceRedundancyElimination);
    145   X(OptimizationPass::kDeadCodeElimination);
    146   X(OptimizationPass::kGlobalValueNumbering);
    147   X(OptimizationPass::kInductionVarAnalysis);
    148   X(OptimizationPass::kInliner);
    149   X(OptimizationPass::kInstructionSimplifier);
    150   X(OptimizationPass::kInvariantCodeMotion);
    151   X(OptimizationPass::kLoadStoreAnalysis);
    152   X(OptimizationPass::kLoadStoreElimination);
    153   X(OptimizationPass::kLoopOptimization);
    154   X(OptimizationPass::kScheduling);
    155   X(OptimizationPass::kSelectGenerator);
    156   X(OptimizationPass::kSideEffectsAnalysis);
    157 #ifdef ART_ENABLE_CODEGEN_arm
    158   X(OptimizationPass::kInstructionSimplifierArm);
    159 #endif
    160 #ifdef ART_ENABLE_CODEGEN_arm64
    161   X(OptimizationPass::kInstructionSimplifierArm64);
    162 #endif
    163 #ifdef ART_ENABLE_CODEGEN_mips
    164   X(OptimizationPass::kPcRelativeFixupsMips);
    165   X(OptimizationPass::kInstructionSimplifierMips);
    166 #endif
    167 #ifdef ART_ENABLE_CODEGEN_x86
    168   X(OptimizationPass::kPcRelativeFixupsX86);
    169   X(OptimizationPass::kX86MemoryOperandGeneration);
    170 #endif
    171   LOG(FATAL) << "Cannot find optimization " << pass_name;
    172   UNREACHABLE();
    173 }
    174 
    175 #undef X
    176 
    177 ArenaVector<HOptimization*> ConstructOptimizations(
    178     const OptimizationDef definitions[],
    179     size_t length,
    180     ArenaAllocator* allocator,
    181     HGraph* graph,
    182     OptimizingCompilerStats* stats,
    183     CodeGenerator* codegen,
    184     const DexCompilationUnit& dex_compilation_unit,
    185     VariableSizedHandleScope* handles) {
    186   ArenaVector<HOptimization*> optimizations(allocator->Adapter());
    187 
    188   // Some optimizations require SideEffectsAnalysis or HInductionVarAnalysis
    189   // instances. This method uses the nearest instance preceeding it in the pass
    190   // name list or fails fatally if no such analysis can be found.
    191   SideEffectsAnalysis* most_recent_side_effects = nullptr;
    192   HInductionVarAnalysis* most_recent_induction = nullptr;
    193   LoadStoreAnalysis* most_recent_lsa = nullptr;
    194 
    195   // Loop over the requested optimizations.
    196   for (size_t i = 0; i < length; i++) {
    197     OptimizationPass pass = definitions[i].pass;
    198     const char* alt_name = definitions[i].pass_name;
    199     const char* pass_name = alt_name != nullptr
    200         ? alt_name
    201         : OptimizationPassName(pass);
    202     HOptimization* opt = nullptr;
    203 
    204     switch (pass) {
    205       //
    206       // Analysis passes (kept in most recent for subsequent passes).
    207       //
    208       case OptimizationPass::kSideEffectsAnalysis:
    209         opt = most_recent_side_effects = new (allocator) SideEffectsAnalysis(graph, pass_name);
    210         break;
    211       case OptimizationPass::kInductionVarAnalysis:
    212         opt = most_recent_induction = new (allocator) HInductionVarAnalysis(graph, pass_name);
    213         break;
    214       case OptimizationPass::kLoadStoreAnalysis:
    215         opt = most_recent_lsa = new (allocator) LoadStoreAnalysis(graph, pass_name);
    216         break;
    217       //
    218       // Passes that need prior analysis.
    219       //
    220       case OptimizationPass::kGlobalValueNumbering:
    221         CHECK(most_recent_side_effects != nullptr);
    222         opt = new (allocator) GVNOptimization(graph, *most_recent_side_effects, pass_name);
    223         break;
    224       case OptimizationPass::kInvariantCodeMotion:
    225         CHECK(most_recent_side_effects != nullptr);
    226         opt = new (allocator) LICM(graph, *most_recent_side_effects, stats, pass_name);
    227         break;
    228       case OptimizationPass::kLoopOptimization:
    229         CHECK(most_recent_induction != nullptr);
    230         opt = new (allocator) HLoopOptimization(
    231             graph, &codegen->GetCompilerOptions(), most_recent_induction, stats, pass_name);
    232         break;
    233       case OptimizationPass::kBoundsCheckElimination:
    234         CHECK(most_recent_side_effects != nullptr && most_recent_induction != nullptr);
    235         opt = new (allocator) BoundsCheckElimination(
    236             graph, *most_recent_side_effects, most_recent_induction, pass_name);
    237         break;
    238       case OptimizationPass::kLoadStoreElimination:
    239         CHECK(most_recent_side_effects != nullptr && most_recent_induction != nullptr);
    240         opt = new (allocator) LoadStoreElimination(
    241             graph, *most_recent_side_effects, *most_recent_lsa, stats, pass_name);
    242         break;
    243       //
    244       // Regular passes.
    245       //
    246       case OptimizationPass::kConstantFolding:
    247         opt = new (allocator) HConstantFolding(graph, pass_name);
    248         break;
    249       case OptimizationPass::kDeadCodeElimination:
    250         opt = new (allocator) HDeadCodeElimination(graph, stats, pass_name);
    251         break;
    252       case OptimizationPass::kInliner: {
    253         CodeItemDataAccessor accessor(*dex_compilation_unit.GetDexFile(),
    254                                       dex_compilation_unit.GetCodeItem());
    255         opt = new (allocator) HInliner(graph,                   // outer_graph
    256                                        graph,                   // outermost_graph
    257                                        codegen,
    258                                        dex_compilation_unit,    // outer_compilation_unit
    259                                        dex_compilation_unit,    // outermost_compilation_unit
    260                                        handles,
    261                                        stats,
    262                                        accessor.RegistersSize(),
    263                                        /* total_number_of_instructions= */ 0,
    264                                        /* parent= */ nullptr,
    265                                        /* depth= */ 0,
    266                                        pass_name);
    267         break;
    268       }
    269       case OptimizationPass::kSelectGenerator:
    270         opt = new (allocator) HSelectGenerator(graph, handles, stats, pass_name);
    271         break;
    272       case OptimizationPass::kInstructionSimplifier:
    273         opt = new (allocator) InstructionSimplifier(graph, codegen, stats, pass_name);
    274         break;
    275       case OptimizationPass::kCHAGuardOptimization:
    276         opt = new (allocator) CHAGuardOptimization(graph, pass_name);
    277         break;
    278       case OptimizationPass::kCodeSinking:
    279         opt = new (allocator) CodeSinking(graph, stats, pass_name);
    280         break;
    281       case OptimizationPass::kConstructorFenceRedundancyElimination:
    282         opt = new (allocator) ConstructorFenceRedundancyElimination(graph, stats, pass_name);
    283         break;
    284       case OptimizationPass::kScheduling:
    285         opt = new (allocator) HInstructionScheduling(
    286             graph, codegen->GetCompilerOptions().GetInstructionSet(), codegen, pass_name);
    287         break;
    288       //
    289       // Arch-specific passes.
    290       //
    291 #ifdef ART_ENABLE_CODEGEN_arm
    292       case OptimizationPass::kInstructionSimplifierArm:
    293         DCHECK(alt_name == nullptr) << "arch-specific pass does not support alternative name";
    294         opt = new (allocator) arm::InstructionSimplifierArm(graph, stats);
    295         break;
    296 #endif
    297 #ifdef ART_ENABLE_CODEGEN_arm64
    298       case OptimizationPass::kInstructionSimplifierArm64:
    299         DCHECK(alt_name == nullptr) << "arch-specific pass does not support alternative name";
    300         opt = new (allocator) arm64::InstructionSimplifierArm64(graph, stats);
    301         break;
    302 #endif
    303 #ifdef ART_ENABLE_CODEGEN_mips
    304       case OptimizationPass::kPcRelativeFixupsMips:
    305         DCHECK(alt_name == nullptr) << "arch-specific pass does not support alternative name";
    306         opt = new (allocator) mips::PcRelativeFixups(graph, codegen, stats);
    307         break;
    308       case OptimizationPass::kInstructionSimplifierMips:
    309         DCHECK(alt_name == nullptr) << "arch-specific pass does not support alternative name";
    310         opt = new (allocator) mips::InstructionSimplifierMips(graph, codegen, stats);
    311         break;
    312 #endif
    313 #ifdef ART_ENABLE_CODEGEN_x86
    314       case OptimizationPass::kPcRelativeFixupsX86:
    315         DCHECK(alt_name == nullptr) << "arch-specific pass does not support alternative name";
    316         opt = new (allocator) x86::PcRelativeFixups(graph, codegen, stats);
    317         break;
    318       case OptimizationPass::kX86MemoryOperandGeneration:
    319         DCHECK(alt_name == nullptr) << "arch-specific pass does not support alternative name";
    320         opt = new (allocator) x86::X86MemoryOperandGeneration(graph, codegen, stats);
    321         break;
    322       case OptimizationPass::kInstructionSimplifierX86:
    323        opt = new (allocator) x86::InstructionSimplifierX86(graph, codegen, stats);
    324        break;
    325 #endif
    326 #ifdef ART_ENABLE_CODEGEN_x86_64
    327       case OptimizationPass::kInstructionSimplifierX86_64:
    328         opt = new (allocator) x86_64::InstructionSimplifierX86_64(graph, codegen, stats);
    329         break;
    330 #endif
    331       case OptimizationPass::kNone:
    332         LOG(FATAL) << "kNone does not represent an actual pass";
    333         UNREACHABLE();
    334     }  // switch
    335 
    336     // Add each next optimization to result vector.
    337     CHECK(opt != nullptr);
    338     DCHECK_STREQ(pass_name, opt->GetPassName());  // sanity
    339     optimizations.push_back(opt);
    340   }
    341 
    342   return optimizations;
    343 }
    344 
    345 }  // namespace art
    346