GuardWidening.cpp | Explore in Territory

//===- GuardWidening.cpp - ---- Guard widening ----------------------------===//
//
// 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 implements the guard widening pass.  The semantics of the
// @llvm.experimental.guard intrinsic lets LLVM transform it so that it fails
// more often that it did before the transform.  This optimization is called
// "widening" and can be used hoist and common runtime checks in situations like
// these:
//
//    %cmp0 = 7 u< Length
//    call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ]
//    call @unknown_side_effects()
//    %cmp1 = 9 u< Length
//    call @llvm.experimental.guard(i1 %cmp1) [ "deopt"(...) ]
//    ...
//
// =>
//
//    %cmp0 = 9 u< Length
//    call @llvm.experimental.guard(i1 %cmp0) [ "deopt"(...) ]
//    call @unknown_side_effects()
//    ...
//
// If %cmp0 is false, @llvm.experimental.guard will "deoptimize" back to a
// generic implementation of the same function, which will have the correct
// semantics from that point onward.  It is always _legal_ to deoptimize (so
// replacing %cmp0 with false is "correct"), though it may not always be
// profitable to do so.
//
// NB! This pass is a work in progress.  It hasn't been tuned to be "production
// ready" yet.  It is known to have quadriatic running time and will not scale
// to large numbers of guards
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/GuardWidening.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/GuardUtils.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/ConstantRange.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/KnownBits.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/GuardUtils.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include <functional>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(GuardsEliminated, "Number of eliminated guards");
STATISTIC(CondBranchEliminated, "Number of eliminated conditional branches");
STATISTIC(FreezeAdded, "Number of freeze instruction introduced");

static cl::opt<bool>
    WidenBranchGuards("guard-widening-widen-branch-guards", cl::Hidden,
                      cl::desc("Whether or not we should widen guards  "
                               "expressed as branches by widenable conditions"),
                      cl::init(true));

namespace {

// Get the condition of \p I. It can either be a guard or a conditional branch.
static Value *getCondition(Instruction *I) { … }

// Set the condition for \p I to \p NewCond. \p I can either be a guard or a
// conditional branch.
static void setCondition(Instruction *I, Value *NewCond) { … }

// Eliminates the guard instruction properly.
static void eliminateGuard(Instruction *GuardInst, MemorySSAUpdater *MSSAU) { … }

/// Find a point at which the widened condition of \p Guard should be inserted.
/// When it is represented as intrinsic call, we can do it right before the call
/// instruction. However, when we are dealing with widenable branch, we must
/// account for the following situation: widening should not turn a
/// loop-invariant condition into a loop-variant. It means that if
/// widenable.condition() call is invariant (w.r.t. any loop), the new wide
/// condition should stay invariant. Otherwise there can be a miscompile, like
/// the one described at https://github.com/llvm/llvm-project/issues/60234. The
/// safest way to do it is to expand the new condition at WC's block.
static std::optional<BasicBlock::iterator>
findInsertionPointForWideCondition(Instruction *WCOrGuard) { … }

class GuardWideningImpl { … };
}

static bool isSupportedGuardInstruction(const Instruction *Insn) { … }

bool GuardWideningImpl::run() { … }

bool GuardWideningImpl::eliminateInstrViaWidening(
    Instruction *Instr, const df_iterator<DomTreeNode *> &DFSI,
    const DenseMap<BasicBlock *, SmallVector<Instruction *, 8>>
        &GuardsInBlock) { … }

GuardWideningImpl::WideningScore GuardWideningImpl::computeWideningScore(
    Instruction *DominatedInstr, Instruction *ToWiden,
    BasicBlock::iterator WideningPoint, SmallVectorImpl<Value *> &ChecksToHoist,
    SmallVectorImpl<Value *> &ChecksToWiden) { … }

bool GuardWideningImpl::canBeHoistedTo(
    const Value *V, BasicBlock::iterator Loc,
    SmallPtrSetImpl<const Instruction *> &Visited) const { … }

void GuardWideningImpl::makeAvailableAt(Value *V,
                                        BasicBlock::iterator Loc) const { … }

// Return Instruction before which we can insert freeze for the value V as close
// to def as possible. If there is no place to add freeze, return empty.
static std::optional<BasicBlock::iterator>
getFreezeInsertPt(Value *V, const DominatorTree &DT) { … }

Value *GuardWideningImpl::freezeAndPush(Value *Orig,
                                        BasicBlock::iterator InsertPt) { … }

std::optional<Value *>
GuardWideningImpl::mergeChecks(SmallVectorImpl<Value *> &ChecksToHoist,
                               SmallVectorImpl<Value *> &ChecksToWiden,
                               std::optional<BasicBlock::iterator> InsertPt) { … }

Value *GuardWideningImpl::hoistChecks(SmallVectorImpl<Value *> &ChecksToHoist,
                                      Value *OldCondition,
                                      BasicBlock::iterator InsertPt) { … }

bool GuardWideningImpl::parseRangeChecks(
    Value *CheckCond, SmallVectorImpl<GuardWideningImpl::RangeCheck> &Checks) { … }

bool GuardWideningImpl::combineRangeChecks(
    SmallVectorImpl<GuardWideningImpl::RangeCheck> &Checks,
    SmallVectorImpl<GuardWideningImpl::RangeCheck> &RangeChecksOut) const { … }

#ifndef NDEBUG
StringRef GuardWideningImpl::scoreTypeToString(WideningScore WS) {
  switch (WS) {
  case WS_IllegalOrNegative:
    return "IllegalOrNegative";
  case WS_Neutral:
    return "Neutral";
  case WS_Positive:
    return "Positive";
  case WS_VeryPositive:
    return "VeryPositive";
  }

  llvm_unreachable("Fully covered switch above!");
}
#endif

PreservedAnalyses GuardWideningPass::run(Function &F,
                                         FunctionAnalysisManager &AM) { … }

PreservedAnalyses GuardWideningPass::run(Loop &L, LoopAnalysisManager &AM,
                                         LoopStandardAnalysisResults &AR,
                                         LPMUpdater &U) { … }
llvm/llvm/lib/Transforms/Scalar/GuardWidening.cpp
