1 //===- MCExpr.cpp - Assembly Level Expression Implementation --------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #define DEBUG_TYPE "mcexpr"
11 #include "llvm/MC/MCExpr.h"
12 #include "llvm/ADT/Statistic.h"
13 #include "llvm/ADT/StringSwitch.h"
14 #include "llvm/MC/MCAsmLayout.h"
15 #include "llvm/MC/MCAssembler.h"
16 #include "llvm/MC/MCContext.h"
17 #include "llvm/MC/MCSymbol.h"
18 #include "llvm/MC/MCValue.h"
19 #include "llvm/Support/Debug.h"
20 #include "llvm/Support/raw_ostream.h"
21 #include "llvm/Target/TargetAsmBackend.h"
26 STATISTIC(MCExprEvaluate
, "Number of MCExpr evaluations");
30 void MCExpr::print(raw_ostream
&OS
) const {
33 return cast
<MCTargetExpr
>(this)->PrintImpl(OS
);
34 case MCExpr::Constant
:
35 OS
<< cast
<MCConstantExpr
>(*this).getValue();
38 case MCExpr::SymbolRef
: {
39 const MCSymbolRefExpr
&SRE
= cast
<MCSymbolRefExpr
>(*this);
40 const MCSymbol
&Sym
= SRE
.getSymbol();
41 // Parenthesize names that start with $ so that they don't look like
43 bool UseParens
= Sym
.getName()[0] == '$';
45 if (SRE
.getKind() == MCSymbolRefExpr::VK_PPC_DARWIN_HA16
||
46 SRE
.getKind() == MCSymbolRefExpr::VK_PPC_DARWIN_LO16
) {
47 OS
<< MCSymbolRefExpr::getVariantKindName(SRE
.getKind());
52 OS
<< '(' << Sym
<< ')';
56 if (SRE
.getKind() == MCSymbolRefExpr::VK_ARM_PLT
||
57 SRE
.getKind() == MCSymbolRefExpr::VK_ARM_TLSGD
||
58 SRE
.getKind() == MCSymbolRefExpr::VK_ARM_GOT
||
59 SRE
.getKind() == MCSymbolRefExpr::VK_ARM_GOTOFF
||
60 SRE
.getKind() == MCSymbolRefExpr::VK_ARM_TPOFF
||
61 SRE
.getKind() == MCSymbolRefExpr::VK_ARM_GOTTPOFF
)
62 OS
<< MCSymbolRefExpr::getVariantKindName(SRE
.getKind());
63 else if (SRE
.getKind() != MCSymbolRefExpr::VK_None
&&
64 SRE
.getKind() != MCSymbolRefExpr::VK_PPC_DARWIN_HA16
&&
65 SRE
.getKind() != MCSymbolRefExpr::VK_PPC_DARWIN_LO16
)
66 OS
<< '@' << MCSymbolRefExpr::getVariantKindName(SRE
.getKind());
72 const MCUnaryExpr
&UE
= cast
<MCUnaryExpr
>(*this);
73 switch (UE
.getOpcode()) {
74 default: assert(0 && "Invalid opcode!");
75 case MCUnaryExpr::LNot
: OS
<< '!'; break;
76 case MCUnaryExpr::Minus
: OS
<< '-'; break;
77 case MCUnaryExpr::Not
: OS
<< '~'; break;
78 case MCUnaryExpr::Plus
: OS
<< '+'; break;
80 OS
<< *UE
.getSubExpr();
84 case MCExpr::Binary
: {
85 const MCBinaryExpr
&BE
= cast
<MCBinaryExpr
>(*this);
87 // Only print parens around the LHS if it is non-trivial.
88 if (isa
<MCConstantExpr
>(BE
.getLHS()) || isa
<MCSymbolRefExpr
>(BE
.getLHS())) {
91 OS
<< '(' << *BE
.getLHS() << ')';
94 switch (BE
.getOpcode()) {
95 default: assert(0 && "Invalid opcode!");
96 case MCBinaryExpr::Add
:
97 // Print "X-42" instead of "X+-42".
98 if (const MCConstantExpr
*RHSC
= dyn_cast
<MCConstantExpr
>(BE
.getRHS())) {
99 if (RHSC
->getValue() < 0) {
100 OS
<< RHSC
->getValue();
107 case MCBinaryExpr::And
: OS
<< '&'; break;
108 case MCBinaryExpr::Div
: OS
<< '/'; break;
109 case MCBinaryExpr::EQ
: OS
<< "=="; break;
110 case MCBinaryExpr::GT
: OS
<< '>'; break;
111 case MCBinaryExpr::GTE
: OS
<< ">="; break;
112 case MCBinaryExpr::LAnd
: OS
<< "&&"; break;
113 case MCBinaryExpr::LOr
: OS
<< "||"; break;
114 case MCBinaryExpr::LT
: OS
<< '<'; break;
115 case MCBinaryExpr::LTE
: OS
<< "<="; break;
116 case MCBinaryExpr::Mod
: OS
<< '%'; break;
117 case MCBinaryExpr::Mul
: OS
<< '*'; break;
118 case MCBinaryExpr::NE
: OS
<< "!="; break;
119 case MCBinaryExpr::Or
: OS
<< '|'; break;
120 case MCBinaryExpr::Shl
: OS
<< "<<"; break;
121 case MCBinaryExpr::Shr
: OS
<< ">>"; break;
122 case MCBinaryExpr::Sub
: OS
<< '-'; break;
123 case MCBinaryExpr::Xor
: OS
<< '^'; break;
126 // Only print parens around the LHS if it is non-trivial.
127 if (isa
<MCConstantExpr
>(BE
.getRHS()) || isa
<MCSymbolRefExpr
>(BE
.getRHS())) {
130 OS
<< '(' << *BE
.getRHS() << ')';
136 assert(0 && "Invalid expression kind!");
139 void MCExpr::dump() const {
146 const MCBinaryExpr
*MCBinaryExpr::Create(Opcode Opc
, const MCExpr
*LHS
,
147 const MCExpr
*RHS
, MCContext
&Ctx
) {
148 return new (Ctx
) MCBinaryExpr(Opc
, LHS
, RHS
);
151 const MCUnaryExpr
*MCUnaryExpr::Create(Opcode Opc
, const MCExpr
*Expr
,
153 return new (Ctx
) MCUnaryExpr(Opc
, Expr
);
156 const MCConstantExpr
*MCConstantExpr::Create(int64_t Value
, MCContext
&Ctx
) {
157 return new (Ctx
) MCConstantExpr(Value
);
162 const MCSymbolRefExpr
*MCSymbolRefExpr::Create(const MCSymbol
*Sym
,
165 return new (Ctx
) MCSymbolRefExpr(Sym
, Kind
);
168 const MCSymbolRefExpr
*MCSymbolRefExpr::Create(StringRef Name
, VariantKind Kind
,
170 return Create(Ctx
.GetOrCreateSymbol(Name
), Kind
, Ctx
);
173 StringRef
MCSymbolRefExpr::getVariantKindName(VariantKind Kind
) {
176 case VK_Invalid
: return "<<invalid>>";
177 case VK_None
: return "<<none>>";
179 case VK_GOT
: return "GOT";
180 case VK_GOTOFF
: return "GOTOFF";
181 case VK_GOTPCREL
: return "GOTPCREL";
182 case VK_GOTTPOFF
: return "GOTTPOFF";
183 case VK_INDNTPOFF
: return "INDNTPOFF";
184 case VK_NTPOFF
: return "NTPOFF";
185 case VK_GOTNTPOFF
: return "GOTNTPOFF";
186 case VK_PLT
: return "PLT";
187 case VK_TLSGD
: return "TLSGD";
188 case VK_TLSLD
: return "TLSLD";
189 case VK_TLSLDM
: return "TLSLDM";
190 case VK_TPOFF
: return "TPOFF";
191 case VK_DTPOFF
: return "DTPOFF";
192 case VK_TLVP
: return "TLVP";
193 case VK_ARM_PLT
: return "(PLT)";
194 case VK_ARM_GOT
: return "(GOT)";
195 case VK_ARM_GOTOFF
: return "(GOTOFF)";
196 case VK_ARM_TPOFF
: return "(tpoff)";
197 case VK_ARM_GOTTPOFF
: return "(gottpoff)";
198 case VK_ARM_TLSGD
: return "(tlsgd)";
199 case VK_PPC_TOC
: return "toc";
200 case VK_PPC_DARWIN_HA16
: return "ha16";
201 case VK_PPC_DARWIN_LO16
: return "lo16";
202 case VK_PPC_GAS_HA16
: return "ha";
203 case VK_PPC_GAS_LO16
: return "l";
207 MCSymbolRefExpr::VariantKind
208 MCSymbolRefExpr::getVariantKindForName(StringRef Name
) {
209 return StringSwitch
<VariantKind
>(Name
)
212 .Case("GOTOFF", VK_GOTOFF
)
213 .Case("gotoff", VK_GOTOFF
)
214 .Case("GOTPCREL", VK_GOTPCREL
)
215 .Case("gotpcrel", VK_GOTPCREL
)
216 .Case("GOTTPOFF", VK_GOTTPOFF
)
217 .Case("gottpoff", VK_GOTTPOFF
)
218 .Case("INDNTPOFF", VK_INDNTPOFF
)
219 .Case("indntpoff", VK_INDNTPOFF
)
220 .Case("NTPOFF", VK_NTPOFF
)
221 .Case("ntpoff", VK_NTPOFF
)
222 .Case("GOTNTPOFF", VK_GOTNTPOFF
)
223 .Case("gotntpoff", VK_GOTNTPOFF
)
226 .Case("TLSGD", VK_TLSGD
)
227 .Case("tlsgd", VK_TLSGD
)
228 .Case("TLSLD", VK_TLSLD
)
229 .Case("tlsld", VK_TLSLD
)
230 .Case("TLSLDM", VK_TLSLDM
)
231 .Case("tlsldm", VK_TLSLDM
)
232 .Case("TPOFF", VK_TPOFF
)
233 .Case("tpoff", VK_TPOFF
)
234 .Case("DTPOFF", VK_DTPOFF
)
235 .Case("dtpoff", VK_DTPOFF
)
236 .Case("TLVP", VK_TLVP
)
237 .Case("tlvp", VK_TLVP
)
238 .Default(VK_Invalid
);
243 void MCTargetExpr::Anchor() {}
247 bool MCExpr::EvaluateAsAbsolute(int64_t &Res
) const {
248 return EvaluateAsAbsolute(Res
, 0, 0, 0);
251 bool MCExpr::EvaluateAsAbsolute(int64_t &Res
,
252 const MCAsmLayout
&Layout
) const {
253 return EvaluateAsAbsolute(Res
, &Layout
.getAssembler(), &Layout
, 0);
256 bool MCExpr::EvaluateAsAbsolute(int64_t &Res
,
257 const MCAsmLayout
&Layout
,
258 const SectionAddrMap
&Addrs
) const {
259 return EvaluateAsAbsolute(Res
, &Layout
.getAssembler(), &Layout
, &Addrs
);
262 bool MCExpr::EvaluateAsAbsolute(int64_t &Res
, const MCAssembler
&Asm
) const {
263 return EvaluateAsAbsolute(Res
, &Asm
, 0, 0);
266 bool MCExpr::EvaluateAsAbsolute(int64_t &Res
, const MCAssembler
*Asm
,
267 const MCAsmLayout
*Layout
,
268 const SectionAddrMap
*Addrs
) const {
271 // Fast path constants.
272 if (const MCConstantExpr
*CE
= dyn_cast
<MCConstantExpr
>(this)) {
273 Res
= CE
->getValue();
277 // FIXME: The use if InSet = Addrs is a hack. Setting InSet causes us
278 // absolutize differences across sections and that is what the MachO writer
281 EvaluateAsRelocatableImpl(Value
, Asm
, Layout
, Addrs
, /*InSet*/ Addrs
);
283 // Record the current value.
284 Res
= Value
.getConstant();
286 return IsRelocatable
&& Value
.isAbsolute();
289 /// \brief Helper method for \see EvaluateSymbolAdd().
290 static void AttemptToFoldSymbolOffsetDifference(const MCAssembler
*Asm
,
291 const MCAsmLayout
*Layout
,
292 const SectionAddrMap
*Addrs
,
294 const MCSymbolRefExpr
*&A
,
295 const MCSymbolRefExpr
*&B
,
300 const MCSymbol
&SA
= A
->getSymbol();
301 const MCSymbol
&SB
= B
->getSymbol();
303 if (SA
.isUndefined() || SB
.isUndefined())
306 if (!Asm
->getWriter().IsSymbolRefDifferenceFullyResolved(*Asm
, A
, B
, InSet
))
309 MCSymbolData
&AD
= Asm
->getSymbolData(SA
);
310 MCSymbolData
&BD
= Asm
->getSymbolData(SB
);
312 if (AD
.getFragment() == BD
.getFragment()) {
313 Addend
+= (AD
.getOffset() - BD
.getOffset());
315 // Pointers to Thumb symbols need to have their low-bit set to allow
317 if (Asm
->isThumbFunc(&SA
))
320 // Clear the symbol expr pointers to indicate we have folded these
329 const MCSectionData
&SecA
= *AD
.getFragment()->getParent();
330 const MCSectionData
&SecB
= *BD
.getFragment()->getParent();
332 if ((&SecA
!= &SecB
) && !Addrs
)
336 Addend
+= (Layout
->getSymbolOffset(&Asm
->getSymbolData(A
->getSymbol())) -
337 Layout
->getSymbolOffset(&Asm
->getSymbolData(B
->getSymbol())));
338 if (Addrs
&& (&SecA
!= &SecB
))
339 Addend
+= (Addrs
->lookup(&SecA
) - Addrs
->lookup(&SecB
));
341 // Clear the symbol expr pointers to indicate we have folded these
346 /// \brief Evaluate the result of an add between (conceptually) two MCValues.
348 /// This routine conceptually attempts to construct an MCValue:
349 /// Result = (Result_A - Result_B + Result_Cst)
350 /// from two MCValue's LHS and RHS where
351 /// Result = LHS + RHS
353 /// Result = (LHS_A - LHS_B + LHS_Cst) + (RHS_A - RHS_B + RHS_Cst).
355 /// This routine attempts to aggresively fold the operands such that the result
356 /// is representable in an MCValue, but may not always succeed.
358 /// \returns True on success, false if the result is not representable in an
361 /// NOTE: It is really important to have both the Asm and Layout arguments.
362 /// They might look redundant, but this function can be used before layout
363 /// is done (see the object streamer for example) and having the Asm argument
364 /// lets us avoid relaxations early.
365 static bool EvaluateSymbolicAdd(const MCAssembler
*Asm
,
366 const MCAsmLayout
*Layout
,
367 const SectionAddrMap
*Addrs
,
369 const MCValue
&LHS
,const MCSymbolRefExpr
*RHS_A
,
370 const MCSymbolRefExpr
*RHS_B
, int64_t RHS_Cst
,
372 // FIXME: This routine (and other evaluation parts) are *incredibly* sloppy
373 // about dealing with modifiers. This will ultimately bite us, one day.
374 const MCSymbolRefExpr
*LHS_A
= LHS
.getSymA();
375 const MCSymbolRefExpr
*LHS_B
= LHS
.getSymB();
376 int64_t LHS_Cst
= LHS
.getConstant();
378 // Fold the result constant immediately.
379 int64_t Result_Cst
= LHS_Cst
+ RHS_Cst
;
381 assert((!Layout
|| Asm
) &&
382 "Must have an assembler object if layout is given!");
384 // If we have a layout, we can fold resolved differences.
386 // First, fold out any differences which are fully resolved. By
387 // reassociating terms in
388 // Result = (LHS_A - LHS_B + LHS_Cst) + (RHS_A - RHS_B + RHS_Cst).
389 // we have the four possible differences:
394 // Since we are attempting to be as aggressive as possible about folding, we
395 // attempt to evaluate each possible alternative.
396 AttemptToFoldSymbolOffsetDifference(Asm
, Layout
, Addrs
, InSet
, LHS_A
, LHS_B
,
398 AttemptToFoldSymbolOffsetDifference(Asm
, Layout
, Addrs
, InSet
, LHS_A
, RHS_B
,
400 AttemptToFoldSymbolOffsetDifference(Asm
, Layout
, Addrs
, InSet
, RHS_A
, LHS_B
,
402 AttemptToFoldSymbolOffsetDifference(Asm
, Layout
, Addrs
, InSet
, RHS_A
, RHS_B
,
406 // We can't represent the addition or subtraction of two symbols.
407 if ((LHS_A
&& RHS_A
) || (LHS_B
&& RHS_B
))
410 // At this point, we have at most one additive symbol and one subtractive
411 // symbol -- find them.
412 const MCSymbolRefExpr
*A
= LHS_A
? LHS_A
: RHS_A
;
413 const MCSymbolRefExpr
*B
= LHS_B
? LHS_B
: RHS_B
;
415 // If we have a negated symbol, then we must have also have a non-negated
416 // symbol in order to encode the expression.
420 Res
= MCValue::get(A
, B
, Result_Cst
);
424 bool MCExpr::EvaluateAsRelocatable(MCValue
&Res
,
425 const MCAsmLayout
&Layout
) const {
426 return EvaluateAsRelocatableImpl(Res
, &Layout
.getAssembler(), &Layout
,
430 bool MCExpr::EvaluateAsRelocatableImpl(MCValue
&Res
,
431 const MCAssembler
*Asm
,
432 const MCAsmLayout
*Layout
,
433 const SectionAddrMap
*Addrs
,
435 ++stats::MCExprEvaluate
;
439 return cast
<MCTargetExpr
>(this)->EvaluateAsRelocatableImpl(Res
, Layout
);
442 Res
= MCValue::get(cast
<MCConstantExpr
>(this)->getValue());
446 const MCSymbolRefExpr
*SRE
= cast
<MCSymbolRefExpr
>(this);
447 const MCSymbol
&Sym
= SRE
->getSymbol();
449 // Evaluate recursively if this is a variable.
450 if (Sym
.isVariable() && SRE
->getKind() == MCSymbolRefExpr::VK_None
) {
451 bool Ret
= Sym
.getVariableValue()->EvaluateAsRelocatableImpl(Res
, Asm
,
455 // If we failed to simplify this to a constant, let the target
457 if (Ret
&& !Res
.getSymA() && !Res
.getSymB())
461 Res
= MCValue::get(SRE
, 0, 0);
466 const MCUnaryExpr
*AUE
= cast
<MCUnaryExpr
>(this);
469 if (!AUE
->getSubExpr()->EvaluateAsRelocatableImpl(Value
, Asm
, Layout
,
473 switch (AUE
->getOpcode()) {
474 case MCUnaryExpr::LNot
:
475 if (!Value
.isAbsolute())
477 Res
= MCValue::get(!Value
.getConstant());
479 case MCUnaryExpr::Minus
:
480 /// -(a - b + const) ==> (b - a - const)
481 if (Value
.getSymA() && !Value
.getSymB())
483 Res
= MCValue::get(Value
.getSymB(), Value
.getSymA(),
484 -Value
.getConstant());
486 case MCUnaryExpr::Not
:
487 if (!Value
.isAbsolute())
489 Res
= MCValue::get(~Value
.getConstant());
491 case MCUnaryExpr::Plus
:
500 const MCBinaryExpr
*ABE
= cast
<MCBinaryExpr
>(this);
501 MCValue LHSValue
, RHSValue
;
503 if (!ABE
->getLHS()->EvaluateAsRelocatableImpl(LHSValue
, Asm
, Layout
,
505 !ABE
->getRHS()->EvaluateAsRelocatableImpl(RHSValue
, Asm
, Layout
,
509 // We only support a few operations on non-constant expressions, handle
511 if (!LHSValue
.isAbsolute() || !RHSValue
.isAbsolute()) {
512 switch (ABE
->getOpcode()) {
515 case MCBinaryExpr::Sub
:
516 // Negate RHS and add.
517 return EvaluateSymbolicAdd(Asm
, Layout
, Addrs
, InSet
, LHSValue
,
518 RHSValue
.getSymB(), RHSValue
.getSymA(),
519 -RHSValue
.getConstant(),
522 case MCBinaryExpr::Add
:
523 return EvaluateSymbolicAdd(Asm
, Layout
, Addrs
, InSet
, LHSValue
,
524 RHSValue
.getSymA(), RHSValue
.getSymB(),
525 RHSValue
.getConstant(),
530 // FIXME: We need target hooks for the evaluation. It may be limited in
531 // width, and gas defines the result of comparisons and right shifts
532 // differently from Apple as.
533 int64_t LHS
= LHSValue
.getConstant(), RHS
= RHSValue
.getConstant();
535 switch (ABE
->getOpcode()) {
536 case MCBinaryExpr::Add
: Result
= LHS
+ RHS
; break;
537 case MCBinaryExpr::And
: Result
= LHS
& RHS
; break;
538 case MCBinaryExpr::Div
: Result
= LHS
/ RHS
; break;
539 case MCBinaryExpr::EQ
: Result
= LHS
== RHS
; break;
540 case MCBinaryExpr::GT
: Result
= LHS
> RHS
; break;
541 case MCBinaryExpr::GTE
: Result
= LHS
>= RHS
; break;
542 case MCBinaryExpr::LAnd
: Result
= LHS
&& RHS
; break;
543 case MCBinaryExpr::LOr
: Result
= LHS
|| RHS
; break;
544 case MCBinaryExpr::LT
: Result
= LHS
< RHS
; break;
545 case MCBinaryExpr::LTE
: Result
= LHS
<= RHS
; break;
546 case MCBinaryExpr::Mod
: Result
= LHS
% RHS
; break;
547 case MCBinaryExpr::Mul
: Result
= LHS
* RHS
; break;
548 case MCBinaryExpr::NE
: Result
= LHS
!= RHS
; break;
549 case MCBinaryExpr::Or
: Result
= LHS
| RHS
; break;
550 case MCBinaryExpr::Shl
: Result
= LHS
<< RHS
; break;
551 case MCBinaryExpr::Shr
: Result
= LHS
>> RHS
; break;
552 case MCBinaryExpr::Sub
: Result
= LHS
- RHS
; break;
553 case MCBinaryExpr::Xor
: Result
= LHS
^ RHS
; break;
556 Res
= MCValue::get(Result
);
561 assert(0 && "Invalid assembly expression kind!");
565 const MCSection
*MCExpr::FindAssociatedSection() const {
568 // We never look through target specific expressions.
569 return cast
<MCTargetExpr
>(this)->FindAssociatedSection();
572 return MCSymbol::AbsolutePseudoSection
;
575 const MCSymbolRefExpr
*SRE
= cast
<MCSymbolRefExpr
>(this);
576 const MCSymbol
&Sym
= SRE
->getSymbol();
579 return &Sym
.getSection();
585 return cast
<MCUnaryExpr
>(this)->getSubExpr()->FindAssociatedSection();
588 const MCBinaryExpr
*BE
= cast
<MCBinaryExpr
>(this);
589 const MCSection
*LHS_S
= BE
->getLHS()->FindAssociatedSection();
590 const MCSection
*RHS_S
= BE
->getRHS()->FindAssociatedSection();
592 // If either section is absolute, return the other.
593 if (LHS_S
== MCSymbol::AbsolutePseudoSection
)
595 if (RHS_S
== MCSymbol::AbsolutePseudoSection
)
598 // Otherwise, return the first non-null section.
599 return LHS_S
? LHS_S
: RHS_S
;
603 assert(0 && "Invalid assembly expression kind!");