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