contrib/llvm-project/llvm/lib/Transforms/IPO/CalledValuePropagation.cpp

   1 //===- CalledValuePropagation.cpp - Propagate called values -----*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements a transformation that attaches !callees metadata to
  10 // indirect call sites. For a given call site, the metadata, if present,
  11 // indicates the set of functions the call site could possibly target at
  12 // run-time. This metadata is added to indirect call sites when the set of
  13 // possible targets can be determined by analysis and is known to be small. The
  14 // analysis driving the transformation is similar to constant propagation and
  15 // makes uses of the generic sparse propagation solver.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/Transforms/IPO/CalledValuePropagation.h"
  20 #include "llvm/Analysis/SparsePropagation.h"
  21 #include "llvm/Analysis/ValueLatticeUtils.h"
  22 #include "llvm/IR/InstVisitor.h"
  23 #include "llvm/IR/MDBuilder.h"
  24 #include "llvm/InitializePasses.h"
  25 #include "llvm/Support/CommandLine.h"
  26 #include "llvm/Transforms/IPO.h"
  27 using namespace llvm;
  28
  29 #define DEBUG_TYPE "called-value-propagation"
  30
  31 /// The maximum number of functions to track per lattice value. Once the number
  32 /// of functions a call site can possibly target exceeds this threshold, it's
  33 /// lattice value becomes overdefined. The number of possible lattice values is
  34 /// bounded by Ch(F, M), where F is the number of functions in the module and M
  35 /// is MaxFunctionsPerValue. As such, this value should be kept very small. We
  36 /// likely can't do anything useful for call sites with a large number of
  37 /// possible targets, anyway.
  38 static cl::opt<unsigned> MaxFunctionsPerValue(
  39     "cvp-max-functions-per-value", cl::Hidden, cl::init(4),
  40     cl::desc("The maximum number of functions to track per lattice value"));
  41
  42 namespace {
  43 /// To enable interprocedural analysis, we assign LLVM values to the following
  44 /// groups. The register group represents SSA registers, the return group
  45 /// represents the return values of functions, and the memory group represents
  46 /// in-memory values. An LLVM Value can technically be in more than one group.
  47 /// It's necessary to distinguish these groups so we can, for example, track a
  48 /// global variable separately from the value stored at its location.
  49 enum class IPOGrouping { Register, Return, Memory };
  50
  51 /// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings.
  52 using CVPLatticeKey = PointerIntPair<Value *, 2, IPOGrouping>;
  53
  54 /// The lattice value type used by our custom lattice function. It holds the
  55 /// lattice state, and a set of functions.
  56 class CVPLatticeVal {
  57 public:
  58   /// The states of the lattice values. Only the FunctionSet state is
  59   /// interesting. It indicates the set of functions to which an LLVM value may
  60   /// refer.
  61   enum CVPLatticeStateTy { Undefined, FunctionSet, Overdefined, Untracked };
  62
  63   /// Comparator for sorting the functions set. We want to keep the order
  64   /// deterministic for testing, etc.
  65   struct Compare {
  66     bool operator()(const Function *LHS, const Function *RHS) const {
  67       return LHS->getName() < RHS->getName();
  68     }
  69   };
  70
  71   CVPLatticeVal() : LatticeState(Undefined) {}
  72   CVPLatticeVal(CVPLatticeStateTy LatticeState) : LatticeState(LatticeState) {}
  73   CVPLatticeVal(std::vector<Function *> &&Functions)
  74       : LatticeState(FunctionSet), Functions(std::move(Functions)) {
  75     assert(std::is_sorted(this->Functions.begin(), this->Functions.end(),
  76                           Compare()));
  77   }
  78
  79   /// Get a reference to the functions held by this lattice value. The number
  80   /// of functions will be zero for states other than FunctionSet.
  81   const std::vector<Function *> &getFunctions() const {
  82     return Functions;
  83   }
  84
  85   /// Returns true if the lattice value is in the FunctionSet state.
  86   bool isFunctionSet() const { return LatticeState == FunctionSet; }
  87
  88   bool operator==(const CVPLatticeVal &RHS) const {
  89     return LatticeState == RHS.LatticeState && Functions == RHS.Functions;
  90   }
  91
  92   bool operator!=(const CVPLatticeVal &RHS) const {
  93     return LatticeState != RHS.LatticeState || Functions != RHS.Functions;
  94   }
  95
  96 private:
  97   /// Holds the state this lattice value is in.
  98   CVPLatticeStateTy LatticeState;
  99
 100   /// Holds functions indicating the possible targets of call sites. This set
 101   /// is empty for lattice values in the undefined, overdefined, and untracked
 102   /// states. The maximum size of the set is controlled by
 103   /// MaxFunctionsPerValue. Since most LLVM values are expected to be in
 104   /// uninteresting states (i.e., overdefined), CVPLatticeVal objects should be
 105   /// small and efficiently copyable.
 106   // FIXME: This could be a TinyPtrVector and/or merge with LatticeState.
 107   std::vector<Function *> Functions;
 108 };
 109
 110 /// The custom lattice function used by the generic sparse propagation solver.
 111 /// It handles merging lattice values and computing new lattice values for
 112 /// constants, arguments, values returned from trackable functions, and values
 113 /// located in trackable global variables. It also computes the lattice values
 114 /// that change as a result of executing instructions.
 115 class CVPLatticeFunc
 116     : public AbstractLatticeFunction<CVPLatticeKey, CVPLatticeVal> {
 117 public:
 118   CVPLatticeFunc()
 119       : AbstractLatticeFunction(CVPLatticeVal(CVPLatticeVal::Undefined),
 120                                 CVPLatticeVal(CVPLatticeVal::Overdefined),
 121                                 CVPLatticeVal(CVPLatticeVal::Untracked)) {}
 122
 123   /// Compute and return a CVPLatticeVal for the given CVPLatticeKey.
 124   CVPLatticeVal ComputeLatticeVal(CVPLatticeKey Key) override {
 125     switch (Key.getInt()) {
 126     case IPOGrouping::Register:
 127       if (isa<Instruction>(Key.getPointer())) {
 128         return getUndefVal();
 129       } else if (auto *A = dyn_cast<Argument>(Key.getPointer())) {
 130         if (canTrackArgumentsInterprocedurally(A->getParent()))
 131           return getUndefVal();
 132       } else if (auto *C = dyn_cast<Constant>(Key.getPointer())) {
 133         return computeConstant(C);
 134       }
 135       return getOverdefinedVal();
 136     case IPOGrouping::Memory:
 137     case IPOGrouping::Return:
 138       if (auto *GV = dyn_cast<GlobalVariable>(Key.getPointer())) {
 139         if (canTrackGlobalVariableInterprocedurally(GV))
 140           return computeConstant(GV->getInitializer());
 141       } else if (auto *F = cast<Function>(Key.getPointer()))
 142         if (canTrackReturnsInterprocedurally(F))
 143           return getUndefVal();
 144     }
 145     return getOverdefinedVal();
 146   }
 147
 148   /// Merge the two given lattice values. The interesting cases are merging two
 149   /// FunctionSet values and a FunctionSet value with an Undefined value. For
 150   /// these cases, we simply union the function sets. If the size of the union
 151   /// is greater than the maximum functions we track, the merged value is
 152   /// overdefined.
 153   CVPLatticeVal MergeValues(CVPLatticeVal X, CVPLatticeVal Y) override {
 154     if (X == getOverdefinedVal() || Y == getOverdefinedVal())
 155       return getOverdefinedVal();
 156     if (X == getUndefVal() && Y == getUndefVal())
 157       return getUndefVal();
 158     std::vector<Function *> Union;
 159     std::set_union(X.getFunctions().begin(), X.getFunctions().end(),
 160                    Y.getFunctions().begin(), Y.getFunctions().end(),
 161                    std::back_inserter(Union), CVPLatticeVal::Compare{});
 162     if (Union.size() > MaxFunctionsPerValue)
 163       return getOverdefinedVal();
 164     return CVPLatticeVal(std::move(Union));
 165   }
 166
 167   /// Compute the lattice values that change as a result of executing the given
 168   /// instruction. The changed values are stored in \p ChangedValues. We handle
 169   /// just a few kinds of instructions since we're only propagating values that
 170   /// can be called.
 171   void ComputeInstructionState(
 172       Instruction &I, DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
 173       SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) override {
 174     switch (I.getOpcode()) {
 175     case Instruction::Call:
 176       return visitCallSite(cast<CallInst>(&I), ChangedValues, SS);
 177     case Instruction::Invoke:
 178       return visitCallSite(cast<InvokeInst>(&I), ChangedValues, SS);
 179     case Instruction::Load:
 180       return visitLoad(*cast<LoadInst>(&I), ChangedValues, SS);
 181     case Instruction::Ret:
 182       return visitReturn(*cast<ReturnInst>(&I), ChangedValues, SS);
 183     case Instruction::Select:
 184       return visitSelect(*cast<SelectInst>(&I), ChangedValues, SS);
 185     case Instruction::Store:
 186       return visitStore(*cast<StoreInst>(&I), ChangedValues, SS);
 187     default:
 188       return visitInst(I, ChangedValues, SS);
 189     }
 190   }
 191
 192   /// Print the given CVPLatticeVal to the specified stream.
 193   void PrintLatticeVal(CVPLatticeVal LV, raw_ostream &OS) override {
 194     if (LV == getUndefVal())
 195       OS << "Undefined  ";
 196     else if (LV == getOverdefinedVal())
 197       OS << "Overdefined";
 198     else if (LV == getUntrackedVal())
 199       OS << "Untracked  ";
 200     else
 201       OS << "FunctionSet";
 202   }
 203
 204   /// Print the given CVPLatticeKey to the specified stream.
 205   void PrintLatticeKey(CVPLatticeKey Key, raw_ostream &OS) override {
 206     if (Key.getInt() == IPOGrouping::Register)
 207       OS << "<reg> ";
 208     else if (Key.getInt() == IPOGrouping::Memory)
 209       OS << "<mem> ";
 210     else if (Key.getInt() == IPOGrouping::Return)
 211       OS << "<ret> ";
 212     if (isa<Function>(Key.getPointer()))
 213       OS << Key.getPointer()->getName();
 214     else
 215       OS << *Key.getPointer();
 216   }
 217
 218   /// We collect a set of indirect calls when visiting call sites. This method
 219   /// returns a reference to that set.
 220   SmallPtrSetImpl<Instruction *> &getIndirectCalls() { return IndirectCalls; }
 221
 222 private:
 223   /// Holds the indirect calls we encounter during the analysis. We will attach
 224   /// metadata to these calls after the analysis indicating the functions the
 225   /// calls can possibly target.
 226   SmallPtrSet<Instruction *, 32> IndirectCalls;
 227
 228   /// Compute a new lattice value for the given constant. The constant, after
 229   /// stripping any pointer casts, should be a Function. We ignore null
 230   /// pointers as an optimization, since calling these values is undefined
 231   /// behavior.
 232   CVPLatticeVal computeConstant(Constant *C) {
 233     if (isa<ConstantPointerNull>(C))
 234       return CVPLatticeVal(CVPLatticeVal::FunctionSet);
 235     if (auto *F = dyn_cast<Function>(C->stripPointerCasts()))
 236       return CVPLatticeVal({F});
 237     return getOverdefinedVal();
 238   }
 239
 240   /// Handle return instructions. The function's return state is the merge of
 241   /// the returned value state and the function's return state.
 242   void visitReturn(ReturnInst &I,
 243                    DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
 244                    SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
 245     Function *F = I.getParent()->getParent();
 246     if (F->getReturnType()->isVoidTy())
 247       return;
 248     auto RegI = CVPLatticeKey(I.getReturnValue(), IPOGrouping::Register);
 249     auto RetF = CVPLatticeKey(F, IPOGrouping::Return);
 250     ChangedValues[RetF] =
 251         MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
 252   }
 253
 254   /// Handle call sites. The state of a called function's formal arguments is
 255   /// the merge of the argument state with the call sites corresponding actual
 256   /// argument state. The call site state is the merge of the call site state
 257   /// with the returned value state of the called function.
 258   void visitCallSite(CallSite CS,
 259                      DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
 260                      SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
 261     Function *F = CS.getCalledFunction();
 262     Instruction *I = CS.getInstruction();
 263     auto RegI = CVPLatticeKey(I, IPOGrouping::Register);
 264
 265     // If this is an indirect call, save it so we can quickly revisit it when
 266     // attaching metadata.
 267     if (!F)
 268       IndirectCalls.insert(I);
 269
 270     // If we can't track the function's return values, there's nothing to do.
 271     if (!F || !canTrackReturnsInterprocedurally(F)) {
 272       // Void return, No need to create and update CVPLattice state as no one
 273       // can use it.
 274       if (I->getType()->isVoidTy())
 275         return;
 276       ChangedValues[RegI] = getOverdefinedVal();
 277       return;
 278     }
 279
 280     // Inform the solver that the called function is executable, and perform
 281     // the merges for the arguments and return value.
 282     SS.MarkBlockExecutable(&F->front());
 283     auto RetF = CVPLatticeKey(F, IPOGrouping::Return);
 284     for (Argument &A : F->args()) {
 285       auto RegFormal = CVPLatticeKey(&A, IPOGrouping::Register);
 286       auto RegActual =
 287           CVPLatticeKey(CS.getArgument(A.getArgNo()), IPOGrouping::Register);
 288       ChangedValues[RegFormal] =
 289           MergeValues(SS.getValueState(RegFormal), SS.getValueState(RegActual));
 290     }
 291
 292     // Void return, No need to create and update CVPLattice state as no one can
 293     // use it.
 294     if (I->getType()->isVoidTy())
 295       return;
 296
 297     ChangedValues[RegI] =
 298         MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
 299   }
 300
 301   /// Handle select instructions. The select instruction state is the merge the
 302   /// true and false value states.
 303   void visitSelect(SelectInst &I,
 304                    DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
 305                    SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
 306     auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
 307     auto RegT = CVPLatticeKey(I.getTrueValue(), IPOGrouping::Register);
 308     auto RegF = CVPLatticeKey(I.getFalseValue(), IPOGrouping::Register);
 309     ChangedValues[RegI] =
 310         MergeValues(SS.getValueState(RegT), SS.getValueState(RegF));
 311   }
 312
 313   /// Handle load instructions. If the pointer operand of the load is a global
 314   /// variable, we attempt to track the value. The loaded value state is the
 315   /// merge of the loaded value state with the global variable state.
 316   void visitLoad(LoadInst &I,
 317                  DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
 318                  SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
 319     auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
 320     if (auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand())) {
 321       auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
 322       ChangedValues[RegI] =
 323           MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));
 324     } else {
 325       ChangedValues[RegI] = getOverdefinedVal();
 326     }
 327   }
 328
 329   /// Handle store instructions. If the pointer operand of the store is a
 330   /// global variable, we attempt to track the value. The global variable state
 331   /// is the merge of the stored value state with the global variable state.
 332   void visitStore(StoreInst &I,
 333                   DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
 334                   SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
 335     auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand());
 336     if (!GV)
 337       return;
 338     auto RegI = CVPLatticeKey(I.getValueOperand(), IPOGrouping::Register);
 339     auto MemGV = CVPLatticeKey(GV, IPOGrouping::Memory);
 340     ChangedValues[MemGV] =
 341         MergeValues(SS.getValueState(RegI), SS.getValueState(MemGV));
 342   }
 343
 344   /// Handle all other instructions. All other instructions are marked
 345   /// overdefined.
 346   void visitInst(Instruction &I,
 347                  DenseMap<CVPLatticeKey, CVPLatticeVal> &ChangedValues,
 348                  SparseSolver<CVPLatticeKey, CVPLatticeVal> &SS) {
 349     // Simply bail if this instruction has no user.
 350     if (I.use_empty())
 351       return;
 352     auto RegI = CVPLatticeKey(&I, IPOGrouping::Register);
 353     ChangedValues[RegI] = getOverdefinedVal();
 354   }
 355 };
 356 } // namespace
 357
 358 namespace llvm {
 359 /// A specialization of LatticeKeyInfo for CVPLatticeKeys. The generic solver
 360 /// must translate between LatticeKeys and LLVM Values when adding Values to
 361 /// its work list and inspecting the state of control-flow related values.
 362 template <> struct LatticeKeyInfo<CVPLatticeKey> {
 363   static inline Value *getValueFromLatticeKey(CVPLatticeKey Key) {
 364     return Key.getPointer();
 365   }
 366   static inline CVPLatticeKey getLatticeKeyFromValue(Value *V) {
 367     return CVPLatticeKey(V, IPOGrouping::Register);
 368   }
 369 };
 370 } // namespace llvm
 371
 372 static bool runCVP(Module &M) {
 373   // Our custom lattice function and generic sparse propagation solver.
 374   CVPLatticeFunc Lattice;
 375   SparseSolver<CVPLatticeKey, CVPLatticeVal> Solver(&Lattice);
 376
 377   // For each function in the module, if we can't track its arguments, let the
 378   // generic solver assume it is executable.
 379   for (Function &F : M)
 380     if (!F.isDeclaration() && !canTrackArgumentsInterprocedurally(&F))
 381       Solver.MarkBlockExecutable(&F.front());
 382
 383   // Solver our custom lattice. In doing so, we will also build a set of
 384   // indirect call sites.
 385   Solver.Solve();
 386
 387   // Attach metadata to the indirect call sites that were collected indicating
 388   // the set of functions they can possibly target.
 389   bool Changed = false;
 390   MDBuilder MDB(M.getContext());
 391   for (Instruction *C : Lattice.getIndirectCalls()) {
 392     CallSite CS(C);
 393     auto RegI = CVPLatticeKey(CS.getCalledValue(), IPOGrouping::Register);
 394     CVPLatticeVal LV = Solver.getExistingValueState(RegI);
 395     if (!LV.isFunctionSet() || LV.getFunctions().empty())
 396       continue;
 397     MDNode *Callees = MDB.createCallees(LV.getFunctions());
 398     C->setMetadata(LLVMContext::MD_callees, Callees);
 399     Changed = true;
 400   }
 401
 402   return Changed;
 403 }
 404
 405 PreservedAnalyses CalledValuePropagationPass::run(Module &M,
 406                                                   ModuleAnalysisManager &) {
 407   runCVP(M);
 408   return PreservedAnalyses::all();
 409 }
 410
 411 namespace {
 412 class CalledValuePropagationLegacyPass : public ModulePass {
 413 public:
 414   static char ID;
 415
 416   void getAnalysisUsage(AnalysisUsage &AU) const override {
 417     AU.setPreservesAll();
 418   }
 419
 420   CalledValuePropagationLegacyPass() : ModulePass(ID) {
 421     initializeCalledValuePropagationLegacyPassPass(
 422         *PassRegistry::getPassRegistry());
 423   }
 424
 425   bool runOnModule(Module &M) override {
 426     if (skipModule(M))
 427       return false;
 428     return runCVP(M);
 429   }
 430 };
 431 } // namespace
 432
 433 char CalledValuePropagationLegacyPass::ID = 0;
 434 INITIALIZE_PASS(CalledValuePropagationLegacyPass, "called-value-propagation",
 435                 "Called Value Propagation", false, false)
 436
 437 ModulePass *llvm::createCalledValuePropagationPass() {
 438   return new CalledValuePropagationLegacyPass();
 439 }