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