path: root/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

//===-- LoopIdiomRecognize.cpp - Loop idiom recognition -------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass implements an idiom recognizer that transforms simple loops into a
// non-loop form.  In cases that this kicks in, it can be a significant
// performance win.
//
//===----------------------------------------------------------------------===//
//
// TODO List:
//
// Future loop memory idioms to recognize:
//   memcmp, memmove, strlen, etc.
// Future floating point idioms to recognize in -ffast-math mode:
//   fpowi
// Future integer operation idioms to recognize:
//   ctpop, ctlz, cttz
//
// Beware that isel's default lowering for ctpop is highly inefficient for
// i64 and larger types when i64 is legal and the value has few bits set.  It
// would be good to enhance isel to emit a loop for ctpop in this case.
//
// We should enhance the memset/memcpy recognition to handle multiple stores in
// the loop.  This would handle things like:
//   void foo(_Complex float *P)
//     for (i) { __real__(*P) = 0;  __imag__(*P) = 0; }
//
// We should enhance this to handle negative strides through memory.
// Alternatively (and perhaps better) we could rely on an earlier pass to force
// forward iteration through memory, which is generally better for cache
// behavior.  Negative strides *do* happen for memset/memcpy loops.
//
// This could recognize common matrix multiplies and dot product idioms and
// replace them with calls to BLAS (if linked in??).
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "loop-idiom"
#include "llvm/Transforms/Scalar.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolutionExpander.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DataLayout.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetLibraryInfo.h"
#include "llvm/Transforms/Utils/Local.h"
using namespace llvm;

STATISTIC(NumMemSet, "Number of memset's formed from loop stores");
STATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores");

namespace {

  class LoopIdiomRecognize;

  /// This class defines some utility functions for loop idiom recognization.
  class LIRUtil {
  public:
    /// Return true iff the block contains nothing but an uncondition branch
    /// (aka goto instruction).
    static bool isAlmostEmpty(BasicBlock *);

    static BranchInst *getBranch(BasicBlock *BB) {
      return dyn_cast<BranchInst>(BB->getTerminator());
    }

    /// Return the condition of the branch terminating the given basic block.
    static Value *getBrCondtion(BasicBlock *);

    /// Derive the precondition block (i.e the block that guards the loop 
    /// preheader) from the given preheader.
    static BasicBlock *getPrecondBb(BasicBlock *PreHead);
  };

  /// This class is to recoginize idioms of population-count conducted in
  /// a noncountable loop. Currently it only recognizes this pattern:
  /// \code
  ///   while(x) {cnt++; ...; x &= x - 1; ...}
  /// \endcode
  class NclPopcountRecognize {
    LoopIdiomRecognize &LIR;
    Loop *CurLoop;
    BasicBlock *PreCondBB;

    typedef IRBuilder<> IRBuilderTy;

  public:
    explicit NclPopcountRecognize(LoopIdiomRecognize &TheLIR);
    bool recognize();

  private:
    /// Take a glimpse of the loop to see if we need to go ahead recoginizing
    /// the idiom.
    bool preliminaryScreen();

    /// Check if the given conditional branch is based on the comparison
    /// beween a variable and zero, and if the variable is non-zero, the
    /// control yeilds to the loop entry. If the branch matches the behavior,
    /// the variable involved in the comparion is returned. This function will
    /// be called to see if the precondition and postcondition of the loop 
    /// are in desirable form.
    Value *matchCondition (BranchInst *Br, BasicBlock *NonZeroTarget) const;

    /// Return true iff the idiom is detected in the loop. and 1) \p CntInst
    /// is set to the instruction counting the pupulation bit. 2) \p CntPhi
    /// is set to the corresponding phi node. 3) \p Var is set to the value
    /// whose population bits are being counted.
    bool detectIdiom
      (Instruction *&CntInst, PHINode *&CntPhi, Value *&Var) const;

    /// Insert ctpop intrinsic function and some obviously dead instructions.
    void transform (Instruction *CntInst, PHINode *CntPhi, Value *Var);

    /// Create llvm.ctpop.* intrinsic function.
    CallInst *createPopcntIntrinsic(IRBuilderTy &IRB, Value *Val, DebugLoc DL);
  };

  class LoopIdiomRecognize : public LoopPass {
    Loop *CurLoop;
    const DataLayout *TD;
    DominatorTree *DT;
    ScalarEvolution *SE;
    TargetLibraryInfo *TLI;
    const TargetTransformInfo *TTI;
  public:
    static char ID;
    explicit LoopIdiomRecognize() : LoopPass(ID) {
      initializeLoopIdiomRecognizePass(*PassRegistry::getPassRegistry());
      TD = 0; DT = 0; SE = 0; TLI = 0; TTI = 0;
    }

    bool runOnLoop(Loop *L, LPPassManager &LPM);
    bool <