lib/SILOptimizer/Mandatory/DiagnoseInfiniteRecursion.cpp

//==-- DiagnoseInfiniteRecursion.cpp - Find infinitely-recursive applies --==//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// This file implements a diagnostic pass that detects deleterious forms of
// recursive functions.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "infinite-recursion"
#include "swift/AST/DiagnosticsSIL.h"
#include "swift/AST/Expr.h"
#include "swift/Parse/Lexer.h"
#include "swift/SIL/CFG.h"
#include "swift/SIL/SILArgument.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SILOptimizer/Analysis/PostOrderAnalysis.h"
#include "swift/SILOptimizer/PassManager/Passes.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "swift/SILOptimizer/Utils/Devirtualize.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Support/Debug.h"

using namespace swift;

template<typename...T, typename...U>
static void diagnose(ASTContext &Context, SourceLoc loc, Diag<T...> diag,
                     U &&...args) {
  Context.Diags.diagnose(loc,
                         diag, std::forward<U>(args)...);
}

static bool hasRecursiveCallInPath(SILBasicBlock &Block,
                                   SILFunction *Target,
                                   ModuleDecl *TargetModule) {
  // Process all instructions in the block to find applies that reference
  // the parent function.  Also looks through vtables for statically
  // dispatched (witness) methods.
  for (auto &I : Block) {
    auto *AI = dyn_cast<ApplyInst>(&I);
    if (AI && AI->getCalleeFunction() && AI->getCalleeFunction() == Target)
      return true;

    if (FullApplySite FAI = FullApplySite::isa(&I)) {
      // Don't touch dynamic dispatch.
      if (isa<ObjCMethodInst>(FAI.getCallee()))
        continue;

      auto &M = FAI.getModule();
      if (auto *CMI = dyn_cast<ClassMethodInst>(FAI.getCallee())) {
        auto ClassType = CMI->getOperand()->getType();

        // FIXME: If we're not inside the module context of the method,
        // we may have to deserialize vtables.  If the serialized tables
        // are damaged, the pass will crash.
        //
        // Though, this has the added bonus of not looking into vtables
        // outside the current module.  Because we're not doing IPA, let
        // alone cross-module IPA, this is all well and good.
        auto *BGC = ClassType.getNominalOrBoundGenericNominal();
        if (BGC && BGC->getModuleContext() != TargetModule) {
          continue;
        }

        auto *F = getTargetClassMethod(M, ClassType, CMI);
        if (F == Target)
          return true;

        continue;
      }

      if (auto *WMI = dyn_cast<WitnessMethodInst>(FAI.getCallee())) {
        SILFunction *F;
        SILWitnessTable *WT;

        std::tie(F, WT) = M.lookUpFunctionInWitnessTable(
            WMI->getConformance(), WMI->getMember());
        if (F == Target)
          return true;

        continue;
      }
    }
  }
  return false;
}

static bool hasInfinitelyRecursiveApply(SILFunction &Fn,
                                        SILFunction *TargetFn) {
  SmallPtrSet<SILBasicBlock *, 16> Visited;
  SmallVector<SILBasicBlock *, 16> WorkList;
  // Keep track of whether we found at least one recursive path.
  bool foundRecursion = false;

  auto *TargetModule = TargetFn->getModule().getSwiftModule();
  auto analyzeSuccessor = [&](SILBasicBlock *Succ) -> bool {
    if (!Visited.insert(Succ).second)
      return false;

    // If the successor block contains a recursive call, end analysis there.
    if (!hasRecursiveCallInPath(*Succ, TargetFn, TargetModule)) {
      WorkList.push_back(Succ);
      return false;
    }
    return true;
  };

  // Seed the work list with the entry block.
  foundRecursion |= analyzeSuccessor(Fn.getEntryBlock());
  
  while (!WorkList.empty()) {
    SILBasicBlock *CurBlock = WorkList.pop_back_val();
    // Found a path to the exit node without a recursive call.
    if (CurBlock->getTerminator()->isFunctionExiting())
      return false;

    for (SILBasicBlock *Succ : CurBlock->getSuccessorBlocks())
      foundRecursion |= analyzeSuccessor(Succ);
  }
  return foundRecursion;
}

namespace {
  class DiagnoseInfiniteRecursion : public SILFunctionTransform {
  public:
    DiagnoseInfiniteRecursion() {}

  private:
    void run() override {
      SILFunction *Fn = getFunction();
      // Don't rerun diagnostics on deserialized functions.
      if (Fn->wasDeserializedCanonical())
        return;

      // Ignore empty functions and straight-line thunks.
      if (Fn->empty() || Fn->isThunk() != IsNotThunk)
        return;

      // If we can't diagnose it, there's no sense analyzing it.
      if (!Fn->hasLocation() || Fn->getLocation().getSourceLoc().isInvalid())
        return;

      if (hasInfinitelyRecursiveApply(*Fn, Fn)) {
        diagnose(Fn->getModule().getASTContext(),
                 Fn->getLocation().getSourceLoc(),
                 diag::warn_infinite_recursive_function);
      }
    }
  };
} // end anonymous namespace

SILTransform *swift::createDiagnoseInfiniteRecursion() {
  return new DiagnoseInfiniteRecursion();
}