lib/IRGen/SwitchBuilder.h

//===--- SwitchBuilder.h ----------------------------------------*- C++ -*-===//
//
// 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
//
//===----------------------------------------------------------------------===//

#ifndef SWIFT_IRGEN_SWITCHBUILDER_H
#define SWIFT_IRGEN_SWITCHBUILDER_H

#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"

#include "IRBuilder.h"
#include "IRGenFunction.h"

namespace swift {
namespace irgen {

/// A builder that produces an LLVM branch or switch instruction for a set
/// of destinations.
class SwitchBuilder {
private:
#ifndef NDEBUG
  /// Track whether we added as many cases as we expected to.
  unsigned CasesToAdd;
#endif

protected:
  IRBuilder Builder;
  llvm::Value *Subject;

  /// Protected initializer. Clients should use the `create` factory method.
  SwitchBuilder(IRGenFunction &IGF, llvm::Value *Subject, unsigned NumCases)
      :
#ifndef NDEBUG
        CasesToAdd(NumCases),
#endif
        // Create our own IRBuilder, so that the SwitchBuilder is always able to
        // generate the branch instruction at the right point, even if it needs
        // to collect multiple cases before building an instruction.
        Builder(IGF.IGM.getLLVMContext(), /*DebugInfo*/ false),
        Subject(Subject) {
    // Start our builder off at IGF's current insertion point.
    Builder.SetInsertPoint(IGF.Builder.GetInsertBlock(),
                           IGF.Builder.GetInsertPoint());
  }

public:
  virtual ~SwitchBuilder() {
#ifndef NDEBUG
    assert(CasesToAdd == 0 && "Did not add enough cases");
#endif
  }

  // Create a SwitchBuilder instance for a switch that will have the given
  // number of cases.
  static std::unique_ptr<SwitchBuilder> create(IRGenFunction &IGF,
                                               llvm::Value *Subject,
                                               SwitchDefaultDest Default,
                                               unsigned NumCases);

  /// Add a case to the switch.
  virtual void addCase(llvm::ConstantInt *value, llvm::BasicBlock *dest) {
#ifndef NDEBUG
    assert(CasesToAdd > 0 && "Added too many cases");
    --CasesToAdd;
#endif
  }
};

/// A builder that emits an unconditional branch for a "switch" with only
/// one destination.
class BrSwitchBuilder final : public SwitchBuilder {
private:
  friend class SwitchBuilder;

  BrSwitchBuilder(IRGenFunction &IGF, llvm::Value *Subject, unsigned NumCases)
      : SwitchBuilder(IGF, Subject, NumCases) {
    assert(NumCases == 1 && "should have only one branch");
  }

public:
  void addCase(llvm::ConstantInt *value, llvm::BasicBlock *dest) override {
    SwitchBuilder::addCase(value, dest);
    Builder.CreateBr(dest);
  }
};

/// A builder that produces a conditional branch for a "switch" with two
/// defined destinations.
class CondBrSwitchBuilder final : public SwitchBuilder {
private:
  friend class SwitchBuilder;
  llvm::BasicBlock *FirstDest;

  CondBrSwitchBuilder(IRGenFunction &IGF, llvm::Value *Subject,
                      SwitchDefaultDest Default, unsigned NumCases)
      : SwitchBuilder(IGF, Subject, NumCases),
        FirstDest(Default.getInt() == IsUnreachable ? nullptr
                                                    : Default.getPointer()) {
    assert(NumCases + (Default.getInt() == IsNotUnreachable) == 2 &&
           "should have two branches total");
  }

public:
  void addCase(llvm::ConstantInt *value, llvm::BasicBlock *dest) override {
    SwitchBuilder::addCase(value, dest);

    // If we don't have a first destination yet, save it.
    // We don't need to save the value in this case since we assume that the
    // subject must be one of the case values. We only have to test one or
    // the other.
    //
    // TODO: It may make sense to save both case values, and pick which one
    // to compare based on which value is more likely to be efficiently
    // representable in the target machine language. For example, zero
    // or a small immediate is usually cheaper to materialize than a larger
    // value that may require multiple instructions or a bigger encoding.
    if (!FirstDest) {
      FirstDest = dest;
      return;
    }

    // Otherwise, we have both destinations for the branch and a value to
    // test against. We can make the instruction now.
    if (cast<llvm::IntegerType>(Subject->getType())->getBitWidth() == 1) {
      // If the subject is already i1, we can use it directly as the branch
      // condition.
      if (value->isZero())
        Builder.CreateCondBr(Subject, FirstDest, dest);
      else
        Builder.CreateCondBr(Subject, dest, FirstDest);
      return;
    }
    // Otherwise, compare against the case value we have.
    auto test = Builder.CreateICmpNE(Subject, value);
    Builder.CreateCondBr(test, FirstDest, dest);
  }
};

/// A builder that produces a switch instruction for a switch with many
/// destinations.
class SwitchSwitchBuilder final : public SwitchBuilder {
private:
  friend class SwitchBuilder;
  llvm::SwitchInst *TheSwitch;

  SwitchSwitchBuilder(IRGenFunction &IGF, llvm::Value *Subject,
                      SwitchDefaultDest Default, unsigned NumCases)
      : SwitchBuilder(IGF, Subject, NumCases) {
    TheSwitch =
        IGF.Builder.CreateSwitch(Subject, Default.getPointer(), NumCases);
  }

public:
  void addCase(llvm::ConstantInt *value, llvm::BasicBlock *dest) override {
    SwitchBuilder::addCase(value, dest);
    TheSwitch->addCase(value, dest);
  }
};

std::unique_ptr<SwitchBuilder> SwitchBuilder::create(IRGenFunction &IGF,
                                                     llvm::Value *Subject,
                                                     SwitchDefaultDest Default,
                                                     unsigned NumCases) {
  // Pick a builder based on how many total reachable destinations we intend
  // to have.
  switch (NumCases + (Default.getInt() == IsNotUnreachable)) {
  case 0:
    // No reachable destinations. We can emit an unreachable and go about
    // our business.
    IGF.Builder.CreateUnreachable();
    return nullptr;
  case 1:
    // One reachable destination. We can emit an unconditional branch.
    // If that one branch is the default, we're done.
    if (Default.getInt() == IsNotUnreachable) {
      IGF.Builder.CreateBr(Default.getPointer());
      return nullptr;
    }

    // Otherwise, use a builder to emit the one case.
    return std::unique_ptr<SwitchBuilder>(
        new BrSwitchBuilder(IGF, Subject, NumCases));
  case 2:
    // Two reachable destinations. We can emit a single conditional branch.
    return std::unique_ptr<SwitchBuilder>(
        new CondBrSwitchBuilder(IGF, Subject, Default, NumCases));
  default:
    // Anything more, fall over into a switch.
    // TODO: Since fast isel doesn't support switch insns, we may want to
    // also support a "pre-lowered-switch" builder that builds a jump tree
    // for unoptimized builds.
    return std::unique_ptr<SwitchBuilder>(
        new SwitchSwitchBuilder(IGF, Subject, Default, NumCases));
  }
}

} // end irgen namespace
} // end swift namespace

#endif