Index: include/llvm/IR/DebugInfoMetadata.h =================================================================== --- include/llvm/IR/DebugInfoMetadata.h +++ include/llvm/IR/DebugInfoMetadata.h @@ -1430,6 +1430,9 @@ /// Reverse transformation as getPrefixEncodingFromUnsigned. static unsigned getUnsignedFromPrefixEncoding(unsigned U) { + if (U & 1) + return 0; + U >>= 1; return (U & 0x20) ? (((U >> 1) & 0xfe0) | (U & 0x1f)) : (U & 0x1f); } @@ -1448,6 +1451,14 @@ getRawInlinedAt(), isImplicitCode()); } + static unsigned encodeComponent(unsigned C) { + return (C == 0) ? 1U : (getPrefixEncodingFromUnsigned(C) << 1); + } + + static unsigned encodingBits(unsigned C) { + return (C == 0) ? 1 : (C > 0x1f ? 14 : 7); + } + public: // Disallow replacing operands. void replaceOperandWith(unsigned I, Metadata *New) = delete; @@ -1518,20 +1529,35 @@ /// order. If the lowest bit is 1, the current component is empty, and the /// next component will start in the next bit. Otherwise, the current /// component is non-empty, and its content starts in the next bit. The - /// length of each components is either 5 bit or 12 bit: if the 7th bit + /// value of each components is either 5 bit or 12 bit: if the 7th bit /// is 0, the bit 2~6 (5 bits) are used to represent the component; if the /// 7th bit is 1, the bit 2~6 (5 bits) and 8~14 (7 bits) are combined to - /// represent the component. + /// represent the component. Thus, the number of bits used for a component + /// is either 0 (if it and all the next components are empty); 1 - if it is + /// empty; 7 - if its value is up to and including 0x1f (lsb and msb are both + /// 0); or 14, if its value is up to and including 0x1ff. Note that the last + /// component is also capped at 0x1ff, even in the case when both first + /// components are 0, and we'd technically have 29 bits available. + /// + /// For precise control over the data being encoded in the discriminator, + /// use encodeDiscriminator/decodeDiscriminator. + /// + /// Use {get|set}BaseDiscriminator and cloneWithDuplicationFactor after reading + /// their documentation, as their behavior has side-effects. inline unsigned getDiscriminator() const; /// Returns a new DILocation with updated \p Discriminator. inline const DILocation *cloneWithDiscriminator(unsigned Discriminator) const; - /// Returns a new DILocation with updated base discriminator \p BD. + /// Returns a new DILocation with updated base discriminator \p BD. Only the + /// base discriminator is set in the new DILocation, the other encoded values + /// are elided. + /// Inability to encode a new discriminator is ignored. inline const DILocation *setBaseDiscriminator(unsigned BD) const; - /// Returns the duplication factor stored in the discriminator. + /// Returns the duplication factor stored in the discriminator, or 1 if no + /// duplication factor (or 0) is encoded. inline unsigned getDuplicationFactor() const; /// Returns the copy identifier stored in the discriminator. @@ -1540,8 +1566,10 @@ /// Returns the base discriminator stored in the discriminator. inline unsigned getBaseDiscriminator() const; - /// Returns a new DILocation with duplication factor \p DF encoded in the - /// discriminator. + /// Returns a new DILocation with duplication factor \p DF * current + /// duplication factor encoded in the discriminator. The current duplication + /// factor is as defined by getDuplicationFactor(). + /// Inability to encode a new discriminator is ignored. inline const DILocation *cloneWithDuplicationFactor(unsigned DF) const; /// When two instructions are combined into a single instruction we also @@ -1563,19 +1591,32 @@ /// Returns the base discriminator for a given encoded discriminator \p D. static unsigned getBaseDiscriminatorFromDiscriminator(unsigned D) { - if ((D & 1) == 0) - return getUnsignedFromPrefixEncoding(D >> 1); - else - return 0; - } - - /// Returns the duplication factor for a given encoded discriminator \p D. + return getUnsignedFromPrefixEncoding(D); + } + + /// Raw encoding of the discriminator. APIs such as setBaseDiscriminator or + /// cloneWithDuplicationFactor have certain side-effects. This API, in + /// conjunction with cloneWithDiscriminator, may be used to encode precisely + /// the values provided. \p BD: base discriminator \p DF: duplication factor + /// \p CI: copy index + /// \p Success is false if the values cannot be encoded in 32 bits - for + /// example, values for BD or DF larger than 12 bits. Returns the encoded + /// value. + static unsigned encodeDiscriminator(unsigned BD, unsigned DF, unsigned CI, + bool &Success); + + /// Raw decoder for values in an encoded discriminator D. + static void decodeDiscriminator(unsigned D, unsigned &BD, unsigned &DF, + unsigned &CI); + + /// Returns the duplication factor for a given encoded discriminator \p D, or + /// 1 if no value or 0 is encoded. static unsigned getDuplicationFactorFromDiscriminator(unsigned D) { D = getNextComponentInDiscriminator(D); - if (D == 0 || (D & 1)) + unsigned Ret = getUnsignedFromPrefixEncoding(D); + if (Ret == 0) return 1; - else - return getUnsignedFromPrefixEncoding(D >> 1); + return Ret; } /// Returns the copy identifier for a given encoded discriminator \p D. @@ -2003,7 +2044,7 @@ if (D == 0) return this; else - return cloneWithDiscriminator(getPrefixEncodingFromUnsigned(D) << 1); + return cloneWithDiscriminator(encodeComponent(D)); } const DILocation *DILocation::cloneWithDuplicationFactor(unsigned DF) const { @@ -2012,14 +2053,9 @@ return this; unsigned BD = getBaseDiscriminator(); - unsigned CI = getCopyIdentifier() << (DF > 0x1f ? 14 : 7); - unsigned D = CI | (getPrefixEncodingFromUnsigned(DF) << 1); - - if (BD == 0) - D = (D << 1) | 1; - else - D = (D << (BD > 0x1f ? 14 : 7)) | (getPrefixEncodingFromUnsigned(BD) << 1); - + unsigned CI = getCopyIdentifier(); + bool Success; + unsigned D = encodeDiscriminator(BD, DF, CI, Success); return cloneWithDiscriminator(D); } Index: lib/IR/DebugInfoMetadata.cpp =================================================================== --- lib/IR/DebugInfoMetadata.cpp +++ lib/IR/DebugInfoMetadata.cpp @@ -20,6 +20,8 @@ #include "llvm/IR/Function.h" #include "llvm/IR/Instructions.h" +#include + using namespace llvm; DILocation::DILocation(LLVMContext &C, StorageType Storage, unsigned Line, @@ -113,6 +115,45 @@ return DILocation::get(Result->getContext(), 0, 0, S, L); } +unsigned DILocation::encodeDiscriminator(unsigned BD, unsigned DF, unsigned CI, + bool &Success) { + SmallVector Components = {BD, DF, CI}; + uint64_t RemainingWork = 0U; + // We use RemainingWork to figure out if we have no remaining components to + // encode. For example: if BD != 0 but DF == 0 && CI == 0, we don't need to + // encode anything for the latter 2. + // Since any of the input components is at most 32 bits, their sum will be + // less than 34 bits, and thus RemainingWork won't overflow. + RemainingWork = std::accumulate(Components.begin(), Components.end(), RemainingWork); + + int I = 0; + unsigned Ret = 0; + unsigned NextBitInsertionIndex = 0; + while (RemainingWork > 0) { + unsigned C = Components[I++]; + RemainingWork -= C; + unsigned EC = encodeComponent(C); + Ret |= (EC << NextBitInsertionIndex); + NextBitInsertionIndex += encodingBits(C); + } + + // Alternatively, we could determine Success during encoding, but the alternative + // here is simpler to understand. + unsigned TBD, TDF, TCI = 0; + decodeDiscriminator(Ret, TBD, TDF, TCI); + Success = TBD == BD && TDF == DF && TCI == CI; + return Ret; +} + +void DILocation::decodeDiscriminator(unsigned D, unsigned &BD, unsigned &DF, + unsigned &CI) { + BD = getUnsignedFromPrefixEncoding(D); + DF = getUnsignedFromPrefixEncoding(getNextComponentInDiscriminator(D)); + CI = getUnsignedFromPrefixEncoding( + getNextComponentInDiscriminator(getNextComponentInDiscriminator(D))); +} + + DINode::DIFlags DINode::getFlag(StringRef Flag) { return StringSwitch(Flag) #define HANDLE_DI_FLAG(ID, NAME) .Case("DIFlag" #NAME, Flag##NAME) Index: lib/Target/X86/X86DiscriminateMemOps.cpp =================================================================== --- lib/Target/X86/X86DiscriminateMemOps.cpp +++ lib/Target/X86/X86DiscriminateMemOps.cpp @@ -21,6 +21,7 @@ #include "llvm/IR/DebugInfoMetadata.h" #include "llvm/ProfileData/SampleProf.h" #include "llvm/ProfileData/SampleProfReader.h" +#include "llvm/Support/Debug.h" #include "llvm/Transforms/IPO/SampleProfile.h" using namespace llvm; @@ -107,27 +108,38 @@ if (!DI) { DI = ReferenceDI; } - DenseSet &Set = Seen[diToLocation(DI)]; + Location L = diToLocation(DI); + DenseSet &Set = Seen[L]; const std::pair::iterator, bool> TryInsert = Set.insert(DI->getBaseDiscriminator()); if (!TryInsert.second) { - DI = DI->setBaseDiscriminator(++MemOpDiscriminators[diToLocation(DI)]); + bool EncodingSucceeded = false; + unsigned BF, DF, CI = 0; + DILocation::decodeDiscriminator(DI->getDiscriminator(), BF, DF, CI); + unsigned EncodedDiscriminator = DILocation::encodeDiscriminator( + MemOpDiscriminators[L] + 1, DF, CI, + EncodingSucceeded); + + if (!EncodingSucceeded) { + // FIXME(mtrofin): The assumption is that this scenario is infrequent/OK + // not to support. If evidence points otherwise, we can explore synthesizeing + // unique DIs by adding fake line numbers, or by constructing 64 bit + // discriminators. + LLVM_DEBUG(dbgs() << "Unable to create a unique discriminator " + "for instruction with memory operand in: " + << DI->getFilename() << " Line: " << DI->getLine() + << " Column: " << DI->getColumn() + << ". This is likely due to a large macro expansion. \n"); + continue; + } + // Since we were able to encode, bump the MemOpDiscriminators. + ++MemOpDiscriminators[L]; + DI = DI->cloneWithDiscriminator(EncodedDiscriminator); updateDebugInfo(&MI, DI); Changed = true; const std::pair::iterator, bool> MustInsert = Set.insert(DI->getBaseDiscriminator()); - // FIXME (mtrofin): check if the to-be inserted base discriminator can - // be added. This requires a new API on DILocation. - // The assumption is that this scenario is infrequent/OK not to support. - // If evidence points otherwise, we can explore synthesize unique DIs by - // adding fake line numbers. - if (!MustInsert.second) { - LLVM_DEBUG(dbgs() - << "Unable to create a unique discriminator in " - << DI->getFilename() << " Line: " << DI->getLine() - << " Column: " << DI->getColumn() - << ". This is likely due to a large macro expansion.\n"); - } + assert(MustInsert.second && "New discriminator shouldn't be present in set"); } // Bump the reference DI to avoid cramming discriminators on line 0. Index: unittests/IR/MetadataTest.cpp =================================================================== --- unittests/IR/MetadataTest.cpp +++ unittests/IR/MetadataTest.cpp @@ -981,6 +981,122 @@ EXPECT_TRUE(L2->isTemporary()); } +TEST_F(DILocationTest, discriminatorEncoding) { + bool Success = false; + EXPECT_EQ(0U, DILocation::encodeDiscriminator(0, 0, 0, Success)); + EXPECT_TRUE(Success); + + // Encode base discriminator as a component: lsb is 0, then the value. + // The other components are all absent, so we leave all the other bits 0. + EXPECT_EQ(2U, DILocation::encodeDiscriminator(1, 0, 0, Success)); + EXPECT_TRUE(Success); + + // Base discriminator component is empty, so lsb is 1. Next component is not + // empty, so its lsb is 0, then its value (1). Next component is empty. + // So the bit pattern is 101. + EXPECT_EQ(5U, DILocation::encodeDiscriminator(0, 1, 0, Success)); + EXPECT_TRUE(Success); + + // First 2 components are empty, so the bit pattern is 11. Then the + // next component - ending up with 1011. + EXPECT_EQ(0xbU, DILocation::encodeDiscriminator(0, 0, 1, Success)); + EXPECT_TRUE(Success); + + // The bit pattern for the first 2 components is 11. The next bit is 0, + // because the last component is not empty. We have 29 bits usable for + // encoding, but we cap it at 12 bits uniformously for all components. We + // encode the last component over 14 bits. + EXPECT_EQ(0xfffbU, DILocation::encodeDiscriminator(0, 0, 0xfff, Success)); + EXPECT_TRUE(Success); + + EXPECT_EQ(0x102U, DILocation::encodeDiscriminator(1, 1, 0, Success)); + EXPECT_TRUE(Success); + + EXPECT_EQ(0x13eU, DILocation::encodeDiscriminator(0x1f, 1, 0, Success)); + EXPECT_TRUE(Success); + + EXPECT_EQ(0x87feU, DILocation::encodeDiscriminator(0x1ff, 1, 0, Success)); + EXPECT_TRUE(Success); + + EXPECT_EQ(0x1f3eU, DILocation::encodeDiscriminator(0x1f, 0x1f, 0, Success)); + EXPECT_TRUE(Success); + + EXPECT_EQ(0x3ff3eU, DILocation::encodeDiscriminator(0x1f, 0x1ff, 0, Success)); + EXPECT_TRUE(Success); + + EXPECT_EQ(0x1ff87feU, + DILocation::encodeDiscriminator(0x1ff, 0x1ff, 0, Success)); + EXPECT_TRUE(Success); + + EXPECT_EQ(0xfff9f3eU, + DILocation::encodeDiscriminator(0x1f, 0x1f, 0xfff, Success)); + EXPECT_TRUE(Success); + + EXPECT_EQ(0xffc3ff3eU, + DILocation::encodeDiscriminator(0x1f, 0x1ff, 0x1ff, Success)); + EXPECT_TRUE(Success); + + EXPECT_EQ(0xffcf87feU, + DILocation::encodeDiscriminator(0x1ff, 0x1f, 0x1ff, Success)); + EXPECT_TRUE(Success); + + EXPECT_EQ(0xe1ff87feU, + DILocation::encodeDiscriminator(0x1ff, 0x1ff, 7, Success)); + EXPECT_TRUE(Success); +} + +TEST_F(DILocationTest, discriminatorEncodingNegativeTests) { + bool Success = false; + DILocation::encodeDiscriminator(0, 0, 0x1000, Success); + EXPECT_FALSE(Success); + + DILocation::encodeDiscriminator(0x1000, 0, 0, Success); + EXPECT_FALSE(Success); + + DILocation::encodeDiscriminator(0, 0x1000, 0, Success); + EXPECT_FALSE(Success); + + DILocation::encodeDiscriminator(0, 0, 0x1000, Success); + EXPECT_FALSE(Success); + + DILocation::encodeDiscriminator(0x1ff, 0x1ff, 8, Success); + EXPECT_FALSE(Success); + + DILocation::encodeDiscriminator(std::numeric_limits::max(), + std::numeric_limits::max(), + 0, Success); + EXPECT_FALSE(Success); +} + +TEST_F(DILocationTest, discriminatorSpecialCases) { + // We don't test getCopyIdentifier here because the only way + // to set it is by constructing an encoded discriminator using + // encodeDiscriminator, which is already tested. + auto L1 = DILocation::get(Context, 1, 2, getSubprogram()); + EXPECT_EQ(0U, L1->getBaseDiscriminator()); + EXPECT_EQ(1U, L1->getDuplicationFactor()); + + auto L2 = L1->setBaseDiscriminator(1); + EXPECT_EQ(0U, L1->getBaseDiscriminator()); + EXPECT_EQ(1U, L1->getDuplicationFactor()); + + EXPECT_EQ(1U, L2->getBaseDiscriminator()); + EXPECT_EQ(1U, L2->getDuplicationFactor()); + + auto L3 = L2->cloneWithDuplicationFactor(2); + EXPECT_EQ(1U, L3->getBaseDiscriminator()); + EXPECT_EQ(2U, L3->getDuplicationFactor()); + + auto L4 = L3->cloneWithDuplicationFactor(4); + EXPECT_EQ(1U, L4->getBaseDiscriminator()); + EXPECT_EQ(8U, L4->getDuplicationFactor()); + + auto L5 = L4->setBaseDiscriminator(2); + EXPECT_EQ(2U, L5->getBaseDiscriminator()); + EXPECT_EQ(1U, L5->getDuplicationFactor()); +} + + typedef MetadataTest GenericDINodeTest; TEST_F(GenericDINodeTest, get) {