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