aboutsummaryrefslogtreecommitdiffstats
path: root/lib/CodeGen/JumpInstrTables.cpp
blob: 75fa261973981b2968fa45f41021676f49c70841 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
//===-- JumpInstrTables.cpp: Jump-Instruction Tables ----------------------===//
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
///
/// \file
/// \brief An implementation of jump-instruction tables.
///
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "jt"

#include "llvm/CodeGen/JumpInstrTables.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/JumpInstrTableInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/CallSite.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/Operator.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Verifier.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <vector>

using namespace llvm;

char JumpInstrTables::ID = 0;

INITIALIZE_PASS_BEGIN(JumpInstrTables, "jump-instr-tables",
                      "Jump-Instruction Tables", true, true)
INITIALIZE_PASS_DEPENDENCY(JumpInstrTableInfo);
INITIALIZE_PASS_END(JumpInstrTables, "jump-instr-tables",
                    "Jump-Instruction Tables", true, true)

STATISTIC(NumJumpTables, "Number of indirect call tables generated");
STATISTIC(NumFuncsInJumpTables, "Number of functions in the jump tables");

ModulePass *llvm::createJumpInstrTablesPass() {
  // The default implementation uses a single table for all functions.
  return new JumpInstrTables(JumpTable::Single);
}

ModulePass *llvm::createJumpInstrTablesPass(JumpTable::JumpTableType JTT) {
  return new JumpInstrTables(JTT);
}

namespace {
static const char jump_func_prefix[] = "__llvm_jump_instr_table_";
static const char jump_section_prefix[] = ".jump.instr.table.text.";

// Checks to see if a given CallSite is making an indirect call, including
// cases where the indirect call is made through a bitcast.
bool isIndirectCall(CallSite &CS) {
  if (CS.getCalledFunction())
    return false;

  // Check the value to see if it is merely a bitcast of a function. In
  // this case, it will translate to a direct function call in the resulting
  // assembly, so we won't treat it as an indirect call here.
  const Value *V = CS.getCalledValue();
  if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
    return !(CE->isCast() && isa<Function>(CE->getOperand(0)));
  }

  // Otherwise, since we know it's a call, it must be an indirect call
  return true;
}

// Replaces Functions and GlobalAliases with a different Value.
bool replaceGlobalValueIndirectUse(GlobalValue *GV, Value *V, Use *U) {
  User *Us = U->getUser();
  if (!Us)
    return false;
  if (Instruction *I = dyn_cast<Instruction>(Us)) {
    CallSite CS(I);

    // Don't do the replacement if this use is a direct call to this function.
    // If the use is not the called value, then replace it.
    if (CS && (isIndirectCall(CS) || CS.isCallee(U))) {
      return false;
    }

    U->set(V);
  } else if (Constant *C = dyn_cast<Constant>(Us)) {
    // Don't replace calls to bitcasts of function symbols, since they get
    // translated to direct calls.
    if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Us)) {
      if (CE->getOpcode() == Instruction::BitCast) {
        // This bitcast must have exactly one user.
        if (CE->user_begin() != CE->user_end()) {
          User *ParentUs = *CE->user_begin();
          if (CallInst *CI = dyn_cast<CallInst>(ParentUs)) {
            CallSite CS(CI);
            Use &CEU = *CE->use_begin();
            if (CS.isCallee(&CEU)) {
              return false;
            }
          }
        }
      }
    }

    // GlobalAlias doesn't support replaceUsesOfWithOnConstant. And the verifier
    // requires alias to point to a defined function. So, GlobalAlias is handled
    // as a separate case in runOnModule.
    if (!isa<GlobalAlias>(C))
      C->replaceUsesOfWithOnConstant(GV, V, U);
  } else {
    llvm_unreachable("The Use of a Function symbol is neither an instruction "
                     "nor a constant");
  }

  return true;
}

// Replaces all replaceable address-taken uses of GV with a pointer to a
// jump-instruction table entry.
void replaceValueWithFunction(GlobalValue *GV, Function *F) {
  // Go through all uses of this function and replace the uses of GV with the
  // jump-table version of the function. Get the uses as a vector before
  // replacing them, since replacing them changes the use list and invalidates
  // the iterator otherwise.
  for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E;) {
    Use &U = *I++;

    // Replacement of constants replaces all instances in the constant. So, some
    // uses might have already been handled by the time we reach them here.
    if (U.get() == GV)
      replaceGlobalValueIndirectUse(GV, F, &U);
  }

  return;
}
} // end anonymous namespace

JumpInstrTables::JumpInstrTables()
    : ModulePass(ID), Metadata(), JITI(nullptr), TableCount(0),
      JTType(JumpTable::Single) {
  initializeJumpInstrTablesPass(*PassRegistry::getPassRegistry());
}

JumpInstrTables::JumpInstrTables(JumpTable::JumpTableType JTT)
    : ModulePass(ID), Metadata(), JITI(nullptr), TableCount(0), JTType(JTT) {
  initializeJumpInstrTablesPass(*PassRegistry::getPassRegistry());
}

JumpInstrTables::~JumpInstrTables() {}

void JumpInstrTables::getAnalysisUsage(AnalysisUsage &AU) const {
  AU.addRequired<JumpInstrTableInfo>();
}

Function *JumpInstrTables::insertEntry(Module &M, Function *Target) {
  FunctionType *OrigFunTy = Target->getFunctionType();
  FunctionType *FunTy = transformType(JTType, OrigFunTy);

  JumpMap::iterator it = Metadata.find(FunTy);
  if (Metadata.end() == it) {
    struct TableMeta Meta;
    Meta.TableNum = TableCount;
    Meta.Count = 0;
    Metadata[FunTy] = Meta;
    it = Metadata.find(FunTy);
    ++NumJumpTables;
    ++TableCount;
  }

  it->second.Count++;

  std::string NewName(jump_func_prefix);
  NewName += (Twine(it->second.TableNum) + "_" + Twine(it->second.Count)).str();
  Function *JumpFun =
      Function::Create(OrigFunTy, GlobalValue::ExternalLinkage, NewName, &M);
  // The section for this table
  JumpFun->setSection((jump_section_prefix + Twine(it->second.TableNum)).str());
  JITI->insertEntry(FunTy, Target, JumpFun);

  ++NumFuncsInJumpTables;
  return JumpFun;
}

bool JumpInstrTables::hasTable(FunctionType *FunTy) {
  FunctionType *TransTy = transformType(JTType, FunTy);
  return Metadata.end() != Metadata.find(TransTy);
}

FunctionType *JumpInstrTables::transformType(JumpTable::JumpTableType JTT,
                                             FunctionType *FunTy) {
  // Returning nullptr forces all types into the same table, since all types map
  // to the same type
  Type *VoidPtrTy = Type::getInt8PtrTy(FunTy->getContext());

  // Ignore the return type.
  Type *RetTy = VoidPtrTy;
  bool IsVarArg = FunTy->isVarArg();
  std::vector<Type *> ParamTys(FunTy->getNumParams());
  FunctionType::param_iterator PI, PE;
  int i = 0;

  std::vector<Type *> EmptyParams;
  Type *Int32Ty = Type::getInt32Ty(FunTy->getContext());
  FunctionType *VoidFnTy = FunctionType::get(
      Type::getVoidTy(FunTy->getContext()), EmptyParams, false);
  switch (JTT) {
  case JumpTable::Single:

    return FunctionType::get(RetTy, EmptyParams, false);
  case JumpTable::Arity:
    // Transform all types to void* so that all functions with the same arity
    // end up in the same table.
    for (PI = FunTy->param_begin(), PE = FunTy->param_end(); PI != PE;
         PI++, i++) {
      ParamTys[i] = VoidPtrTy;
    }

    return FunctionType::get(RetTy, ParamTys, IsVarArg);
  case JumpTable::Simplified:
    // Project all parameters types to one of 3 types: composite, integer, and
    // function, matching the three subclasses of Type.
    for (PI = FunTy->param_begin(), PE = FunTy->param_end(); PI != PE;
         ++PI, ++i) {
      assert((isa<IntegerType>(*PI) || isa<FunctionType>(*PI) ||
              isa<CompositeType>(*PI)) &&
             "This type is not an Integer or a Composite or a Function");
      if (isa<CompositeType>(*PI)) {
        ParamTys[i] = VoidPtrTy;
      } else if (isa<FunctionType>(*PI)) {
        ParamTys[i] = VoidFnTy;
      } else if (isa<IntegerType>(*PI)) {
        ParamTys[i] = Int32Ty;
      }
    }

    return FunctionType::get(RetTy, ParamTys, IsVarArg);
  case JumpTable::Full:
    // Don't transform this type at all.
    return FunTy;
  }

  return nullptr;
}

bool JumpInstrTables::runOnModule(Module &M) {
  JITI = &getAnalysis<JumpInstrTableInfo>();

  // Get the set of jumptable-annotated functions that have their address taken.
  DenseMap<Function *, Function *> Functions;
  for (Function &F : M) {
    if (F.hasFnAttribute(Attribute::JumpTable) && F.hasAddressTaken()) {
      assert(F.hasUnnamedAddr() &&
             "Attribute 'jumptable' requires 'unnamed_addr'");
      Functions[&F] = nullptr;
    }
  }

  // Create the jump-table functions.
  for (auto &KV : Functions) {
    Function *F = KV.first;
    KV.second = insertEntry(M, F);
  }

  // GlobalAlias is a special case, because the target of an alias statement
  // must be a defined function. So, instead of replacing a given function in
  // the alias, we replace all uses of aliases that target jumptable functions.
  // Note that there's no need to create these functions, since only aliases
  // that target known jumptable functions are replaced, and there's no way to
  // put the jumptable annotation on a global alias.
  DenseMap<GlobalAlias *, Function *> Aliases;
  for (GlobalAlias &GA : M.aliases()) {
    Constant *Aliasee = GA.getAliasee();
    if (Function *F = dyn_cast<Function>(Aliasee)) {
      auto it = Functions.find(F);
      if (it != Functions.end()) {
        Aliases[&GA] = it->second;
      }
    }
  }

  // Replace each address taken function with its jump-instruction table entry.
  for (auto &KV : Functions)
    replaceValueWithFunction(KV.first, KV.second);

  for (auto &KV : Aliases)
    replaceValueWithFunction(KV.first, KV.second);

  return !Functions.empty();
}