X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FMC%2FMCExpr.cpp;h=f3a91cbd5ef7d408b581621c1a486b0f99e022af;hb=d4a19b6a72d19a6f90b676aac37118664b7b7a84;hp=57d02c95f13a87a1f8c82709a79e54aa5a393f4a;hpb=10b318bcb39218d2ed525e4862c854bc8d1baf63;p=oota-llvm.git diff --git a/lib/MC/MCExpr.cpp b/lib/MC/MCExpr.cpp index 57d02c95f13..f3a91cbd5ef 100644 --- a/lib/MC/MCExpr.cpp +++ b/lib/MC/MCExpr.cpp @@ -7,59 +7,91 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "mcexpr" #include "llvm/MC/MCExpr.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/ADT/StringSwitch.h" +#include "llvm/MC/MCAsmLayout.h" +#include "llvm/MC/MCAssembler.h" #include "llvm/MC/MCContext.h" #include "llvm/MC/MCSymbol.h" #include "llvm/MC/MCValue.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; -void MCExpr::print(raw_ostream &OS, const MCAsmInfo *MAI) const { +namespace { +namespace stats { +STATISTIC(MCExprEvaluate, "Number of MCExpr evaluations"); +} +} + +void MCExpr::print(raw_ostream &OS) const { switch (getKind()) { + case MCExpr::Target: + return cast(this)->PrintImpl(OS); case MCExpr::Constant: OS << cast(*this).getValue(); return; case MCExpr::SymbolRef: { - const MCSymbol &Sym = cast(*this).getSymbol(); - + const MCSymbolRefExpr &SRE = cast(*this); + const MCSymbol &Sym = SRE.getSymbol(); // Parenthesize names that start with $ so that they don't look like // absolute names. - if (Sym.getName()[0] == '$') + bool UseParens = Sym.getName()[0] == '$'; + + if (SRE.getKind() == MCSymbolRefExpr::VK_PPC_DARWIN_HA16 || + SRE.getKind() == MCSymbolRefExpr::VK_PPC_DARWIN_LO16) { + OS << MCSymbolRefExpr::getVariantKindName(SRE.getKind()); + UseParens = true; + } + + if (UseParens) OS << '(' << Sym << ')'; else OS << Sym; + + if (SRE.getKind() == MCSymbolRefExpr::VK_ARM_PLT || + SRE.getKind() == MCSymbolRefExpr::VK_ARM_TLSGD || + SRE.getKind() == MCSymbolRefExpr::VK_ARM_GOT || + SRE.getKind() == MCSymbolRefExpr::VK_ARM_GOTOFF || + SRE.getKind() == MCSymbolRefExpr::VK_ARM_TPOFF || + SRE.getKind() == MCSymbolRefExpr::VK_ARM_GOTTPOFF || + SRE.getKind() == MCSymbolRefExpr::VK_ARM_TARGET1) + OS << MCSymbolRefExpr::getVariantKindName(SRE.getKind()); + else if (SRE.getKind() != MCSymbolRefExpr::VK_None && + SRE.getKind() != MCSymbolRefExpr::VK_PPC_DARWIN_HA16 && + SRE.getKind() != MCSymbolRefExpr::VK_PPC_DARWIN_LO16) + OS << '@' << MCSymbolRefExpr::getVariantKindName(SRE.getKind()); + return; } case MCExpr::Unary: { const MCUnaryExpr &UE = cast(*this); switch (UE.getOpcode()) { - default: assert(0 && "Invalid opcode!"); case MCUnaryExpr::LNot: OS << '!'; break; case MCUnaryExpr::Minus: OS << '-'; break; case MCUnaryExpr::Not: OS << '~'; break; case MCUnaryExpr::Plus: OS << '+'; break; } - UE.getSubExpr()->print(OS, MAI); + OS << *UE.getSubExpr(); return; } case MCExpr::Binary: { const MCBinaryExpr &BE = cast(*this); - + // Only print parens around the LHS if it is non-trivial. if (isa(BE.getLHS()) || isa(BE.getLHS())) { - BE.getLHS()->print(OS, MAI); + OS << *BE.getLHS(); } else { - OS << '('; - BE.getLHS()->print(OS, MAI); - OS << ')'; + OS << '(' << *BE.getLHS() << ')'; } - + switch (BE.getOpcode()) { - default: assert(0 && "Invalid opcode!"); case MCBinaryExpr::Add: // Print "X-42" instead of "X+-42". if (const MCConstantExpr *RHSC = dyn_cast(BE.getRHS())) { @@ -68,7 +100,7 @@ void MCExpr::print(raw_ostream &OS, const MCAsmInfo *MAI) const { return; } } - + OS << '+'; break; case MCBinaryExpr::And: OS << '&'; break; @@ -89,24 +121,22 @@ void MCExpr::print(raw_ostream &OS, const MCAsmInfo *MAI) const { case MCBinaryExpr::Sub: OS << '-'; break; case MCBinaryExpr::Xor: OS << '^'; break; } - + // Only print parens around the LHS if it is non-trivial. if (isa(BE.getRHS()) || isa(BE.getRHS())) { - BE.getRHS()->print(OS, MAI); + OS << *BE.getRHS(); } else { - OS << '('; - BE.getRHS()->print(OS, MAI); - OS << ')'; + OS << '(' << *BE.getRHS() << ')'; } return; } } - assert(0 && "Invalid expression kind!"); + llvm_unreachable("Invalid expression kind!"); } void MCExpr::dump() const { - print(dbgs(), 0); + print(dbgs()); dbgs() << '\n'; } @@ -126,64 +156,328 @@ const MCConstantExpr *MCConstantExpr::Create(int64_t Value, MCContext &Ctx) { return new (Ctx) MCConstantExpr(Value); } +/* *** */ + const MCSymbolRefExpr *MCSymbolRefExpr::Create(const MCSymbol *Sym, + VariantKind Kind, MCContext &Ctx) { - return new (Ctx) MCSymbolRefExpr(Sym); + return new (Ctx) MCSymbolRefExpr(Sym, Kind); } -const MCSymbolRefExpr *MCSymbolRefExpr::Create(StringRef Name, MCContext &Ctx) { - return Create(Ctx.GetOrCreateSymbol(Name), Ctx); +const MCSymbolRefExpr *MCSymbolRefExpr::Create(StringRef Name, VariantKind Kind, + MCContext &Ctx) { + return Create(Ctx.GetOrCreateSymbol(Name), Kind, Ctx); } +StringRef MCSymbolRefExpr::getVariantKindName(VariantKind Kind) { + switch (Kind) { + case VK_Invalid: return "<>"; + case VK_None: return "<>"; + + case VK_GOT: return "GOT"; + case VK_GOTOFF: return "GOTOFF"; + case VK_GOTPCREL: return "GOTPCREL"; + case VK_GOTTPOFF: return "GOTTPOFF"; + case VK_INDNTPOFF: return "INDNTPOFF"; + case VK_NTPOFF: return "NTPOFF"; + case VK_GOTNTPOFF: return "GOTNTPOFF"; + case VK_PLT: return "PLT"; + case VK_TLSGD: return "TLSGD"; + case VK_TLSLD: return "TLSLD"; + case VK_TLSLDM: return "TLSLDM"; + case VK_TPOFF: return "TPOFF"; + case VK_DTPOFF: return "DTPOFF"; + case VK_TLVP: return "TLVP"; + case VK_SECREL: return "SECREL"; + case VK_ARM_PLT: return "(PLT)"; + case VK_ARM_GOT: return "(GOT)"; + case VK_ARM_GOTOFF: return "(GOTOFF)"; + case VK_ARM_TPOFF: return "(tpoff)"; + case VK_ARM_GOTTPOFF: return "(gottpoff)"; + case VK_ARM_TLSGD: return "(tlsgd)"; + case VK_ARM_TARGET1: return "(target1)"; + case VK_PPC_TOC: return "toc"; + case VK_PPC_DARWIN_HA16: return "ha16"; + case VK_PPC_DARWIN_LO16: return "lo16"; + case VK_PPC_GAS_HA16: return "ha"; + case VK_PPC_GAS_LO16: return "l"; + case VK_Mips_GPREL: return "GPREL"; + case VK_Mips_GOT_CALL: return "GOT_CALL"; + case VK_Mips_GOT16: return "GOT16"; + case VK_Mips_GOT: return "GOT"; + case VK_Mips_ABS_HI: return "ABS_HI"; + case VK_Mips_ABS_LO: return "ABS_LO"; + case VK_Mips_TLSGD: return "TLSGD"; + case VK_Mips_TLSLDM: return "TLSLDM"; + case VK_Mips_DTPREL_HI: return "DTPREL_HI"; + case VK_Mips_DTPREL_LO: return "DTPREL_LO"; + case VK_Mips_GOTTPREL: return "GOTTPREL"; + case VK_Mips_TPREL_HI: return "TPREL_HI"; + case VK_Mips_TPREL_LO: return "TPREL_LO"; + case VK_Mips_GPOFF_HI: return "GPOFF_HI"; + case VK_Mips_GPOFF_LO: return "GPOFF_LO"; + case VK_Mips_GOT_DISP: return "GOT_DISP"; + case VK_Mips_GOT_PAGE: return "GOT_PAGE"; + case VK_Mips_GOT_OFST: return "GOT_OFST"; + } + llvm_unreachable("Invalid variant kind"); +} + +MCSymbolRefExpr::VariantKind +MCSymbolRefExpr::getVariantKindForName(StringRef Name) { + return StringSwitch(Name) + .Case("GOT", VK_GOT) + .Case("got", VK_GOT) + .Case("GOTOFF", VK_GOTOFF) + .Case("gotoff", VK_GOTOFF) + .Case("GOTPCREL", VK_GOTPCREL) + .Case("gotpcrel", VK_GOTPCREL) + .Case("GOTTPOFF", VK_GOTTPOFF) + .Case("gottpoff", VK_GOTTPOFF) + .Case("INDNTPOFF", VK_INDNTPOFF) + .Case("indntpoff", VK_INDNTPOFF) + .Case("NTPOFF", VK_NTPOFF) + .Case("ntpoff", VK_NTPOFF) + .Case("GOTNTPOFF", VK_GOTNTPOFF) + .Case("gotntpoff", VK_GOTNTPOFF) + .Case("PLT", VK_PLT) + .Case("plt", VK_PLT) + .Case("TLSGD", VK_TLSGD) + .Case("tlsgd", VK_TLSGD) + .Case("TLSLD", VK_TLSLD) + .Case("tlsld", VK_TLSLD) + .Case("TLSLDM", VK_TLSLDM) + .Case("tlsldm", VK_TLSLDM) + .Case("TPOFF", VK_TPOFF) + .Case("tpoff", VK_TPOFF) + .Case("DTPOFF", VK_DTPOFF) + .Case("dtpoff", VK_DTPOFF) + .Case("TLVP", VK_TLVP) + .Case("tlvp", VK_TLVP) + .Default(VK_Invalid); +} + +/* *** */ + +void MCTargetExpr::Anchor() {} /* *** */ bool MCExpr::EvaluateAsAbsolute(int64_t &Res) const { + return EvaluateAsAbsolute(Res, 0, 0, 0); +} + +bool MCExpr::EvaluateAsAbsolute(int64_t &Res, + const MCAsmLayout &Layout) const { + return EvaluateAsAbsolute(Res, &Layout.getAssembler(), &Layout, 0); +} + +bool MCExpr::EvaluateAsAbsolute(int64_t &Res, + const MCAsmLayout &Layout, + const SectionAddrMap &Addrs) const { + return EvaluateAsAbsolute(Res, &Layout.getAssembler(), &Layout, &Addrs); +} + +bool MCExpr::EvaluateAsAbsolute(int64_t &Res, const MCAssembler &Asm) const { + return EvaluateAsAbsolute(Res, &Asm, 0, 0); +} + +bool MCExpr::EvaluateAsAbsolute(int64_t &Res, const MCAssembler *Asm, + const MCAsmLayout *Layout, + const SectionAddrMap *Addrs) const { MCValue Value; - - if (!EvaluateAsRelocatable(Value) || !Value.isAbsolute()) - return false; + // Fast path constants. + if (const MCConstantExpr *CE = dyn_cast(this)) { + Res = CE->getValue(); + return true; + } + + // FIXME: The use if InSet = Addrs is a hack. Setting InSet causes us + // absolutize differences across sections and that is what the MachO writer + // uses Addrs for. + bool IsRelocatable = + EvaluateAsRelocatableImpl(Value, Asm, Layout, Addrs, /*InSet*/ Addrs); + + // Record the current value. Res = Value.getConstant(); - return true; + + return IsRelocatable && Value.isAbsolute(); } -static bool EvaluateSymbolicAdd(const MCValue &LHS, const MCSymbol *RHS_A, - const MCSymbol *RHS_B, int64_t RHS_Cst, +/// \brief Helper method for \see EvaluateSymbolAdd(). +static void AttemptToFoldSymbolOffsetDifference(const MCAssembler *Asm, + const MCAsmLayout *Layout, + const SectionAddrMap *Addrs, + bool InSet, + const MCSymbolRefExpr *&A, + const MCSymbolRefExpr *&B, + int64_t &Addend) { + if (!A || !B) + return; + + const MCSymbol &SA = A->getSymbol(); + const MCSymbol &SB = B->getSymbol(); + + if (SA.isUndefined() || SB.isUndefined()) + return; + + if (!Asm->getWriter().IsSymbolRefDifferenceFullyResolved(*Asm, A, B, InSet)) + return; + + MCSymbolData &AD = Asm->getSymbolData(SA); + MCSymbolData &BD = Asm->getSymbolData(SB); + + if (AD.getFragment() == BD.getFragment()) { + Addend += (AD.getOffset() - BD.getOffset()); + + // Pointers to Thumb symbols need to have their low-bit set to allow + // for interworking. + if (Asm->isThumbFunc(&SA)) + Addend |= 1; + + // Clear the symbol expr pointers to indicate we have folded these + // operands. + A = B = 0; + return; + } + + if (!Layout) + return; + + const MCSectionData &SecA = *AD.getFragment()->getParent(); + const MCSectionData &SecB = *BD.getFragment()->getParent(); + + if ((&SecA != &SecB) && !Addrs) + return; + + // Eagerly evaluate. + Addend += (Layout->getSymbolOffset(&Asm->getSymbolData(A->getSymbol())) - + Layout->getSymbolOffset(&Asm->getSymbolData(B->getSymbol()))); + if (Addrs && (&SecA != &SecB)) + Addend += (Addrs->lookup(&SecA) - Addrs->lookup(&SecB)); + + // Clear the symbol expr pointers to indicate we have folded these + // operands. + A = B = 0; +} + +/// \brief Evaluate the result of an add between (conceptually) two MCValues. +/// +/// This routine conceptually attempts to construct an MCValue: +/// Result = (Result_A - Result_B + Result_Cst) +/// from two MCValue's LHS and RHS where +/// Result = LHS + RHS +/// and +/// Result = (LHS_A - LHS_B + LHS_Cst) + (RHS_A - RHS_B + RHS_Cst). +/// +/// This routine attempts to aggresively fold the operands such that the result +/// is representable in an MCValue, but may not always succeed. +/// +/// \returns True on success, false if the result is not representable in an +/// MCValue. + +/// NOTE: It is really important to have both the Asm and Layout arguments. +/// They might look redundant, but this function can be used before layout +/// is done (see the object streamer for example) and having the Asm argument +/// lets us avoid relaxations early. +static bool EvaluateSymbolicAdd(const MCAssembler *Asm, + const MCAsmLayout *Layout, + const SectionAddrMap *Addrs, + bool InSet, + const MCValue &LHS,const MCSymbolRefExpr *RHS_A, + const MCSymbolRefExpr *RHS_B, int64_t RHS_Cst, MCValue &Res) { - // We can't add or subtract two symbols. - if ((LHS.getSymA() && RHS_A) || - (LHS.getSymB() && RHS_B)) + // FIXME: This routine (and other evaluation parts) are *incredibly* sloppy + // about dealing with modifiers. This will ultimately bite us, one day. + const MCSymbolRefExpr *LHS_A = LHS.getSymA(); + const MCSymbolRefExpr *LHS_B = LHS.getSymB(); + int64_t LHS_Cst = LHS.getConstant(); + + // Fold the result constant immediately. + int64_t Result_Cst = LHS_Cst + RHS_Cst; + + assert((!Layout || Asm) && + "Must have an assembler object if layout is given!"); + + // If we have a layout, we can fold resolved differences. + if (Asm) { + // First, fold out any differences which are fully resolved. By + // reassociating terms in + // Result = (LHS_A - LHS_B + LHS_Cst) + (RHS_A - RHS_B + RHS_Cst). + // we have the four possible differences: + // (LHS_A - LHS_B), + // (LHS_A - RHS_B), + // (RHS_A - LHS_B), + // (RHS_A - RHS_B). + // Since we are attempting to be as aggressive as possible about folding, we + // attempt to evaluate each possible alternative. + AttemptToFoldSymbolOffsetDifference(Asm, Layout, Addrs, InSet, LHS_A, LHS_B, + Result_Cst); + AttemptToFoldSymbolOffsetDifference(Asm, Layout, Addrs, InSet, LHS_A, RHS_B, + Result_Cst); + AttemptToFoldSymbolOffsetDifference(Asm, Layout, Addrs, InSet, RHS_A, LHS_B, + Result_Cst); + AttemptToFoldSymbolOffsetDifference(Asm, Layout, Addrs, InSet, RHS_A, RHS_B, + Result_Cst); + } + + // We can't represent the addition or subtraction of two symbols. + if ((LHS_A && RHS_A) || (LHS_B && RHS_B)) return false; - const MCSymbol *A = LHS.getSymA() ? LHS.getSymA() : RHS_A; - const MCSymbol *B = LHS.getSymB() ? LHS.getSymB() : RHS_B; - if (B) { - // If we have a negated symbol, then we must have also have a non-negated - // symbol in order to encode the expression. We can do this check later to - // permit expressions which eventually fold to a representable form -- such - // as (a + (0 - b)) -- if necessary. - if (!A) - return false; - } - Res = MCValue::get(A, B, LHS.getConstant() + RHS_Cst); + // At this point, we have at most one additive symbol and one subtractive + // symbol -- find them. + const MCSymbolRefExpr *A = LHS_A ? LHS_A : RHS_A; + const MCSymbolRefExpr *B = LHS_B ? LHS_B : RHS_B; + + // If we have a negated symbol, then we must have also have a non-negated + // symbol in order to encode the expression. + if (B && !A) + return false; + + Res = MCValue::get(A, B, Result_Cst); return true; } -bool MCExpr::EvaluateAsRelocatable(MCValue &Res) const { +bool MCExpr::EvaluateAsRelocatable(MCValue &Res, + const MCAsmLayout &Layout) const { + return EvaluateAsRelocatableImpl(Res, &Layout.getAssembler(), &Layout, + 0, false); +} + +bool MCExpr::EvaluateAsRelocatableImpl(MCValue &Res, + const MCAssembler *Asm, + const MCAsmLayout *Layout, + const SectionAddrMap *Addrs, + bool InSet) const { + ++stats::MCExprEvaluate; + switch (getKind()) { + case Target: + return cast(this)->EvaluateAsRelocatableImpl(Res, Layout); + case Constant: Res = MCValue::get(cast(this)->getValue()); return true; case SymbolRef: { - const MCSymbol &Sym = cast(this)->getSymbol(); + const MCSymbolRefExpr *SRE = cast(this); + const MCSymbol &Sym = SRE->getSymbol(); // Evaluate recursively if this is a variable. - if (Sym.isVariable()) - return Sym.getValue()->EvaluateAsRelocatable(Res); + if (Sym.isVariable() && SRE->getKind() == MCSymbolRefExpr::VK_None) { + bool Ret = Sym.getVariableValue()->EvaluateAsRelocatableImpl(Res, Asm, + Layout, + Addrs, + true); + // If we failed to simplify this to a constant, let the target + // handle it. + if (Ret && !Res.getSymA() && !Res.getSymB()) + return true; + } - Res = MCValue::get(&Sym, 0, 0); + Res = MCValue::get(SRE, 0, 0); return true; } @@ -191,7 +485,8 @@ bool MCExpr::EvaluateAsRelocatable(MCValue &Res) const { const MCUnaryExpr *AUE = cast(this); MCValue Value; - if (!AUE->getSubExpr()->EvaluateAsRelocatable(Value)) + if (!AUE->getSubExpr()->EvaluateAsRelocatableImpl(Value, Asm, Layout, + Addrs, InSet)) return false; switch (AUE->getOpcode()) { @@ -204,13 +499,13 @@ bool MCExpr::EvaluateAsRelocatable(MCValue &Res) const { /// -(a - b + const) ==> (b - a - const) if (Value.getSymA() && !Value.getSymB()) return false; - Res = MCValue::get(Value.getSymB(), Value.getSymA(), - -Value.getConstant()); + Res = MCValue::get(Value.getSymB(), Value.getSymA(), + -Value.getConstant()); break; case MCUnaryExpr::Not: if (!Value.isAbsolute()) return false; - Res = MCValue::get(~Value.getConstant()); + Res = MCValue::get(~Value.getConstant()); break; case MCUnaryExpr::Plus: Res = Value; @@ -223,9 +518,11 @@ bool MCExpr::EvaluateAsRelocatable(MCValue &Res) const { case Binary: { const MCBinaryExpr *ABE = cast(this); MCValue LHSValue, RHSValue; - - if (!ABE->getLHS()->EvaluateAsRelocatable(LHSValue) || - !ABE->getRHS()->EvaluateAsRelocatable(RHSValue)) + + if (!ABE->getLHS()->EvaluateAsRelocatableImpl(LHSValue, Asm, Layout, + Addrs, InSet) || + !ABE->getRHS()->EvaluateAsRelocatableImpl(RHSValue, Asm, Layout, + Addrs, InSet)) return false; // We only support a few operations on non-constant expressions, handle @@ -236,13 +533,13 @@ bool MCExpr::EvaluateAsRelocatable(MCValue &Res) const { return false; case MCBinaryExpr::Sub: // Negate RHS and add. - return EvaluateSymbolicAdd(LHSValue, + return EvaluateSymbolicAdd(Asm, Layout, Addrs, InSet, LHSValue, RHSValue.getSymB(), RHSValue.getSymA(), -RHSValue.getConstant(), Res); case MCBinaryExpr::Add: - return EvaluateSymbolicAdd(LHSValue, + return EvaluateSymbolicAdd(Asm, Layout, Addrs, InSet, LHSValue, RHSValue.getSymA(), RHSValue.getSymB(), RHSValue.getConstant(), Res); @@ -250,8 +547,8 @@ bool MCExpr::EvaluateAsRelocatable(MCValue &Res) const { } // FIXME: We need target hooks for the evaluation. It may be limited in - // width, and gas defines the result of comparisons differently from Apple - // as (the result is sign extended). + // width, and gas defines the result of comparisons and right shifts + // differently from Apple as. int64_t LHS = LHSValue.getConstant(), RHS = RHSValue.getConstant(); int64_t Result = 0; switch (ABE->getOpcode()) { @@ -280,6 +577,46 @@ bool MCExpr::EvaluateAsRelocatable(MCValue &Res) const { } } - assert(0 && "Invalid assembly expression kind!"); - return false; + llvm_unreachable("Invalid assembly expression kind!"); +} + +const MCSection *MCExpr::FindAssociatedSection() const { + switch (getKind()) { + case Target: + // We never look through target specific expressions. + return cast(this)->FindAssociatedSection(); + + case Constant: + return MCSymbol::AbsolutePseudoSection; + + case SymbolRef: { + const MCSymbolRefExpr *SRE = cast(this); + const MCSymbol &Sym = SRE->getSymbol(); + + if (Sym.isDefined()) + return &Sym.getSection(); + + return 0; + } + + case Unary: + return cast(this)->getSubExpr()->FindAssociatedSection(); + + case Binary: { + const MCBinaryExpr *BE = cast(this); + const MCSection *LHS_S = BE->getLHS()->FindAssociatedSection(); + const MCSection *RHS_S = BE->getRHS()->FindAssociatedSection(); + + // If either section is absolute, return the other. + if (LHS_S == MCSymbol::AbsolutePseudoSection) + return RHS_S; + if (RHS_S == MCSymbol::AbsolutePseudoSection) + return LHS_S; + + // Otherwise, return the first non-null section. + return LHS_S ? LHS_S : RHS_S; + } + } + + llvm_unreachable("Invalid assembly expression kind!"); }