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 operations that yield a constant. For example
22// `input * 0` is replaced by a null constant.
23class 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
41void HConstantFolding::Run() {
42  InstructionWithAbsorbingInputSimplifier simplifier(graph_);
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.
52    for (HInstructionIterator inst_it(block->GetInstructions());
53         !inst_it.Done(); inst_it.Advance()) {
54      HInstruction* inst = inst_it.Current();
55      if (inst->IsBinaryOperation()) {
56        // Constant folding: replace `op(a, b)' with a constant at
57        // compile time if `a' and `b' are both constants.
58        HConstant* constant = inst->AsBinaryOperation()->TryStaticEvaluation();
59        if (constant != nullptr) {
60          inst->ReplaceWith(constant);
61          inst->GetBlock()->RemoveInstruction(inst);
62        } else {
63          inst->Accept(&simplifier);
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 = inst->AsUnaryOperation()->TryStaticEvaluation();
69        if (constant != nullptr) {
70          inst->ReplaceWith(constant);
71          inst->GetBlock()->RemoveInstruction(inst);
72        }
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        }
81      }
82    }
83  }
84}
85
86void 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
99void 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
111void 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
128void 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
145void 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    instruction->ReplaceWith(GetGraph()->GetConstant(type, 0));
177    block->RemoveInstruction(instruction);
178  }
179}
180
181void InstructionWithAbsorbingInputSimplifier::VisitShl(HShl* instruction) {
182  VisitShift(instruction);
183}
184
185void InstructionWithAbsorbingInputSimplifier::VisitShr(HShr* instruction) {
186  VisitShift(instruction);
187}
188
189void InstructionWithAbsorbingInputSimplifier::VisitSub(HSub* instruction) {
190  Primitive::Type type = instruction->GetType();
191
192  if (!Primitive::IsIntegralType(type)) {
193    return;
194  }
195
196  HBasicBlock* block = instruction->GetBlock();
197
198  // We assume that GVN has run before, so we only perform a pointer
199  // comparison.  If for some reason the values are equal but the pointers are
200  // different, we are still correct and only miss an optimisation
201  // opportunity.
202  if (instruction->GetLeft() == instruction->GetRight()) {
203    // Replace code looking like
204    //    SUB dst, src, src
205    // with
206    //    CONSTANT 0
207    // Note that we cannot optimise `x - x` to `0` for floating-point. It does
208    // not work when `x` is an infinity.
209    instruction->ReplaceWith(GetGraph()->GetConstant(type, 0));
210    block->RemoveInstruction(instruction);
211  }
212}
213
214void InstructionWithAbsorbingInputSimplifier::VisitUShr(HUShr* instruction) {
215  VisitShift(instruction);
216}
217
218void InstructionWithAbsorbingInputSimplifier::VisitXor(HXor* instruction) {
219  if (instruction->GetLeft() == instruction->GetRight()) {
220    // Replace code looking like
221    //    XOR dst, src, src
222    // with
223    //    CONSTANT 0
224    Primitive::Type type = instruction->GetType();
225    HBasicBlock* block = instruction->GetBlock();
226    instruction->ReplaceWith(GetGraph()->GetConstant(type, 0));
227    block->RemoveInstruction(instruction);
228  }
229}
230
231}  // namespace art
232