Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- MipsELFObjectWriter.cpp - Mips ELF Writer -------------------------===//
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
#include "MCTargetDesc/MipsFixupKinds.h"
10
#include "MCTargetDesc/MipsMCTargetDesc.h"
11
#include "llvm/ADT/STLExtras.h"
12
#include "llvm/BinaryFormat/ELF.h"
13
#include "llvm/MC/MCContext.h"
14
#include "llvm/MC/MCELFObjectWriter.h"
15
#include "llvm/MC/MCFixup.h"
16
#include "llvm/MC/MCObjectWriter.h"
17
#include "llvm/MC/MCSymbolELF.h"
18
#include "llvm/Support/Casting.h"
19
#include "llvm/Support/Compiler.h"
20
#include "llvm/Support/Debug.h"
21
#include "llvm/Support/ErrorHandling.h"
22
#include "llvm/Support/MathExtras.h"
23
#include "llvm/Support/raw_ostream.h"
24
#include <algorithm>
25
#include <cassert>
26
#include <cstdint>
27
#include <iterator>
28
#include <list>
29
#include <utility>
30
31
#define DEBUG_TYPE "mips-elf-object-writer"
32
33
using namespace llvm;
34
35
namespace {
36
37
/// Holds additional information needed by the relocation ordering algorithm.
38
struct MipsRelocationEntry {
39
  const ELFRelocationEntry R; ///< The relocation.
40
  bool Matched = false;       ///< Is this relocation part of a match.
41
42
959
  MipsRelocationEntry(const ELFRelocationEntry &R) : R(R) {}
43
44
0
  void print(raw_ostream &Out) const {
45
0
    R.print(Out);
46
0
    Out << ", Matched=" << Matched;
47
0
  }
48
};
49
50
#ifndef NDEBUG
51
raw_ostream &operator<<(raw_ostream &OS, const MipsRelocationEntry &RHS) {
52
  RHS.print(OS);
53
  return OS;
54
}
55
#endif
56
57
class MipsELFObjectWriter : public MCELFObjectTargetWriter {
58
public:
59
  MipsELFObjectWriter(uint8_t OSABI, bool HasRelocationAddend, bool Is64);
60
61
3.18k
  ~MipsELFObjectWriter() override = default;
62
63
  unsigned getRelocType(MCContext &Ctx, const MCValue &Target,
64
                        const MCFixup &Fixup, bool IsPCRel) const override;
65
  bool needsRelocateWithSymbol(const MCSymbol &Sym,
66
                               unsigned Type) const override;
67
  void sortRelocs(const MCAssembler &Asm,
68
                  std::vector<ELFRelocationEntry> &Relocs) override;
69
};
70
71
/// The possible results of the Predicate function used by find_best.
72
enum FindBestPredicateResult {
73
  FindBest_NoMatch = 0,  ///< The current element is not a match.
74
  FindBest_Match,        ///< The current element is a match but better ones are
75
                         ///  possible.
76
  FindBest_PerfectMatch, ///< The current element is an unbeatable match.
77
};
78
79
} // end anonymous namespace
80
81
/// Copy elements in the range [First, Last) to d1 when the predicate is true or
82
/// d2 when the predicate is false. This is essentially both std::copy_if and
83
/// std::remove_copy_if combined into a single pass.
84
template <class InputIt, class OutputIt1, class OutputIt2, class UnaryPredicate>
85
static std::pair<OutputIt1, OutputIt2> copy_if_else(InputIt First, InputIt Last,
86
                                                    OutputIt1 d1, OutputIt2 d2,
87
179
                                                    UnaryPredicate Predicate) {
88
1.13k
  for (InputIt I = First; I != Last; 
++I959
) {
89
959
    if (Predicate(*I)) {
90
149
      *d1 = *I;
91
149
      d1++;
92
810
    } else {
93
810
      *d2 = *I;
94
810
      d2++;
95
810
    }
96
959
  }
97
179
98
179
  return std::make_pair(d1, d2);
99
179
}
100
101
/// Find the best match in the range [First, Last).
102
///
103
/// An element matches when Predicate(X) returns FindBest_Match or
104
/// FindBest_PerfectMatch. A value of FindBest_PerfectMatch also terminates
105
/// the search. BetterThan(A, B) is a comparator that returns true when A is a
106
/// better match than B. The return value is the position of the best match.
107
///
108
/// This is similar to std::find_if but finds the best of multiple possible
109
/// matches.
110
template <class InputIt, class UnaryPredicate, class Comparator>
111
static InputIt find_best(InputIt First, InputIt Last, UnaryPredicate Predicate,
112
149
                         Comparator BetterThan) {
113
149
  InputIt Best = Last;
114
149
115
596
  for (InputIt I = First; I != Last; 
++I447
) {
116
575
    unsigned Matched = Predicate(*I);
117
575
    if (Matched != FindBest_NoMatch) {
118
167
      LLVM_DEBUG(dbgs() << std::distance(First, I) << " is a match (";
119
167
                 I->print(dbgs()); dbgs() << ")\n");
120
167
      if (Best == Last || 
BetterThan(*I, *Best)23
) {
121
164
        LLVM_DEBUG(dbgs() << ".. and it beats the last one\n");
122
164
        Best = I;
123
164
      }
124
167
    }
125
575
    if (Matched == FindBest_PerfectMatch) {
126
128
      LLVM_DEBUG(dbgs() << ".. and it is unbeatable\n");
127
128
      break;
128
128
    }
129
575
  }
130
149
131
149
  return Best;
132
149
}
133
134
/// Determine the low relocation that matches the given relocation.
135
/// If the relocation does not need a low relocation then the return value
136
/// is ELF::R_MIPS_NONE.
137
///
138
/// The relocations that need a matching low part are
139
/// R_(MIPS|MICROMIPS|MIPS16)_HI16 for all symbols and
140
/// R_(MIPS|MICROMIPS|MIPS16)_GOT16 for local symbols only.
141
1.10k
static unsigned getMatchingLoType(const ELFRelocationEntry &Reloc) {
142
1.10k
  unsigned Type = Reloc.Type;
143
1.10k
  if (Type == ELF::R_MIPS_HI16)
144
122
    return ELF::R_MIPS_LO16;
145
986
  if (Type == ELF::R_MICROMIPS_HI16)
146
42
    return ELF::R_MICROMIPS_LO16;
147
944
  if (Type == ELF::R_MIPS16_HI16)
148
0
    return ELF::R_MIPS16_LO16;
149
944
150
944
  if (Reloc.OriginalSymbol &&
151
944
      
Reloc.OriginalSymbol->getBinding() != ELF::STB_LOCAL912
)
152
454
    return ELF::R_MIPS_NONE;
153
490
154
490
  if (Type == ELF::R_MIPS_GOT16)
155
110
    return ELF::R_MIPS_LO16;
156
380
  if (Type == ELF::R_MICROMIPS_GOT16)
157
24
    return ELF::R_MICROMIPS_LO16;
158
356
  if (Type == ELF::R_MIPS16_GOT16)
159
0
    return ELF::R_MIPS16_LO16;
160
356
161
356
  return ELF::R_MIPS_NONE;
162
356
}
163
164
/// Determine whether a relocation (X) matches the one given in R.
165
///
166
/// A relocation matches if:
167
/// - It's type matches that of a corresponding low part. This is provided in
168
///   MatchingType for efficiency.
169
/// - It's based on the same symbol.
170
/// - It's offset of greater or equal to that of the one given in R.
171
///   It should be noted that this rule assumes the programmer does not use
172
///   offsets that exceed the alignment of the symbol. The carry-bit will be
173
///   incorrect if this is not true.
174
///
175
/// A matching relocation is unbeatable if:
176
/// - It is not already involved in a match.
177
/// - It's offset is exactly that of the one given in R.
178
static FindBestPredicateResult isMatchingReloc(const MipsRelocationEntry &X,
179
                                               const ELFRelocationEntry &R,
180
575
                                               unsigned MatchingType) {
181
575
  if (X.R.Type == MatchingType && 
X.R.OriginalSymbol == R.OriginalSymbol280
) {
182
174
    if (!X.Matched &&
183
174
        
X.R.OriginalAddend == R.OriginalAddend149
)
184
128
      return FindBest_PerfectMatch;
185
46
    else if (X.R.OriginalAddend >= R.OriginalAddend)
186
39
      return FindBest_Match;
187
408
  }
188
408
  return FindBest_NoMatch;
189
408
}
190
191
/// Determine whether Candidate or PreviousBest is the better match.
192
/// The return value is true if Candidate is the better match.
193
///
194
/// A matching relocation is a better match if:
195
/// - It has a smaller addend.
196
/// - It is not already involved in a match.
197
static bool compareMatchingRelocs(const MipsRelocationEntry &Candidate,
198
23
                                  const MipsRelocationEntry &PreviousBest) {
199
23
  if (Candidate.R.OriginalAddend != PreviousBest.R.OriginalAddend)
200
10
    return Candidate.R.OriginalAddend < PreviousBest.R.OriginalAddend;
201
13
  return PreviousBest.Matched && !Candidate.Matched;
202
13
}
203
204
#ifndef NDEBUG
205
/// Print all the relocations.
206
template <class Container>
207
static void dumpRelocs(const char *Prefix, const Container &Relocs) {
208
  for (const auto &R : Relocs)
209
    dbgs() << Prefix << R << "\n";
210
}
211
#endif
212
213
MipsELFObjectWriter::MipsELFObjectWriter(uint8_t OSABI,
214
                                         bool HasRelocationAddend, bool Is64)
215
3.19k
    : MCELFObjectTargetWriter(Is64, OSABI, ELF::EM_MIPS, HasRelocationAddend) {}
216
217
unsigned MipsELFObjectWriter::getRelocType(MCContext &Ctx,
218
                                           const MCValue &Target,
219
                                           const MCFixup &Fixup,
220
11.5k
                                           bool IsPCRel) const {
221
11.5k
  // Determine the type of the relocation.
222
11.5k
  unsigned Kind = (unsigned)Fixup.getKind();
223
11.5k
224
11.5k
  switch (Kind) {
225
11.5k
  case FK_NONE:
226
12
    return ELF::R_MIPS_NONE;
227
11.5k
  case FK_Data_1:
228
2
    Ctx.reportError(Fixup.getLoc(),
229
2
                    "MIPS does not support one byte relocations");
230
2
    return ELF::R_MIPS_NONE;
231
11.5k
  case Mips::fixup_Mips_16:
232
7
  case FK_Data_2:
233
7
    return IsPCRel ? 
ELF::R_MIPS_PC162
:
ELF::R_MIPS_165
;
234
452
  case Mips::fixup_Mips_32:
235
452
  case FK_Data_4:
236
452
    return IsPCRel ? 
ELF::R_MIPS_PC3217
:
ELF::R_MIPS_32435
;
237
11.1k
  }
238
11.1k
239
11.1k
  if (IsPCRel) {
240
119
    switch (Kind) {
241
119
    case FK_Data_8:
242
1
      Ctx.reportError(Fixup.getLoc(),
243
1
                      "MIPS does not support 64-bit PC-relative relocations");
244
1
      return ELF::R_MIPS_NONE;
245
119
    case Mips::fixup_Mips_Branch_PCRel:
246
22
    case Mips::fixup_Mips_PC16:
247
22
      return ELF::R_MIPS_PC16;
248
22
    case Mips::fixup_MICROMIPS_PC7_S1:
249
4
      return ELF::R_MICROMIPS_PC7_S1;
250
22
    case Mips::fixup_MICROMIPS_PC10_S1:
251
4
      return ELF::R_MICROMIPS_PC10_S1;
252
22
    case Mips::fixup_MICROMIPS_PC16_S1:
253
11
      return ELF::R_MICROMIPS_PC16_S1;
254
22
    case Mips::fixup_MICROMIPS_PC26_S1:
255
9
      return ELF::R_MICROMIPS_PC26_S1;
256
22
    case Mips::fixup_MICROMIPS_PC19_S2:
257
5
      return ELF::R_MICROMIPS_PC19_S2;
258
22
    case Mips::fixup_MICROMIPS_PC18_S3:
259
0
      return ELF::R_MICROMIPS_PC18_S3;
260
22
    case Mips::fixup_MICROMIPS_PC21_S1:
261
4
      return ELF::R_MICROMIPS_PC21_S1;
262
22
    case Mips::fixup_MIPS_PC19_S2:
263
14
      return ELF::R_MIPS_PC19_S2;
264
22
    case Mips::fixup_MIPS_PC18_S3:
265
5
      return ELF::R_MIPS_PC18_S3;
266
22
    case Mips::fixup_MIPS_PC21_S2:
267
11
      return ELF::R_MIPS_PC21_S2;
268
22
    case Mips::fixup_MIPS_PC26_S2:
269
11
      return ELF::R_MIPS_PC26_S2;
270
22
    case Mips::fixup_MIPS_PCHI16:
271
9
      return ELF::R_MIPS_PCHI16;
272
22
    case Mips::fixup_MIPS_PCLO16:
273
9
      return ELF::R_MIPS_PCLO16;
274
0
    }
275
0
276
0
    llvm_unreachable("invalid PC-relative fixup kind!");
277
0
  }
278
10.9k
279
10.9k
  switch (Kind) {
280
10.9k
  case Mips::fixup_Mips_64:
281
62
  case FK_Data_8:
282
62
    return ELF::R_MIPS_64;
283
62
  case FK_DTPRel_4:
284
3
    return ELF::R_MIPS_TLS_DTPREL32;
285
62
  case FK_DTPRel_8:
286
3
    return ELF::R_MIPS_TLS_DTPREL64;
287
62
  case FK_TPRel_4:
288
3
    return ELF::R_MIPS_TLS_TPREL32;
289
62
  case FK_TPRel_8:
290
3
    return ELF::R_MIPS_TLS_TPREL64;
291
62
  case FK_GPRel_4:
292
27
    if (is64Bit()) {
293
13
      unsigned Type = (unsigned)ELF::R_MIPS_NONE;
294
13
      Type = setRType((unsigned)ELF::R_MIPS_GPREL32, Type);
295
13
      Type = setRType2((unsigned)ELF::R_MIPS_64, Type);
296
13
      Type = setRType3((unsigned)ELF::R_MIPS_NONE, Type);
297
13
      return Type;
298
13
    }
299
14
    return ELF::R_MIPS_GPREL32;
300
14
  case Mips::fixup_Mips_GPREL16:
301
8
    return ELF::R_MIPS_GPREL16;
302
67
  case Mips::fixup_Mips_26:
303
67
    return ELF::R_MIPS_26;
304
10.0k
  case Mips::fixup_Mips_CALL16:
305
10.0k
    return ELF::R_MIPS_CALL16;
306
83
  case Mips::fixup_Mips_GOT:
307
83
    return ELF::R_MIPS_GOT16;
308
67
  case Mips::fixup_Mips_HI16:
309
67
    return ELF::R_MIPS_HI16;
310
125
  case Mips::fixup_Mips_LO16:
311
125
    return ELF::R_MIPS_LO16;
312
17
  case Mips::fixup_Mips_TLSGD:
313
17
    return ELF::R_MIPS_TLS_GD;
314
16
  case Mips::fixup_Mips_GOTTPREL:
315
16
    return ELF::R_MIPS_TLS_GOTTPREL;
316
14
  case Mips::fixup_Mips_TPREL_HI:
317
8
    return ELF::R_MIPS_TLS_TPREL_HI16;
318
14
  case Mips::fixup_Mips_TPREL_LO:
319
8
    return ELF::R_MIPS_TLS_TPREL_LO16;
320
14
  case Mips::fixup_Mips_TLSLDM:
321
10
    return ELF::R_MIPS_TLS_LDM;
322
14
  case Mips::fixup_Mips_DTPREL_HI:
323
9
    return ELF::R_MIPS_TLS_DTPREL_HI16;
324
14
  case Mips::fixup_Mips_DTPREL_LO:
325
10
    return ELF::R_MIPS_TLS_DTPREL_LO16;
326
34
  case Mips::fixup_Mips_GOT_PAGE:
327
34
    return ELF::R_MIPS_GOT_PAGE;
328
24
  case Mips::fixup_Mips_GOT_OFST:
329
24
    return ELF::R_MIPS_GOT_OFST;
330
31
  case Mips::fixup_Mips_GOT_DISP:
331
31
    return ELF::R_MIPS_GOT_DISP;
332
28
  case Mips::fixup_Mips_GPOFF_HI: {
333
28
    unsigned Type = (unsigned)ELF::R_MIPS_NONE;
334
28
    Type = setRType((unsigned)ELF::R_MIPS_GPREL16, Type);
335
28
    Type = setRType2((unsigned)ELF::R_MIPS_SUB, Type);
336
28
    Type = setRType3((unsigned)ELF::R_MIPS_HI16, Type);
337
28
    return Type;
338
14
  }
339
14
  case Mips::fixup_MICROMIPS_GPOFF_HI: {
340
4
    unsigned Type = (unsigned)ELF::R_MIPS_NONE;
341
4
    Type = setRType((unsigned)ELF::R_MICROMIPS_GPREL16, Type);
342
4
    Type = setRType2((unsigned)ELF::R_MICROMIPS_SUB, Type);
343
4
    Type = setRType3((unsigned)ELF::R_MICROMIPS_HI16, Type);
344
4
    return Type;
345
14
  }
346
26
  case Mips::fixup_Mips_GPOFF_LO: {
347
26
    unsigned Type = (unsigned)ELF::R_MIPS_NONE;
348
26
    Type = setRType((unsigned)ELF::R_MIPS_GPREL16, Type);
349
26
    Type = setRType2((unsigned)ELF::R_MIPS_SUB, Type);
350
26
    Type = setRType3((unsigned)ELF::R_MIPS_LO16, Type);
351
26
    return Type;
352
14
  }
353
14
  case Mips::fixup_MICROMIPS_GPOFF_LO: {
354
4
    unsigned Type = (unsigned)ELF::R_MIPS_NONE;
355
4
    Type = setRType((unsigned)ELF::R_MICROMIPS_GPREL16, Type);
356
4
    Type = setRType2((unsigned)ELF::R_MICROMIPS_SUB, Type);
357
4
    Type = setRType3((unsigned)ELF::R_MICROMIPS_LO16, Type);
358
4
    return Type;
359
14
  }
360
14
  case Mips::fixup_Mips_HIGHER:
361
7
    return ELF::R_MIPS_HIGHER;
362
14
  case Mips::fixup_Mips_HIGHEST:
363
7
    return ELF::R_MIPS_HIGHEST;
364
14
  case Mips::fixup_Mips_SUB:
365
0
    return ELF::R_MIPS_SUB;
366
14
  case Mips::fixup_Mips_GOT_HI16:
367
11
    return ELF::R_MIPS_GOT_HI16;
368
14
  case Mips::fixup_Mips_GOT_LO16:
369
11
    return ELF::R_MIPS_GOT_LO16;
370
14
  case Mips::fixup_Mips_CALL_HI16:
371
9
    return ELF::R_MIPS_CALL_HI16;
372
14
  case Mips::fixup_Mips_CALL_LO16:
373
9
    return ELF::R_MIPS_CALL_LO16;
374
25
  case Mips::fixup_MICROMIPS_26_S1:
375
25
    return ELF::R_MICROMIPS_26_S1;
376
21
  case Mips::fixup_MICROMIPS_HI16:
377
21
    return ELF::R_MICROMIPS_HI16;
378
33
  case Mips::fixup_MICROMIPS_LO16:
379
33
    return ELF::R_MICROMIPS_LO16;
380
22
  case Mips::fixup_MICROMIPS_GOT16:
381
22
    return ELF::R_MICROMIPS_GOT16;
382
15
  case Mips::fixup_MICROMIPS_CALL16:
383
15
    return ELF::R_MICROMIPS_CALL16;
384
14
  case Mips::fixup_MICROMIPS_GOT_DISP:
385
4
    return ELF::R_MICROMIPS_GOT_DISP;
386
14
  case Mips::fixup_MICROMIPS_GOT_PAGE:
387
6
    return ELF::R_MICROMIPS_GOT_PAGE;
388
14
  case Mips::fixup_MICROMIPS_GOT_OFST:
389
6
    return ELF::R_MICROMIPS_GOT_OFST;
390
14
  case Mips::fixup_MICROMIPS_TLS_GD:
391
4
    return ELF::R_MICROMIPS_TLS_GD;
392
14
  case Mips::fixup_MICROMIPS_TLS_LDM:
393
4
    return ELF::R_MICROMIPS_TLS_LDM;
394
14
  case Mips::fixup_MICROMIPS_TLS_DTPREL_HI16:
395
4
    return ELF::R_MICROMIPS_TLS_DTPREL_HI16;
396
14
  case Mips::fixup_MICROMIPS_TLS_DTPREL_LO16:
397
4
    return ELF::R_MICROMIPS_TLS_DTPREL_LO16;
398
14
  case Mips::fixup_MICROMIPS_GOTTPREL:
399
5
    return ELF::R_MICROMIPS_TLS_GOTTPREL;
400
14
  case Mips::fixup_MICROMIPS_TLS_TPREL_HI16:
401
4
    return ELF::R_MICROMIPS_TLS_TPREL_HI16;
402
14
  case Mips::fixup_MICROMIPS_TLS_TPREL_LO16:
403
4
    return ELF::R_MICROMIPS_TLS_TPREL_LO16;
404
14
  case Mips::fixup_MICROMIPS_SUB:
405
0
    return ELF::R_MICROMIPS_SUB;
406
14
  case Mips::fixup_MICROMIPS_HIGHER:
407
2
    return ELF::R_MICROMIPS_HIGHER;
408
14
  case Mips::fixup_MICROMIPS_HIGHEST:
409
2
    return ELF::R_MICROMIPS_HIGHEST;
410
31
  case Mips::fixup_Mips_JALR:
411
31
    return ELF::R_MIPS_JALR;
412
14
  case Mips::fixup_MICROMIPS_JALR:
413
12
    return ELF::R_MICROMIPS_JALR;
414
0
  }
415
0
416
0
  llvm_unreachable("invalid fixup kind!");
417
0
}
418
419
/// Sort relocation table entries by offset except where another order is
420
/// required by the MIPS ABI.
421
///
422
/// MIPS has a few relocations that have an AHL component in the expression used
423
/// to evaluate them. This AHL component is an addend with the same number of
424
/// bits as a symbol value but not all of our ABI's are able to supply a
425
/// sufficiently sized addend in a single relocation.
426
///
427
/// The O32 ABI for example, uses REL relocations which store the addend in the
428
/// section data. All the relocations with AHL components affect 16-bit fields
429
/// so the addend for a single relocation is limited to 16-bit. This ABI
430
/// resolves the limitation by linking relocations (e.g. R_MIPS_HI16 and
431
/// R_MIPS_LO16) and distributing the addend between the linked relocations. The
432
/// ABI mandates that such relocations must be next to each other in a
433
/// particular order (e.g. R_MIPS_HI16 must be immediately followed by a
434
/// matching R_MIPS_LO16) but the rule is less strict in practice.
435
///
436
/// The de facto standard is lenient in the following ways:
437
/// - 'Immediately following' does not refer to the next relocation entry but
438
///   the next matching relocation.
439
/// - There may be multiple high parts relocations for one low part relocation.
440
/// - There may be multiple low part relocations for one high part relocation.
441
/// - The AHL addend in each part does not have to be exactly equal as long as
442
///   the difference does not affect the carry bit from bit 15 into 16. This is
443
///   to allow, for example, the use of %lo(foo) and %lo(foo+4) when loading
444
///   both halves of a long long.
445
///
446
/// See getMatchingLoType() for a description of which high part relocations
447
/// match which low part relocations. One particular thing to note is that
448
/// R_MIPS_GOT16 and similar only have AHL addends if they refer to local
449
/// symbols.
450
///
451
/// It should also be noted that this function is not affected by whether
452
/// the symbol was kept or rewritten into a section-relative equivalent. We
453
/// always match using the expressions from the source.
454
void MipsELFObjectWriter::sortRelocs(const MCAssembler &Asm,
455
453
                                     std::vector<ELFRelocationEntry> &Relocs) {
456
453
  // We do not need to sort the relocation table for RELA relocations which
457
453
  // N32/N64 uses as the relocation addend contains the value we require,
458
453
  // rather than it being split across a pair of relocations.
459
453
  if (hasRelocationAddend())
460
152
    return;
461
301
462
301
  if (Relocs.size() < 2)
463
122
    return;
464
179
465
179
  // Sort relocations by the address they are applied to.
466
179
  llvm::sort(Relocs,
467
2.53k
             [](const ELFRelocationEntry &A, const ELFRelocationEntry &B) {
468
2.53k
               return A.Offset < B.Offset;
469
2.53k
             });
470
179
471
179
  std::list<MipsRelocationEntry> Sorted;
472
179
  std::list<ELFRelocationEntry> Remainder;
473
179
474
179
  LLVM_DEBUG(dumpRelocs("R: ", Relocs));
475
179
476
179
  // Separate the movable relocations (AHL relocations using the high bits) from
477
179
  // the immobile relocations (everything else). This does not preserve high/low
478
179
  // matches that already existed in the input.
479
179
  copy_if_else(Relocs.begin(), Relocs.end(), std::back_inserter(Remainder),
480
959
               std::back_inserter(Sorted), [](const ELFRelocationEntry &Reloc) {
481
959
                 return getMatchingLoType(Reloc) != ELF::R_MIPS_NONE;
482
959
               });
483
179
484
179
  for (auto &R : Remainder) {
485
149
    LLVM_DEBUG(dbgs() << "Matching: " << R << "\n");
486
149
487
149
    unsigned MatchingType = getMatchingLoType(R);
488
149
    assert(MatchingType != ELF::R_MIPS_NONE &&
489
149
           "Wrong list for reloc that doesn't need a match");
490
149
491
149
    // Find the best matching relocation for the current high part.
492
149
    // See isMatchingReloc for a description of a matching relocation and
493
149
    // compareMatchingRelocs for a description of what 'best' means.
494
149
    auto InsertionPoint =
495
149
        find_best(Sorted.begin(), Sorted.end(),
496
575
                  [&R, &MatchingType](const MipsRelocationEntry &X) {
497
575
                    return isMatchingReloc(X, R, MatchingType);
498
575
                  },
499
149
                  compareMatchingRelocs);
500
149
501
149
    // If we matched then insert the high part in front of the match and mark
502
149
    // both relocations as being involved in a match. We only mark the high
503
149
    // part for cosmetic reasons in the debug output.
504
149
    //
505
149
    // If we failed to find a match then the high part is orphaned. This is not
506
149
    // permitted since the relocation cannot be evaluated without knowing the
507
149
    // carry-in. We can sometimes handle this using a matching low part that is
508
149
    // already used in a match but we already cover that case in
509
149
    // isMatchingReloc and compareMatchingRelocs. For the remaining cases we
510
149
    // should insert the high part at the end of the list. This will cause the
511
149
    // linker to fail but the alternative is to cause the linker to bind the
512
149
    // high part to a semi-matching low part and silently calculate the wrong
513
149
    // value. Unfortunately we have no means to warn the user that we did this
514
149
    // so leave it up to the linker to complain about it.
515
149
    if (InsertionPoint != Sorted.end())
516
144
      InsertionPoint->Matched = true;
517
149
    Sorted.insert(InsertionPoint, R)->Matched = true;
518
149
  }
519
179
520
179
  LLVM_DEBUG(dumpRelocs("S: ", Sorted));
521
179
522
179
  assert(Relocs.size() == Sorted.size() && "Some relocs were not consumed");
523
179
524
179
  // Overwrite the original vector with the sorted elements. The caller expects
525
179
  // them in reverse order.
526
179
  unsigned CopyTo = 0;
527
179
  for (const auto &R : reverse(Sorted))
528
959
    Relocs[CopyTo++] = R.R;
529
179
}
530
531
bool MipsELFObjectWriter::needsRelocateWithSymbol(const MCSymbol &Sym,
532
647
                                                  unsigned Type) const {
533
647
  // If it's a compound relocation for N64 then we need the relocation if any
534
647
  // sub-relocation needs it.
535
647
  if (!isUInt<8>(Type))
536
23
    return needsRelocateWithSymbol(Sym, Type & 0xff) ||
537
23
           
needsRelocateWithSymbol(Sym, (Type >> 8) & 0xff)19
||
538
23
           
needsRelocateWithSymbol(Sym, (Type >> 16) & 0xff)19
;
539
624
540
624
  switch (Type) {
541
624
  default:
542
0
    errs() << Type << "\n";
543
0
    llvm_unreachable("Unexpected relocation");
544
624
    
return true0
;
545
624
546
624
  // This relocation doesn't affect the section data.
547
624
  case ELF::R_MIPS_NONE:
548
22
    return false;
549
624
550
624
  // On REL ABI's (e.g. O32), these relocations form pairs. The pairing is done
551
624
  // by the static linker by matching the symbol and offset.
552
624
  // We only see one relocation at a time but it's still safe to relocate with
553
624
  // the section so long as both relocations make the same decision.
554
624
  //
555
624
  // Some older linkers may require the symbol for particular cases. Such cases
556
624
  // are not supported yet but can be added as required.
557
624
  case ELF::R_MIPS_GOT16:
558
148
  case ELF::R_MIPS16_GOT16:
559
148
  case ELF::R_MICROMIPS_GOT16:
560
148
  case ELF::R_MIPS_HIGHER:
561
148
  case ELF::R_MIPS_HIGHEST:
562
148
  case ELF::R_MIPS_HI16:
563
148
  case ELF::R_MIPS16_HI16:
564
148
  case ELF::R_MICROMIPS_HI16:
565
148
  case ELF::R_MIPS_LO16:
566
148
  case ELF::R_MIPS16_LO16:
567
148
  case ELF::R_MICROMIPS_LO16:
568
148
    // FIXME: It should be safe to return false for the STO_MIPS_MICROMIPS but
569
148
    //        we neglect to handle the adjustment to the LSB of the addend that
570
148
    //        it causes in applyFixup() and similar.
571
148
    if (cast<MCSymbolELF>(Sym).getOther() & ELF::STO_MIPS_MICROMIPS)
572
10
      return true;
573
138
    return false;
574
138
575
295
  case ELF::R_MIPS_GOT_PAGE:
576
295
  case ELF::R_MICROMIPS_GOT_PAGE:
577
295
  case ELF::R_MIPS_GOT_OFST:
578
295
  case ELF::R_MICROMIPS_GOT_OFST:
579
295
  case ELF::R_MIPS_16:
580
295
  case ELF::R_MIPS_32:
581
295
  case ELF::R_MIPS_GPREL32:
582
295
    if (cast<MCSymbolELF>(Sym).getOther() & ELF::STO_MIPS_MICROMIPS)
583
4
      return true;
584
291
    LLVM_FALLTHROUGH;
585
389
  case ELF::R_MIPS_26:
586
389
  case ELF::R_MIPS_64:
587
389
  case ELF::R_MIPS_GPREL16:
588
389
  case ELF::R_MIPS_PC16:
589
389
  case ELF::R_MIPS_SUB:
590
389
    return false;
591
389
592
389
  // FIXME: Many of these relocations should probably return false but this
593
389
  //        hasn't been confirmed to be safe yet.
594
389
  case ELF::R_MIPS_REL32:
595
61
  case ELF::R_MIPS_LITERAL:
596
61
  case ELF::R_MIPS_CALL16:
597
61
  case ELF::R_MIPS_SHIFT5:
598
61
  case ELF::R_MIPS_SHIFT6:
599
61
  case ELF::R_MIPS_GOT_DISP:
600
61
  case ELF::R_MIPS_GOT_HI16:
601
61
  case ELF::R_MIPS_GOT_LO16:
602
61
  case ELF::R_MIPS_INSERT_A:
603
61
  case ELF::R_MIPS_INSERT_B:
604
61
  case ELF::R_MIPS_DELETE:
605
61
  case ELF::R_MIPS_CALL_HI16:
606
61
  case ELF::R_MIPS_CALL_LO16:
607
61
  case ELF::R_MIPS_SCN_DISP:
608
61
  case ELF::R_MIPS_REL16:
609
61
  case ELF::R_MIPS_ADD_IMMEDIATE:
610
61
  case ELF::R_MIPS_PJUMP:
611
61
  case ELF::R_MIPS_RELGOT:
612
61
  case ELF::R_MIPS_JALR:
613
61
  case ELF::R_MIPS_TLS_DTPMOD32:
614
61
  case ELF::R_MIPS_TLS_DTPREL32:
615
61
  case ELF::R_MIPS_TLS_DTPMOD64:
616
61
  case ELF::R_MIPS_TLS_DTPREL64:
617
61
  case ELF::R_MIPS_TLS_GD:
618
61
  case ELF::R_MIPS_TLS_LDM:
619
61
  case ELF::R_MIPS_TLS_DTPREL_HI16:
620
61
  case ELF::R_MIPS_TLS_DTPREL_LO16:
621
61
  case ELF::R_MIPS_TLS_GOTTPREL:
622
61
  case ELF::R_MIPS_TLS_TPREL32:
623
61
  case ELF::R_MIPS_TLS_TPREL64:
624
61
  case ELF::R_MIPS_TLS_TPREL_HI16:
625
61
  case ELF::R_MIPS_TLS_TPREL_LO16:
626
61
  case ELF::R_MIPS_GLOB_DAT:
627
61
  case ELF::R_MIPS_PC21_S2:
628
61
  case ELF::R_MIPS_PC26_S2:
629
61
  case ELF::R_MIPS_PC18_S3:
630
61
  case ELF::R_MIPS_PC19_S2:
631
61
  case ELF::R_MIPS_PCHI16:
632
61
  case ELF::R_MIPS_PCLO16:
633
61
  case ELF::R_MIPS_COPY:
634
61
  case ELF::R_MIPS_JUMP_SLOT:
635
61
  case ELF::R_MIPS_NUM:
636
61
  case ELF::R_MIPS_PC32:
637
61
  case ELF::R_MIPS_EH:
638
61
  case ELF::R_MICROMIPS_26_S1:
639
61
  case ELF::R_MICROMIPS_GPREL16:
640
61
  case ELF::R_MICROMIPS_LITERAL:
641
61
  case ELF::R_MICROMIPS_PC7_S1:
642
61
  case ELF::R_MICROMIPS_PC10_S1:
643
61
  case ELF::R_MICROMIPS_PC16_S1:
644
61
  case ELF::R_MICROMIPS_CALL16:
645
61
  case ELF::R_MICROMIPS_GOT_DISP:
646
61
  case ELF::R_MICROMIPS_GOT_HI16:
647
61
  case ELF::R_MICROMIPS_GOT_LO16:
648
61
  case ELF::R_MICROMIPS_SUB:
649
61
  case ELF::R_MICROMIPS_HIGHER:
650
61
  case ELF::R_MICROMIPS_HIGHEST:
651
61
  case ELF::R_MICROMIPS_CALL_HI16:
652
61
  case ELF::R_MICROMIPS_CALL_LO16:
653
61
  case ELF::R_MICROMIPS_SCN_DISP:
654
61
  case ELF::R_MICROMIPS_JALR:
655
61
  case ELF::R_MICROMIPS_HI0_LO16:
656
61
  case ELF::R_MICROMIPS_TLS_GD:
657
61
  case ELF::R_MICROMIPS_TLS_LDM:
658
61
  case ELF::R_MICROMIPS_TLS_DTPREL_HI16:
659
61
  case ELF::R_MICROMIPS_TLS_DTPREL_LO16:
660
61
  case ELF::R_MICROMIPS_TLS_GOTTPREL:
661
61
  case ELF::R_MICROMIPS_TLS_TPREL_HI16:
662
61
  case ELF::R_MICROMIPS_TLS_TPREL_LO16:
663
61
  case ELF::R_MICROMIPS_GPREL7_S2:
664
61
  case ELF::R_MICROMIPS_PC23_S2:
665
61
  case ELF::R_MICROMIPS_PC21_S1:
666
61
  case ELF::R_MICROMIPS_PC26_S1:
667
61
  case ELF::R_MICROMIPS_PC18_S3:
668
61
  case ELF::R_MICROMIPS_PC19_S2:
669
61
    return true;
670
61
671
61
  // FIXME: Many of these should probably return false but MIPS16 isn't
672
61
  //        supported by the integrated assembler.
673
61
  case ELF::R_MIPS16_26:
674
0
  case ELF::R_MIPS16_GPREL:
675
0
  case ELF::R_MIPS16_CALL16:
676
0
  case ELF::R_MIPS16_TLS_GD:
677
0
  case ELF::R_MIPS16_TLS_LDM:
678
0
  case ELF::R_MIPS16_TLS_DTPREL_HI16:
679
0
  case ELF::R_MIPS16_TLS_DTPREL_LO16:
680
0
  case ELF::R_MIPS16_TLS_GOTTPREL:
681
0
  case ELF::R_MIPS16_TLS_TPREL_HI16:
682
0
  case ELF::R_MIPS16_TLS_TPREL_LO16:
683
0
    llvm_unreachable("Unsupported MIPS16 relocation");
684
0
    return true;
685
624
  }
686
624
}
687
688
std::unique_ptr<MCObjectTargetWriter>
689
3.19k
llvm::createMipsELFObjectWriter(const Triple &TT, bool IsN32) {
690
3.19k
  uint8_t OSABI = MCELFObjectTargetWriter::getOSABI(TT.getOS());
691
3.19k
  bool IsN64 = TT.isArch64Bit() && 
!IsN321.01k
;
692
3.19k
  bool HasRelocationAddend = TT.isArch64Bit();
693
3.19k
  return llvm::make_unique<MipsELFObjectWriter>(OSABI, HasRelocationAddend,
694
3.19k
                                                IsN64);
695
3.19k
}