source/opt/loop_dependence_helpers.cpp

// 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 <ostream>
#include <set>
#include <string>
#include <unordered_set>
#include <utility>
#include <vector>

#include "source/opt/basic_block.h"
#include "source/opt/instruction.h"
#include "source/opt/loop_dependence.h"
#include "source/opt/scalar_analysis_nodes.h"

namespace spvtools {
namespace opt {

bool LoopDependenceAnalysis::IsZIV(
    const std::pair<SENode*, SENode*>& subscript_pair) {
  return CountInductionVariables(subscript_pair.first, subscript_pair.second) ==
         0;
}

bool LoopDependenceAnalysis::IsSIV(
    const std::pair<SENode*, SENode*>& subscript_pair) {
  return CountInductionVariables(subscript_pair.first, subscript_pair.second) ==
         1;
}

bool LoopDependenceAnalysis::IsMIV(
    const std::pair<SENode*, SENode*>& subscript_pair) {
  return CountInductionVariables(subscript_pair.first, subscript_pair.second) >
         1;
}

SENode* LoopDependenceAnalysis::GetLowerBound(const Loop* loop) {
  Instruction* cond_inst = loop->GetConditionInst();
  if (!cond_inst) {
    return nullptr;
  }
  Instruction* lower_inst = GetOperandDefinition(cond_inst, 0);
  switch (cond_inst->opcode()) {
    case spv::Op::OpULessThan:
    case spv::Op::OpSLessThan:
    case spv::Op::OpULessThanEqual:
    case spv::Op::OpSLessThanEqual:
    case spv::Op::OpUGreaterThan:
    case spv::Op::OpSGreaterThan:
    case spv::Op::OpUGreaterThanEqual:
    case spv::Op::OpSGreaterThanEqual: {
      // If we have a phi we are looking at the induction variable. We look
      // through the phi to the initial value of the phi upon entering the loop.
      if (lower_inst->opcode() == spv::Op::OpPhi) {
        lower_inst = GetOperandDefinition(lower_inst, 0);
        // We don't handle looking through multiple phis.
        if (lower_inst->opcode() == spv::Op::OpPhi) {
          return nullptr;
        }
      }
      return scalar_evolution_.SimplifyExpression(
          scalar_evolution_.AnalyzeInstruction(lower_inst));
    }
    default:
      return nullptr;
  }
}

SENode* LoopDependenceAnalysis::GetUpperBound(const Loop* loop) {
  Instruction* cond_inst = loop->GetConditionInst();
  if (!cond_inst) {
    return nullptr;
  }
  Instruction* upper_inst = GetOperandDefinition(cond_inst, 1);
  switch (cond_inst->opcode()) {
    case spv::Op::OpULessThan:
    case spv::Op::OpSLessThan: {
      // When we have a < condition we must subtract 1 from the analyzed upper
      // instruction.
      SENode* upper_bound = scalar_evolution_.SimplifyExpression(
          scalar_evolution_.CreateSubtraction(
              scalar_evolution_.AnalyzeInstruction(upper_inst),
              scalar_evolution_.CreateConstant(1)));
      return upper_bound;
    }
    case spv::Op::OpUGreaterThan:
    case spv::Op::OpSGreaterThan: {
      // When we have a > condition we must add 1 to the analyzed upper
      // instruction.
      SENode* upper_bound =
          scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateAddNode(
              scalar_evolution_.AnalyzeInstruction(upper_inst),
              scalar_evolution_.CreateConstant(1)));
      return upper_bound;
    }
    case spv::Op::OpULessThanEqual:
    case spv::Op::OpSLessThanEqual:
    case spv::Op::OpUGreaterThanEqual:
    case spv::Op::OpSGreaterThanEqual: {
      // We don't need to modify the results of analyzing when we have <= or >=.
      SENode* upper_bound = scalar_evolution_.SimplifyExpression(
          scalar_evolution_.AnalyzeInstruction(upper_inst));
      return upper_bound;
    }
    default:
      return nullptr;
  }
}

bool LoopDependenceAnalysis::IsWithinBounds(int64_t value, int64_t bound_one,
                                            int64_t bound_two) {
  if (bound_one < bound_two) {
    // If |bound_one| is the lower bound.
    return (value >= bound_one && value <= bound_two);
  } else if (bound_one > bound_two) {
    // If |bound_two| is the lower bound.
    return (value >= bound_two && value <= bound_one);
  } else {
    // Both bounds have the same value.
    return value == bound_one;
  }
}

bool LoopDependenceAnalysis::IsProvablyOutsideOfLoopBounds(
    const Loop* loop, SENode* distance, SENode* coefficient) {
  // We test to see if we can reduce the coefficient to an integral constant.
  SEConstantNode* coefficient_constant = coefficient->AsSEConstantNode();
  if (!coefficient_constant) {
    PrintDebug(
        "IsProvablyOutsideOfLoopBounds could not reduce coefficient to a "
        "SEConstantNode so must exit.");
    return false;
  }

  SENode* lower_bound = GetLowerBound(loop);
  SENode* upper_bound = GetUpperBound(loop);
  if (!lower_bound || !upper_bound) {
    PrintDebug(
        "IsProvablyOutsideOfLoopBounds could not get both the lower and upper "
        "bounds so must exit.");
    return false;
  }
  // If the coefficient is positive we calculate bounds as upper - lower
  // If the coefficient is negative we calculate bounds as lower - upper
  SENode* bounds = nullptr;
  if (coefficient_constant->FoldToSingleValue() >= 0) {
    PrintDebug(
        "IsProvablyOutsideOfLoopBounds found coefficient >= 0.\n"
        "Using bounds as upper - lower.");
    bounds = scalar_evolution_.SimplifyExpression(
        scalar_evolution_.CreateSubtraction(upper_bound, lower_bound));
  } else {
    PrintDebug(
        "IsProvablyOutsideOfLoopBounds found coefficient < 0.\n"
        "Using bounds as lower - upper.");
    bounds = scalar_evolution_.SimplifyExpression(
        scalar_evolution_.CreateSubtraction(lower_bound, upper_bound));
  }

  // We can attempt to deal with symbolic cases by subtracting |distance| and
  // the bound nodes. If we can subtract, simplify and produce a SEConstantNode
  // we can produce some information.
  SEConstantNode* distance_minus_bounds =
      scalar_evolution_
          .SimplifyExpression(
              scalar_evolution_.CreateSubtraction(distance, bounds))
          ->AsSEConstantNode();
  if (distance_minus_bounds) {
    PrintDebug(
        "IsProvablyOutsideOfLoopBounds found distance - bounds as a "
        "SEConstantNode with value " +
        ToString(distance_minus_bounds->FoldToSingleValue()));
    // If distance - bounds > 0 we prove the distance is outwith the loop
    // bounds.
    if (distance_minus_bounds->FoldToSingleValue() > 0) {
      PrintDebug(
          "IsProvablyOutsideOfLoopBounds found distance escaped the loop "
          "bounds.");
      return true;
    }
  }

  return false;
}

const Loop* LoopDependenceAnalysis::GetLoopForSubscriptPair(
    const std::pair<SENode*, SENode*>& subscript_pair) {
  // Collect all the SERecurrentNodes.
  std::vector<SERecurrentNode*> source_nodes =
      std::get<0>(subscript_pair)->CollectRecurrentNodes();
  std::vector<SERecurrentNode*> destination_nodes =
      std::get<1>(subscript_pair)->CollectRecurrentNodes();

  // Collect all the loops stored by the SERecurrentNodes.
  std::unordered_set<const Loop*> loops{};
  for (auto source_nodes_it = source_nodes.begin();
       source_nodes_it != source_nodes.end(); ++source_nodes_it) {
    loops.insert((*source_nodes_it)->GetLoop());
  }
  for (auto destination_nodes_it = destination_nodes.begin();
       destination_nodes_it != destination_nodes.end();
       ++destination_nodes_it) {
    loops.insert((*destination_nodes_it)->GetLoop());
  }

  // If we didn't find 1 loop |subscript_pair| is a subscript over multiple or 0
  // loops. We don't handle this so return nullptr.
  if (loops.size() != 1) {
    PrintDebug("GetLoopForSubscriptPair found loops.size() != 1.");
    return nullptr;
  }
  return *loops.begin();
}

DistanceEntry* LoopDependenceAnalysis::GetDistanceEntryForLoop(
    const Loop* loop, DistanceVector* distance_vector) {
  if (!loop) {
    return nullptr;
  }

  DistanceEntry* distance_entry = nullptr;
  for (size_t loop_index = 0; loop_index < loops_.size(); ++loop_index) {
    if (loop == loops_[loop_index]) {
      distance_entry = &(distance_vector->GetEntries()[loop_index]);
      break;
    }
  }

  return distance_entry;
}

DistanceEntry* LoopDependenceAnalysis::GetDistanceEntryForSubscriptPair(
    const std::pair<SENode*, SENode*>& subscript_pair,
    DistanceVector* distance_vector) {
  const Loop* loop = GetLoopForSubscriptPair(subscript_pair);

  return GetDistanceEntryForLoop(loop, distance_vector);
}

SENode* LoopDependenceAnalysis::GetTripCount(const Loop* loop) {
  BasicBlock* condition_block = loop->FindConditionBlock();
  if (!condition_block) {
    return nullptr;
  }
  Instruction* induction_instr = loop->FindConditionVariable(condition_block);
  if (!induction_instr) {
    return nullptr;
  }
  Instruction* cond_instr = loop->GetConditionInst();
  if (!cond_instr) {
    return nullptr;
  }

  size_t iteration_count = 0;

  // We have to check the instruction type here. If the condition instruction
  // isn't a supported type we can't calculate the trip count.
  if (loop->IsSupportedCondition(cond_instr->opcode())) {
    if (loop->FindNumberOfIterations(induction_instr, &*condition_block->tail(),
                                     &iteration_count)) {
      return scalar_evolution_.CreateConstant(
          static_cast<int64_t>(iteration_count));
    }
  }

  return nullptr;
}

SENode* LoopDependenceAnalysis::GetFirstTripInductionNode(const Loop* loop) {
  BasicBlock* condition_block = loop->FindConditionBlock();
  if (!condition_block) {
    return nullptr;
  }
  Instruction* induction_instr = loop->FindConditionVariable(condition_block);
  if (!induction_instr) {
    return nullptr;
  }
  int64_t induction_initial_value = 0;
  if (!loop->GetInductionInitValue(induction_instr, &induction_initial_value)) {
    return nullptr;
  }

  SENode* induction_init_SENode = scalar_evolution_.SimplifyExpression(
      scalar_evolution_.CreateConstant(induction_initial_value));
  return induction_init_SENode;
}

SENode* LoopDependenceAnalysis::GetFinalTripInductionNode(
    const Loop* loop, SENode* induction_coefficient) {
  SENode* first_trip_induction_node = GetFirstTripInductionNode(loop);
  if (!first_trip_induction_node) {
    return nullptr;
  }
  // Get trip_count as GetTripCount - 1
  // This is because the induction variable is not stepped on the first
  // iteration of the loop
  SENode* trip_count =
      scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateSubtraction(
          GetTripCount(loop), scalar_evolution_.CreateConstant(1)));
  // Return first_trip_induction_node + trip_count * induction_coefficient
  return scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateAddNode(
      first_trip_induction_node,
      scalar_evolution_.CreateMultiplyNode(trip_count, induction_coefficient)));
}

std::set<const Loop*> LoopDependenceAnalysis::CollectLoops(
    const std::vector<SERecurrentNode*>& recurrent_nodes) {
  // We don't handle loops with more than one induction variable. Therefore we
  // can identify the number of induction variables by collecting all of the
  // loops the collected recurrent nodes belong to.
  std::set<const Loop*> loops{};
  for (auto recurrent_nodes_it = recurrent_nodes.begin();
       recurrent_nodes_it != recurrent_nodes.end(); ++recurrent_nodes_it) {
    loops.insert((*recurrent_nodes_it)->GetLoop());
  }

  return loops;
}

int64_t LoopDependenceAnalysis::CountInductionVariables(SENode* node) {
  if (!node) {
    return -1;
  }

  std::vector<SERecurrentNode*> recurrent_nodes = node->CollectRecurrentNodes();

  // We don't handle loops with more than one induction variable. Therefore we
  // can identify the number of induction variables by collecting all of the
  // loops the collected recurrent nodes belong to.
  std::set<const Loop*> loops = CollectLoops(recurrent_nodes);

  return static_cast<int64_t>(loops.size());
}

std::set<const Loop*> LoopDependenceAnalysis::CollectLoops(
    SENode* source, SENode* destination) {
  if (!source || !destination) {
    return std::set<const Loop*>{};
  }

  std::vector<SERecurrentNode*> source_nodes = source->CollectRecurrentNodes();
  std::vector<SERecurrentNode*> destination_nodes =
      destination->CollectRecurrentNodes();

  std::set<const Loop*> loops = CollectLoops(source_nodes);
  std::set<const Loop*> destination_loops = CollectLoops(destination_nodes);

  loops.insert(std::begin(destination_loops), std::end(destination_loops));

  return loops;
}

int64_t LoopDependenceAnalysis::CountInductionVariables(SENode* source,
                                                        SENode* destination) {
  if (!source || !destination) {
    return -1;
  }

  std::set<const Loop*> loops = CollectLoops(source, destination);

  return static_cast<int64_t>(loops.size());
}

Instruction* LoopDependenceAnalysis::GetOperandDefinition(
    const Instruction* instruction, int id) {
  return context_->get_def_use_mgr()->GetDef(
      instruction->GetSingleWordInOperand(id));
}

std::vector<Instruction*> LoopDependenceAnalysis::GetSubscripts(
    const Instruction* instruction) {
  Instruction* access_chain = GetOperandDefinition(instruction, 0);

  std::vector<Instruction*> subscripts;

  for (auto i = 1u; i < access_chain->NumInOperandWords(); ++i) {
    subscripts.push_back(GetOperandDefinition(access_chain, i));
  }

  return subscripts;
}

SENode* LoopDependenceAnalysis::GetConstantTerm(const Loop* loop,
                                                SERecurrentNode* induction) {
  SENode* offset = induction->GetOffset();
  SENode* lower_bound = GetLowerBound(loop);
  if (!offset || !lower_bound) {
    return nullptr;
  }
  SENode* constant_term = scalar_evolution_.SimplifyExpression(
      scalar_evolution_.CreateSubtraction(offset, lower_bound));
  return constant_term;
}

bool LoopDependenceAnalysis::CheckSupportedLoops(
    std::vector<const Loop*> loops) {
  for (auto loop : loops) {
    if (!IsSupportedLoop(loop)) {
      return false;
    }
  }
  return true;
}

void LoopDependenceAnalysis::MarkUnsusedDistanceEntriesAsIrrelevant(
    const Instruction* source, const Instruction* destination,
    DistanceVector* distance_vector) {
  std::vector<Instruction*> source_subscripts = GetSubscripts(source);
  std::vector<Instruction*> destination_subscripts = GetSubscripts(destination);

  std::set<const Loop*> used_loops{};

  for (Instruction* source_inst : source_subscripts) {
    SENode* source_node = scalar_evolution_.SimplifyExpression(
        scalar_evolution_.AnalyzeInstruction(source_inst));
    std::vector<SERecurrentNode*> recurrent_nodes =
        source_node->CollectRecurrentNodes();
    for (SERecurrentNode* recurrent_node : recurrent_nodes) {
      used_loops.insert(recurrent_node->GetLoop());
    }
  }

  for (Instruction* destination_inst : destination_subscripts) {
    SENode* destination_node = scalar_evolution_.SimplifyExpression(
        scalar_evolution_.AnalyzeInstruction(destination_inst));
    std::vector<SERecurrentNode*> recurrent_nodes =
        destination_node->CollectRecurrentNodes();
    for (SERecurrentNode* recurrent_node : recurrent_nodes) {
      used_loops.insert(recurrent_node->GetLoop());
    }
  }

  for (size_t i = 0; i < loops_.size(); ++i) {
    if (used_loops.find(loops_[i]) == used_loops.end()) {
      distance_vector->GetEntries()[i].dependence_information =
          DistanceEntry::DependenceInformation::IRRELEVANT;
    }
  }
}

bool LoopDependenceAnalysis::IsSupportedLoop(const Loop* loop) {
  std::vector<Instruction*> inductions{};
  loop->GetInductionVariables(inductions);
  if (inductions.size() != 1) {
    return false;
  }
  Instruction* induction = inductions[0];
  SENode* induction_node = scalar_evolution_.SimplifyExpression(
      scalar_evolution_.AnalyzeInstruction(induction));
  if (!induction_node->AsSERecurrentNode()) {
    return false;
  }
  SENode* induction_step =
      induction_node->AsSERecurrentNode()->GetCoefficient();
  if (!induction_step->AsSEConstantNode()) {
    return false;
  }
  if (!(induction_step->AsSEConstantNode()->FoldToSingleValue() == 1 ||
        induction_step->AsSEConstantNode()->FoldToSingleValue() == -1)) {
    return false;
  }
  return true;
}

void LoopDependenceAnalysis::PrintDebug(std::string debug_msg) {
  if (debug_stream_) {
    (*debug_stream_) << debug_msg << "\n";
  }
}

bool Constraint::operator==(const Constraint& other) const {
  // A distance of |d| is equivalent to a line |x - y = -d|
  if ((GetType() == ConstraintType::Distance &&
       other.GetType() == ConstraintType::Line) ||
      (GetType() == ConstraintType::Line &&
       other.GetType() == ConstraintType::Distance)) {
    auto is_distance = AsDependenceLine() != nullptr;

    auto as_distance =
        is_distance ? AsDependenceDistance() : other.AsDependenceDistance();
    auto distance = as_distance->GetDistance();

    auto line = other.AsDependenceLine();

    auto scalar_evolution = distance->GetParentAnalysis();

    auto neg_distance = scalar_evolution->SimplifyExpression(
        scalar_evolution->CreateNegation(distance));

    return *scalar_evolution->CreateConstant(1) == *line->GetA() &&
           *scalar_evolution->CreateConstant(-1) == *line->GetB() &&
           *neg_distance == *line->GetC();
  }

  if (GetType() != other.GetType()) {
    return false;
  }

  if (AsDependenceDistance()) {
    return *AsDependenceDistance()->GetDistance() ==
           *other.AsDependenceDistance()->GetDistance();
  }

  if (AsDependenceLine()) {
    auto this_line = AsDependenceLine();
    auto other_line = other.AsDependenceLine();
    return *this_line->GetA() == *other_line->GetA() &&
           *this_line->GetB() == *other_line->GetB() &&
           *this_line->GetC() == *other_line->GetC();
  }

  if (AsDependencePoint()) {
    auto this_point = AsDependencePoint();
    auto other_point = other.AsDependencePoint();

    return *this_point->GetSource() == *other_point->GetSource() &&
           *this_point->GetDestination() == *other_point->GetDestination();
  }

  return true;
}

bool Constraint::operator!=(const Constraint& other) const {
  return !(*this == other);
}

}  // namespace opt
}  // namespace spvtools