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 // TODO: Support intermediate address for object arrays on arm. 206 if (type == DataType::Type::kReference) { 207 return; 208 } 209 210 if (type == DataType::Type::kInt64 211 || type == DataType::Type::kFloat32 212 || type == DataType::Type::kFloat64) { 213 // T32 doesn't support ShiftedRegOffset mem address mode for these types 214 // to enable optimization. 215 return; 216 } 217 218 if (TryExtractArrayAccessAddress(instruction, 219 instruction->GetArray(), 220 instruction->GetIndex(), 221 data_offset)) { 222 RecordSimplification(); 223 } 224 } 225 226 void InstructionSimplifierArmVisitor::VisitArraySet(HArraySet* instruction) { 227 size_t access_size = DataType::Size(instruction->GetComponentType()); 228 size_t data_offset = mirror::Array::DataOffset(access_size).Uint32Value(); 229 DataType::Type type = instruction->GetComponentType(); 230 231 if (type == DataType::Type::kInt64 232 || type == DataType::Type::kFloat32 233 || type == DataType::Type::kFloat64) { 234 // T32 doesn't support ShiftedRegOffset mem address mode for these types 235 // to enable optimization. 236 return; 237 } 238 239 if (TryExtractArrayAccessAddress(instruction, 240 instruction->GetArray(), 241 instruction->GetIndex(), 242 data_offset)) { 243 RecordSimplification(); 244 } 245 } 246 247 void InstructionSimplifierArmVisitor::VisitMul(HMul* instruction) { 248 if (TryCombineMultiplyAccumulate(instruction, InstructionSet::kArm)) { 249 RecordSimplification(); 250 } 251 } 252 253 void InstructionSimplifierArmVisitor::VisitOr(HOr* instruction) { 254 if (TryMergeNegatedInput(instruction)) { 255 RecordSimplification(); 256 } 257 } 258 259 void InstructionSimplifierArmVisitor::VisitShl(HShl* instruction) { 260 if (instruction->InputAt(1)->IsConstant()) { 261 TryMergeIntoUsersShifterOperand(instruction); 262 } 263 } 264 265 void InstructionSimplifierArmVisitor::VisitShr(HShr* instruction) { 266 if (instruction->InputAt(1)->IsConstant()) { 267 TryMergeIntoUsersShifterOperand(instruction); 268 } 269 } 270 271 void InstructionSimplifierArmVisitor::VisitTypeConversion(HTypeConversion* instruction) { 272 DataType::Type result_type = instruction->GetResultType(); 273 DataType::Type input_type = instruction->GetInputType(); 274 275 if (input_type == result_type) { 276 // We let the arch-independent code handle this. 277 return; 278 } 279 280 if (DataType::IsIntegralType(result_type) && DataType::IsIntegralType(input_type)) { 281 TryMergeIntoUsersShifterOperand(instruction); 282 } 283 } 284 285 void InstructionSimplifierArmVisitor::VisitUShr(HUShr* instruction) { 286 if (instruction->InputAt(1)->IsConstant()) { 287 TryMergeIntoUsersShifterOperand(instruction); 288 } 289 } 290 291 bool InstructionSimplifierArm::Run() { 292 InstructionSimplifierArmVisitor visitor(graph_, stats_); 293 visitor.VisitReversePostOrder(); 294 return true; 295 } 296 297 } // namespace arm 298 } // namespace art 299