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