MipsELFObjectWriter.cpp revision 303975 
1//===-- MipsELFObjectWriter.cpp - Mips ELF Writer -------------------------===//
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#include "MCTargetDesc/MipsBaseInfo.h"
11#include "MCTargetDesc/MipsFixupKinds.h"
12#include "MCTargetDesc/MipsMCTargetDesc.h"
13#include "llvm/ADT/STLExtras.h"
14#include "llvm/MC/MCAssembler.h"
15#include "llvm/MC/MCELFObjectWriter.h"
16#include "llvm/MC/MCExpr.h"
17#include "llvm/MC/MCSection.h"
18#include "llvm/MC/MCSymbolELF.h"
19#include "llvm/MC/MCValue.h"
20#include "llvm/Support/ErrorHandling.h"
21#include <list>
22
23using namespace llvm;
24
25namespace {
26// A helper structure based on ELFRelocationEntry, used for sorting entries in
27// the relocation table.
28struct MipsRelocationEntry {
29  MipsRelocationEntry(const ELFRelocationEntry &R)
30      : R(R), SortOffset(R.Offset), HasMatchingHi(false) {}
31  const ELFRelocationEntry R;
32  // SortOffset equals R.Offset except for the *HI16 relocations, for which it
33  // will be set based on the R.Offset of the matching *LO16 relocation.
34  int64_t SortOffset;
35  // True when this is a *LO16 relocation chosen as a match for a *HI16
36  // relocation.
37  bool HasMatchingHi;
38};
39
40  class MipsELFObjectWriter : public MCELFObjectTargetWriter {
41  public:
42    MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI,
43                        bool _isN64, bool IsLittleEndian);
44
45    ~MipsELFObjectWriter() override;
46
47    unsigned GetRelocType(const MCValue &Target, const MCFixup &Fixup,
48                          bool IsPCRel) const override;
49    bool needsRelocateWithSymbol(const MCSymbol &Sym,
50                                 unsigned Type) const override;
51    virtual void sortRelocs(const MCAssembler &Asm,
52                            std::vector<ELFRelocationEntry> &Relocs) override;
53  };
54}
55
56MipsELFObjectWriter::MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI,
57                                         bool _isN64, bool IsLittleEndian)
58    : MCELFObjectTargetWriter(_is64Bit, OSABI, ELF::EM_MIPS,
59                              /*HasRelocationAddend*/ _isN64,
60                              /*IsN64*/ _isN64) {}
61
62MipsELFObjectWriter::~MipsELFObjectWriter() {}
63
64unsigned MipsELFObjectWriter::GetRelocType(const MCValue &Target,
65                                           const MCFixup &Fixup,
66                                           bool IsPCRel) const {
67  // Determine the type of the relocation.
68  unsigned Kind = (unsigned)Fixup.getKind();
69
70  switch (Kind) {
71  case Mips::fixup_Mips_NONE:
72    return ELF::R_MIPS_NONE;
73  case Mips::fixup_Mips_16:
74  case FK_Data_2:
75    return IsPCRel ? ELF::R_MIPS_PC16 : ELF::R_MIPS_16;
76  case Mips::fixup_Mips_32:
77  case FK_Data_4:
78    return IsPCRel ? ELF::R_MIPS_PC32 : ELF::R_MIPS_32;
79  }
80
81  if (IsPCRel) {
82    switch (Kind) {
83    case Mips::fixup_Mips_Branch_PCRel:
84    case Mips::fixup_Mips_PC16:
85      return ELF::R_MIPS_PC16;
86    case Mips::fixup_MICROMIPS_PC7_S1:
87      return ELF::R_MICROMIPS_PC7_S1;
88    case Mips::fixup_MICROMIPS_PC10_S1:
89      return ELF::R_MICROMIPS_PC10_S1;
90    case Mips::fixup_MICROMIPS_PC16_S1:
91      return ELF::R_MICROMIPS_PC16_S1;
92    case Mips::fixup_MIPS_PC19_S2:
93      return ELF::R_MIPS_PC19_S2;
94    case Mips::fixup_MIPS_PC18_S3:
95      return ELF::R_MIPS_PC18_S3;
96    case Mips::fixup_MIPS_PC21_S2:
97      return ELF::R_MIPS_PC21_S2;
98    case Mips::fixup_MIPS_PC26_S2:
99      return ELF::R_MIPS_PC26_S2;
100    case Mips::fixup_MIPS_PCHI16:
101      return ELF::R_MIPS_PCHI16;
102    case Mips::fixup_MIPS_PCLO16:
103      return ELF::R_MIPS_PCLO16;
104    }
105
106    llvm_unreachable("invalid PC-relative fixup kind!");
107  }
108
109  switch (Kind) {
110  case Mips::fixup_Mips_64:
111  case FK_Data_8:
112    return ELF::R_MIPS_64;
113  case FK_GPRel_4:
114    if (isN64()) {
115      unsigned Type = (unsigned)ELF::R_MIPS_NONE;
116      Type = setRType((unsigned)ELF::R_MIPS_GPREL32, Type);
117      Type = setRType2((unsigned)ELF::R_MIPS_64, Type);
118      Type = setRType3((unsigned)ELF::R_MIPS_NONE, Type);
119      return Type;
120    }
121    return ELF::R_MIPS_GPREL32;
122  case Mips::fixup_Mips_GPREL16:
123    return ELF::R_MIPS_GPREL16;
124  case Mips::fixup_Mips_26:
125    return ELF::R_MIPS_26;
126  case Mips::fixup_Mips_CALL16:
127    return ELF::R_MIPS_CALL16;
128  case Mips::fixup_Mips_GOT_Global:
129  case Mips::fixup_Mips_GOT_Local:
130    return ELF::R_MIPS_GOT16;
131  case Mips::fixup_Mips_HI16:
132    return ELF::R_MIPS_HI16;
133  case Mips::fixup_Mips_LO16:
134    return ELF::R_MIPS_LO16;
135  case Mips::fixup_Mips_TLSGD:
136    return ELF::R_MIPS_TLS_GD;
137  case Mips::fixup_Mips_GOTTPREL:
138    return ELF::R_MIPS_TLS_GOTTPREL;
139  case Mips::fixup_Mips_TPREL_HI:
140    return ELF::R_MIPS_TLS_TPREL_HI16;
141  case Mips::fixup_Mips_TPREL_LO:
142    return ELF::R_MIPS_TLS_TPREL_LO16;
143  case Mips::fixup_Mips_TLSLDM:
144    return ELF::R_MIPS_TLS_LDM;
145  case Mips::fixup_Mips_DTPREL_HI:
146    return ELF::R_MIPS_TLS_DTPREL_HI16;
147  case Mips::fixup_Mips_DTPREL_LO:
148    return ELF::R_MIPS_TLS_DTPREL_LO16;
149  case Mips::fixup_Mips_GOT_PAGE:
150    return ELF::R_MIPS_GOT_PAGE;
151  case Mips::fixup_Mips_GOT_OFST:
152    return ELF::R_MIPS_GOT_OFST;
153  case Mips::fixup_Mips_GOT_DISP:
154    return ELF::R_MIPS_GOT_DISP;
155  case Mips::fixup_Mips_GPOFF_HI: {
156    unsigned Type = (unsigned)ELF::R_MIPS_NONE;
157    Type = setRType((unsigned)ELF::R_MIPS_GPREL16, Type);
158    Type = setRType2((unsigned)ELF::R_MIPS_SUB, Type);
159    Type = setRType3((unsigned)ELF::R_MIPS_HI16, Type);
160    return Type;
161  }
162  case Mips::fixup_Mips_GPOFF_LO: {
163    unsigned Type = (unsigned)ELF::R_MIPS_NONE;
164    Type = setRType((unsigned)ELF::R_MIPS_GPREL16, Type);
165    Type = setRType2((unsigned)ELF::R_MIPS_SUB, Type);
166    Type = setRType3((unsigned)ELF::R_MIPS_LO16, Type);
167    return Type;
168  }
169  case Mips::fixup_Mips_HIGHER:
170    return ELF::R_MIPS_HIGHER;
171  case Mips::fixup_Mips_HIGHEST:
172    return ELF::R_MIPS_HIGHEST;
173  case Mips::fixup_Mips_GOT_HI16:
174    return ELF::R_MIPS_GOT_HI16;
175  case Mips::fixup_Mips_GOT_LO16:
176    return ELF::R_MIPS_GOT_LO16;
177  case Mips::fixup_Mips_CALL_HI16:
178    return ELF::R_MIPS_CALL_HI16;
179  case Mips::fixup_Mips_CALL_LO16:
180    return ELF::R_MIPS_CALL_LO16;
181  case Mips::fixup_MICROMIPS_26_S1:
182    return ELF::R_MICROMIPS_26_S1;
183  case Mips::fixup_MICROMIPS_HI16:
184    return ELF::R_MICROMIPS_HI16;
185  case Mips::fixup_MICROMIPS_LO16:
186    return ELF::R_MICROMIPS_LO16;
187  case Mips::fixup_MICROMIPS_GOT16:
188    return ELF::R_MICROMIPS_GOT16;
189  case Mips::fixup_MICROMIPS_CALL16:
190    return ELF::R_MICROMIPS_CALL16;
191  case Mips::fixup_MICROMIPS_GOT_DISP:
192    return ELF::R_MICROMIPS_GOT_DISP;
193  case Mips::fixup_MICROMIPS_GOT_PAGE:
194    return ELF::R_MICROMIPS_GOT_PAGE;
195  case Mips::fixup_MICROMIPS_GOT_OFST:
196    return ELF::R_MICROMIPS_GOT_OFST;
197  case Mips::fixup_MICROMIPS_TLS_GD:
198    return ELF::R_MICROMIPS_TLS_GD;
199  case Mips::fixup_MICROMIPS_TLS_LDM:
200    return ELF::R_MICROMIPS_TLS_LDM;
201  case Mips::fixup_MICROMIPS_TLS_DTPREL_HI16:
202    return ELF::R_MICROMIPS_TLS_DTPREL_HI16;
203  case Mips::fixup_MICROMIPS_TLS_DTPREL_LO16:
204    return ELF::R_MICROMIPS_TLS_DTPREL_LO16;
205  case Mips::fixup_MICROMIPS_TLS_TPREL_HI16:
206    return ELF::R_MICROMIPS_TLS_TPREL_HI16;
207  case Mips::fixup_MICROMIPS_TLS_TPREL_LO16:
208    return ELF::R_MICROMIPS_TLS_TPREL_LO16;
209  }
210
211  llvm_unreachable("invalid fixup kind!");
212}
213
214// Sort entries by SortOffset in descending order.
215// When there are more *HI16 relocs paired with one *LO16 reloc, the 2nd rule
216// sorts them in ascending order of R.Offset.
217static int cmpRelMips(const MipsRelocationEntry *AP,
218                      const MipsRelocationEntry *BP) {
219  const MipsRelocationEntry &A = *AP;
220  const MipsRelocationEntry &B = *BP;
221  if (A.SortOffset != B.SortOffset)
222    return B.SortOffset - A.SortOffset;
223  if (A.R.Offset != B.R.Offset)
224    return A.R.Offset - B.R.Offset;
225  if (B.R.Type != A.R.Type)
226    return B.R.Type - A.R.Type;
227  //llvm_unreachable("ELFRelocs might be unstable!");
228  return 0;
229}
230
231// For the given Reloc.Type, return the matching relocation type, as in the
232// table below.
233static unsigned getMatchingLoType(const MCAssembler &Asm,
234                                  const ELFRelocationEntry &Reloc) {
235  unsigned Type = Reloc.Type;
236  if (Type == ELF::R_MIPS_HI16)
237    return ELF::R_MIPS_LO16;
238  if (Type == ELF::R_MICROMIPS_HI16)
239    return ELF::R_MICROMIPS_LO16;
240  if (Type == ELF::R_MIPS16_HI16)
241    return ELF::R_MIPS16_LO16;
242
243  if (Reloc.Symbol->getBinding() != ELF::STB_LOCAL)
244    return ELF::R_MIPS_NONE;
245
246  if (Type == ELF::R_MIPS_GOT16)
247    return ELF::R_MIPS_LO16;
248  if (Type == ELF::R_MICROMIPS_GOT16)
249    return ELF::R_MICROMIPS_LO16;
250  if (Type == ELF::R_MIPS16_GOT16)
251    return ELF::R_MIPS16_LO16;
252
253  return ELF::R_MIPS_NONE;
254}
255
256// Return true if First needs a matching *LO16, its matching *LO16 type equals
257// Second's type and both relocations are against the same symbol.
258static bool areMatchingHiAndLo(const MCAssembler &Asm,
259                               const ELFRelocationEntry &First,
260                               const ELFRelocationEntry &Second) {
261  return getMatchingLoType(Asm, First) != ELF::R_MIPS_NONE &&
262         getMatchingLoType(Asm, First) == Second.Type &&
263         First.Symbol && First.Symbol == Second.Symbol;
264}
265
266// Return true if MipsRelocs[Index] is a *LO16 preceded by a matching *HI16.
267static bool
268isPrecededByMatchingHi(const MCAssembler &Asm, uint32_t Index,
269                       std::vector<MipsRelocationEntry> &MipsRelocs) {
270  return Index < MipsRelocs.size() - 1 &&
271         areMatchingHiAndLo(Asm, MipsRelocs[Index + 1].R, MipsRelocs[Index].R);
272}
273
274// Return true if MipsRelocs[Index] is a *LO16 not preceded by a matching *HI16
275// and not chosen by a *HI16 as a match.
276static bool isFreeLo(const MCAssembler &Asm, uint32_t Index,
277                     std::vector<MipsRelocationEntry> &MipsRelocs) {
278  return Index < MipsRelocs.size() && !MipsRelocs[Index].HasMatchingHi &&
279         !isPrecededByMatchingHi(Asm, Index, MipsRelocs);
280}
281
282// Lo is chosen as a match for Hi, set their fields accordingly.
283// Mips instructions have fixed length of at least two bytes (two for
284// micromips/mips16, four for mips32/64), so we can set HI's SortOffset to
285// matching LO's Offset minus one to simplify the sorting function.
286static void setMatch(MipsRelocationEntry &Hi, MipsRelocationEntry &Lo) {
287  Lo.HasMatchingHi = true;
288  Hi.SortOffset = Lo.R.Offset - 1;
289}
290
291// We sort relocation table entries by offset, except for one additional rule
292// required by MIPS ABI: every *HI16 relocation must be immediately followed by
293// the corresponding *LO16 relocation. We also support a GNU extension that
294// allows more *HI16s paired with one *LO16.
295//
296// *HI16 relocations and their matching *LO16 are:
297//
298// +---------------------------------------------+-------------------+
299// |               *HI16                         |  matching *LO16   |
300// |---------------------------------------------+-------------------|
301// |  R_MIPS_HI16, local R_MIPS_GOT16            |    R_MIPS_LO16    |
302// |  R_MICROMIPS_HI16, local R_MICROMIPS_GOT16  | R_MICROMIPS_LO16  |
303// |  R_MIPS16_HI16, local R_MIPS16_GOT16        |  R_MIPS16_LO16    |
304// +---------------------------------------------+-------------------+
305//
306// (local R_*_GOT16 meaning R_*_GOT16 against the local symbol.)
307//
308// To handle *HI16 and *LO16 relocations, the linker needs a combined addend
309// ("AHL") calculated from both *HI16 ("AHI") and *LO16 ("ALO") relocations:
310// AHL = (AHI << 16) + (short)ALO;
311//
312// We are reusing gnu as sorting algorithm so we are emitting the relocation
313// table sorted the same way as gnu as would sort it, for easier comparison of
314// the generated .o files.
315//
316// The logic is:
317// search the table (starting from the highest offset and going back to zero)
318// for all *HI16 relocations that don't have a matching *LO16.
319// For every such HI, find a matching LO with highest offset that isn't already
320// matched with another HI. If there are no free LOs, match it with the first
321// found (starting from lowest offset).
322// When there are more HIs matched with one LO, sort them in descending order by
323// offset.
324//
325// In other words, when searching for a matching LO:
326// - don't look for a 'better' match for the HIs that are already followed by a
327//   matching LO;
328// - prefer LOs without a pair;
329// - prefer LOs with higher offset;
330
331static int cmpRel(const ELFRelocationEntry *AP, const ELFRelocationEntry *BP) {
332  const ELFRelocationEntry &A = *AP;
333  const ELFRelocationEntry &B = *BP;
334  if (A.Offset != B.Offset)
335    return B.Offset - A.Offset;
336  if (B.Type != A.Type)
337    return A.Type - B.Type;
338  return 0;
339}
340
341void MipsELFObjectWriter::sortRelocs(const MCAssembler &Asm,
342                                     std::vector<ELFRelocationEntry> &Relocs) {
343  if (Relocs.size() < 2)
344    return;
345
346  // Sorts entries by Offset in descending order.
347  array_pod_sort(Relocs.begin(), Relocs.end(), cmpRel);
348
349  // Init MipsRelocs from Relocs.
350  std::vector<MipsRelocationEntry> MipsRelocs;
351  for (unsigned I = 0, E = Relocs.size(); I != E; ++I)
352    MipsRelocs.push_back(MipsRelocationEntry(Relocs[I]));
353
354  // Find a matching LO for all HIs that need it.
355  for (int32_t I = 0, E = MipsRelocs.size(); I != E; ++I) {
356    if (getMatchingLoType(Asm, MipsRelocs[I].R) == ELF::R_MIPS_NONE ||
357        (I > 0 && isPrecededByMatchingHi(Asm, I - 1, MipsRelocs)))
358      continue;
359
360    int32_t MatchedLoIndex = -1;
361
362    // Search the list in the ascending order of Offset.
363    for (int32_t J = MipsRelocs.size() - 1, N = -1; J != N; --J) {
364      // check for a match
365      if (areMatchingHiAndLo(Asm, MipsRelocs[I].R, MipsRelocs[J].R) &&
366          (MatchedLoIndex == -1 || // first match
367           // or we already have a match,
368           // but this one is with higher offset and it's free
369           (MatchedLoIndex > J && isFreeLo(Asm, J, MipsRelocs))))
370        MatchedLoIndex = J;
371    }
372
373    if (MatchedLoIndex != -1)
374      // We have a match.
375      setMatch(MipsRelocs[I], MipsRelocs[MatchedLoIndex]);
376  }
377
378  // SortOffsets are calculated, call the sorting function.
379  array_pod_sort(MipsRelocs.begin(), MipsRelocs.end(), cmpRelMips);
380
381  // Copy sorted MipsRelocs back to Relocs.
382  for (unsigned I = 0, E = MipsRelocs.size(); I != E; ++I)
383    Relocs[I] = MipsRelocs[I].R;
384}
385
386bool MipsELFObjectWriter::needsRelocateWithSymbol(const MCSymbol &Sym,
387                                                  unsigned Type) const {
388  // FIXME: This is extremely conservative. This really needs to use a
389  // whitelist with a clear explanation for why each realocation needs to
390  // point to the symbol, not to the section.
391  switch (Type) {
392  default:
393    return true;
394
395  case ELF::R_MIPS_GOT16:
396  case ELF::R_MIPS16_GOT16:
397  case ELF::R_MICROMIPS_GOT16:
398    llvm_unreachable("Should have been handled already");
399
400  // These relocations might be paired with another relocation. The pairing is
401  // done by the static linker by matching the symbol. Since we only see one
402  // relocation at a time, we have to force them to relocate with a symbol to
403  // avoid ending up with a pair where one points to a section and another
404  // points to a symbol.
405  case ELF::R_MIPS_HI16:
406  case ELF::R_MIPS16_HI16:
407  case ELF::R_MICROMIPS_HI16:
408  case ELF::R_MIPS_LO16:
409  case ELF::R_MIPS16_LO16:
410  case ELF::R_MICROMIPS_LO16:
411    return true;
412
413  case ELF::R_MIPS_32:
414    if (cast<MCSymbolELF>(Sym).getOther() & ELF::STO_MIPS_MICROMIPS)
415      return true;
416    // falltrough
417  case ELF::R_MIPS_26:
418  case ELF::R_MIPS_64:
419  case ELF::R_MIPS_GPREL16:
420    return false;
421  }
422}
423
424MCObjectWriter *llvm::createMipsELFObjectWriter(raw_pwrite_stream &OS,
425                                                uint8_t OSABI,
426                                                bool IsLittleEndian,
427                                                bool Is64Bit) {
428  MCELFObjectTargetWriter *MOTW =
429      new MipsELFObjectWriter(Is64Bit, OSABI, Is64Bit, IsLittleEndian);
430  return createELFObjectWriter(MOTW, OS, IsLittleEndian);
431}
432