llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp

//===- AssumeBundleBuilder.cpp - tools to preserve informations -*- 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
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumeBundleQueries.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Operator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/DebugCounter.h"
#include "llvm/Transforms/Utils/Local.h"

using namespace llvm;

namespace llvm {
cl::opt<bool> EnableKnowledgeRetention(
    "enable-knowledge-retention", cl::init(false), cl::Hidden,
    cl::desc(
        "enable preservation of attributes throughout code transformation"));
} // namespace llvm

#define DEBUG_TYPE "assume-builder"

STATISTIC(NumAssumeBuilt, "Number of assume built by the assume builder");
STATISTIC(NumBundlesInAssumes, "Total number of Bundles in the assume built");

DEBUG_COUNTER(BuildAssumeCounter, "assume-builder-counter",
              "Controls which assumes gets created");

namespace {

bool isUsefullToPreserve(Attribute::AttrKind Kind) {
  switch (Kind) {
    case Attribute::NonNull:
    case Attribute::NoUndef:
    case Attribute::Alignment:
    case Attribute::Dereferenceable:
    case Attribute::DereferenceableOrNull:
    case Attribute::Cold:
      return true;
    default:
      return false;
  }
}

/// This function will try to transform the given knowledge into a more
/// canonical one. the canonical knowledge maybe the given one.
RetainedKnowledge canonicalizedKnowledge(RetainedKnowledge RK,
                                         const DataLayout &DL) {
  switch (RK.AttrKind) {
  default:
    return RK;
  case Attribute::NonNull:
    RK.WasOn = RK.WasOn->stripInBoundsOffsets();
    return RK;
  case Attribute::Alignment: {
    Value *V = RK.WasOn->stripInBoundsOffsets([&](const Value *Strip) {
      if (auto *GEP = dyn_cast<GEPOperator>(Strip))
        RK.ArgValue =
            MinAlign(RK.ArgValue, GEP->getMaxPreservedAlignment(DL).value());
    });
    RK.WasOn = V;
    return RK;
  }
  case Attribute::Dereferenceable:
  case Attribute::DereferenceableOrNull: {
    int64_t Offset = 0;
    Value *V = GetPointerBaseWithConstantOffset(RK.WasOn, Offset, DL,
                                                /*AllowNonInBounds*/ false);
    if (Offset < 0)
      return RK;
    RK.ArgValue = RK.ArgValue + Offset;
    RK.WasOn = V;
  }
  }
  return RK;
}

/// This class contain all knowledge that have been gather while building an
/// llvm.assume and the function to manipulate it.
struct AssumeBuilderState {
  Module *M;

  using MapKey = std::pair<Value *, Attribute::AttrKind>;
  SmallMapVector<MapKey, uint64_t, 8> AssumedKnowledgeMap;
  Instruction *InstBeingModified = nullptr;
  AssumptionCache* AC = nullptr;
  DominatorTree* DT = nullptr;

  AssumeBuilderState(Module *M, Instruction *I = nullptr,
                     AssumptionCache *AC = nullptr, DominatorTree *DT = nullptr)
      : M(M), InstBeingModified(I), AC(AC), DT(DT) {}

  bool tryToPreserveWithoutAddingAssume(RetainedKnowledge RK) {
    if (!InstBeingModified || !RK.WasOn || !AC)
      return false;
    bool HasBeenPreserved = false;
    Use* ToUpdate = nullptr;
    getKnowledgeForValue(
        RK.WasOn, {RK.AttrKind}, *AC,
        [&](RetainedKnowledge RKOther, Instruction *Assume,
            const CallInst::BundleOpInfo *Bundle) {
          if (!isValidAssumeForContext(Assume, InstBeingModified, DT))
            return false;
          if (RKOther.ArgValue >= RK.ArgValue) {
            HasBeenPreserved = true;
            return true;
          } else if (isValidAssumeForContext(InstBeingModified, Assume, DT)) {
            HasBeenPreserved = true;
            IntrinsicInst *Intr = cast<IntrinsicInst>(Assume);
            ToUpdate = &Intr->op_begin()[Bundle->Begin + ABA_Argument];
            return true;
          }
          return false;
        });
    if (ToUpdate)
      ToUpdate->set(
          ConstantInt::get(Type::getInt64Ty(M->getContext()), RK.ArgValue));
    return HasBeenPreserved;
  }

  bool isKnowledgeWorthPreserving(RetainedKnowledge RK) {
    if (!RK)
      return false;
    if (!RK.WasOn)
      return true;
    if (RK.WasOn->getType()->isPointerTy()) {
      Value *UnderlyingPtr = getUnderlyingObject(RK.WasOn);
      if (isa<AllocaInst>(UnderlyingPtr) || isa<GlobalValue>(UnderlyingPtr))
        return false;
    }
    if (auto *Arg = dyn_cast<Argument>(RK.WasOn)) {
      if (Arg->hasAttribute(RK.AttrKind) &&
          (!Attribute::isIntAttrKind(RK.AttrKind) ||
           Arg->getAttribute(RK.AttrKind).getValueAsInt() >= RK.ArgValue))
        return false;
      return true;
    }
    if (auto *Inst = dyn_cast<Instruction>(RK.WasOn))
      if (wouldInstructionBeTriviallyDead(Inst)) {
        if (RK.WasOn->use_empty())
          return false;
        Use *SingleUse = RK.WasOn->getSingleUndroppableUse();
        if (SingleUse && SingleUse->getUser() == InstBeingModified)
          return false;
      }
    return true;
  }

  void addKnowledge(RetainedKnowledge RK) {
    RK = canonicalizedKnowledge(RK, M->getDataLayout());

    if (!isKnowledgeWorthPreserving(RK))
      return;

    if (tryToPreserveWithoutAddingAssume(RK))
      return;
    MapKey Key{RK.WasOn, RK.AttrKind};
    auto [Lookup, Inserted] = AssumedKnowledgeMap.try_emplace(Key, RK.ArgValue);
    if (Inserted)
      return;
    assert(((Lookup->second == 0 && RK.ArgValue == 0) ||
            (Lookup->second != 0 && RK.ArgValue != 0)) &&
           "inconsistent argument value");

    /// This is only desirable because for all attributes taking an argument
    /// higher is better.
    Lookup->second = std::max(Lookup->second, RK.ArgValue);
  }

  void addAttribute(Attribute Attr, Value *WasOn) {
    if (Attr.isTypeAttribute() || Attr.isStringAttribute() ||
        !isUsefullToPreserve(Attr.getKindAsEnum()))
      return;
    uint64_t AttrArg = 0;
    if (Attr.isIntAttribute())
      AttrArg = Attr.getValueAsInt();
    addKnowledge({Attr.getKindAsEnum(), AttrArg, WasOn});
  }

  void addCall(const CallBase *Call) {
    auto addAttrList = [&](AttributeList AttrList, unsigned NumArgs) {
      for (unsigned Idx = 0; Idx < NumArgs; Idx++)
        for (Attribute Attr : AttrList.getParamAttrs(Idx)) {
          bool IsPoisonAttr = Attr.hasAttribute(Attribute::NonNull) ||
                              Attr.hasAttribute(Attribute::Alignment);
          if (!IsPoisonAttr || Call->isPassingUndefUB(Idx))
            addAttribute(Attr, Call->getArgOperand(Idx));
        }
      for (Attribute Attr : AttrList.getFnAttrs())
        addAttribute(Attr, nullptr);
    };
    addAttrList(Call->getAttributes(), Call->arg_size());
    if (Function *Fn = Call->getCalledFunction())
      addAttrList(Fn->getAttributes(), Fn->arg_size());
  }

  AssumeInst *build() {
    if (AssumedKnowledgeMap.empty())
      return nullptr;
    if (!DebugCounter::shouldExecute(BuildAssumeCounter))
      return nullptr;
    Function *FnAssume =
        Intrinsic::getOrInsertDeclaration(M, Intrinsic::assume);
    LLVMContext &C = M->getContext();
    SmallVector<OperandBundleDef, 8> OpBundle;
    for (auto &MapElem : AssumedKnowledgeMap) {
      SmallVector<Value *, 2> Args;
      if (MapElem.first.first)
        Args.push_back(MapElem.first.first);

      /// This is only valid because for all attribute that currently exist a
      /// value of 0 is useless. and should not be preserved.
      if (MapElem.second)
        Args.push_back(ConstantInt::get(Type::getInt64Ty(M->getContext()),
                                        MapElem.second));
      OpBundle.push_back(OperandBundleDefT<Value *>(
          std::string(Attribute::getNameFromAttrKind(MapElem.first.second)),
          Args));
      NumBundlesInAssumes++;
    }
    NumAssumeBuilt++;
    return cast<AssumeInst>(CallInst::Create(
        FnAssume, ArrayRef<Value *>({ConstantInt::getTrue(C)}), OpBundle));
  }

  void addAccessedPtr(Instruction *MemInst, Value *Pointer, Type *AccType,
                      MaybeAlign MA) {
    unsigned DerefSize = MemInst->getModule()
                             ->getDataLayout()
                             .getTypeStoreSize(AccType)
                             .getKnownMinValue();
    if (DerefSize != 0) {
      addKnowledge({Attribute::Dereferenceable, DerefSize, Pointer});
      if (!NullPointerIsDefined(MemInst->getFunction(),
                                Pointer->getType()->getPointerAddressSpace()))
        addKnowledge({Attribute::NonNull, 0u, Pointer});
    }
    if (MA.valueOrOne() > 1)
      addKnowledge({Attribute::Alignment, MA.valueOrOne().value(), Pointer});
  }

  void addInstruction(Instruction *I) {
    if (auto *Call = dyn_cast<CallBase>(I))
      return addCall(Call);
    if (auto *Load = dyn_cast<LoadInst>(I))
      return addAccessedPtr(I, Load->getPointerOperand(), Load->getType(),
                            Load->getAlign());
    if (auto *Store = dyn_cast<StoreInst>(I))
      return addAccessedPtr(I, Store->getPointerOperand(),
                            Store->getValueOperand()->getType(),
                            Store->getAlign());
    if (auto *RMW = dyn_cast<AtomicRMWInst>(I))
      return addAccessedPtr(I, RMW->getPointerOperand(),
                            RMW->getValOperand()->getType(), RMW->getAlign());
    if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(I))
      return addAccessedPtr(I, CmpXchg->getPointerOperand(),
                            CmpXchg->getCompareOperand()->getType(),
                            CmpXchg->getAlign());
    // TODO: Maybe we should look around and merge with other llvm.assume.
  }
};

} // namespace

AssumeInst *llvm::buildAssumeFromInst(Instruction *I) {
  if (!EnableKnowledgeRetention)
    return nullptr;
  AssumeBuilderState Builder(I->getModule());
  Builder.addInstruction(I);
  return Builder.build();
}

bool llvm::salvageKnowledge(Instruction *I, AssumptionCache *AC,
                            DominatorTree *DT) {
  if (!EnableKnowledgeRetention || I->isTerminator())
    return false;
  bool Changed = false;
  AssumeBuilderState Builder(I->getModule(), I, AC, DT);
  Builder.addInstruction(I);
  if (auto *Intr = Builder.build()) {
    Intr->insertBefore(I->getIterator());
    Changed = true;
    if (AC)
      AC->registerAssumption(Intr);
  }
  return Changed;
}

PreservedAnalyses AssumeBuilderPass::run(Function &F,
                                         FunctionAnalysisManager &AM) {
  AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(F);
  DominatorTree* DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
  bool Changed = false;
  for (Instruction &I : instructions(F))
    Changed |= salvageKnowledge(&I, AC, DT);
  if (!Changed)
    PreservedAnalyses::all();
  PreservedAnalyses PA;
  PA.preserveSet<CFGAnalyses>();
  return PA;
}