path: root/lib/Transforms/Vectorize/LoopVectorize.cpp

//===- LoopVectorize.cpp - A Loop Vectorizer ------------------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This is a simple loop vectorizer. We currently only support single block
// loops. We have a very simple and restrictive legality check: we need to read
// and write from disjoint memory locations. We still don't have a cost model.
// This pass has three parts:
// 1. The main loop pass that drives the different parts.
// 2. LoopVectorizationLegality - A helper class that checks for the legality
//    of the vectorization.
// 3. SingleBlockLoopVectorizer - A helper class that performs the actual
//    widening of instructions.
//
//===----------------------------------------------------------------------===//
#define LV_NAME "loop-vectorize"
#define DEBUG_TYPE LV_NAME
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
#include "llvm/LLVMContext.h"
#include "llvm/Pass.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Value.h"
#include "llvm/Function.h"
#include "llvm/Analysis/Verifier.h"
#include "llvm/Module.h"
#include "llvm/Type.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/DataLayout.h"
#include "llvm/Transforms/Utils/Local.h"
#include <algorithm>
using namespace llvm;

static cl::opt<unsigned>
DefaultVectorizationFactor("default-loop-vectorize-width",
                          cl::init(4), cl::Hidden,
                          cl::desc("Set the default loop vectorization width"));

namespace {

/// Vectorize a simple loop. This class performs the widening of simple single
/// basic block loops into vectors. It does not perform any
/// vectorization-legality checks, and just does it.  It widens the vectors
/// to a given vectorization factor (VF).
class SingleBlockLoopVectorizer {
public:
  /// Ctor.
  SingleBlockLoopVectorizer(Loop *OrigLoop, ScalarEvolution *Se, LoopInfo *Li,
                            LPPassManager *Lpm, unsigned VecWidth):
  Orig(OrigLoop), SE(Se), LI(Li), LPM(Lpm), VF(VecWidth),
   Builder(0), Induction(0), OldInduction(0) { }

  ~SingleBlockLoopVectorizer() {
    delete Builder;
  }

  // Perform the actual loop widening (vectorization).
  void vectorize() {
    ///Create a new empty loop. Unlink the old loop and connect the new one.
    createEmptyLoop();
    /// Widen each instruction in the old loop to a new one in the new loop.
    vectorizeLoop();
    // register the new loop.
    cleanup();
 }

private:
  /// Create an empty loop, based on the loop ranges of the old loop.
  void createEmptyLoop();
  /// Copy and widen the instructions from the old loop.
  void vectorizeLoop();
  /// Insert the new loop to the loop hierarchy and pass manager.
  void cleanup();

  /// This instruction is un-vectorizable. Implement it as a sequence
  /// of scalars.
  void scalarizeInstruction(Instruction *Instr);

  /// Create a broadcast instruction. This method generates a broadcast
  /// instruction (shuffle) for loop invariant values and for the induction
  /// value. If this is the induction variable then we extend it to N, N+1, ...
  /// this is needed because each iteration in the loop corresponds to a SIMD
  /// element.
  Value *getBroadcastInstrs(Value *V);

  /// This is a helper function used by getBroadcastInstrs. It adds 0, 1, 2 ..
  /// for each element in the vector. Starting from zero.
  Value *getConsecutiveVector(Value* Val);

  /// Check that the GEP operands are all uniform except for the last index
  /// which has to be the induction variable.
  bool isConsecutiveGep(GetElementPtrInst *Gep);

  /// When we go over instructions in the basic block we rely on previous
  /// values within the current basic block or on loop invariant values.
  /// When we widen (vectorize) values we place them in the map. If the values
  /// are not within the map, they have to be loop invariant, so we simply
  /// broadcast them into a vector.
  Value *getVectorValue(Value *V);

  typedef DenseMap<Value*, Value*> ValueMap;

  /// The original loop.
  Loop *Orig;
  // Scev analysis to use.
  ScalarEvolution *SE;
  // Loop Info.
  LoopInfo *LI;
  // Loop Pass Manager;
  LPPassManager *LPM;
  // The vectorization factor to use.
  unsigned VF;

  // The builder that we use
  IRBuilder<> *Builder;

  // --- Vectorization state ---

  /// The new Induction variable which was added to the new block.
  PHINode *Induction;
  /// The induction variable of the old basic block.
  PHINode *OldInduction;
  // Maps scalars to widened vectors.
  ValueMap WidenMap;
};

/// Perform the vectorization legality check. This class does not look at the
/// profitability of vectorization, only the legality. At the moment the checks
/// are very simple and focus on single basic block loops with a constant
/// iteration count and no reductions.
class LoopVectorizationLegality {
public:
  LoopVectorizationLegality(Loop *Lp, ScalarEvolution *Se, DataLayout *Dl):
  TheLoop(Lp), SE(Se), DL(Dl) { }

  /// Returns the maximum vectorization factor that we *can* use to vectorize
  /// this loop. This does not mean that it is profitable to vectorize this
  /// loop, only that it is legal to do so. This may be a large number. We
  /// can vectorize to any SIMD width below this number.
  unsigned getLoopMaxVF();

private:
  /// Check if a single basic block loop is vectorizable.
  /// At this point we know that this is a loop with a constant trip count
  /// and we only need to check individual instructions.
  bool canVectorizeBlock(BasicBlock &BB);

  // Check if a pointer value is known to be disjoint.
  // Example: Alloca, Global, NoAlias.
  bool isIdentifiedSafeObject(Value* Val);

  /// The loop that we evaluate.
  Loop *TheLoop;
  /// Scev analysis.
  ScalarEvolution *SE;
  /// DataLayout analysis.
  DataLayout *DL;
};

struct LoopVectorize : public LoopPass {
  static char ID; // Pass identification, replacement for typeid

  LoopVectorize() : LoopPass(ID) {
    initializeLoopVectorizePass(*PassRegistry::getPassRegistry());
  }

  ScalarEvolution *SE;
  DataLayout *DL;
  LoopInfo *LI;

  virtual bool runOnLoop(Loop *L, LPPassManager &LPM) {
    // Only vectorize innermost loops.
    if (!L->empty())
      return false;

    SE = &getAnalysis<ScalarEvolution>();
    DL = getAnalysisIfAvailable<DataLayout>();
    LI = &getAnalysis<LoopInfo>();

    DEBUG(dbgs() << "LV: Checking a loop in \"" <<
          L->getHeader()->getParent()->getName() << "\"\n");

    // Check if it is legal to vectorize the loop.
    LoopVectorizationLegality LVL(