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