Home | History | Annotate | Download | only in optimizing 
      1 /*
      2  * Copyright (C) 2015 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 "instruction_simplifier_arm.h"
     18 
     19 #include "code_generator.h"
     20 #include "common_arm.h"
     21 #include "instruction_simplifier_shared.h"
     22 #include "mirror/array-inl.h"
     23 #include "mirror/string.h"
     24 #include "nodes.h"
     25 
     26 namespace art {
     27 
     28 using helpers::CanFitInShifterOperand;
     29 using helpers::HasShifterOperand;
     30 
     31 namespace arm {
     32 
     33 class InstructionSimplifierArmVisitor : public HGraphVisitor {
     34  public:
     35   InstructionSimplifierArmVisitor(HGraph* graph, OptimizingCompilerStats* stats)
     36       : HGraphVisitor(graph), stats_(stats) {}
     37 
     38  private:
     39   void RecordSimplification() {
     40     MaybeRecordStat(stats_, MethodCompilationStat::kInstructionSimplificationsArch);
     41   }
     42 
     43   bool TryMergeIntoUsersShifterOperand(HInstruction* instruction);
     44   bool TryMergeIntoShifterOperand(HInstruction* use, HInstruction* bitfield_op, bool do_merge);
     45   bool CanMergeIntoShifterOperand(HInstruction* use, HInstruction* bitfield_op) {
     46     return TryMergeIntoShifterOperand(use, bitfield_op, /* do_merge */ false);
     47   }
     48   bool MergeIntoShifterOperand(HInstruction* use, HInstruction* bitfield_op) {
     49     DCHECK(CanMergeIntoShifterOperand(use, bitfield_op));
     50     return TryMergeIntoShifterOperand(use, bitfield_op, /* do_merge */ true);
     51   }
     52 
     53   /**
     54    * This simplifier uses a special-purpose BB visitor.
     55    * (1) No need to visit Phi nodes.
     56    * (2) Since statements can be removed in a "forward" fashion,
     57    *     the visitor should test if each statement is still there.
     58    */
     59   void VisitBasicBlock(HBasicBlock* block) OVERRIDE {
     60     // TODO: fragile iteration, provide more robust iterators?
     61     for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
     62       HInstruction* instruction = it.Current();
     63       if (instruction->IsInBlock()) {
     64         instruction->Accept(this);
     65       }
     66     }
     67   }
     68 
     69   void VisitAnd(HAnd* instruction) OVERRIDE;
     70   void VisitArrayGet(HArrayGet* instruction) OVERRIDE;
     71   void VisitArraySet(HArraySet* instruction) OVERRIDE;
     72   void VisitMul(HMul* instruction) OVERRIDE;
     73   void VisitOr(HOr* instruction) OVERRIDE;
     74   void VisitShl(HShl* instruction) OVERRIDE;
     75   void VisitShr(HShr* instruction) OVERRIDE;
     76   void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE;
     77   void VisitUShr(HUShr* instruction) OVERRIDE;
     78 
     79   OptimizingCompilerStats* stats_;
     80 };
     81 
     82 bool InstructionSimplifierArmVisitor::TryMergeIntoShifterOperand(HInstruction* use,
     83                                                                  HInstruction* bitfield_op,
     84                                                                  bool do_merge) {
     85   DCHECK(HasShifterOperand(use, InstructionSet::kArm));
     86   DCHECK(use->IsBinaryOperation());
     87   DCHECK(CanFitInShifterOperand(bitfield_op));
     88   DCHECK(!bitfield_op->HasEnvironmentUses());
     89 
     90   DataType::Type type = use->GetType();
     91   if (type != DataType::Type::kInt32 && type != DataType::Type::kInt64) {
     92     return false;
     93   }
     94 
     95   HInstruction* left = use->InputAt(0);
     96   HInstruction* right = use->InputAt(1);
     97   DCHECK(left == bitfield_op || right == bitfield_op);
     98 
     99   if (left == right) {
    100     // TODO: Handle special transformations in this situation?
    101     // For example should we transform `(x << 1) + (x << 1)` into `(x << 2)`?
    102     // Or should this be part of a separate transformation logic?
    103     return false;
    104   }
    105 
    106   bool is_commutative = use->AsBinaryOperation()->IsCommutative();
    107   HInstruction* other_input;
    108   if (bitfield_op == right) {
    109     other_input = left;
    110   } else {
    111     if (is_commutative) {
    112       other_input = right;
    113     } else {
    114       return false;
    115     }
    116   }
    117 
    118   HDataProcWithShifterOp::OpKind op_kind;
    119   int shift_amount = 0;
    120 
    121   HDataProcWithShifterOp::GetOpInfoFromInstruction(bitfield_op, &op_kind, &shift_amount);
    122   shift_amount &= use->GetType() == DataType::Type::kInt32
    123       ? kMaxIntShiftDistance
    124       : kMaxLongShiftDistance;
    125 
    126   if (HDataProcWithShifterOp::IsExtensionOp(op_kind)) {
    127     if (!use->IsAdd() && (!use->IsSub() || use->GetType() != DataType::Type::kInt64)) {
    128       return false;
    129     }
    130   // Shift by 1 is a special case that results in the same number and type of instructions
    131   // as this simplification, but potentially shorter code.
    132   } else if (type == DataType::Type::kInt64 && shift_amount == 1) {
    133     return false;
    134   }
    135 
    136   if (do_merge) {
    137     HDataProcWithShifterOp* alu_with_op =
    138         new (GetGraph()->GetAllocator()) HDataProcWithShifterOp(use,
    139                                                                 other_input,
    140                                                                 bitfield_op->InputAt(0),
    141                                                                 op_kind,
    142                                                                 shift_amount,
    143                                                                 use->GetDexPc());
    144     use->GetBlock()->ReplaceAndRemoveInstructionWith(use, alu_with_op);
    145     if (bitfield_op->GetUses().empty()) {
    146       bitfield_op->GetBlock()->RemoveInstruction(bitfield_op);
    147     }
    148     RecordSimplification();
    149   }
    150 
    151   return true;
    152 }
    153 
    154 // Merge a bitfield move instruction into its uses if it can be merged in all of them.
    155 bool InstructionSimplifierArmVisitor::TryMergeIntoUsersShifterOperand(HInstruction* bitfield_op) {
    156   DCHECK(CanFitInShifterOperand(bitfield_op));
    157 
    158   if (bitfield_op->HasEnvironmentUses()) {
    159     return false;
    160   }
    161 
    162   const HUseList<HInstruction*>& uses = bitfield_op->GetUses();
    163 
    164   // Check whether we can merge the instruction in all its users' shifter operand.
    165   for (const HUseListNode<HInstruction*>& use : uses) {
    166     HInstruction* user = use.GetUser();
    167     if (!HasShifterOperand(user, InstructionSet::kArm)) {
    168       return false;
    169     }
    170     if (!CanMergeIntoShifterOperand(user, bitfield_op)) {
    171       return false;
    172     }
    173   }
    174 
    175   // Merge the instruction into its uses.
    176   for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
    177     HInstruction* user = it->GetUser();
    178     // Increment `it` now because `*it` will disappear thanks to MergeIntoShifterOperand().
    179     ++it;
    180     bool merged = MergeIntoShifterOperand(user, bitfield_op);
    181     DCHECK(merged);
    182   }
    183 
    184   return true;
    185 }
    186 
    187 void InstructionSimplifierArmVisitor::VisitAnd(HAnd* instruction) {
    188   if (TryMergeNegatedInput(instruction)) {
    189     RecordSimplification();
    190   }
    191 }
    192 
    193 void InstructionSimplifierArmVisitor::VisitArrayGet(HArrayGet* instruction) {
    194   size_t data_offset = CodeGenerator::GetArrayDataOffset(instruction);
    195   DataType::Type type = instruction->GetType();
    196 
    197   // TODO: Implement reading (length + compression) for String compression feature from
    198   // negative offset (count_offset - data_offset). Thumb2Assembler (now removed) did
    199   // not support T4 encoding of "LDR (immediate)", but ArmVIXLMacroAssembler might.
    200   // Don't move array pointer if it is charAt because we need to take the count first.
    201   if (mirror::kUseStringCompression && instruction->IsStringCharAt()) {
    202     return;
    203   }
    204 
    205   if (type == DataType::Type::kInt64
    206       || type == DataType::Type::kFloat32
    207       || type == DataType::Type::kFloat64) {
    208     // T32 doesn't support ShiftedRegOffset mem address mode for these types
    209     // to enable optimization.
    210     return;
    211   }
    212 
    213   if (TryExtractArrayAccessAddress(instruction,
    214                                    instruction->GetArray(),
    215                                    instruction->GetIndex(),
    216                                    data_offset)) {
    217     RecordSimplification();
    218   }
    219 }
    220 
    221 void InstructionSimplifierArmVisitor::VisitArraySet(HArraySet* instruction) {
    222   size_t access_size = DataType::Size(instruction->GetComponentType());
    223   size_t data_offset = mirror::Array::DataOffset(access_size).Uint32Value();
    224   DataType::Type type = instruction->GetComponentType();
    225 
    226   if (type == DataType::Type::kInt64
    227       || type == DataType::Type::kFloat32
    228       || type == DataType::Type::kFloat64) {
    229     // T32 doesn't support ShiftedRegOffset mem address mode for these types
    230     // to enable optimization.
    231     return;
    232   }
    233 
    234   if (TryExtractArrayAccessAddress(instruction,
    235                                    instruction->GetArray(),
    236                                    instruction->GetIndex(),
    237                                    data_offset)) {
    238     RecordSimplification();
    239   }
    240 }
    241 
    242 void InstructionSimplifierArmVisitor::VisitMul(HMul* instruction) {
    243   if (TryCombineMultiplyAccumulate(instruction, InstructionSet::kArm)) {
    244     RecordSimplification();
    245   }
    246 }
    247 
    248 void InstructionSimplifierArmVisitor::VisitOr(HOr* instruction) {
    249   if (TryMergeNegatedInput(instruction)) {
    250     RecordSimplification();
    251   }
    252 }
    253 
    254 void InstructionSimplifierArmVisitor::VisitShl(HShl* instruction) {
    255   if (instruction->InputAt(1)->IsConstant()) {
    256     TryMergeIntoUsersShifterOperand(instruction);
    257   }
    258 }
    259 
    260 void InstructionSimplifierArmVisitor::VisitShr(HShr* instruction) {
    261   if (instruction->InputAt(1)->IsConstant()) {
    262     TryMergeIntoUsersShifterOperand(instruction);
    263   }
    264 }
    265 
    266 void InstructionSimplifierArmVisitor::VisitTypeConversion(HTypeConversion* instruction) {
    267   DataType::Type result_type = instruction->GetResultType();
    268   DataType::Type input_type = instruction->GetInputType();
    269 
    270   if (input_type == result_type) {
    271     // We let the arch-independent code handle this.
    272     return;
    273   }
    274 
    275   if (DataType::IsIntegralType(result_type) && DataType::IsIntegralType(input_type)) {
    276     TryMergeIntoUsersShifterOperand(instruction);
    277   }
    278 }
    279 
    280 void InstructionSimplifierArmVisitor::VisitUShr(HUShr* instruction) {
    281   if (instruction->InputAt(1)->IsConstant()) {
    282     TryMergeIntoUsersShifterOperand(instruction);
    283   }
    284 }
    285 
    286 void InstructionSimplifierArm::Run() {
    287   InstructionSimplifierArmVisitor visitor(graph_, stats_);
    288   visitor.VisitReversePostOrder();
    289 }
    290 
    291 }  // namespace arm
    292 }  // namespace art
    293