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

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