1//===- MCExpr.cpp - Assembly Level Expression Implementation --------------===//
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 "llvm/MC/MCExpr.h"
11#include "llvm/ADT/Statistic.h"
12#include "llvm/ADT/StringSwitch.h"
13#include "llvm/MC/MCAsmInfo.h"
14#include "llvm/MC/MCAsmLayout.h"
15#include "llvm/MC/MCAssembler.h"
16#include "llvm/MC/MCContext.h"
17#include "llvm/MC/MCObjectWriter.h"
18#include "llvm/MC/MCSymbol.h"
19#include "llvm/MC/MCValue.h"
20#include "llvm/Support/Debug.h"
21#include "llvm/Support/ErrorHandling.h"
22#include "llvm/Support/raw_ostream.h"
23using namespace llvm;
24
25#define DEBUG_TYPE "mcexpr"
26
27namespace {
28namespace stats {
29STATISTIC(MCExprEvaluate, "Number of MCExpr evaluations");
30}
31}
32
33void MCExpr::print(raw_ostream &OS, const MCAsmInfo *MAI, bool InParens) const {
34  switch (getKind()) {
35  case MCExpr::Target:
36    return cast<MCTargetExpr>(this)->printImpl(OS, MAI);
37  case MCExpr::Constant:
38    OS << cast<MCConstantExpr>(*this).getValue();
39    return;
40
41  case MCExpr::SymbolRef: {
42    const MCSymbolRefExpr &SRE = cast<MCSymbolRefExpr>(*this);
43    const MCSymbol &Sym = SRE.getSymbol();
44    // Parenthesize names that start with $ so that they don't look like
45    // absolute names.
46    bool UseParens =
47        !InParens && Sym.getName().size() && Sym.getName()[0] == '$';
48    if (UseParens) {
49      OS << '(';
50      Sym.print(OS, MAI);
51      OS << ')';
52    } else
53      Sym.print(OS, MAI);
54
55    if (SRE.getKind() != MCSymbolRefExpr::VK_None)
56      SRE.printVariantKind(OS);
57
58    return;
59  }
60
61  case MCExpr::Unary: {
62    const MCUnaryExpr &UE = cast<MCUnaryExpr>(*this);
63    switch (UE.getOpcode()) {
64    case MCUnaryExpr::LNot:  OS << '!'; break;
65    case MCUnaryExpr::Minus: OS << '-'; break;
66    case MCUnaryExpr::Not:   OS << '~'; break;
67    case MCUnaryExpr::Plus:  OS << '+'; break;
68    }
69    UE.getSubExpr()->print(OS, MAI);
70    return;
71  }
72
73  case MCExpr::Binary: {
74    const MCBinaryExpr &BE = cast<MCBinaryExpr>(*this);
75
76    // Only print parens around the LHS if it is non-trivial.
77    if (isa<MCConstantExpr>(BE.getLHS()) || isa<MCSymbolRefExpr>(BE.getLHS())) {
78      BE.getLHS()->print(OS, MAI);
79    } else {
80      OS << '(';
81      BE.getLHS()->print(OS, MAI);
82      OS << ')';
83    }
84
85    switch (BE.getOpcode()) {
86    case MCBinaryExpr::Add:
87      // Print "X-42" instead of "X+-42".
88      if (const MCConstantExpr *RHSC = dyn_cast<MCConstantExpr>(BE.getRHS())) {
89        if (RHSC->getValue() < 0) {
90          OS << RHSC->getValue();
91          return;
92        }
93      }
94
95      OS <<  '+';
96      break;
97    case MCBinaryExpr::AShr: OS << ">>"; break;
98    case MCBinaryExpr::And:  OS <<  '&'; break;
99    case MCBinaryExpr::Div:  OS <<  '/'; break;
100    case MCBinaryExpr::EQ:   OS << "=="; break;
101    case MCBinaryExpr::GT:   OS <<  '>'; break;
102    case MCBinaryExpr::GTE:  OS << ">="; break;
103    case MCBinaryExpr::LAnd: OS << "&&"; break;
104    case MCBinaryExpr::LOr:  OS << "||"; break;
105    case MCBinaryExpr::LShr: OS << ">>"; break;
106    case MCBinaryExpr::LT:   OS <<  '<'; break;
107    case MCBinaryExpr::LTE:  OS << "<="; break;
108    case MCBinaryExpr::Mod:  OS <<  '%'; break;
109    case MCBinaryExpr::Mul:  OS <<  '*'; break;
110    case MCBinaryExpr::NE:   OS << "!="; break;
111    case MCBinaryExpr::Or:   OS <<  '|'; break;
112    case MCBinaryExpr::Shl:  OS << "<<"; break;
113    case MCBinaryExpr::Sub:  OS <<  '-'; break;
114    case MCBinaryExpr::Xor:  OS <<  '^'; break;
115    }
116
117    // Only print parens around the LHS if it is non-trivial.
118    if (isa<MCConstantExpr>(BE.getRHS()) || isa<MCSymbolRefExpr>(BE.getRHS())) {
119      BE.getRHS()->print(OS, MAI);
120    } else {
121      OS << '(';
122      BE.getRHS()->print(OS, MAI);
123      OS << ')';
124    }
125    return;
126  }
127  }
128
129  llvm_unreachable("Invalid expression kind!");
130}
131
132#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
133LLVM_DUMP_METHOD void MCExpr::dump() const {
134  dbgs() << *this;
135  dbgs() << '\n';
136}
137#endif
138
139/* *** */
140
141const MCBinaryExpr *MCBinaryExpr::create(Opcode Opc, const MCExpr *LHS,
142                                         const MCExpr *RHS, MCContext &Ctx) {
143  return new (Ctx) MCBinaryExpr(Opc, LHS, RHS);
144}
145
146const MCUnaryExpr *MCUnaryExpr::create(Opcode Opc, const MCExpr *Expr,
147                                       MCContext &Ctx) {
148  return new (Ctx) MCUnaryExpr(Opc, Expr);
149}
150
151const MCConstantExpr *MCConstantExpr::create(int64_t Value, MCContext &Ctx) {
152  return new (Ctx) MCConstantExpr(Value);
153}
154
155/* *** */
156
157MCSymbolRefExpr::MCSymbolRefExpr(const MCSymbol *Symbol, VariantKind Kind,
158                                 const MCAsmInfo *MAI)
159    : MCExpr(MCExpr::SymbolRef), Kind(Kind),
160      UseParensForSymbolVariant(MAI->useParensForSymbolVariant()),
161      HasSubsectionsViaSymbols(MAI->hasSubsectionsViaSymbols()),
162      Symbol(Symbol) {
163  assert(Symbol);
164}
165
166const MCSymbolRefExpr *MCSymbolRefExpr::create(const MCSymbol *Sym,
167                                               VariantKind Kind,
168                                               MCContext &Ctx) {
169  return new (Ctx) MCSymbolRefExpr(Sym, Kind, Ctx.getAsmInfo());
170}
171
172const MCSymbolRefExpr *MCSymbolRefExpr::create(StringRef Name, VariantKind Kind,
173                                               MCContext &Ctx) {
174  return create(Ctx.getOrCreateSymbol(Name), Kind, Ctx);
175}
176
177StringRef MCSymbolRefExpr::getVariantKindName(VariantKind Kind) {
178  switch (Kind) {
179  case VK_Invalid: return "<<invalid>>";
180  case VK_None: return "<<none>>";
181
182  case VK_DTPOFF: return "DTPOFF";
183  case VK_DTPREL: return "DTPREL";
184  case VK_GOT: return "GOT";
185  case VK_GOTOFF: return "GOTOFF";
186  case VK_GOTREL: return "GOTREL";
187  case VK_GOTPCREL: return "GOTPCREL";
188  case VK_GOTTPOFF: return "GOTTPOFF";
189  case VK_INDNTPOFF: return "INDNTPOFF";
190  case VK_NTPOFF: return "NTPOFF";
191  case VK_GOTNTPOFF: return "GOTNTPOFF";
192  case VK_PLT: return "PLT";
193  case VK_TLSGD: return "TLSGD";
194  case VK_TLSLD: return "TLSLD";
195  case VK_TLSLDM: return "TLSLDM";
196  case VK_TPOFF: return "TPOFF";
197  case VK_TPREL: return "TPREL";
198  case VK_TLSCALL: return "tlscall";
199  case VK_TLSDESC: return "tlsdesc";
200  case VK_TLVP: return "TLVP";
201  case VK_TLVPPAGE: return "TLVPPAGE";
202  case VK_TLVPPAGEOFF: return "TLVPPAGEOFF";
203  case VK_PAGE: return "PAGE";
204  case VK_PAGEOFF: return "PAGEOFF";
205  case VK_GOTPAGE: return "GOTPAGE";
206  case VK_GOTPAGEOFF: return "GOTPAGEOFF";
207  case VK_SECREL: return "SECREL32";
208  case VK_SIZE: return "SIZE";
209  case VK_WEAKREF: return "WEAKREF";
210  case VK_ARM_NONE: return "none";
211  case VK_ARM_GOT_PREL: return "GOT_PREL";
212  case VK_ARM_TARGET1: return "target1";
213  case VK_ARM_TARGET2: return "target2";
214  case VK_ARM_PREL31: return "prel31";
215  case VK_ARM_SBREL: return "sbrel";
216  case VK_ARM_TLSLDO: return "tlsldo";
217  case VK_ARM_TLSDESCSEQ: return "tlsdescseq";
218  case VK_PPC_LO: return "l";
219  case VK_PPC_HI: return "h";
220  case VK_PPC_HA: return "ha";
221  case VK_PPC_HIGHER: return "higher";
222  case VK_PPC_HIGHERA: return "highera";
223  case VK_PPC_HIGHEST: return "highest";
224  case VK_PPC_HIGHESTA: return "highesta";
225  case VK_PPC_GOT_LO: return "got@l";
226  case VK_PPC_GOT_HI: return "got@h";
227  case VK_PPC_GOT_HA: return "got@ha";
228  case VK_PPC_TOCBASE: return "tocbase";
229  case VK_PPC_TOC: return "toc";
230  case VK_PPC_TOC_LO: return "toc@l";
231  case VK_PPC_TOC_HI: return "toc@h";
232  case VK_PPC_TOC_HA: return "toc@ha";
233  case VK_PPC_DTPMOD: return "dtpmod";
234  case VK_PPC_TPREL_LO: return "tprel@l";
235  case VK_PPC_TPREL_HI: return "tprel@h";
236  case VK_PPC_TPREL_HA: return "tprel@ha";
237  case VK_PPC_TPREL_HIGHER: return "tprel@higher";
238  case VK_PPC_TPREL_HIGHERA: return "tprel@highera";
239  case VK_PPC_TPREL_HIGHEST: return "tprel@highest";
240  case VK_PPC_TPREL_HIGHESTA: return "tprel@highesta";
241  case VK_PPC_DTPREL_LO: return "dtprel@l";
242  case VK_PPC_DTPREL_HI: return "dtprel@h";
243  case VK_PPC_DTPREL_HA: return "dtprel@ha";
244  case VK_PPC_DTPREL_HIGHER: return "dtprel@higher";
245  case VK_PPC_DTPREL_HIGHERA: return "dtprel@highera";
246  case VK_PPC_DTPREL_HIGHEST: return "dtprel@highest";
247  case VK_PPC_DTPREL_HIGHESTA: return "dtprel@highesta";
248  case VK_PPC_GOT_TPREL: return "got@tprel";
249  case VK_PPC_GOT_TPREL_LO: return "got@tprel@l";
250  case VK_PPC_GOT_TPREL_HI: return "got@tprel@h";
251  case VK_PPC_GOT_TPREL_HA: return "got@tprel@ha";
252  case VK_PPC_GOT_DTPREL: return "got@dtprel";
253  case VK_PPC_GOT_DTPREL_LO: return "got@dtprel@l";
254  case VK_PPC_GOT_DTPREL_HI: return "got@dtprel@h";
255  case VK_PPC_GOT_DTPREL_HA: return "got@dtprel@ha";
256  case VK_PPC_TLS: return "tls";
257  case VK_PPC_GOT_TLSGD: return "got@tlsgd";
258  case VK_PPC_GOT_TLSGD_LO: return "got@tlsgd@l";
259  case VK_PPC_GOT_TLSGD_HI: return "got@tlsgd@h";
260  case VK_PPC_GOT_TLSGD_HA: return "got@tlsgd@ha";
261  case VK_PPC_TLSGD: return "tlsgd";
262  case VK_PPC_GOT_TLSLD: return "got@tlsld";
263  case VK_PPC_GOT_TLSLD_LO: return "got@tlsld@l";
264  case VK_PPC_GOT_TLSLD_HI: return "got@tlsld@h";
265  case VK_PPC_GOT_TLSLD_HA: return "got@tlsld@ha";
266  case VK_PPC_TLSLD: return "tlsld";
267  case VK_PPC_LOCAL: return "local";
268  case VK_COFF_IMGREL32: return "IMGREL";
269  case VK_Hexagon_PCREL: return "PCREL";
270  case VK_Hexagon_LO16: return "LO16";
271  case VK_Hexagon_HI16: return "HI16";
272  case VK_Hexagon_GPREL: return "GPREL";
273  case VK_Hexagon_GD_GOT: return "GDGOT";
274  case VK_Hexagon_LD_GOT: return "LDGOT";
275  case VK_Hexagon_GD_PLT: return "GDPLT";
276  case VK_Hexagon_LD_PLT: return "LDPLT";
277  case VK_Hexagon_IE: return "IE";
278  case VK_Hexagon_IE_GOT: return "IEGOT";
279  case VK_WebAssembly_FUNCTION: return "FUNCTION";
280  }
281  llvm_unreachable("Invalid variant kind");
282}
283
284MCSymbolRefExpr::VariantKind
285MCSymbolRefExpr::getVariantKindForName(StringRef Name) {
286  return StringSwitch<VariantKind>(Name.lower())
287    .Case("dtprel", VK_DTPREL)
288    .Case("dtpoff", VK_DTPOFF)
289    .Case("got", VK_GOT)
290    .Case("gotoff", VK_GOTOFF)
291    .Case("gotrel", VK_GOTREL)
292    .Case("gotpcrel", VK_GOTPCREL)
293    .Case("gottpoff", VK_GOTTPOFF)
294    .Case("indntpoff", VK_INDNTPOFF)
295    .Case("ntpoff", VK_NTPOFF)
296    .Case("gotntpoff", VK_GOTNTPOFF)
297    .Case("plt", VK_PLT)
298    .Case("tlscall", VK_TLSCALL)
299    .Case("tlsdesc", VK_TLSDESC)
300    .Case("tlsgd", VK_TLSGD)
301    .Case("tlsld", VK_TLSLD)
302    .Case("tlsldm", VK_TLSLDM)
303    .Case("tpoff", VK_TPOFF)
304    .Case("tprel", VK_TPREL)
305    .Case("tlvp", VK_TLVP)
306    .Case("tlvppage", VK_TLVPPAGE)
307    .Case("tlvppageoff", VK_TLVPPAGEOFF)
308    .Case("page", VK_PAGE)
309    .Case("pageoff", VK_PAGEOFF)
310    .Case("gotpage", VK_GOTPAGE)
311    .Case("gotpageoff", VK_GOTPAGEOFF)
312    .Case("imgrel", VK_COFF_IMGREL32)
313    .Case("secrel32", VK_SECREL)
314    .Case("size", VK_SIZE)
315    .Case("l", VK_PPC_LO)
316    .Case("h", VK_PPC_HI)
317    .Case("ha", VK_PPC_HA)
318    .Case("higher", VK_PPC_HIGHER)
319    .Case("highera", VK_PPC_HIGHERA)
320    .Case("highest", VK_PPC_HIGHEST)
321    .Case("highesta", VK_PPC_HIGHESTA)
322    .Case("got@l", VK_PPC_GOT_LO)
323    .Case("got@h", VK_PPC_GOT_HI)
324    .Case("got@ha", VK_PPC_GOT_HA)
325    .Case("local", VK_PPC_LOCAL)
326    .Case("tocbase", VK_PPC_TOCBASE)
327    .Case("toc", VK_PPC_TOC)
328    .Case("toc@l", VK_PPC_TOC_LO)
329    .Case("toc@h", VK_PPC_TOC_HI)
330    .Case("toc@ha", VK_PPC_TOC_HA)
331    .Case("tls", VK_PPC_TLS)
332    .Case("dtpmod", VK_PPC_DTPMOD)
333    .Case("tprel@l", VK_PPC_TPREL_LO)
334    .Case("tprel@h", VK_PPC_TPREL_HI)
335    .Case("tprel@ha", VK_PPC_TPREL_HA)
336    .Case("tprel@higher", VK_PPC_TPREL_HIGHER)
337    .Case("tprel@highera", VK_PPC_TPREL_HIGHERA)
338    .Case("tprel@highest", VK_PPC_TPREL_HIGHEST)
339    .Case("tprel@highesta", VK_PPC_TPREL_HIGHESTA)
340    .Case("dtprel@l", VK_PPC_DTPREL_LO)
341    .Case("dtprel@h", VK_PPC_DTPREL_HI)
342    .Case("dtprel@ha", VK_PPC_DTPREL_HA)
343    .Case("dtprel@higher", VK_PPC_DTPREL_HIGHER)
344    .Case("dtprel@highera", VK_PPC_DTPREL_HIGHERA)
345    .Case("dtprel@highest", VK_PPC_DTPREL_HIGHEST)
346    .Case("dtprel@highesta", VK_PPC_DTPREL_HIGHESTA)
347    .Case("got@tprel", VK_PPC_GOT_TPREL)
348    .Case("got@tprel@l", VK_PPC_GOT_TPREL_LO)
349    .Case("got@tprel@h", VK_PPC_GOT_TPREL_HI)
350    .Case("got@tprel@ha", VK_PPC_GOT_TPREL_HA)
351    .Case("got@dtprel", VK_PPC_GOT_DTPREL)
352    .Case("got@dtprel@l", VK_PPC_GOT_DTPREL_LO)
353    .Case("got@dtprel@h", VK_PPC_GOT_DTPREL_HI)
354    .Case("got@dtprel@ha", VK_PPC_GOT_DTPREL_HA)
355    .Case("got@tlsgd", VK_PPC_GOT_TLSGD)
356    .Case("got@tlsgd@l", VK_PPC_GOT_TLSGD_LO)
357    .Case("got@tlsgd@h", VK_PPC_GOT_TLSGD_HI)
358    .Case("got@tlsgd@ha", VK_PPC_GOT_TLSGD_HA)
359    .Case("got@tlsld", VK_PPC_GOT_TLSLD)
360    .Case("got@tlsld@l", VK_PPC_GOT_TLSLD_LO)
361    .Case("got@tlsld@h", VK_PPC_GOT_TLSLD_HI)
362    .Case("got@tlsld@ha", VK_PPC_GOT_TLSLD_HA)
363    .Case("gdgot", VK_Hexagon_GD_GOT)
364    .Case("gdplt", VK_Hexagon_GD_PLT)
365    .Case("iegot", VK_Hexagon_IE_GOT)
366    .Case("ie", VK_Hexagon_IE)
367    .Case("ldgot", VK_Hexagon_LD_GOT)
368    .Case("ldplt", VK_Hexagon_LD_PLT)
369    .Case("pcrel", VK_Hexagon_PCREL)
370    .Case("none", VK_ARM_NONE)
371    .Case("got_prel", VK_ARM_GOT_PREL)
372    .Case("target1", VK_ARM_TARGET1)
373    .Case("target2", VK_ARM_TARGET2)
374    .Case("prel31", VK_ARM_PREL31)
375    .Case("sbrel", VK_ARM_SBREL)
376    .Case("tlsldo", VK_ARM_TLSLDO)
377    .Default(VK_Invalid);
378}
379
380void MCSymbolRefExpr::printVariantKind(raw_ostream &OS) const {
381  if (UseParensForSymbolVariant)
382    OS << '(' << MCSymbolRefExpr::getVariantKindName(getKind()) << ')';
383  else
384    OS << '@' << MCSymbolRefExpr::getVariantKindName(getKind());
385}
386
387/* *** */
388
389void MCTargetExpr::anchor() {}
390
391/* *** */
392
393bool MCExpr::evaluateAsAbsolute(int64_t &Res) const {
394  return evaluateAsAbsolute(Res, nullptr, nullptr, nullptr);
395}
396
397bool MCExpr::evaluateAsAbsolute(int64_t &Res,
398                                const MCAsmLayout &Layout) const {
399  return evaluateAsAbsolute(Res, &Layout.getAssembler(), &Layout, nullptr);
400}
401
402bool MCExpr::evaluateAsAbsolute(int64_t &Res,
403                                const MCAsmLayout &Layout,
404                                const SectionAddrMap &Addrs) const {
405  return evaluateAsAbsolute(Res, &Layout.getAssembler(), &Layout, &Addrs);
406}
407
408bool MCExpr::evaluateAsAbsolute(int64_t &Res, const MCAssembler &Asm) const {
409  return evaluateAsAbsolute(Res, &Asm, nullptr, nullptr);
410}
411
412bool MCExpr::evaluateKnownAbsolute(int64_t &Res,
413                                   const MCAsmLayout &Layout) const {
414  return evaluateAsAbsolute(Res, &Layout.getAssembler(), &Layout, nullptr,
415                            true);
416}
417
418bool MCExpr::evaluateAsAbsolute(int64_t &Res, const MCAssembler *Asm,
419                                const MCAsmLayout *Layout,
420                                const SectionAddrMap *Addrs) const {
421  // FIXME: The use if InSet = Addrs is a hack. Setting InSet causes us
422  // absolutize differences across sections and that is what the MachO writer
423  // uses Addrs for.
424  return evaluateAsAbsolute(Res, Asm, Layout, Addrs, Addrs);
425}
426
427bool MCExpr::evaluateAsAbsolute(int64_t &Res, const MCAssembler *Asm,
428                                const MCAsmLayout *Layout,
429                                const SectionAddrMap *Addrs, bool InSet) const {
430  MCValue Value;
431
432  // Fast path constants.
433  if (const MCConstantExpr *CE = dyn_cast<MCConstantExpr>(this)) {
434    Res = CE->getValue();
435    return true;
436  }
437
438  bool IsRelocatable =
439      evaluateAsRelocatableImpl(Value, Asm, Layout, nullptr, Addrs, InSet);
440
441  // Record the current value.
442  Res = Value.getConstant();
443
444  return IsRelocatable && Value.isAbsolute();
445}
446
447/// \brief Helper method for \see EvaluateSymbolAdd().
448static void AttemptToFoldSymbolOffsetDifference(
449    const MCAssembler *Asm, const MCAsmLayout *Layout,
450    const SectionAddrMap *Addrs, bool InSet, const MCSymbolRefExpr *&A,
451    const MCSymbolRefExpr *&B, int64_t &Addend) {
452  if (!A || !B)
453    return;
454
455  const MCSymbol &SA = A->getSymbol();
456  const MCSymbol &SB = B->getSymbol();
457
458  if (SA.isUndefined() || SB.isUndefined())
459    return;
460
461  if (!Asm->getWriter().isSymbolRefDifferenceFullyResolved(*Asm, A, B, InSet))
462    return;
463
464  if (SA.getFragment() == SB.getFragment() && !SA.isVariable() &&
465      !SB.isVariable()) {
466    Addend += (SA.getOffset() - SB.getOffset());
467
468    // Pointers to Thumb symbols need to have their low-bit set to allow
469    // for interworking.
470    if (Asm->isThumbFunc(&SA))
471      Addend |= 1;
472
473    // Clear the symbol expr pointers to indicate we have folded these
474    // operands.
475    A = B = nullptr;
476    return;
477  }
478
479  if (!Layout)
480    return;
481
482  const MCSection &SecA = *SA.getFragment()->getParent();
483  const MCSection &SecB = *SB.getFragment()->getParent();
484
485  if ((&SecA != &SecB) && !Addrs)
486    return;
487
488  // Eagerly evaluate.
489  Addend += Layout->getSymbolOffset(A->getSymbol()) -
490            Layout->getSymbolOffset(B->getSymbol());
491  if (Addrs && (&SecA != &SecB))
492    Addend += (Addrs->lookup(&SecA) - Addrs->lookup(&SecB));
493
494  // Pointers to Thumb symbols need to have their low-bit set to allow
495  // for interworking.
496  if (Asm->isThumbFunc(&SA))
497    Addend |= 1;
498
499  // Clear the symbol expr pointers to indicate we have folded these
500  // operands.
501  A = B = nullptr;
502}
503
504/// \brief Evaluate the result of an add between (conceptually) two MCValues.
505///
506/// This routine conceptually attempts to construct an MCValue:
507///   Result = (Result_A - Result_B + Result_Cst)
508/// from two MCValue's LHS and RHS where
509///   Result = LHS + RHS
510/// and
511///   Result = (LHS_A - LHS_B + LHS_Cst) + (RHS_A - RHS_B + RHS_Cst).
512///
513/// This routine attempts to aggresively fold the operands such that the result
514/// is representable in an MCValue, but may not always succeed.
515///
516/// \returns True on success, false if the result is not representable in an
517/// MCValue.
518
519/// NOTE: It is really important to have both the Asm and Layout arguments.
520/// They might look redundant, but this function can be used before layout
521/// is done (see the object streamer for example) and having the Asm argument
522/// lets us avoid relaxations early.
523static bool
524EvaluateSymbolicAdd(const MCAssembler *Asm, const MCAsmLayout *Layout,
525                    const SectionAddrMap *Addrs, bool InSet, const MCValue &LHS,
526                    const MCSymbolRefExpr *RHS_A, const MCSymbolRefExpr *RHS_B,
527                    int64_t RHS_Cst, MCValue &Res) {
528  // FIXME: This routine (and other evaluation parts) are *incredibly* sloppy
529  // about dealing with modifiers. This will ultimately bite us, one day.
530  const MCSymbolRefExpr *LHS_A = LHS.getSymA();
531  const MCSymbolRefExpr *LHS_B = LHS.getSymB();
532  int64_t LHS_Cst = LHS.getConstant();
533
534  // Fold the result constant immediately.
535  int64_t Result_Cst = LHS_Cst + RHS_Cst;
536
537  assert((!Layout || Asm) &&
538         "Must have an assembler object if layout is given!");
539
540  // If we have a layout, we can fold resolved differences.
541  if (Asm) {
542    // First, fold out any differences which are fully resolved. By
543    // reassociating terms in
544    //   Result = (LHS_A - LHS_B + LHS_Cst) + (RHS_A - RHS_B + RHS_Cst).
545    // we have the four possible differences:
546    //   (LHS_A - LHS_B),
547    //   (LHS_A - RHS_B),
548    //   (RHS_A - LHS_B),
549    //   (RHS_A - RHS_B).
550    // Since we are attempting to be as aggressive as possible about folding, we
551    // attempt to evaluate each possible alternative.
552    AttemptToFoldSymbolOffsetDifference(Asm, Layout, Addrs, InSet, LHS_A, LHS_B,
553                                        Result_Cst);
554    AttemptToFoldSymbolOffsetDifference(Asm, Layout, Addrs, InSet, LHS_A, RHS_B,
555                                        Result_Cst);
556    AttemptToFoldSymbolOffsetDifference(Asm, Layout, Addrs, InSet, RHS_A, LHS_B,
557                                        Result_Cst);
558    AttemptToFoldSymbolOffsetDifference(Asm, Layout, Addrs, InSet, RHS_A, RHS_B,
559                                        Result_Cst);
560  }
561
562  // We can't represent the addition or subtraction of two symbols.
563  if ((LHS_A && RHS_A) || (LHS_B && RHS_B))
564    return false;
565
566  // At this point, we have at most one additive symbol and one subtractive
567  // symbol -- find them.
568  const MCSymbolRefExpr *A = LHS_A ? LHS_A : RHS_A;
569  const MCSymbolRefExpr *B = LHS_B ? LHS_B : RHS_B;
570
571  Res = MCValue::get(A, B, Result_Cst);
572  return true;
573}
574
575bool MCExpr::evaluateAsRelocatable(MCValue &Res,
576                                   const MCAsmLayout *Layout,
577                                   const MCFixup *Fixup) const {
578  MCAssembler *Assembler = Layout ? &Layout->getAssembler() : nullptr;
579  return evaluateAsRelocatableImpl(Res, Assembler, Layout, Fixup, nullptr,
580                                   false);
581}
582
583bool MCExpr::evaluateAsValue(MCValue &Res, const MCAsmLayout &Layout) const {
584  MCAssembler *Assembler = &Layout.getAssembler();
585  return evaluateAsRelocatableImpl(Res, Assembler, &Layout, nullptr, nullptr,
586                                   true);
587}
588
589static bool canExpand(const MCSymbol &Sym, bool InSet) {
590  const MCExpr *Expr = Sym.getVariableValue();
591  const auto *Inner = dyn_cast<MCSymbolRefExpr>(Expr);
592  if (Inner) {
593    if (Inner->getKind() == MCSymbolRefExpr::VK_WEAKREF)
594      return false;
595  }
596
597  if (InSet)
598    return true;
599  return !Sym.isInSection();
600}
601
602bool MCExpr::evaluateAsRelocatableImpl(MCValue &Res, const MCAssembler *Asm,
603                                       const MCAsmLayout *Layout,
604                                       const MCFixup *Fixup,
605                                       const SectionAddrMap *Addrs,
606                                       bool InSet) const {
607  ++stats::MCExprEvaluate;
608
609  switch (getKind()) {
610  case Target:
611    return cast<MCTargetExpr>(this)->evaluateAsRelocatableImpl(Res, Layout,
612                                                               Fixup);
613
614  case Constant:
615    Res = MCValue::get(cast<MCConstantExpr>(this)->getValue());
616    return true;
617
618  case SymbolRef: {
619    const MCSymbolRefExpr *SRE = cast<MCSymbolRefExpr>(this);
620    const MCSymbol &Sym = SRE->getSymbol();
621
622    // Evaluate recursively if this is a variable.
623    if (Sym.isVariable() && SRE->getKind() == MCSymbolRefExpr::VK_None &&
624        canExpand(Sym, InSet)) {
625      bool IsMachO = SRE->hasSubsectionsViaSymbols();
626      if (Sym.getVariableValue()->evaluateAsRelocatableImpl(
627              Res, Asm, Layout, Fixup, Addrs, InSet || IsMachO)) {
628        if (!IsMachO)
629          return true;
630
631        const MCSymbolRefExpr *A = Res.getSymA();
632        const MCSymbolRefExpr *B = Res.getSymB();
633        // FIXME: This is small hack. Given
634        // a = b + 4
635        // .long a
636        // the OS X assembler will completely drop the 4. We should probably
637        // include it in the relocation or produce an error if that is not
638        // possible.
639        if (!A && !B)
640          return true;
641      }
642    }
643
644    Res = MCValue::get(SRE, nullptr, 0);
645    return true;
646  }
647
648  case Unary: {
649    const MCUnaryExpr *AUE = cast<MCUnaryExpr>(this);
650    MCValue Value;
651
652    if (!AUE->getSubExpr()->evaluateAsRelocatableImpl(Value, Asm, Layout, Fixup,
653                                                      Addrs, InSet))
654      return false;
655
656    switch (AUE->getOpcode()) {
657    case MCUnaryExpr::LNot:
658      if (!Value.isAbsolute())
659        return false;
660      Res = MCValue::get(!Value.getConstant());
661      break;
662    case MCUnaryExpr::Minus:
663      /// -(a - b + const) ==> (b - a - const)
664      if (Value.getSymA() && !Value.getSymB())
665        return false;
666
667      // The cast avoids undefined behavior if the constant is INT64_MIN.
668      Res = MCValue::get(Value.getSymB(), Value.getSymA(),
669                         -(uint64_t)Value.getConstant());
670      break;
671    case MCUnaryExpr::Not:
672      if (!Value.isAbsolute())
673        return false;
674      Res = MCValue::get(~Value.getConstant());
675      break;
676    case MCUnaryExpr::Plus:
677      Res = Value;
678      break;
679    }
680
681    return true;
682  }
683
684  case Binary: {
685    const MCBinaryExpr *ABE = cast<MCBinaryExpr>(this);
686    MCValue LHSValue, RHSValue;
687
688    if (!ABE->getLHS()->evaluateAsRelocatableImpl(LHSValue, Asm, Layout, Fixup,
689                                                  Addrs, InSet) ||
690        !ABE->getRHS()->evaluateAsRelocatableImpl(RHSValue, Asm, Layout, Fixup,
691                                                  Addrs, InSet))
692      return false;
693
694    // We only support a few operations on non-constant expressions, handle
695    // those first.
696    if (!LHSValue.isAbsolute() || !RHSValue.isAbsolute()) {
697      switch (ABE->getOpcode()) {
698      default:
699        return false;
700      case MCBinaryExpr::Sub:
701        // Negate RHS and add.
702        // The cast avoids undefined behavior if the constant is INT64_MIN.
703        return EvaluateSymbolicAdd(Asm, Layout, Addrs, InSet, LHSValue,
704                                   RHSValue.getSymB(), RHSValue.getSymA(),
705                                   -(uint64_t)RHSValue.getConstant(), Res);
706
707      case MCBinaryExpr::Add:
708        return EvaluateSymbolicAdd(Asm, Layout, Addrs, InSet, LHSValue,
709                                   RHSValue.getSymA(), RHSValue.getSymB(),
710                                   RHSValue.getConstant(), Res);
711      }
712    }
713
714    // FIXME: We need target hooks for the evaluation. It may be limited in
715    // width, and gas defines the result of comparisons differently from
716    // Apple as.
717    int64_t LHS = LHSValue.getConstant(), RHS = RHSValue.getConstant();
718    int64_t Result = 0;
719    switch (ABE->getOpcode()) {
720    case MCBinaryExpr::AShr: Result = LHS >> RHS; break;
721    case MCBinaryExpr::Add:  Result = LHS + RHS; break;
722    case MCBinaryExpr::And:  Result = LHS & RHS; break;
723    case MCBinaryExpr::Div:
724      // Handle division by zero. gas just emits a warning and keeps going,
725      // we try to be stricter.
726      // FIXME: Currently the caller of this function has no way to understand
727      // we're bailing out because of 'division by zero'. Therefore, it will
728      // emit a 'expected relocatable expression' error. It would be nice to
729      // change this code to emit a better diagnostic.
730      if (RHS == 0)
731        return false;
732      Result = LHS / RHS;
733      break;
734    case MCBinaryExpr::EQ:   Result = LHS == RHS; break;
735    case MCBinaryExpr::GT:   Result = LHS > RHS; break;
736    case MCBinaryExpr::GTE:  Result = LHS >= RHS; break;
737    case MCBinaryExpr::LAnd: Result = LHS && RHS; break;
738    case MCBinaryExpr::LOr:  Result = LHS || RHS; break;
739    case MCBinaryExpr::LShr: Result = uint64_t(LHS) >> uint64_t(RHS); break;
740    case MCBinaryExpr::LT:   Result = LHS < RHS; break;
741    case MCBinaryExpr::LTE:  Result = LHS <= RHS; break;
742    case MCBinaryExpr::Mod:  Result = LHS % RHS; break;
743    case MCBinaryExpr::Mul:  Result = LHS * RHS; break;
744    case MCBinaryExpr::NE:   Result = LHS != RHS; break;
745    case MCBinaryExpr::Or:   Result = LHS | RHS; break;
746    case MCBinaryExpr::Shl:  Result = uint64_t(LHS) << uint64_t(RHS); break;
747    case MCBinaryExpr::Sub:  Result = LHS - RHS; break;
748    case MCBinaryExpr::Xor:  Result = LHS ^ RHS; break;
749    }
750
751    Res = MCValue::get(Result);
752    return true;
753  }
754  }
755
756  llvm_unreachable("Invalid assembly expression kind!");
757}
758
759MCFragment *MCExpr::findAssociatedFragment() const {
760  switch (getKind()) {
761  case Target:
762    // We never look through target specific expressions.
763    return cast<MCTargetExpr>(this)->findAssociatedFragment();
764
765  case Constant:
766    return MCSymbol::AbsolutePseudoFragment;
767
768  case SymbolRef: {
769    const MCSymbolRefExpr *SRE = cast<MCSymbolRefExpr>(this);
770    const MCSymbol &Sym = SRE->getSymbol();
771    return Sym.getFragment();
772  }
773
774  case Unary:
775    return cast<MCUnaryExpr>(this)->getSubExpr()->findAssociatedFragment();
776
777  case Binary: {
778    const MCBinaryExpr *BE = cast<MCBinaryExpr>(this);
779    MCFragment *LHS_F = BE->getLHS()->findAssociatedFragment();
780    MCFragment *RHS_F = BE->getRHS()->findAssociatedFragment();
781
782    // If either is absolute, return the other.
783    if (LHS_F == MCSymbol::AbsolutePseudoFragment)
784      return RHS_F;
785    if (RHS_F == MCSymbol::AbsolutePseudoFragment)
786      return LHS_F;
787
788    // Not always correct, but probably the best we can do without more context.
789    if (BE->getOpcode() == MCBinaryExpr::Sub)
790      return MCSymbol::AbsolutePseudoFragment;
791
792    // Otherwise, return the first non-null fragment.
793    return LHS_F ? LHS_F : RHS_F;
794  }
795  }
796
797  llvm_unreachable("Invalid assembly expression kind!");
798}
799