Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- LoopVersioning.h - Utility to version a loop -------------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// This file defines a utility class to perform loop versioning.  The versioned

// loop speculates that otherwise may-aliasing memory accesses don't overlap and

// emits checks to prove this.

//

//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H

#define LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H

#include "llvm/IR/PassManager.h"

#include "llvm/Transforms/Utils/LoopUtils.h"

#include "llvm/Transforms/Utils/ValueMapper.h"

namespace llvm {

class Loop;

class SCEVPredicate;

class ScalarEvolution;

class LoopAccessInfo;

class LoopInfo;

struct RuntimeCheckingPtrGroup;

typedef std::pair<const RuntimeCheckingPtrGroup *,

                  const RuntimeCheckingPtrGroup *>

    RuntimePointerCheck;

template <typename T> class ArrayRef;

/// This class emits a version of the loop where run-time checks ensure

/// that may-alias pointers can't overlap.

///

/// It currently only supports single-exit loops and assumes that the loop

/// already has a preheader.

class LoopVersioning {

public:

  /// Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.

  /// It uses runtime check provided by the user. If \p UseLAIChecks is true,

  /// we will retain the default checks made by LAI. Otherwise, construct an

  /// object having no checks and we expect the user to add them.

  LoopVersioning(const LoopAccessInfo &LAI,

                 ArrayRef<RuntimePointerCheck> Checks, Loop *L, LoopInfo *LI,

                 DominatorTree *DT, ScalarEvolution *SE);

  /// Performs the CFG manipulation part of versioning the loop including

  /// the DominatorTree and LoopInfo updates.

  ///

  /// The loop that was used to construct the class will be the "versioned" loop

  /// i.e. the loop that will receive control if all the memchecks pass.

  ///

  /// This allows the loop transform pass to operate on the same loop regardless

  /// of whether versioning was necessary or not:

  ///

  ///    for each loop L:

  ///        analyze L

  ///        if versioning is necessary version L

  ///        transform L

  void versionLoop() { versionLoop(findDefsUsedOutsideOfLoop(VersionedLoop)); }

  /// Same but if the client has already precomputed the set of values

  /// used outside the loop, this API will allows passing that.

  void versionLoop(const SmallVectorImpl<Instruction *> &DefsUsedOutside);

  /// Returns the versioned loop.  Control flows here if pointers in the

  /// loop don't alias (i.e. all memchecks passed).  (This loop is actually the

  /// same as the original loop that we got constructed with.)

  Loop *getVersionedLoop() { return VersionedLoop; }

  /// Returns the fall-back loop.  Control flows here if pointers in the

  /// loop may alias (i.e. one of the memchecks failed).

  Loop *getNonVersionedLoop() { return NonVersionedLoop; }

  /// Annotate memory instructions in the versioned loop with no-alias

  /// metadata based on the memchecks issued.

  ///

  /// This is just wrapper that calls prepareNoAliasMetadata and

  /// annotateInstWithNoAlias on the instructions of the versioned loop.

  void annotateLoopWithNoAlias();

  /// Set up the aliasing scopes based on the memchecks.  This needs to

  /// be called before the first call to annotateInstWithNoAlias.

  void prepareNoAliasMetadata();

  /// Add the noalias annotations to \p VersionedInst.

  ///

  /// \p OrigInst is the instruction corresponding to \p VersionedInst in the

  /// original loop.  Initialize the aliasing scopes with

  /// prepareNoAliasMetadata once before this can be called.

  void annotateInstWithNoAlias(Instruction *VersionedInst,

                               const Instruction *OrigInst);

private:

  /// Adds the necessary PHI nodes for the versioned loops based on the

  /// loop-defined values used outside of the loop.

  ///

  /// This needs to be called after versionLoop if there are defs in the loop

  /// that are used outside the loop.

  void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside);

  /// Add the noalias annotations to \p I.  Initialize the aliasing

  /// scopes with prepareNoAliasMetadata once before this can be called.

  void annotateInstWithNoAlias(Instruction *I) {

    annotateInstWithNoAlias(I, I);

  }

  /// The original loop.  This becomes the "versioned" one.  I.e.,

  /// control flows here if pointers in the loop don't alias.

  Loop *VersionedLoop;

  /// The fall-back loop.  I.e. control flows here if pointers in the

  /// loop may alias (memchecks failed).

  Loop *NonVersionedLoop = nullptr;

  /// This maps the instructions from VersionedLoop to their counterpart

  /// in NonVersionedLoop.

  ValueToValueMapTy VMap;

  /// The set of alias checks that we are versioning for.

  SmallVector<RuntimePointerCheck, 4> AliasChecks;

  /// The set of SCEV checks that we are versioning for.

  const SCEVPredicate &Preds;

  /// Maps a pointer to the pointer checking group that the pointer

  /// belongs to.

  DenseMap<const Value *, const RuntimeCheckingPtrGroup *> PtrToGroup;

  /// The alias scope corresponding to a pointer checking group.

  DenseMap<const RuntimeCheckingPtrGroup *, MDNode *> GroupToScope;

  /// The list of alias scopes that a pointer checking group can't alias.

  DenseMap<const RuntimeCheckingPtrGroup *, MDNode *>

      GroupToNonAliasingScopeList;

  /// Analyses used.

  const LoopAccessInfo &LAI;

  LoopInfo *LI;

  DominatorTree *DT;

  ScalarEvolution *SE;

};

/// Expose LoopVersioning as a pass.  Currently this is only used for

/// unit-testing.  It adds all memchecks necessary to remove all may-aliasing

/// array accesses from the loop.

class LoopVersioningPass : public PassInfoMixin<LoopVersioningPass> {

public:

  PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);

};

}

#endif