CallSiteSplitting.cpp | Explore in Territory

//===- CallSiteSplitting.cpp ----------------------------------------------===//
//
// 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 a transformation that tries to split a call-site to pass
// more constrained arguments if its argument is predicated in the control flow
// so that we can expose better context to the later passes (e.g, inliner, jump
// threading, or IPA-CP based function cloning, etc.).
// As of now we support two cases :
//
// 1) Try to a split call-site with constrained arguments, if any constraints
// on any argument can be found by following the single predecessors of the
// all site's predecessors. Currently this pass only handles call-sites with 2
// predecessors. For example, in the code below, we try to split the call-site
// since we can predicate the argument(ptr) based on the OR condition.
//
// Split from :
//   if (!ptr || c)
//     callee(ptr);
// to :
//   if (!ptr)
//     callee(null)         // set the known constant value
//   else if (c)
//     callee(nonnull ptr)  // set non-null attribute in the argument
//
// 2) We can also split a call-site based on constant incoming values of a PHI
// For example,
// from :
//   Header:
//    %c = icmp eq i32 %i1, %i2
//    br i1 %c, label %Tail, label %TBB
//   TBB:
//    br label Tail%
//   Tail:
//    %p = phi i32 [ 0, %Header], [ 1, %TBB]
//    call void @bar(i32 %p)
// to
//   Header:
//    %c = icmp eq i32 %i1, %i2
//    br i1 %c, label %Tail-split0, label %TBB
//   TBB:
//    br label %Tail-split1
//   Tail-split0:
//    call void @bar(i32 0)
//    br label %Tail
//   Tail-split1:
//    call void @bar(i32 1)
//    br label %Tail
//   Tail:
//    %p = phi i32 [ 0, %Tail-split0 ], [ 1, %Tail-split1 ]
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Scalar/CallSiteSplitting.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/Analysis/TargetTransformInfo.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/PatternMatch.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"

usingnamespacellvm;
usingnamespacePatternMatch;

#define DEBUG_TYPE …

STATISTIC(NumCallSiteSplit, "Number of call-site split");

/// Only allow instructions before a call, if their CodeSize cost is below
/// DuplicationThreshold. Those instructions need to be duplicated in all
/// split blocks.
static cl::opt<unsigned>
    DuplicationThreshold("callsite-splitting-duplication-threshold", cl::Hidden,
                         cl::desc("Only allow instructions before a call, if "
                                  "their cost is below DuplicationThreshold"),
                         cl::init(5));

static void addNonNullAttribute(CallBase &CB, Value *Op) { … }

static void setConstantInArgument(CallBase &CB, Value *Op,
                                  Constant *ConstValue) { … }

static bool isCondRelevantToAnyCallArgument(ICmpInst *Cmp, CallBase &CB) { … }

ConditionTy;
ConditionsTy;

/// If From has a conditional jump to To, add the condition to Conditions,
/// if it is relevant to any argument at CB.
static void recordCondition(CallBase &CB, BasicBlock *From, BasicBlock *To,
                            ConditionsTy &Conditions) { … }

/// Record ICmp conditions relevant to any argument in CB following Pred's
/// single predecessors. If there are conflicting conditions along a path, like
/// x == 1 and x == 0, the first condition will be used. We stop once we reach
/// an edge to StopAt.
static void recordConditions(CallBase &CB, BasicBlock *Pred,
                             ConditionsTy &Conditions, BasicBlock *StopAt) { … }

static void addConditions(CallBase &CB, const ConditionsTy &Conditions) { … }

static SmallVector<BasicBlock *, 2> getTwoPredecessors(BasicBlock *BB) { … }

static bool canSplitCallSite(CallBase &CB, TargetTransformInfo &TTI) { … }

static Instruction *cloneInstForMustTail(Instruction *I, Instruction *Before,
                                         Value *V) { … }

/// Copy mandatory `musttail` return sequence that follows original `CI`, and
/// link it up to `NewCI` value instead:
///
///   * (optional) `bitcast NewCI to ...`
///   * `ret bitcast or NewCI`
///
/// Insert this sequence right before `SplitBB`'s terminator, which will be
/// cleaned up later in `splitCallSite` below.
static void copyMustTailReturn(BasicBlock *SplitBB, Instruction *CI,
                               Instruction *NewCI) { … }

/// For each (predecessor, conditions from predecessors) pair, it will split the
/// basic block containing the call site, hook it up to the predecessor and
/// replace the call instruction with new call instructions, which contain
/// constraints based on the conditions from their predecessors.
/// For example, in the IR below with an OR condition, the call-site can
/// be split. In this case, Preds for Tail is [(Header, a == null),
/// (TBB, a != null, b == null)]. Tail is replaced by 2 split blocks, containing
/// CallInst1, which has constraints based on the conditions from Head and
/// CallInst2, which has constraints based on the conditions coming from TBB.
///
/// From :
///
///   Header:
///     %c = icmp eq i32* %a, null
///     br i1 %c %Tail, %TBB
///   TBB:
///     %c2 = icmp eq i32* %b, null
///     br i1 %c %Tail, %End
///   Tail:
///     %ca = call i1  @callee (i32* %a, i32* %b)
///
///  to :
///
///   Header:                          // PredBB1 is Header
///     %c = icmp eq i32* %a, null
///     br i1 %c %Tail-split1, %TBB
///   TBB:                             // PredBB2 is TBB
///     %c2 = icmp eq i32* %b, null
///     br i1 %c %Tail-split2, %End
///   Tail-split1:
///     %ca1 = call @callee (i32* null, i32* %b)         // CallInst1
///    br %Tail
///   Tail-split2:
///     %ca2 = call @callee (i32* nonnull %a, i32* null) // CallInst2
///    br %Tail
///   Tail:
///    %p = phi i1 [%ca1, %Tail-split1],[%ca2, %Tail-split2]
///
/// Note that in case any arguments at the call-site are constrained by its
/// predecessors, new call-sites with more constrained arguments will be
/// created in createCallSitesOnPredicatedArgument().
static void splitCallSite(CallBase &CB,
                          ArrayRef<std::pair<BasicBlock *, ConditionsTy>> Preds,
                          DomTreeUpdater &DTU) { … }

// Return true if the call-site has an argument which is a PHI with only
// constant incoming values.
static bool isPredicatedOnPHI(CallBase &CB) { … }

PredsWithCondsTy;

// Check if any of the arguments in CS are predicated on a PHI node and return
// the set of predecessors we should use for splitting.
static PredsWithCondsTy shouldSplitOnPHIPredicatedArgument(CallBase &CB) { … }

// Checks if any of the arguments in CS are predicated in a predecessor and
// returns a list of predecessors with the conditions that hold on their edges
// to CS.
static PredsWithCondsTy shouldSplitOnPredicatedArgument(CallBase &CB,
                                                        DomTreeUpdater &DTU) { … }

static bool tryToSplitCallSite(CallBase &CB, TargetTransformInfo &TTI,
                               DomTreeUpdater &DTU) { … }

static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI,
                                TargetTransformInfo &TTI, DominatorTree &DT) { … }

PreservedAnalyses CallSiteSplittingPass::run(Function &F,
                                             FunctionAnalysisManager &AM) { … }
llvm/llvm/lib/Transforms/Scalar/CallSiteSplitting.cpp
