lib/CodeGen/JumpInstrTables.cpp

   1 //===-- JumpInstrTables.cpp: Jump-Instruction Tables ----------------------===//
   2 //
   3 // This file is distributed under the University of Illinois Open Source
   4 // License. See LICENSE.TXT for details.
   5 //
   6 //===----------------------------------------------------------------------===//
   7 ///
   8 /// \file
   9 /// \brief An implementation of jump-instruction tables.
  10 ///
  11 //===----------------------------------------------------------------------===//
  12
  13 #define DEBUG_TYPE "jt"
  14
  15 #include "llvm/CodeGen/JumpInstrTables.h"
  16
  17 #include "llvm/ADT/Statistic.h"
  18 #include "llvm/Analysis/JumpInstrTableInfo.h"
  19 #include "llvm/CodeGen/Passes.h"
  20 #include "llvm/IR/Attributes.h"
  21 #include "llvm/IR/CallSite.h"
  22 #include "llvm/IR/Constants.h"
  23 #include "llvm/IR/DerivedTypes.h"
  24 #include "llvm/IR/Function.h"
  25 #include "llvm/IR/LLVMContext.h"
  26 #include "llvm/IR/Module.h"
  27 #include "llvm/IR/Operator.h"
  28 #include "llvm/IR/Type.h"
  29 #include "llvm/IR/Verifier.h"
  30 #include "llvm/Support/CommandLine.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/raw_ostream.h"
  33
  34 #include <vector>
  35
  36 using namespace llvm;
  37
  38 char JumpInstrTables::ID = 0;
  39
  40 INITIALIZE_PASS_BEGIN(JumpInstrTables, "jump-instr-tables",
  41                       "Jump-Instruction Tables", true, true)
  42 INITIALIZE_PASS_DEPENDENCY(JumpInstrTableInfo);
  43 INITIALIZE_PASS_END(JumpInstrTables, "jump-instr-tables",
  44                     "Jump-Instruction Tables", true, true)
  45
  46 STATISTIC(NumJumpTables, "Number of indirect call tables generated");
  47 STATISTIC(NumFuncsInJumpTables, "Number of functions in the jump tables");
  48
  49 ModulePass *llvm::createJumpInstrTablesPass() {
  50   // The default implementation uses a single table for all functions.
  51   return new JumpInstrTables(JumpTable::Single);
  52 }
  53
  54 ModulePass *llvm::createJumpInstrTablesPass(JumpTable::JumpTableType JTT) {
  55   return new JumpInstrTables(JTT);
  56 }
  57
  58 namespace {
  59 static const char jump_func_prefix[] = "__llvm_jump_instr_table_";
  60 static const char jump_section_prefix[] = ".jump.instr.table.text.";
  61
  62 // Checks to see if a given CallSite is making an indirect call, including
  63 // cases where the indirect call is made through a bitcast.
  64 bool isIndirectCall(CallSite &CS) {
  65   if (CS.getCalledFunction())
  66     return false;
  67
  68   // Check the value to see if it is merely a bitcast of a function. In
  69   // this case, it will translate to a direct function call in the resulting
  70   // assembly, so we won't treat it as an indirect call here.
  71   const Value *V = CS.getCalledValue();
  72   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
  73     return !(CE->isCast() && isa<Function>(CE->getOperand(0)));
  74   }
  75
  76   // Otherwise, since we know it's a call, it must be an indirect call
  77   return true;
  78 }
  79
  80 // Replaces Functions and GlobalAliases with a different Value.
  81 bool replaceGlobalValueIndirectUse(GlobalValue *GV, Value *V, Use *U) {
  82   User *Us = U->getUser();
  83   if (!Us)
  84     return false;
  85   if (Instruction *I = dyn_cast<Instruction>(Us)) {
  86     CallSite CS(I);
  87
  88     // Don't do the replacement if this use is a direct call to this function.
  89     // If the use is not the called value, then replace it.
  90     if (CS && (isIndirectCall(CS) || CS.isCallee(U))) {
  91       return false;
  92     }
  93
  94     U->set(V);
  95   } else if (Constant *C = dyn_cast<Constant>(Us)) {
  96     // Don't replace calls to bitcasts of function symbols, since they get
  97     // translated to direct calls.
  98     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Us)) {
  99       if (CE->getOpcode() == Instruction::BitCast) {
 100         // This bitcast must have exactly one user.
 101         if (CE->user_begin() != CE->user_end()) {
 102           User *ParentUs = *CE->user_begin();
 103           if (CallInst *CI = dyn_cast<CallInst>(ParentUs)) {
 104             CallSite CS(CI);
 105             Use &CEU = *CE->use_begin();
 106             if (CS.isCallee(&CEU)) {
 107               return false;
 108             }
 109           }
 110         }
 111       }
 112     }
 113
 114     // GlobalAlias doesn't support replaceUsesOfWithOnConstant. And the verifier
 115     // requires alias to point to a defined function. So, GlobalAlias is handled
 116     // as a separate case in runOnModule.
 117     if (!isa<GlobalAlias>(C))
 118       C->replaceUsesOfWithOnConstant(GV, V, U);
 119   } else {
 120     assert(false && "The Use of a Function symbol is neither an instruction nor"
 121                     " a constant");
 122   }
 123
 124   return true;
 125 }
 126
 127 // Replaces all replaceable address-taken uses of GV with a pointer to a
 128 // jump-instruction table entry.
 129 void replaceValueWithFunction(GlobalValue *GV, Function *F) {
 130   // Go through all uses of this function and replace the uses of GV with the
 131   // jump-table version of the function. Get the uses as a vector before
 132   // replacing them, since replacing them changes the use list and invalidates
 133   // the iterator otherwise.
 134   for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E;) {
 135     Use &U = *I++;
 136
 137     // Replacement of constants replaces all instances in the constant. So, some
 138     // uses might have already been handled by the time we reach them here.
 139     if (U.get() == GV)
 140       replaceGlobalValueIndirectUse(GV, F, &U);
 141   }
 142
 143   return;
 144 }
 145 } // end anonymous namespace
 146
 147 JumpInstrTables::JumpInstrTables()
 148     : ModulePass(ID), Metadata(), JITI(nullptr), TableCount(0),
 149       JTType(JumpTable::Single) {
 150   initializeJumpInstrTablesPass(*PassRegistry::getPassRegistry());
 151 }
 152
 153 JumpInstrTables::JumpInstrTables(JumpTable::JumpTableType JTT)
 154     : ModulePass(ID), Metadata(), JITI(nullptr), TableCount(0), JTType(JTT) {
 155   initializeJumpInstrTablesPass(*PassRegistry::getPassRegistry());
 156 }
 157
 158 JumpInstrTables::~JumpInstrTables() {}
 159
 160 void JumpInstrTables::getAnalysisUsage(AnalysisUsage &AU) const {
 161   AU.addRequired<JumpInstrTableInfo>();
 162 }
 163
 164 Function *JumpInstrTables::insertEntry(Module &M, Function *Target) {
 165   FunctionType *OrigFunTy = Target->getFunctionType();
 166   FunctionType *FunTy = transformType(OrigFunTy);
 167
 168   JumpMap::iterator it = Metadata.find(FunTy);
 169   if (Metadata.end() == it) {
 170     struct TableMeta Meta;
 171     Meta.TableNum = TableCount;
 172     Meta.Count = 0;
 173     Metadata[FunTy] = Meta;
 174     it = Metadata.find(FunTy);
 175     ++NumJumpTables;
 176     ++TableCount;
 177   }
 178
 179   it->second.Count++;
 180
 181   std::string NewName(jump_func_prefix);
 182   NewName += (Twine(it->second.TableNum) + "_" + Twine(it->second.Count)).str();
 183   Function *JumpFun =
 184       Function::Create(OrigFunTy, GlobalValue::ExternalLinkage, NewName, &M);
 185   // The section for this table
 186   JumpFun->setSection((jump_section_prefix + Twine(it->second.TableNum)).str());
 187   JITI->insertEntry(FunTy, Target, JumpFun);
 188
 189   ++NumFuncsInJumpTables;
 190   return JumpFun;
 191 }
 192
 193 bool JumpInstrTables::hasTable(FunctionType *FunTy) {
 194   FunctionType *TransTy = transformType(FunTy);
 195   return Metadata.end() != Metadata.find(TransTy);
 196 }
 197
 198 FunctionType *JumpInstrTables::transformType(FunctionType *FunTy) {
 199   // Returning nullptr forces all types into the same table, since all types map
 200   // to the same type
 201   Type *VoidPtrTy = Type::getInt8PtrTy(FunTy->getContext());
 202
 203   // Ignore the return type.
 204   Type *RetTy = VoidPtrTy;
 205   bool IsVarArg = FunTy->isVarArg();
 206   std::vector<Type *> ParamTys(FunTy->getNumParams());
 207   FunctionType::param_iterator PI, PE;
 208   int i = 0;
 209
 210   std::vector<Type *> EmptyParams;
 211   Type *Int32Ty = Type::getInt32Ty(FunTy->getContext());
 212   FunctionType *VoidFnTy = FunctionType::get(
 213       Type::getVoidTy(FunTy->getContext()), EmptyParams, false);
 214   switch (JTType) {
 215   case JumpTable::Single:
 216
 217     return FunctionType::get(RetTy, EmptyParams, false);
 218   case JumpTable::Arity:
 219     // Transform all types to void* so that all functions with the same arity
 220     // end up in the same table.
 221     for (PI = FunTy->param_begin(), PE = FunTy->param_end(); PI != PE;
 222          PI++, i++) {
 223       ParamTys[i] = VoidPtrTy;
 224     }
 225
 226     return FunctionType::get(RetTy, ParamTys, IsVarArg);
 227   case JumpTable::Simplified:
 228     // Project all parameters types to one of 3 types: composite, integer, and
 229     // function, matching the three subclasses of Type.
 230     for (PI = FunTy->param_begin(), PE = FunTy->param_end(); PI != PE;
 231          ++PI, ++i) {
 232       assert((isa<IntegerType>(*PI) || isa<FunctionType>(*PI) ||
 233               isa<CompositeType>(*PI)) &&
 234              "This type is not an Integer or a Composite or a Function");
 235       if (isa<CompositeType>(*PI)) {
 236         ParamTys[i] = VoidPtrTy;
 237       } else if (isa<FunctionType>(*PI)) {
 238         ParamTys[i] = VoidFnTy;
 239       } else if (isa<IntegerType>(*PI)) {
 240         ParamTys[i] = Int32Ty;
 241       }
 242     }
 243
 244     return FunctionType::get(RetTy, ParamTys, IsVarArg);
 245   case JumpTable::Full:
 246     // Don't transform this type at all.
 247     return FunTy;
 248   }
 249
 250   return nullptr;
 251 }
 252
 253 bool JumpInstrTables::runOnModule(Module &M) {
 254   // Make sure the module is well-formed, especially with respect to jumptable.
 255   if (verifyModule(M))
 256     return false;
 257
 258   JITI = &getAnalysis<JumpInstrTableInfo>();
 259
 260   // Get the set of jumptable-annotated functions.
 261   DenseMap<Function *, Function *> Functions;
 262   for (Function &F : M) {
 263     if (F.hasFnAttribute(Attribute::JumpTable)) {
 264       assert(F.hasUnnamedAddr() &&
 265              "Attribute 'jumptable' requires 'unnamed_addr'");
 266       Functions[&F] = nullptr;
 267     }
 268   }
 269
 270   // Create the jump-table functions.
 271   for (auto &KV : Functions) {
 272     Function *F = KV.first;
 273     KV.second = insertEntry(M, F);
 274   }
 275
 276   // GlobalAlias is a special case, because the target of an alias statement
 277   // must be a defined function. So, instead of replacing a given function in
 278   // the alias, we replace all uses of aliases that target jumptable functions.
 279   // Note that there's no need to create these functions, since only aliases
 280   // that target known jumptable functions are replaced, and there's no way to
 281   // put the jumptable annotation on a global alias.
 282   DenseMap<GlobalAlias *, Function *> Aliases;
 283   for (GlobalAlias &GA : M.aliases()) {
 284     Constant *Aliasee = GA.getAliasee();
 285     if (Function *F = dyn_cast<Function>(Aliasee)) {
 286       auto it = Functions.find(F);
 287       if (it != Functions.end()) {
 288         Aliases[&GA] = it->second;
 289       }
 290     }
 291   }
 292
 293   // Replace each address taken function with its jump-instruction table entry.
 294   for (auto &KV : Functions)
 295     replaceValueWithFunction(KV.first, KV.second);
 296
 297   for (auto &KV : Aliases)
 298     replaceValueWithFunction(KV.first, KV.second);
 299
 300   return !Functions.empty();
 301 }