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