<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">An important test to perform before committing to any action might be this: what is the proportion of unique SourceLocations constructed by the Lexer to the number of bytes in the input buffers, when you run out of SourceLocations? <div class=""><br class=""></div><div class="">If it is extremely high, that suggests the problem may be large unused macro expansions cluttering up the buffer (if that is possible). This means however that the "index solution" introduced earlier would solve the issue.<div class=""><br class=""></div><div class="">I don’t know quite how the Preprocessor works but the reason I suspect there may be large unused macro expansions is a) the use of BOOST_PP stuff in this problematic case, and b) the documentation of SourceLocation:</div><div class="">```</div><div class="">/// Technically, a source location is simply an offset into the manager's view<br class="">/// of the input source, which is all input buffers (including macro<br class="">/// expansions) concatenated in an effectively arbitrary order. </div><div class="">```</div><div class="">Does "all input buffers (including macro expansion)" include even unused expansions, such as the first arg in in </div><div class="">`BOOST_PP_IF(1, UNUSED_BUT_EXPANDED_MACRO(a,b,c), USED_EXPANDED_MACRO(a,b,c))`?</div><div class=""><br class=""></div><div class="">If so I suspect there will be many more bytes than SourceLocations, and thus the index solution may be viable, just in case it is easier to implement than other solutions (which is another matter).</div><div class=""><br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Feb 3, 2021, at 4:19 PM, Richard Smith <<a href="mailto:richard@metafoo.co.uk" class="">richard@metafoo.co.uk</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div dir="ltr" class="">On Wed, 3 Feb 2021 at 12:10, Keane, Erich <<a href="mailto:erich.keane@intel.com" class="">erich.keane@intel.com</a>> wrote:<br class=""></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div lang="EN-US" style="overflow-wrap: break-word;" class="">
<div class="gmail-m_7138898228170345008WordSection1"><p class="MsoNormal">Thanks for the response Richard! I’m working with my QA team to get a better reproducer to see if we can figure out what is the root-cause. It DOES include a couple of other files so I’m not sure all of what is entailed.<u class=""></u><u class=""></u></p><p class="MsoNormal"><u class=""></u> <u class=""></u></p><p class="MsoNormal">>There are also some relatively cheap things we could do to expand our capacity: we could remove the 'is macro location' bit without much effort (though this would slow down the current places that check the flag), which would double our
available source location capacity. <u class=""></u><u class=""></u></p><p class="MsoNormal">This seems like a useful and cheap thing to do, if find this is a legitimate issue, I’ll see if I can put a patch together to do this one.<u class=""></u><u class=""></u></p><p class="MsoNormal"><u class=""></u> <u class=""></u></p><p class="MsoNormal">>And we could allow the division between local and imported locations to be determined dynamically rather than fixing a 50/50 split, which would in practice be likely to double the available capacity again. But those would only be useful
if we're just a little over the limit; they wouldn't help if there's an asymptotic problem in our source location usage.<u class=""></u><u class=""></u></p><p class="MsoNormal"><u class=""></u> <u class=""></u></p><p class="MsoNormal">I don’t have a great idea on how to do this, or how we use this, but based on your description it seems worth-while. At least in non-module TUs I’d assume that the “imported-from-ast-file” is relatively rare. Also, I would think these
imports happen ‘first’, right? So we could figure out the split as soon as we’re done with imports and optimize our space.</p></div></div></blockquote><div class=""><br class=""></div><div class="">Not necessarily, no -- in some configurations, we don't find out which AST files we want to load until we see a #include, which could happen arbitrarily late through preprocessing.</div><div class=""><br class=""></div><div class="">I don't think we need to pick the split point up front. Currently, we essentially use positive source locations for local locs and negative ones for imported locs. So we could handle this by effectively allowing both/either to wrap around, making sure they don't pass each other, and checking which side a location is on by performing an (unsigned) comparison instead of checking the sign bit.</div><div class=""> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div lang="EN-US" style="overflow-wrap: break-word;" class=""><div class="gmail-m_7138898228170345008WordSection1">
<div style="border-right:none;border-bottom:none;border-left:none;border-top:1pt solid rgb(225,225,225);padding:3pt 0in 0in" class=""><p class="MsoNormal"><b class="">From:</b> Richard Smith <<a href="mailto:richard@metafoo.co.uk" target="_blank" class="">richard@metafoo.co.uk</a>> <br class="">
<b class="">Sent:</b> Wednesday, February 3, 2021 11:54 AM<br class="">
<b class="">To:</b> Keane, Erich <<a href="mailto:erich.keane@intel.com" target="_blank" class="">erich.keane@intel.com</a>><br class="">
<b class="">Cc:</b> David Rector <<a href="mailto:davrecthreads@gmail.com" target="_blank" class="">davrecthreads@gmail.com</a>>; clang developer list <<a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class="">cfe-dev@lists.llvm.org</a>><br class="">
<b class="">Subject:</b> Re: [cfe-dev] [RFC] Clang SourceLocation overflow<u class=""></u><u class=""></u></p>
</div><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
<div class="">
<div class=""><p class="MsoNormal">On Tue, 2 Feb 2021 at 10:41, Keane, Erich via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class="">cfe-dev@lists.llvm.org</a>> wrote:<u class=""></u><u class=""></u></p>
</div>
<div class="">
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in" class="">
<div class="">
<div class=""><p class="MsoNormal">Presumably, yes, we could hit that limit, and that limit is closer than we’d think.<u class=""></u><u class=""></u></p><p class="MsoNormal"> <u class=""></u><u class=""></u></p><p class="MsoNormal">Based on my understanding though, we currently stores the ‘offset’ into the buffer. If we were to go with your plan, we’d reduce the ‘SourceLocation’ space significantly, since
we’d only have 1 value taken up by “ALongFunctionName” instead of ~15? Or, at least, only 1 instead of 3 in ‘int’.<u class=""></u><u class=""></u></p><p class="MsoNormal"> <u class=""></u><u class=""></u></p><p class="MsoNormal">I presume that anything short of expanding the size of SourceLocation is going to be a temporary measure at best.
<u class=""></u><u class=""></u></p><p class="MsoNormal"> <u class=""></u><u class=""></u></p><p class="MsoNormal">One consideration: What do we think about making SourceLocation have an underlying type of ‘bitfield’ that is a smaller size than 64 bits? Then at least we could make SourceRange
be a packed value? So make SourceLocation be 40 bits (obviously would still be 64 if stored directly), but at least we could pack 2 of them into 80 bits for any type that does some sort of bit-packing? <u class=""></u><u class=""></u></p>
</div>
</div>
</blockquote>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">I doubt this would help in practice -- most of the storage in AST nodes tends to be SourceLocations and pointers.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in" class="">
<div class="">
<div class=""><p class="MsoNormal">Alternatively, what about making SourceRange (instead of 2 SourceLocation objects) be a SourceLocation + unsigned? It would make it a little smaller? Then we could do similar
optimizations over time to the ASTNodes. That is, all of the TypeLoc types could just store things like open/close parens as offsets-from-the-original rather than SourceLocations, then calculate them when needed? I would assume anything that required re-calculation
would be acceptable, since SourceLocations are seemingly quite rarely used (except for the few cases that Richard mentioned below).<u class=""></u><u class=""></u></p>
</div>
</div>
</blockquote>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">That doesn't seem likely to work: we can't assume the beginning and end of a source range are close together in source location space (they could be in different SLocEntrys, which could be a long way apart from each other).<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in" class="">
<div class="">
<div class=""><p class="MsoNormal">My preference is obviously to just make SourceLocation be uint64_t instead, but the impact on AST size is going to be significant. So I guess I’m hoping that Richard Smith can
comment and help us figure out how much pain we are willing to go through for this?<u class=""></u><u class=""></u></p>
</div>
</div>
</blockquote>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">We could do that, and having a build-time selector for 32/64-bit SourceLocations seems like it might not impose a huge cost. But I think we should first try to gain some confidence that we're addressing the right problem -- running out
of source locations seems likely to indicate that there's something more fundamental wrong with the compilation. Currently we reserve one bit for an 'is macro location' flag, and divide the remaining addressable 2GB into a 1GB local region and a 1GB imported-from-AST-file
region. The resulting "1GB of preprocessed source (including all intermediate stages of macro expansion)" implementation limit does not seem especially restrictive to me, so the first thing I think we should find out is how we're actually hitting that limit
in the boost example. We can currently handle huge compilations without hitting the limit, so if a single header file can hit it, that seems indicative of a bug that's not just caused by the limit being too low.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">One possible cause would be that a large header is included a *lot* and doesn't have a proper include guard. If that's the case, that seems like a problem that we should get fixed in boost -- or in Clang if it's a bug in include guard detection
-- because that will contribute to long compile times too. I expect there are other cases where source location address space gets wasted that we could drill down into.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class="">
<div class=""><p class="MsoNormal">If we find the problem is our location tracking for macro expansions (eg, pushing a large volume of tokens through deeply nested macro expansions), we could probably find a way to turn that off; there may even be ways we can intelligently
turn it off selectively in cases where we think the intermediary information is unlikely to be useful. We could also look into throwing away source location address space for macro expansions that ended up producing no tokens. But we need to understand the
nature of the problem first.<u class=""></u><u class=""></u></p>
</div>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">There are also some relatively cheap things we could do to expand our capacity: we could remove the 'is macro location' bit without much effort (though this would slow down the current places that check the flag), which would double our
available source location capacity. And we could allow the division between local and imported locations to be determined dynamically rather than fixing a 50/50 split, which would in practice be likely to double the available capacity again. But those would
only be useful if we're just a little over the limit; they wouldn't help if there's an asymptotic problem in our source location usage.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"><u class=""></u> <u class=""></u></p>
</div>
<blockquote style="border-top:none;border-right:none;border-bottom:none;border-left:1pt solid rgb(204,204,204);padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in" class="">
<div class="">
<div class="">
<div class="">
<div style="border-right:none;border-bottom:none;border-left:none;border-top:1pt solid rgb(225,225,225);padding:3pt 0in 0in" class=""><p class="MsoNormal"><b class="">From:</b> David Rector <<a href="mailto:davrecthreads@gmail.com" target="_blank" class="">davrecthreads@gmail.com</a>>
<br class="">
<b class="">Sent:</b> Tuesday, February 2, 2021 10:28 AM<br class="">
<b class="">To:</b> Keane, Erich <<a href="mailto:erich.keane@intel.com" target="_blank" class="">erich.keane@intel.com</a>><br class="">
<b class="">Cc:</b> clang developer list <<a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class="">cfe-dev@lists.llvm.org</a>><br class="">
<b class="">Subject:</b> Re: [cfe-dev] [RFC] Clang SourceLocation overflow<u class=""></u><u class=""></u></p>
</div>
</div><p class="MsoNormal"> <u class=""></u><u class=""></u></p><p class="MsoNormal">An additional consideration: if the files/buffers are so large that each SourceLocation cannot fit in 30 bits, does that imply that so many SourceLocations will be generated that
the indices to them won’t be able to fit in 30 bits? That may be the case now that I think of it, in which case the only solution really would be 64 bit SourceLocations, or something still more creative/costly.<u class=""></u><u class=""></u></p>
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
<div class="">
<blockquote style="margin-top:5pt;margin-bottom:5pt" class="">
<div class=""><p class="MsoNormal">On Feb 2, 2021, at 11:53 AM, Keane, Erich <<a href="mailto:erich.keane@intel.com" target="_blank" class="">erich.keane@intel.com</a>> wrote:<u class=""></u><u class=""></u></p>
</div><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
<div class="">
<div class=""><p class="MsoNormal">Huh, that is an interesting idea! The issue ends up being the callers of getOffset though, since it is a previate method.<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal">That said, I wonder if the extra bit-use is just putting off the inevitable, and we should just use the vector in SourceManager for everything. My initial thought is that we could
do away with the ‘IsMacro’ bit as well, and just encode that in the vector too. It makes isFileID and isMacroID require the SourceManager as well, but I wonder if that is OK?<u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
<div class="">
<div style="border-right:none;border-bottom:none;border-left:none;border-top:1pt solid rgb(225,225,225);padding:3pt 0in 0in" class="">
<div class=""><p class="MsoNormal"><b class="">From:</b><span class="gmail-m_7138898228170345008gmail-m6785580962079825663apple-converted-space"> </span>David Rector <<a href="mailto:davrecthreads@gmail.com" target="_blank" class="">davrecthreads@gmail.com</a>><span class="gmail-m_7138898228170345008gmail-m6785580962079825663apple-converted-space"> </span><br class="">
<b class="">Sent:</b><span class="gmail-m_7138898228170345008gmail-m6785580962079825663apple-converted-space"> </span>Tuesday, February 2, 2021 8:46 AM<br class="">
<b class="">To:</b><span class="gmail-m_7138898228170345008gmail-m6785580962079825663apple-converted-space"> </span>Keane, Erich <<a href="mailto:erich.keane@intel.com" target="_blank" class="">erich.keane@intel.com</a>><br class="">
<b class="">Cc:</b><span class="gmail-m_7138898228170345008gmail-m6785580962079825663apple-converted-space"> </span>clang developer list <<a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class="">cfe-dev@lists.llvm.org</a>><br class="">
<b class="">Subject:</b><span class="gmail-m_7138898228170345008gmail-m6785580962079825663apple-converted-space"> </span>Re: [cfe-dev] [RFC] Clang SourceLocation overflow<u class=""></u><u class=""></u></p>
</div>
</div>
</div>
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
<div class="">
<div class=""><p class="MsoNormal">A possible solution not mentioned: reserve a bit in SourceLocation for "IsBigLoc". When IsBigLoc = true, the remaining 30 bits of the "ID" field is not an offset but an index into
a vector of uintptr_ts in SourceManager, each holding 64-bit offset data.<u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal">Only a few changes to private methods and isolated details would be needed I think: e.g. method `unsigned SourceLocation::getOffset()` would become `uintptr_t SourceLocation::getOffset(const
SourceManager &SM)`, and would dereference and return the larger data when IsBigLoc. And more generally `unsigned` types should be changed to `uintptr_t` everywhere 32-bit encodings are currently assumed (mostly in SourceManager).<u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal">This might be easier and less intrusive than allowing 64-bit SourceLocations depending on a build flag, if I understand that proposal correctly, since that would require templating
virtually everything with the SourceLocation type.<u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal" style="margin-bottom:12pt"><br class="">
<br class="">
<u class=""></u><u class=""></u></p>
</div>
<blockquote style="margin-top:5pt;margin-bottom:5pt" class="">
<div class="">
<div class=""><p class="MsoNormal">On Feb 2, 2021, at 9:21 AM, Keane, Erich via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class="">cfe-dev@lists.llvm.org</a>> wrote:<u class=""></u><u class=""></u></p>
</div>
</div>
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
<div class="">
<div class="">
<div class=""><p class="MsoNormal">Original thread here:<span class="gmail-m_7138898228170345008gmail-m6785580962079825663apple-converted-space"> </span><a href="https://lists.llvm.org/pipermail/cfe-dev/2019-October/063459.html" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">https://lists.llvm.org/pipermail/cfe-dev/2019-October/063459.html</span></a><u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal">I’m bringing this back up since we have a reproduction of this in Boost now. We haven’t finished analyzing what boost is doing, but simply doing an include of:<u class=""></u><u class=""></u></p>
</div>
</div>
<pre class="">#include <libs/vmd/test/test_doc_modifiers_return_type.cxx><u class=""></u><u class=""></u></pre>
<div class="">
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal">Now causes us to run out of source locations, hitting:<u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal">/llvm/clang/lib/Basic/SourceManager.cpp:680: clang::SourceLocation clang::SourceManager::createExpansionLocImpl(const clang::SrcMgr::ExpansionInfo &, unsigned int, int, unsigned
int): Assertion `NextLocalOffset + TokLength + 1 > NextLocalOffset && NextLocalOffset + TokLength + 1 <= CurrentLoadedOffset && "Ran out of source locations!"' failed.<u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal">From the last discussion, it seems that increasing our source-location size isn’t really acceptable due to how much it is stored in the AST( Multiple times per node), and giving
up on location isn’t viable either. Additionally, the source location/source manager layout is quite complex and I don’t quite understand it yet, so I don’t have a good way of suggesting an alternative.<u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal">SO, I’d like to re-start the discussion into this, we need to find a way to make our compiler able to support more source-locations, as I can’t imagine this is going to be the only
time we run into this.<u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal">-Erihc<span class="gmail-m_7138898228170345008gmail-m6785580962079825663apple-converted-space"> </span><u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
</div>
<div class="">
<div class=""><p class="MsoNormal">>>>>>>>>>>>>>>>>>>>> <u class=""></u><u class=""></u></p>
</div>
</div>
<pre class="">Hi Matt.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">Thanks for the offer. Whenever you’re back and have a moment is fine by me, I don’t think we’re in a massive hurry.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">Thanks,<u class=""></u><u class=""></u></pre>
<pre class="">Christof<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">From: Matt Asplund <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">mwasplund at gmail.com</span></a>><u class=""></u><u class=""></u></pre>
<pre class="">Sent: 10 October 2019 14:09<u class=""></u><u class=""></u></pre>
<pre class="">To: Christof Douma <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">Christof.Douma at arm.com</span></a>><u class=""></u><u class=""></u></pre>
<pre class="">Cc: Richard Smith <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">richard at metafoo.co.uk</span></a>>; Mikhail Maltsev <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">Mikhail.Maltsev at arm.com</span></a>>; Clang Dev <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">cfe-dev at lists.llvm.org</span></a>>; nd <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">nd at arm.com</span></a>><u class=""></u><u class=""></u></pre>
<pre class="">Subject: Re: [cfe-dev] [RFC] Clang SourceLocation overflow<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">Sure, I can share my changes. In general my changes are very localized to the code paths I was hitting oveflow issues and tried to keep as much as possible using 32bit encodings. Is there an ETA for when you will start investigating, I am out of town for the next week but if needed can get access to my desktop.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">-Matt<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">On Thu, Oct 10, 2019, 2:13 AM Christof Douma <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">Christof.Douma at arm.com</span></a><mailto:<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">Christof.Douma at arm.com</span></a>>> wrote:<u class=""></u><u class=""></u></pre>
<pre class="">Hi Richard.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">Thanks for the clarification, I certainly had not realized that location tracking was needed for correctness of clang. Decoupling this sounds like a painful processes, and the only thing we get is errors without any location information. Sounds like not a great trade-off. We’ll go experiment a bit with the size impact of using 64-bits and will attempt to take the route of a cmake configuration option.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">If there are people that have already done some experiments on the size impact of 64-bits location pointers, we’re welcome your insights. @Matt Asplund<mailto:<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">mwasplund at gmail.com</span></a>> I believe you said that you’ve done some prototyping, is there something you can share?<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">Thanks,<u class=""></u><u class=""></u></pre>
<pre class="">Christof<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">From: Richard Smith <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">richard at metafoo.co.uk</span></a><mailto:<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">richard at metafoo.co.uk</span></a>>><u class=""></u><u class=""></u></pre>
<pre class="">Sent: 08 October 2019 19:53<u class=""></u><u class=""></u></pre>
<pre class="">To: Christof Douma <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">Christof.Douma at arm.com</span></a><mailto:<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">Christof.Douma at arm.com</span></a>>><u class=""></u><u class=""></u></pre>
<pre class="">Cc: Mikhail Maltsev <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">Mikhail.Maltsev at arm.com</span></a><mailto:<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">Mikhail.Maltsev at arm.com</span></a>>>; Clang Dev <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">cfe-dev at lists.llvm.org</span></a><mailto:<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">cfe-dev at lists.llvm.org</span></a>>>; nd <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">nd at arm.com</span></a><mailto:<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">nd at arm.com</span></a>>><u class=""></u><u class=""></u></pre>
<pre class="">Subject: Re: [cfe-dev] [RFC] Clang SourceLocation overflow<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">On Tue, 8 Oct 2019, 10:42 Christof Douma via cfe-dev, <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">cfe-dev at lists.llvm.org</span></a><mailto:<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">cfe-dev at lists.llvm.org</span></a>>> wrote:<u class=""></u><u class=""></u></pre>
<pre class="">Hi Richard, Paul and other.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">Thanks for the input so far. I wanted to point out that it’s not our code-base. Rather, we’re seeing more use of the LLVM technology in the automotive market and as usual we’re faced with existing code bases that are tried and tested with other toolchains (gcc or others) and when LLVM comes along things don’t always work directly.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">We’ve suggested better ways of structuring their code and your suggestions are certainly good input. However, legacy code is especially sticky in any market that has to handle ‘safety’ concerns, like automotive, aerospace and medical markets. Code changes are pretty expensive in those fields. So while I hope that over time we see more sensible coding structures, I don’t expect that to happen any time soon. In the mean time, we’re searching for a solution for this coding pattern that doesn’t play well with clang.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">Hope that gave some more background of where this question comes from.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">Do all options that were suggested by Mikhail really require fundamental restructuring of major parts of clang? This surprised me, I had expected that the option 2 to be possible without a complete overhaul. (2 is “Track until an overflow occurs after that make the lexer output the <invalid location> special value for all subsequent tokens.”)<u class=""></u><u class=""></u></pre>
<pre class="">Clang uses source locations as part of the semantic representation of the AST in some cases (simple example: some forms of initialization might use parens or not, with different semantics, and we distinguish between them based on whether we have paren locations; there are also some checks that look at which of two source locations came first when determining which warnings or errors to produce, and so on). Maybe we could go through and fix all of those, but that's still a very large task and it'd be hard to check we got them all.<u class=""></u><u class=""></u></pre>
<pre class="">Not nice user experience but maybe doable? I was hoping there was something slightly better that still works without a major restructuring (maybe something that at least gives a rough location or something that only gives the location of the error and not the include stack under an option or using some kind of heuristic to detect that things go haywire).<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">As an alternative, I was curious if it would be possible and acceptable to make the switch between 32-bit and 64-bit location tracking a build-time/cmake decision? I’ve not done any estimation on the memory size growth, so maybe this is a dead end.<u class=""></u><u class=""></u></pre>
<pre class="">If someone is prepared to do the work to add and maintain this build mode, I think this might be a feasible option.<u class=""></u><u class=""></u></pre>
<pre class="">Thanks,<u class=""></u><u class=""></u></pre>
<pre class="">Christof<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">From: cfe-dev <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">cfe-dev-bounces at lists.llvm.org</span></a><mailto:<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">cfe-dev-bounces at lists.llvm.org</span></a>>> On Behalf Of Richard Smith via cfe-dev<u class=""></u><u class=""></u></pre>
<pre class="">Sent: 07 October 2019 20:36<u class=""></u><u class=""></u></pre>
<pre class="">To: Mikhail Maltsev <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">Mikhail.Maltsev at arm.com</span></a><mailto:<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">Mikhail.Maltsev at arm.com</span></a>>><u class=""></u><u class=""></u></pre>
<pre class="">Cc: nd <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">nd at arm.com</span></a><mailto:<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">nd at arm.com</span></a>>>; <a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">cfe-dev at lists.llvm.org</span></a><mailto:<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">cfe-dev at lists.llvm.org</span></a>><u class=""></u><u class=""></u></pre>
<pre class="">Subject: Re: [cfe-dev] [RFC] Clang SourceLocation overflow<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">On Wed, 2 Oct 2019 at 09:26, Mikhail Maltsev via cfe-dev <<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">cfe-dev at lists.llvm.org</span></a><mailto:<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">cfe-dev at lists.llvm.org</span></a>>> wrote:<u class=""></u><u class=""></u></pre>
<pre class="">Hi all,<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">We are experiencing a problem with Clang SourceLocation overflow.<u class=""></u><u class=""></u></pre>
<pre class="">Currently source locations are 32-bit values, one bit is a flag, which gives<u class=""></u><u class=""></u></pre>
<pre class="">a source location space of 2^31 characters.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">When the Clang lexer processes an #include directive it reserves the total size<u class=""></u><u class=""></u></pre>
<pre class="">of the file being included in the source location space. An overflow can occur<u class=""></u><u class=""></u></pre>
<pre class="">if a large file (which does not have include guards by design) is included many<u class=""></u><u class=""></u></pre>
<pre class="">times into a single TU.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">The pattern of including a file multiple times is for example required by<u class=""></u><u class=""></u></pre>
<pre class="">the AUTOSAR standard [1], which is widely used in the automotive industry.<u class=""></u><u class=""></u></pre>
<pre class="">Specifically the pattern is described in the Specification of Memory Mapping [2]:<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">Section 8.2.1, MEMMAP003:<u class=""></u><u class=""></u></pre>
<pre class="">"The start and stop symbols for section control are configured with section<u class=""></u><u class=""></u></pre>
<pre class="">identifiers defined in MemMap.h [...] For instance:<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">#define EEP_START_SEC_VAR_16BIT<u class=""></u><u class=""></u></pre>
<pre class="">#include "MemMap.h"<u class=""></u><u class=""></u></pre>
<pre class="">static uint16 EepTimer;<u class=""></u><u class=""></u></pre>
<pre class="">static uint16 EepRemainingBytes;<u class=""></u><u class=""></u></pre>
<pre class="">#define EEP_STOP_SEC_VAR_16BIT<u class=""></u><u class=""></u></pre>
<pre class="">#include "MemMap.h""<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">Section 8.2.2, MEMMAP005:<u class=""></u><u class=""></u></pre>
<pre class="">"The file MemMap.h shall provide a mechanism to select different code, variable<u class=""></u><u class=""></u></pre>
<pre class="">or constant sections by checking the definition of the module specific memory<u class=""></u><u class=""></u></pre>
<pre class="">allocation key words for starting a section [...]"<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">In practice MemMap.h can reach several MBs and can be included several thousand<u class=""></u><u class=""></u></pre>
<pre class="">times causing an overflow in the source location space.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">The problem does not occur with GCC because it tracks line numbers rather than<u class=""></u><u class=""></u></pre>
<pre class="">file offsets. Column numbers are tracked separately and are optional. I.e., in<u class=""></u><u class=""></u></pre>
<pre class="">GCC a source location can be either a (line+column) tuple packed into 32 bits or<u class=""></u><u class=""></u></pre>
<pre class="">(when the line number exceeds a certain threshold) a 32-bit line number.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">We are looking for an acceptable way of resolving the problem and propose the<u class=""></u><u class=""></u></pre>
<pre class="">following approaches for discussion:<u class=""></u><u class=""></u></pre>
<pre class="">1. Use 64 bits for source location tracking.<u class=""></u><u class=""></u></pre>
<pre class="">2. Track until an overflow occurs after that make the lexer output<u class=""></u><u class=""></u></pre>
<pre class=""> the <invalid location> special value for all subsequent tokens.<u class=""></u><u class=""></u></pre>
<pre class="">3. Implement an approach similar to the one used by GCC and start tracking line<u class=""></u><u class=""></u></pre>
<pre class=""> numbers instead of file offsets after a certain threshold. Resort to (2)<u class=""></u><u class=""></u></pre>
<pre class=""> when even line numbers overflow.<u class=""></u><u class=""></u></pre>
<pre class="">4. (?) Detect the multiple inclusion pattern and track it differently (for now<u class=""></u><u class=""></u></pre>
<pre class=""> we don't have specific ideas on how to implement this)<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">Is any of these approaches viable? What caveats should we expect? (we already<u class=""></u><u class=""></u></pre>
<pre class="">know about static_asserts guarding the sizes of certain class fields which start<u class=""></u><u class=""></u></pre>
<pre class="">failing in the first approach).<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">Other suggestions are welcome.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">I don't think any of the above approaches are reasonable; they would all require fundamental restructuring of major parts of Clang, an efficiency or memory size hit for all other users of Clang, or some combination of those.<u class=""></u><u class=""></u></pre>
<pre class=""> <u class=""></u><u class=""></u></pre>
<pre class="">Your code pattern seems unreasonable; including a multi-megabyte file thousands of times is not a good idea. Can you split out parts of MemMap.h into a separate header that is only included once, and keep only the parts that actually change on repeated inclusion in MemMap.h itself?<u class=""></u><u class=""></u></pre>
<pre class="">_______________________________________________<u class=""></u><u class=""></u></pre>
<pre class="">cfe-dev mailing list<u class=""></u><u class=""></u></pre>
<pre class=""><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">cfe-dev at lists.llvm.org</span></a><mailto:<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">cfe-dev at lists.llvm.org</span></a>><u class=""></u><u class=""></u></pre>
<pre class=""><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</span></a><u class=""></u><u class=""></u></pre>
<pre class="">-------------- next part --------------<u class=""></u><u class=""></u></pre>
<pre class="">An HTML attachment was scrubbed...<u class=""></u><u class=""></u></pre>
<pre class="">URL: <<a href="http://lists.llvm.org/pipermail/cfe-dev/attachments/20191010/bc5ff8cd/attachment.html" target="_blank" class=""><span style="color:rgb(5,99,193)" class="">http://lists.llvm.org/pipermail/cfe-dev/attachments/20191010/bc5ff8cd/attachment.html</span></a>><u class=""></u><u class=""></u></pre>
<div class="">
<div class=""><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
</div>
<div class=""><p class="MsoNormal"><span style="font-size:9pt;font-family:Helvetica,sans-serif" class="">_______________________________________________<br class="">
cfe-dev mailing list<br class="">
</span><a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class=""><span style="font-size:9pt;font-family:Helvetica,sans-serif;color:rgb(5,99,193)" class="">cfe-dev@lists.llvm.org</span></a><span style="font-size:9pt;font-family:Helvetica,sans-serif" class=""><br class="">
</span><a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class=""><span style="font-size:9pt;font-family:Helvetica,sans-serif;color:rgb(5,99,193)" class="">https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</span></a><u class=""></u><u class=""></u></p>
</div>
</div>
</blockquote>
</div>
</div>
</blockquote>
</div><p class="MsoNormal"> <u class=""></u><u class=""></u></p>
</div>
</div><p class="MsoNormal">_______________________________________________<br class="">
cfe-dev mailing list<br class="">
<a href="mailto:cfe-dev@lists.llvm.org" target="_blank" class="">cfe-dev@lists.llvm.org</a><br class="">
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" target="_blank" class="">https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a><u class=""></u><u class=""></u></p>
</blockquote>
</div>
</div>
</div>
</div>
</blockquote></div></div>
</div></blockquote></div><br class=""></div></div></body></html>