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 "constant_folding.h" 18 19namespace art { 20 21// This visitor tries to simplify instructions that can be evaluated 22// as constants. 23class HConstantFoldingVisitor : public HGraphDelegateVisitor { 24 public: 25 explicit HConstantFoldingVisitor(HGraph* graph) 26 : HGraphDelegateVisitor(graph) {} 27 28 private: 29 void VisitBasicBlock(HBasicBlock* block) OVERRIDE; 30 31 void VisitUnaryOperation(HUnaryOperation* inst) OVERRIDE; 32 void VisitBinaryOperation(HBinaryOperation* inst) OVERRIDE; 33 34 void VisitTypeConversion(HTypeConversion* inst) OVERRIDE; 35 void VisitDivZeroCheck(HDivZeroCheck* inst) OVERRIDE; 36 37 DISALLOW_COPY_AND_ASSIGN(HConstantFoldingVisitor); 38}; 39 40// This visitor tries to simplify operations with an absorbing input, 41// yielding a constant. For example `input * 0` is replaced by a 42// null constant. 43class InstructionWithAbsorbingInputSimplifier : public HGraphVisitor { 44 public: 45 explicit InstructionWithAbsorbingInputSimplifier(HGraph* graph) : HGraphVisitor(graph) {} 46 47 private: 48 void VisitShift(HBinaryOperation* shift); 49 50 void VisitAbove(HAbove* instruction) OVERRIDE; 51 void VisitAboveOrEqual(HAboveOrEqual* instruction) OVERRIDE; 52 void VisitBelow(HBelow* instruction) OVERRIDE; 53 void VisitBelowOrEqual(HBelowOrEqual* instruction) OVERRIDE; 54 55 void VisitAnd(HAnd* instruction) OVERRIDE; 56 void VisitCompare(HCompare* instruction) OVERRIDE; 57 void VisitMul(HMul* instruction) OVERRIDE; 58 void VisitOr(HOr* instruction) OVERRIDE; 59 void VisitRem(HRem* instruction) OVERRIDE; 60 void VisitShl(HShl* instruction) OVERRIDE; 61 void VisitShr(HShr* instruction) OVERRIDE; 62 void VisitSub(HSub* instruction) OVERRIDE; 63 void VisitUShr(HUShr* instruction) OVERRIDE; 64 void VisitXor(HXor* instruction) OVERRIDE; 65}; 66 67 68void HConstantFolding::Run() { 69 HConstantFoldingVisitor visitor(graph_); 70 // Process basic blocks in reverse post-order in the dominator tree, 71 // so that an instruction turned into a constant, used as input of 72 // another instruction, may possibly be used to turn that second 73 // instruction into a constant as well. 74 visitor.VisitReversePostOrder(); 75} 76 77 78void HConstantFoldingVisitor::VisitBasicBlock(HBasicBlock* block) { 79 // Traverse this block's instructions (phis don't need to be 80 // processed) in (forward) order and replace the ones that can be 81 // statically evaluated by a compile-time counterpart. 82 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) { 83 it.Current()->Accept(this); 84 } 85} 86 87void HConstantFoldingVisitor::VisitUnaryOperation(HUnaryOperation* inst) { 88 // Constant folding: replace `op(a)' with a constant at compile 89 // time if `a' is a constant. 90 HConstant* constant = inst->TryStaticEvaluation(); 91 if (constant != nullptr) { 92 inst->ReplaceWith(constant); 93 inst->GetBlock()->RemoveInstruction(inst); 94 } 95} 96 97void HConstantFoldingVisitor::VisitBinaryOperation(HBinaryOperation* inst) { 98 // Constant folding: replace `op(a, b)' with a constant at 99 // compile time if `a' and `b' are both constants. 100 HConstant* constant = inst->TryStaticEvaluation(); 101 if (constant != nullptr) { 102 inst->ReplaceWith(constant); 103 inst->GetBlock()->RemoveInstruction(inst); 104 } else { 105 InstructionWithAbsorbingInputSimplifier simplifier(GetGraph()); 106 inst->Accept(&simplifier); 107 } 108} 109 110void HConstantFoldingVisitor::VisitTypeConversion(HTypeConversion* inst) { 111 // Constant folding: replace `TypeConversion(a)' with a constant at 112 // compile time if `a' is a constant. 113 HConstant* constant = inst->AsTypeConversion()->TryStaticEvaluation(); 114 if (constant != nullptr) { 115 inst->ReplaceWith(constant); 116 inst->GetBlock()->RemoveInstruction(inst); 117 } 118} 119 120void HConstantFoldingVisitor::VisitDivZeroCheck(HDivZeroCheck* inst) { 121 // We can safely remove the check if the input is a non-null constant. 122 HInstruction* check_input = inst->InputAt(0); 123 if (check_input->IsConstant() && !check_input->AsConstant()->IsArithmeticZero()) { 124 inst->ReplaceWith(check_input); 125 inst->GetBlock()->RemoveInstruction(inst); 126 } 127} 128 129 130void InstructionWithAbsorbingInputSimplifier::VisitShift(HBinaryOperation* instruction) { 131 DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr()); 132 HInstruction* left = instruction->GetLeft(); 133 if (left->IsConstant() && left->AsConstant()->IsArithmeticZero()) { 134 // Replace code looking like 135 // SHL dst, 0, shift_amount 136 // with 137 // CONSTANT 0 138 instruction->ReplaceWith(left); 139 instruction->GetBlock()->RemoveInstruction(instruction); 140 } 141} 142 143void InstructionWithAbsorbingInputSimplifier::VisitAbove(HAbove* instruction) { 144 if (instruction->GetLeft()->IsConstant() && 145 instruction->GetLeft()->AsConstant()->IsArithmeticZero()) { 146 // Replace code looking like 147 // ABOVE dst, 0, src // unsigned 0 > src is always false 148 // with 149 // CONSTANT false 150 instruction->ReplaceWith(GetGraph()->GetConstant(Primitive::kPrimBoolean, 0)); 151 instruction->GetBlock()->RemoveInstruction(instruction); 152 } 153} 154 155void InstructionWithAbsorbingInputSimplifier::VisitAboveOrEqual(HAboveOrEqual* instruction) { 156 if (instruction->GetRight()->IsConstant() && 157 instruction->GetRight()->AsConstant()->IsArithmeticZero()) { 158 // Replace code looking like 159 // ABOVE_OR_EQUAL dst, src, 0 // unsigned src >= 0 is always true 160 // with 161 // CONSTANT true 162 instruction->ReplaceWith(GetGraph()->GetConstant(Primitive::kPrimBoolean, 1)); 163 instruction->GetBlock()->RemoveInstruction(instruction); 164 } 165} 166 167void InstructionWithAbsorbingInputSimplifier::VisitBelow(HBelow* instruction) { 168 if (instruction->GetRight()->IsConstant() && 169 instruction->GetRight()->AsConstant()->IsArithmeticZero()) { 170 // Replace code looking like 171 // BELOW dst, src, 0 // unsigned src < 0 is always false 172 // with 173 // CONSTANT false 174 instruction->ReplaceWith(GetGraph()->GetConstant(Primitive::kPrimBoolean, 0)); 175 instruction->GetBlock()->RemoveInstruction(instruction); 176 } 177} 178 179void InstructionWithAbsorbingInputSimplifier::VisitBelowOrEqual(HBelowOrEqual* instruction) { 180 if (instruction->GetLeft()->IsConstant() && 181 instruction->GetLeft()->AsConstant()->IsArithmeticZero()) { 182 // Replace code looking like 183 // BELOW_OR_EQUAL dst, 0, src // unsigned 0 <= src is always true 184 // with 185 // CONSTANT true 186 instruction->ReplaceWith(GetGraph()->GetConstant(Primitive::kPrimBoolean, 1)); 187 instruction->GetBlock()->RemoveInstruction(instruction); 188 } 189} 190 191void InstructionWithAbsorbingInputSimplifier::VisitAnd(HAnd* instruction) { 192 HConstant* input_cst = instruction->GetConstantRight(); 193 if ((input_cst != nullptr) && input_cst->IsZeroBitPattern()) { 194 // Replace code looking like 195 // AND dst, src, 0 196 // with 197 // CONSTANT 0 198 instruction->ReplaceWith(input_cst); 199 instruction->GetBlock()->RemoveInstruction(instruction); 200 } 201} 202 203void InstructionWithAbsorbingInputSimplifier::VisitCompare(HCompare* instruction) { 204 HConstant* input_cst = instruction->GetConstantRight(); 205 if (input_cst != nullptr) { 206 HInstruction* input_value = instruction->GetLeastConstantLeft(); 207 if (Primitive::IsFloatingPointType(input_value->GetType()) && 208 ((input_cst->IsFloatConstant() && input_cst->AsFloatConstant()->IsNaN()) || 209 (input_cst->IsDoubleConstant() && input_cst->AsDoubleConstant()->IsNaN()))) { 210 // Replace code looking like 211 // CMP{G,L}-{FLOAT,DOUBLE} dst, src, NaN 212 // with 213 // CONSTANT +1 (gt bias) 214 // or 215 // CONSTANT -1 (lt bias) 216 instruction->ReplaceWith(GetGraph()->GetConstant(Primitive::kPrimInt, 217 (instruction->IsGtBias() ? 1 : -1))); 218 instruction->GetBlock()->RemoveInstruction(instruction); 219 } 220 } 221} 222 223void InstructionWithAbsorbingInputSimplifier::VisitMul(HMul* instruction) { 224 HConstant* input_cst = instruction->GetConstantRight(); 225 Primitive::Type type = instruction->GetType(); 226 if (Primitive::IsIntOrLongType(type) && 227 (input_cst != nullptr) && input_cst->IsArithmeticZero()) { 228 // Replace code looking like 229 // MUL dst, src, 0 230 // with 231 // CONSTANT 0 232 // Integral multiplication by zero always yields zero, but floating-point 233 // multiplication by zero does not always do. For example `Infinity * 0.0` 234 // should yield a NaN. 235 instruction->ReplaceWith(input_cst); 236 instruction->GetBlock()->RemoveInstruction(instruction); 237 } 238} 239 240void InstructionWithAbsorbingInputSimplifier::VisitOr(HOr* instruction) { 241 HConstant* input_cst = instruction->GetConstantRight(); 242 243 if (input_cst == nullptr) { 244 return; 245 } 246 247 if (Int64FromConstant(input_cst) == -1) { 248 // Replace code looking like 249 // OR dst, src, 0xFFF...FF 250 // with 251 // CONSTANT 0xFFF...FF 252 instruction->ReplaceWith(input_cst); 253 instruction->GetBlock()->RemoveInstruction(instruction); 254 } 255} 256 257void InstructionWithAbsorbingInputSimplifier::VisitRem(HRem* instruction) { 258 Primitive::Type type = instruction->GetType(); 259 260 if (!Primitive::IsIntegralType(type)) { 261 return; 262 } 263 264 HBasicBlock* block = instruction->GetBlock(); 265 266 if (instruction->GetLeft()->IsConstant() && 267 instruction->GetLeft()->AsConstant()->IsArithmeticZero()) { 268 // Replace code looking like 269 // REM dst, 0, src 270 // with 271 // CONSTANT 0 272 instruction->ReplaceWith(instruction->GetLeft()); 273 block->RemoveInstruction(instruction); 274 } 275 276 HConstant* cst_right = instruction->GetRight()->AsConstant(); 277 if (((cst_right != nullptr) && 278 (cst_right->IsOne() || cst_right->IsMinusOne())) || 279 (instruction->GetLeft() == instruction->GetRight())) { 280 // Replace code looking like 281 // REM dst, src, 1 282 // or 283 // REM dst, src, -1 284 // or 285 // REM dst, src, src 286 // with 287 // CONSTANT 0 288 instruction->ReplaceWith(GetGraph()->GetConstant(type, 0)); 289 block->RemoveInstruction(instruction); 290 } 291} 292 293void InstructionWithAbsorbingInputSimplifier::VisitShl(HShl* instruction) { 294 VisitShift(instruction); 295} 296 297void InstructionWithAbsorbingInputSimplifier::VisitShr(HShr* instruction) { 298 VisitShift(instruction); 299} 300 301void InstructionWithAbsorbingInputSimplifier::VisitSub(HSub* instruction) { 302 Primitive::Type type = instruction->GetType(); 303 304 if (!Primitive::IsIntegralType(type)) { 305 return; 306 } 307 308 HBasicBlock* block = instruction->GetBlock(); 309 310 // We assume that GVN has run before, so we only perform a pointer 311 // comparison. If for some reason the values are equal but the pointers are 312 // different, we are still correct and only miss an optimization 313 // opportunity. 314 if (instruction->GetLeft() == instruction->GetRight()) { 315 // Replace code looking like 316 // SUB dst, src, src 317 // with 318 // CONSTANT 0 319 // Note that we cannot optimize `x - x` to `0` for floating-point. It does 320 // not work when `x` is an infinity. 321 instruction->ReplaceWith(GetGraph()->GetConstant(type, 0)); 322 block->RemoveInstruction(instruction); 323 } 324} 325 326void InstructionWithAbsorbingInputSimplifier::VisitUShr(HUShr* instruction) { 327 VisitShift(instruction); 328} 329 330void InstructionWithAbsorbingInputSimplifier::VisitXor(HXor* instruction) { 331 if (instruction->GetLeft() == instruction->GetRight()) { 332 // Replace code looking like 333 // XOR dst, src, src 334 // with 335 // CONSTANT 0 336 Primitive::Type type = instruction->GetType(); 337 HBasicBlock* block = instruction->GetBlock(); 338 instruction->ReplaceWith(GetGraph()->GetConstant(type, 0)); 339 block->RemoveInstruction(instruction); 340 } 341} 342 343} // namespace art 344