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