Method getTrackingVariable

lib/propanalysis/ArrayAnalyzer.cpp:135–216

This API returns a variable would be tracked TODO: This API analyze single loop, not a nested loop. If there is an instruction (array access) in the outer loop, only the outer loop is analyzed If exist in inner loop, analyze only inner loop Nested loop support is required when analyzing ranges of array index.

// If exist in inner loop, analyze only inner loop
// Nested loop support is required when analyzing ranges of array index.
Value *ArrayAnalyzer::getTrackingVariable(Loop &L) {
  bool PositiveStride = false;

  auto LoopHeader = L.getHeader();
  assert(LoopHeader && "Unexpected Program State");

  auto *F = LoopHeader->getParent();
  assert(F && "Unexpected Program State");

  auto &SEA = FAM.getResult<ScalarEvolutionAnalysis>(*F);
  auto *VariantV = getRelatedIndV(L, SEA);
  auto *ExitCond = getLoopExitCond(L);
  if (!ExitCond)
    return nullptr;
  assert(ExitCond->getNumOperands() > 1 && "Unexpected Program State");

  auto *CmpOp0 = ExitCond->getOperand(0);
  auto *CmpOp1 = ExitCond->getOperand(1);

  // For a variable dependent on the induction variable,
  // use the Scalar Evolution to get a phinode(loop-variant) and step
  if (VariantV) {
    if (const auto *AR = dyn_cast<SCEVAddRecExpr>(SEA.getSCEV(VariantV))) {
      const auto *Stride = AR->getStepRecurrence(SEA);
      PositiveStride = SEA.isKnownPositive(Stride);
    }
  } else {
    // For non induction variable, analyze loop termination
    // to get the phinode(loop-variant) and step
    //
    // ex) while(size > 0) size -= getSize()
    //
    // The induction variable increases/decreases by a fixed amount.
    // However the "size" is reduced by the external API's return value.
    // So "size" is not induction variable.
    // There is no induction variable in this loop
    for (unsigned CmpOpNum = 0, E1 = ExitCond->getNumOperands(); CmpOpNum < E1;
         CmpOpNum++) {
      auto *PN = dyn_cast<PHINode>(ExitCond->getOperand(CmpOpNum));
      if (!PN)
        continue;

      VariantV = ExitCond->getOperand(CmpOpNum);

      for (unsigned PnOpNum = 0, E2 = PN->getNumIncomingValues(); PnOpNum < E2;
           PnOpNum++) {
        if (!L.contains(PN->getIncomingBlock(PnOpNum)))
          continue;

        auto *BO = dyn_cast<BinaryOperator>(PN->getIncomingValue(PnOpNum));
        if (!BO)
          continue;

        if (BO->getOpcode() == Instruction::Add ||
            BO->getOpcode() == Instruction::Mul ||
            BO->getOpcode() == Instruction::FAdd ||
            BO->getOpcode() == Instruction::FMul)
          PositiveStride = true;