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