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 operations that yield a constant. For example
22 // `input * 0` is replaced by a null constant.
23 class InstructionWithAbsorbingInputSimplifier : public HGraphVisitor {
24  public:
InstructionWithAbsorbingInputSimplifier(HGraph * graph)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 
Run()41 void 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 
VisitShift(HBinaryOperation * instruction)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 
VisitAnd(HAnd * instruction)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 
VisitMul(HMul * instruction)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 
VisitOr(HOr * instruction)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 
VisitRem(HRem * instruction)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     instruction->ReplaceWith(GetGraph()->GetConstant(type, 0));
177     block->RemoveInstruction(instruction);
178   }
179 }
180 
VisitShl(HShl * instruction)181 void InstructionWithAbsorbingInputSimplifier::VisitShl(HShl* instruction) {
182   VisitShift(instruction);
183 }
184 
VisitShr(HShr * instruction)185 void InstructionWithAbsorbingInputSimplifier::VisitShr(HShr* instruction) {
186   VisitShift(instruction);
187 }
188 
VisitSub(HSub * instruction)189 void 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 
VisitUShr(HUShr * instruction)214 void InstructionWithAbsorbingInputSimplifier::VisitUShr(HUShr* instruction) {
215   VisitShift(instruction);
216 }
217 
VisitXor(HXor * instruction)218 void 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