blob: 52f2d6ad90aa9a54bcc84ab22c7c156f5398d3e4 [file] [log] [blame]
 // Copyright (c) 2018 Google LLC. // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. #include "source/opt/scalar_analysis.h" #include #include #include #include #include #include #include // Simplifies scalar analysis DAGs. // // 1. Given a node passed to SimplifyExpression we first simplify the graph by // calling SimplifyPolynomial. This groups like nodes following basic arithmetic // rules, so multiple adds of the same load instruction could be grouped into a // single multiply of that instruction. SimplifyPolynomial will traverse the DAG // and build up an accumulator buffer for each class of instruction it finds. // For example take the loop: // for (i=0, i accumulators_; }; // From a |multiply| build up the accumulator objects. bool SENodeSimplifyImpl::AccumulatorsFromMultiply(SENode* multiply, bool negation) { if (multiply->GetChildren().size() != 2 || multiply->GetType() != SENode::Multiply) return false; SENode* operand_1 = multiply->GetChild(0); SENode* operand_2 = multiply->GetChild(1); SENode* value_unknown = nullptr; SENode* constant = nullptr; // Work out which operand is the unknown value. if (operand_1->GetType() == SENode::ValueUnknown || operand_1->GetType() == SENode::RecurrentAddExpr) value_unknown = operand_1; else if (operand_2->GetType() == SENode::ValueUnknown || operand_2->GetType() == SENode::RecurrentAddExpr) value_unknown = operand_2; // Work out which operand is the constant coefficient. if (operand_1->GetType() == SENode::Constant) constant = operand_1; else if (operand_2->GetType() == SENode::Constant) constant = operand_2; // If the expression is not a variable multiplied by a constant coefficient, // exit out. if (!(value_unknown && constant)) { return false; } int64_t sign = negation ? -1 : 1; auto iterator = accumulators_.find(value_unknown); int64_t new_value = constant->AsSEConstantNode()->FoldToSingleValue() * sign; // Add the result of the multiplication to the accumulators. if (iterator != accumulators_.end()) { (*iterator).second += new_value; } else { accumulators_.insert({value_unknown, new_value}); } return true; } SENode* SENodeSimplifyImpl::Simplify() { // We only handle graphs with an addition, multiplication, or negation, at the // root. if (node_->GetType() != SENode::Add && node_->GetType() != SENode::Multiply && node_->GetType() != SENode::Negative) return node_; SENode* simplified_polynomial = SimplifyPolynomial(); SERecurrentNode* recurrent_expr = nullptr; node_ = simplified_polynomial; // Fold recurrent expressions which are with respect to the same loop into a // single recurrent expression. simplified_polynomial = FoldRecurrentAddExpressions(simplified_polynomial); simplified_polynomial = EliminateZeroCoefficientRecurrents(simplified_polynomial); // Traverse the immediate children of the new node to find the recurrent // expression. If there is more than one there is nothing further we can do. for (SENode* child : simplified_polynomial->GetChildren()) { if (child->GetType() == SENode::RecurrentAddExpr) { recurrent_expr = child->AsSERecurrentNode(); } } // We need to count the number of unique recurrent expressions in the DAG to // ensure there is only one. for (auto child_iterator = simplified_polynomial->graph_begin(); child_iterator != simplified_polynomial->graph_end(); ++child_iterator) { if (child_iterator->GetType() == SENode::RecurrentAddExpr && recurrent_expr != child_iterator->AsSERecurrentNode()) { return simplified_polynomial; } } if (recurrent_expr) { return SimplifyRecurrentAddExpression(recurrent_expr); } return simplified_polynomial; } // Traverse the graph to build up the accumulator objects. void SENodeSimplifyImpl::GatherAccumulatorsFromChildNodes(SENode* new_node, SENode* child, bool negation) { int32_t sign = negation ? -1 : 1; if (child->GetType() == SENode::Constant) { // Collect all the constants and add them together. constant_accumulator_ += child->AsSEConstantNode()->FoldToSingleValue() * sign; } else if (child->GetType() == SENode::ValueUnknown || child->GetType() == SENode::RecurrentAddExpr) { // To rebuild the graph of X+X+X*2 into 4*X we count the occurrences of X // and create a new node of count*X after. X can either be a ValueUnknown or // a RecurrentAddExpr. The count for each X is stored in the accumulators_ // map. auto iterator = accumulators_.find(child); // If we've encountered this term before add to the accumulator for it. if (iterator == accumulators_.end()) accumulators_.insert({child, sign}); else iterator->second += sign; } else if (child->GetType() == SENode::Multiply) { if (!AccumulatorsFromMultiply(child, negation)) { new_node->AddChild(child); } } else if (child->GetType() == SENode::Add) { for (SENode* next_child : *child) { GatherAccumulatorsFromChildNodes(new_node, next_child, negation); } } else if (child->GetType() == SENode::Negative) { SENode* negated_node = child->GetChild(0); GatherAccumulatorsFromChildNodes(new_node, negated_node, !negation); } else { // If we can't work out how to fold the expression just add it back into // the graph. new_node->AddChild(child); } } SERecurrentNode* SENodeSimplifyImpl::UpdateCoefficient( SERecurrentNode* recurrent, int64_t coefficient_update) const { std::unique_ptr new_recurrent_node{new SERecurrentNode( recurrent->GetParentAnalysis(), recurrent->GetLoop())}; SENode* new_coefficient = analysis_.CreateMultiplyNode( recurrent->GetCoefficient(), analysis_.CreateConstant(coefficient_update)); // See if the node can be simplified. SENode* simplified = analysis_.SimplifyExpression(new_coefficient); if (simplified->GetType() != SENode::CanNotCompute) new_coefficient = simplified; if (coefficient_update < 0) { new_recurrent_node->AddOffset( analysis_.CreateNegation(recurrent->GetOffset())); } else { new_recurrent_node->AddOffset(recurrent->GetOffset()); } new_recurrent_node->AddCoefficient(new_coefficient); return analysis_.GetCachedOrAdd(std::move(new_recurrent_node)) ->AsSERecurrentNode(); } // Simplify all the terms in the polynomial function. SENode* SENodeSimplifyImpl::SimplifyPolynomial() { std::unique_ptr new_add{new SEAddNode(node_->GetParentAnalysis())}; // Traverse the graph and gather the accumulators from it. GatherAccumulatorsFromChildNodes(new_add.get(), node_, false); // Fold all the constants into a single constant node. if (constant_accumulator_ != 0) { new_add->AddChild(analysis_.CreateConstant(constant_accumulator_)); } for (auto& pair : accumulators_) { SENode* term = pair.first; int64_t count = pair.second; // We can eliminate the term completely. if (count == 0) continue; if (count == 1) { new_add->AddChild(term); } else if (count == -1 && term->GetType() != SENode::RecurrentAddExpr) { // If the count is -1 we can just add a negative version of that node, // unless it is a recurrent expression as we would rather the negative // goes on the recurrent expressions children. This makes it easier to // work with in other places. new_add->AddChild(analysis_.CreateNegation(term)); } else { // Output value unknown terms as count*term and output recurrent // expression terms as rec(offset, coefficient + count) offset and // coefficient are the same as in the original expression. if (term->GetType() == SENode::ValueUnknown) { SENode* count_as_constant = analysis_.CreateConstant(count); new_add->AddChild( analysis_.CreateMultiplyNode(count_as_constant, term)); } else { assert(term->GetType() == SENode::RecurrentAddExpr && "We only handle value unknowns or recurrent expressions"); // Create a new recurrent expression by adding the count to the // coefficient of the old one. new_add->AddChild(UpdateCoefficient(term->AsSERecurrentNode(), count)); } } } // If there is only one term in the addition left just return that term. if (new_add->GetChildren().size() == 1) { return new_add->GetChild(0); } // If there are no terms left in the addition just return 0. if (new_add->GetChildren().size() == 0) { return analysis_.CreateConstant(0); } return analysis_.GetCachedOrAdd(std::move(new_add)); } SENode* SENodeSimplifyImpl::FoldRecurrentAddExpressions(SENode* root) { std::unique_ptr new_node{new SEAddNode(&analysis_)}; // A mapping of loops to the list of recurrent expressions which are with // respect to those loops. std::map>> loops_to_recurrent{}; bool has_multiple_same_loop_recurrent_terms = false; for (SENode* child : *root) { bool negation = false; if (child->GetType() == SENode::Negative) { child = child->GetChild(0); negation = true; } if (child->GetType() == SENode::RecurrentAddExpr) { const Loop* loop = child->AsSERecurrentNode()->GetLoop(); SERecurrentNode* rec = child->AsSERecurrentNode(); if (loops_to_recurrent.find(loop) == loops_to_recurrent.end()) { loops_to_recurrent[loop] = {std::make_pair(rec, negation)}; } else { loops_to_recurrent[loop].push_back(std::make_pair(rec, negation)); has_multiple_same_loop_recurrent_terms = true; } } else { new_node->AddChild(child); } } if (!has_multiple_same_loop_recurrent_terms) return root; for (auto pair : loops_to_recurrent) { std::vector>& recurrent_expressions = pair.second; const Loop* loop = pair.first; std::unique_ptr new_coefficient{new SEAddNode(&analysis_)}; std::unique_ptr new_offset{new SEAddNode(&analysis_)}; for (auto node_pair : recurrent_expressions) { SERecurrentNode* node = node_pair.first; bool negative = node_pair.second; if (!negative) { new_coefficient->AddChild(node->GetCoefficient()); new_offset->AddChild(node->GetOffset()); } else { new_coefficient->AddChild( analysis_.CreateNegation(node->GetCoefficient())); new_offset->AddChild(analysis_.CreateNegation(node->GetOffset())); } } std::unique_ptr new_recurrent{ new SERecurrentNode(&analysis_, loop)}; SENode* new_coefficient_simplified = analysis_.SimplifyExpression(new_coefficient.get()); SENode* new_offset_simplified = analysis_.SimplifyExpression(new_offset.get()); if (new_coefficient_simplified->GetType() == SENode::Constant && new_coefficient_simplified->AsSEConstantNode()->FoldToSingleValue() == 0) { return new_offset_simplified; } new_recurrent->AddCoefficient(new_coefficient_simplified); new_recurrent->AddOffset(new_offset_simplified); new_node->AddChild(analysis_.GetCachedOrAdd(std::move(new_recurrent))); } // If we only have one child in the add just return that. if (new_node->GetChildren().size() == 1) { return new_node->GetChild(0); } return analysis_.GetCachedOrAdd(std::move(new_node)); } SENode* SENodeSimplifyImpl::EliminateZeroCoefficientRecurrents(SENode* node) { if (node->GetType() != SENode::Add) return node; bool has_change = false; std::vector new_children{}; for (SENode* child : *node) { if (child->GetType() == SENode::RecurrentAddExpr) { SENode* coefficient = child->AsSERecurrentNode()->GetCoefficient(); // If coefficient is zero then we can eliminate the recurrent expression // entirely and just return the offset as the recurrent expression is // representing the equation coefficient*iterations + offset. if (coefficient->GetType() == SENode::Constant && coefficient->AsSEConstantNode()->FoldToSingleValue() == 0) { new_children.push_back(child->AsSERecurrentNode()->GetOffset()); has_change = true; } else { new_children.push_back(child); } } else { new_children.push_back(child); } } if (!has_change) return node; std::unique_ptr new_add{new SEAddNode(node_->GetParentAnalysis())}; for (SENode* child : new_children) { new_add->AddChild(child); } return analysis_.GetCachedOrAdd(std::move(new_add)); } SENode* SENodeSimplifyImpl::SimplifyRecurrentAddExpression( SERecurrentNode* recurrent_expr) { const std::vector& children = node_->GetChildren(); std::unique_ptr recurrent_node{new SERecurrentNode( recurrent_expr->GetParentAnalysis(), recurrent_expr->GetLoop())}; // Create and simplify the new offset node. std::unique_ptr new_offset{ new SEAddNode(recurrent_expr->GetParentAnalysis())}; new_offset->AddChild(recurrent_expr->GetOffset()); for (SENode* child : children) { if (child->GetType() != SENode::RecurrentAddExpr) { new_offset->AddChild(child); } } // Simplify the new offset. SENode* simplified_child = analysis_.SimplifyExpression(new_offset.get()); // If the child can be simplified, add the simplified form otherwise, add it // via the usual caching mechanism. if (simplified_child->GetType() != SENode::CanNotCompute) { recurrent_node->AddOffset(simplified_child); } else { recurrent_expr->AddOffset(analysis_.GetCachedOrAdd(std::move(new_offset))); } recurrent_node->AddCoefficient(recurrent_expr->GetCoefficient()); return analysis_.GetCachedOrAdd(std::move(recurrent_node)); } /* * Scalar Analysis simplification public methods. */ SENode* ScalarEvolutionAnalysis::SimplifyExpression(SENode* node) { SENodeSimplifyImpl impl{this, node}; return impl.Simplify(); } } // namespace opt } // namespace spvtools