Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 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 | |
Roland Levillain | 75be283 | 2014-10-17 17:02:00 +0100 | [diff] [blame] | 17 | #include "constant_folding.h" |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 18 | |
| 19 | namespace art { |
| 20 | |
Alexandre Rames | b2fd7bc | 2015-03-11 16:48:16 +0000 | [diff] [blame] | 21 | // This visitor tries to simplify operations that yield a constant. For example |
| 22 | // `input * 0` is replaced by a null constant. |
| 23 | class InstructionWithAbsorbingInputSimplifier : public HGraphVisitor { |
| 24 | public: |
| 25 | explicit InstructionWithAbsorbingInputSimplifier(HGraph* graph) : HGraphVisitor(graph) {} |
| 26 | |
| 27 | private: |
| 28 | void VisitShift(HBinaryOperation* shift); |
| 29 | |
| 30 | void VisitAnd(HAnd* instruction) OVERRIDE; |
| 31 | void VisitMul(HMul* instruction) OVERRIDE; |
| 32 | void VisitOr(HOr* instruction) OVERRIDE; |
| 33 | void VisitRem(HRem* instruction) OVERRIDE; |
| 34 | void VisitShl(HShl* instruction) OVERRIDE; |
| 35 | void VisitShr(HShr* instruction) OVERRIDE; |
| 36 | void VisitSub(HSub* instruction) OVERRIDE; |
| 37 | void VisitUShr(HUShr* instruction) OVERRIDE; |
| 38 | void VisitXor(HXor* instruction) OVERRIDE; |
| 39 | }; |
| 40 | |
Roland Levillain | 75be283 | 2014-10-17 17:02:00 +0100 | [diff] [blame] | 41 | void HConstantFolding::Run() { |
Alexandre Rames | b2fd7bc | 2015-03-11 16:48:16 +0000 | [diff] [blame] | 42 | InstructionWithAbsorbingInputSimplifier simplifier(graph_); |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 43 | // Process basic blocks in reverse post-order in the dominator tree, |
| 44 | // so that an instruction turned into a constant, used as input of |
| 45 | // another instruction, may possibly be used to turn that second |
| 46 | // instruction into a constant as well. |
| 47 | for (HReversePostOrderIterator it(*graph_); !it.Done(); it.Advance()) { |
| 48 | HBasicBlock* block = it.Current(); |
| 49 | // Traverse this block's instructions in (forward) order and |
| 50 | // replace the ones that can be statically evaluated by a |
| 51 | // compile-time counterpart. |
Andreas Gampe | 277ccbd | 2014-11-03 21:36:10 -0800 | [diff] [blame] | 52 | for (HInstructionIterator inst_it(block->GetInstructions()); |
| 53 | !inst_it.Done(); inst_it.Advance()) { |
| 54 | HInstruction* inst = inst_it.Current(); |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 55 | if (inst->IsBinaryOperation()) { |
Roland Levillain | 9240d6a | 2014-10-20 16:47:04 +0100 | [diff] [blame] | 56 | // Constant folding: replace `op(a, b)' with a constant at |
| 57 | // compile time if `a' and `b' are both constants. |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 58 | HConstant* constant = |
Roland Levillain | 9240d6a | 2014-10-20 16:47:04 +0100 | [diff] [blame] | 59 | inst->AsBinaryOperation()->TryStaticEvaluation(); |
| 60 | if (constant != nullptr) { |
| 61 | inst->GetBlock()->ReplaceAndRemoveInstructionWith(inst, constant); |
Alexandre Rames | b2fd7bc | 2015-03-11 16:48:16 +0000 | [diff] [blame] | 62 | } else { |
| 63 | inst->Accept(&simplifier); |
Roland Levillain | 9240d6a | 2014-10-20 16:47:04 +0100 | [diff] [blame] | 64 | } |
| 65 | } else if (inst->IsUnaryOperation()) { |
| 66 | // Constant folding: replace `op(a)' with a constant at compile |
| 67 | // time if `a' is a constant. |
| 68 | HConstant* constant = |
| 69 | inst->AsUnaryOperation()->TryStaticEvaluation(); |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 70 | if (constant != nullptr) { |
| 71 | inst->GetBlock()->ReplaceAndRemoveInstructionWith(inst, constant); |
| 72 | } |
Alexandre Rames | b2fd7bc | 2015-03-11 16:48:16 +0000 | [diff] [blame] | 73 | } else if (inst->IsDivZeroCheck()) { |
| 74 | // We can safely remove the check if the input is a non-null constant. |
| 75 | HDivZeroCheck* check = inst->AsDivZeroCheck(); |
| 76 | HInstruction* check_input = check->InputAt(0); |
| 77 | if (check_input->IsConstant() && !check_input->AsConstant()->IsZero()) { |
| 78 | check->ReplaceWith(check_input); |
| 79 | check->GetBlock()->RemoveInstruction(check); |
| 80 | } |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 81 | } |
| 82 | } |
| 83 | } |
| 84 | } |
| 85 | |
Alexandre Rames | b2fd7bc | 2015-03-11 16:48:16 +0000 | [diff] [blame] | 86 | void InstructionWithAbsorbingInputSimplifier::VisitShift(HBinaryOperation* instruction) { |
| 87 | DCHECK(instruction->IsShl() || instruction->IsShr() || instruction->IsUShr()); |
| 88 | HInstruction* left = instruction->GetLeft(); |
| 89 | if (left->IsConstant() && left->AsConstant()->IsZero()) { |
| 90 | // Replace code looking like |
| 91 | // SHL dst, 0, shift_amount |
| 92 | // with |
| 93 | // CONSTANT 0 |
| 94 | instruction->ReplaceWith(left); |
| 95 | instruction->GetBlock()->RemoveInstruction(instruction); |
| 96 | } |
| 97 | } |
| 98 | |
| 99 | void InstructionWithAbsorbingInputSimplifier::VisitAnd(HAnd* instruction) { |
| 100 | HConstant* input_cst = instruction->GetConstantRight(); |
| 101 | if ((input_cst != nullptr) && input_cst->IsZero()) { |
| 102 | // Replace code looking like |
| 103 | // AND dst, src, 0 |
| 104 | // with |
| 105 | // CONSTANT 0 |
| 106 | instruction->ReplaceWith(input_cst); |
| 107 | instruction->GetBlock()->RemoveInstruction(instruction); |
| 108 | } |
| 109 | } |
| 110 | |
| 111 | void InstructionWithAbsorbingInputSimplifier::VisitMul(HMul* instruction) { |
| 112 | HConstant* input_cst = instruction->GetConstantRight(); |
| 113 | Primitive::Type type = instruction->GetType(); |
| 114 | if (Primitive::IsIntOrLongType(type) && |
| 115 | (input_cst != nullptr) && input_cst->IsZero()) { |
| 116 | // Replace code looking like |
| 117 | // MUL dst, src, 0 |
| 118 | // with |
| 119 | // CONSTANT 0 |
| 120 | // Integral multiplication by zero always yields zero, but floating-point |
| 121 | // multiplication by zero does not always do. For example `Infinity * 0.0` |
| 122 | // should yield a NaN. |
| 123 | instruction->ReplaceWith(input_cst); |
| 124 | instruction->GetBlock()->RemoveInstruction(instruction); |
| 125 | } |
| 126 | } |
| 127 | |
| 128 | void InstructionWithAbsorbingInputSimplifier::VisitOr(HOr* instruction) { |
| 129 | HConstant* input_cst = instruction->GetConstantRight(); |
| 130 | |
| 131 | if (input_cst == nullptr) { |
| 132 | return; |
| 133 | } |
| 134 | |
| 135 | if (Int64FromConstant(input_cst) == -1) { |
| 136 | // Replace code looking like |
| 137 | // OR dst, src, 0xFFF...FF |
| 138 | // with |
| 139 | // CONSTANT 0xFFF...FF |
| 140 | instruction->ReplaceWith(input_cst); |
| 141 | instruction->GetBlock()->RemoveInstruction(instruction); |
| 142 | } |
| 143 | } |
| 144 | |
| 145 | void InstructionWithAbsorbingInputSimplifier::VisitRem(HRem* instruction) { |
| 146 | Primitive::Type type = instruction->GetType(); |
| 147 | |
| 148 | if (!Primitive::IsIntegralType(type)) { |
| 149 | return; |
| 150 | } |
| 151 | |
| 152 | HBasicBlock* block = instruction->GetBlock(); |
| 153 | |
| 154 | if (instruction->GetLeft()->IsConstant() && |
| 155 | instruction->GetLeft()->AsConstant()->IsZero()) { |
| 156 | // Replace code looking like |
| 157 | // REM dst, 0, src |
| 158 | // with |
| 159 | // CONSTANT 0 |
| 160 | instruction->ReplaceWith(instruction->GetLeft()); |
| 161 | block->RemoveInstruction(instruction); |
| 162 | } |
| 163 | |
| 164 | HConstant* cst_right = instruction->GetRight()->AsConstant(); |
| 165 | if (((cst_right != nullptr) && |
| 166 | (cst_right->IsOne() || cst_right->IsMinusOne())) || |
| 167 | (instruction->GetLeft() == instruction->GetRight())) { |
| 168 | // Replace code looking like |
| 169 | // REM dst, src, 1 |
| 170 | // or |
| 171 | // REM dst, src, -1 |
| 172 | // or |
| 173 | // REM dst, src, src |
| 174 | // with |
| 175 | // CONSTANT 0 |
| 176 | ArenaAllocator* allocator = GetGraph()->GetArena(); |
| 177 | block->ReplaceAndRemoveInstructionWith(instruction, |
| 178 | HConstant::NewConstant(allocator, type, 0)); |
| 179 | } |
| 180 | } |
| 181 | |
| 182 | void InstructionWithAbsorbingInputSimplifier::VisitShl(HShl* instruction) { |
| 183 | VisitShift(instruction); |
| 184 | } |
| 185 | |
| 186 | void InstructionWithAbsorbingInputSimplifier::VisitShr(HShr* instruction) { |
| 187 | VisitShift(instruction); |
| 188 | } |
| 189 | |
| 190 | void InstructionWithAbsorbingInputSimplifier::VisitSub(HSub* instruction) { |
| 191 | Primitive::Type type = instruction->GetType(); |
| 192 | |
| 193 | if (!Primitive::IsIntegralType(type)) { |
| 194 | return; |
| 195 | } |
| 196 | |
| 197 | HBasicBlock* block = instruction->GetBlock(); |
| 198 | ArenaAllocator* allocator = GetGraph()->GetArena(); |
| 199 | |
| 200 | // We assume that GVN has run before, so we only perform a pointer |
| 201 | // comparison. If for some reason the values are equal but the pointers are |
| 202 | // different, we are still correct and only miss an optimisation |
| 203 | // opportunity. |
| 204 | if (instruction->GetLeft() == instruction->GetRight()) { |
| 205 | // Replace code looking like |
| 206 | // SUB dst, src, src |
| 207 | // with |
| 208 | // CONSTANT 0 |
| 209 | // Note that we cannot optimise `x - x` to `0` for floating-point. It does |
| 210 | // not work when `x` is an infinity. |
| 211 | block->ReplaceAndRemoveInstructionWith(instruction, |
| 212 | HConstant::NewConstant(allocator, type, 0)); |
| 213 | } |
| 214 | } |
| 215 | |
| 216 | void InstructionWithAbsorbingInputSimplifier::VisitUShr(HUShr* instruction) { |
| 217 | VisitShift(instruction); |
| 218 | } |
| 219 | |
| 220 | void InstructionWithAbsorbingInputSimplifier::VisitXor(HXor* instruction) { |
| 221 | if (instruction->GetLeft() == instruction->GetRight()) { |
| 222 | // Replace code looking like |
| 223 | // XOR dst, src, src |
| 224 | // with |
| 225 | // CONSTANT 0 |
| 226 | Primitive::Type type = instruction->GetType(); |
| 227 | HBasicBlock* block = instruction->GetBlock(); |
| 228 | ArenaAllocator* allocator = GetGraph()->GetArena(); |
| 229 | |
| 230 | block->ReplaceAndRemoveInstructionWith(instruction, |
| 231 | HConstant::NewConstant(allocator, type, 0)); |
| 232 | } |
| 233 | } |
| 234 | |
Roland Levillain | 556c3d1 | 2014-09-18 15:25:07 +0100 | [diff] [blame] | 235 | } // namespace art |