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