<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><br><div><div>On Jun 21, 2013, at 1:12 PM, David Blaikie <<a href="mailto:dblaikie@gmail.com">dblaikie@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><div style="letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;">On Fri, Jun 21, 2013 at 12:33 PM, Manman Ren <<a href="mailto:mren@apple.com">mren@apple.com</a>> wrote:<br><blockquote type="cite"><br>On Jun 21, 2013, at 11:56 AM, Eric Christopher wrote:<br><br><blockquote type="cite">On Fri, Jun 21, 2013 at 11:50 AM, Manman Ren <<a href="mailto:mren@apple.com">mren@apple.com</a>> wrote:<br><blockquote type="cite"><br>On Jun 21, 2013, at 11:35 AM, Eric Christopher wrote:<br><br><blockquote type="cite">On Thu, Jun 20, 2013 at 10:52 PM, Manman Ren <<a href="mailto:mren@apple.com">mren@apple.com</a>> wrote:<br><blockquote type="cite"><br>A summary of options for issue #3:<br>3> To actually access the MDNode referenced via the hash value, we need to perform a lookup from the hash value to find the corresponding MDNode.<br>The questions are where to store this map and how to keep it up-to-date when a MDNode is replaced.<br>---------------------<br>Option a) a map in DwarfDebug, AsmWriter and DIBuilder, modify access functions in DI classes to pass in the map.<br>May need to modify printing functions in AsmWriter.<br></blockquote><br>You may not need the map in DIBuilder if you piggy back on the<br>existing map in CGDebugInfo.cpp. The AsmWriter stuff is unfortunate<br>for just debug dumps of the IR. A way around this might be nice, but<br>I've not looked into it.<br></blockquote></blockquote></blockquote><br>Calling dump() on a MDNode inside gdb will not give us the derived type information, since we don't have a handle to the map.<br></blockquote><br>The only case where dump currently navigates a type link that I know<br>is printing derived types, where we print "[from foo]". By just<br>printing the string identifier for the type (without having to<br>navigate the link/use the map) should be about as useful here.<br><br><blockquote type="cite"><br><blockquote type="cite"><blockquote type="cite"><blockquote type="cite"><br><blockquote type="cite">---------------------<br>Option b) I am going to expand David's description with more details, correct me if I am wrong.<br></blockquote><br>I'll let David continue this part of the thread with you.<br><br><blockquote type="cite"><br>I personally prefer option b over a since it is much cleaner.<br><br></blockquote><br>Option b is more general and should probably work. I suggested a<br>originally because I know it would work and the impact is limited to<br>debug info. Also it doesn't involve touching the generic metadata<br>interface or code and could be done quickly and incrementally. b may<br>also require further changes to the debug info infrastructure to deal<br>with lookup, etc so may end up being as much churn as a. b is more<br>useful if we think other users of metadata may want/need similar<br>functionality in the future.<br><br>I'm fine with b as a choice, but it's going to involve more planning<br>and code review and involve people outside of you, me and Dave :)<br></blockquote><br>Got it. David, are you okay with the details I added about option b?<br>Let's start a new thread with title "Proposal: extend Metadata (MDNode) to support MDHash" or something like that.<br></blockquote><br>I'd like to hear a rationale for wanting b first. I don't know (and<br>can think of) any other users of this functionality right now.<br></blockquote><br>I will try my best :]<br>MDNode has a list of operands, one MDNode's full content can be thought of as a graph, when there is a reference to another MDNode, we have<br>an edge. The MDHash can be used to give a unique id (or string) to the full content of the graph.<br><br>The hash value applies to any kind of MDNode with complicated MDNode references.<br><br>If you think this is not general enough to be in MDNode,<br></blockquote><br>Eric's concern/question is whether it's a feature that would be useful<br>to any other code, I believe. (I'm less concerned about this so long<br>as the feature is appropriately general, even if it doesn't have any<br>other consumers at the moment - I don't think it'd drastically<br>complicate the Metadata handling code (which I think is currently<br>fairly simple, but I admit to not knowing it in any great detail))<br></div></blockquote><div><br></div>Yes, I tried to explain why MDHash can help with MDNodes that form a complicated graph.</div><div> <br><blockquote type="cite"><div style="letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br><blockquote type="cite">my earlier proposal of extending MDNode to DINode is going the other direction.<br></blockquote><br>As discussed, this isn't far enough in the other direction. If we're<br>going to touch core LLVM Metadata handling code at all, it needs to be<br>a complete/cohesive feature, not just tendrils of a debug info<br>feature. Hence (a) or (b) not (c).<br><br><blockquote type="cite">Basically, MDNode will have an opcode like the opcode for Instruction, to support TBAA, DI, and other types.<br>Inside streamers (bc ll reader), we can create the specialized class according to the opcode.<br>That requires a lot of changes too :(<br><br><blockquote type="cite"><br><blockquote type="cite">We can add a weight to MDHash (other names are fine with me), to support multiple MDNodes with the same hash, but different weight.<br><br></blockquote><br>Wait, what? This sounds like a bad idea.<br></blockquote>Why?<br>The weight is needed to differentiate a forward declaration vs. a definition, they both name the same class, but they are different.<br></blockquote><br>This would probably tip me over into Eric's perspective that it would<br>be too esoteric a feature to add to a generic/core piece of<br>infrastructure.<br></div></blockquote><div><br></div>If we allow the map to map one hash value (or string) to multiple MDNodes, without adding the weight, it should still work.</div><div>But is that general enough?</div><div><br></div><div>Thanks,</div><div>Manman</div><div> <br><blockquote type="cite"><div style="letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><br>Yes, I'm not sure we should resolve duplicates in this case, then<br>(short of assigning a separate identifier to declarations V<br>definitions so they don't collide/get deduped - then doing a pass in<br>DwarfDebug/during debug-info-generation time to resolve in favor of<br>definitions (hmm, yeah, even that doesn't quite make sense - you'd<br>have to be able to visit the things referring to the declarations &<br>update them to refer to definitions, and we'd have no real way to<br>discover those easily except walking all the debug info... could<br>work))<br><br><blockquote type="cite"><br>Thanks,<br>Manman<br><br><blockquote type="cite"><br>-eric<br><br><blockquote type="cite">Thanks,<br>Manman<br><br><blockquote type="cite"><br>-eric<br><br><br><blockquote type="cite">Thanks,<br>Manman<br><br>On Jun 20, 2013, at 5:39 PM, David Blaikie wrote:<br><br><blockquote type="cite">On Thu, Jun 20, 2013 at 5:25 PM, Manman Ren <<a href="mailto:mren@apple.com">mren@apple.com</a>> wrote:<br><blockquote type="cite"><br>On Jun 20, 2013, at 5:18 PM, David Blaikie <<a href="mailto:dblaikie@gmail.com">dblaikie@gmail.com</a>> wrote:<br><br>On Thu, Jun 20, 2013 at 5:13 PM, Manman Ren <<a href="mailto:mren@apple.com">mren@apple.com</a>> wrote:<br><br><br>On Jun 20, 2013, at 4:52 PM, David Blaikie wrote:<br><br>On Thu, Jun 20, 2013 at 4:45 PM, Manman Ren <<a href="mailto:mren@apple.com">mren@apple.com</a>> wrote:<br><br><br>On Jun 20, 2013, at 3:55 PM, Manman Ren <<a href="mailto:mren@apple.com">mren@apple.com</a>> wrote:<br><br><br>On Jun 20, 2013, at 2:58 PM, Eric Christopher wrote:<br><br>Hi Manman,<br><br>On Thu, Jun 20, 2013 at 2:51 PM, Manman Ren <<a href="mailto:mren@apple.com">mren@apple.com</a>> wrote:<br><br><br>The intent of this proposal is to speedup compilation of "-flto -g" for c++<br>programs.<br>This is based on discussions with Adrian, David and Eric.<br><br><br>Thanks for bringing this back to the list. The original thread was<br>getting quite long.<br><br>---------------------------<br>Problem:<br>A single class can be used in multiple source files and the DI (Debug Info)<br>class is included in multiple bc files. The duplication of<br>class definitions causes blow-up in # of MDNodes, # of DIEs, leading to<br>large memory requirement.<br><br>As an example, SPEC xalancbmk requires 7GB of memory when compiled with<br>-flto -g.<br>With a preliminary implementation of type uniquing, the memory usage will be<br>down to 2GB.<br><br>In order to unique types, we have to break cycles in the MDNodes.<br><br>A simple struct definition<br>struct Base {<br>int a;<br>};<br>can cause cycles in MDNodes:<br>!12 = metadata !{i32 786451, metadata !13, null, metadata !"Base", i32 1,<br>i64 32, i64 32, i32 0, i32 0, null, metadata !14, i32 0, null, null} ; [<br>DW_TAG_structure_type ] [Base] [line 1, size 32, align 32, offset 0] [from ]<br>!14 = metadata !{metadata !15, metadata !16}<br>!15 = metadata !{i32 786445, metadata !13, metadata !12, metadata !"a", i32<br>2, i64 32, i64 32, i64 0, i32 0, metadata !8} ; [ DW_TAG_member ] [a] [line<br>2, size 32, align 32, offset 0] [from int]<br>!16 = metadata !{i32 786478, metadata !13, metadata !12, metadata !"Base",<br>metadata !"Base", metadata !"", i32 1, metadata !17, i1 false, i1 false, i32<br>0, i32 0, null, i32 320, i1 false, null, null, i32 0, metadata !20, i32 1} ;<br>[ DW_TAG_subprogram ] [line 1] [Base]<br><br>Cycles: !12 -- !14 -- !15 -- !12<br> !12 -- !14 -- !16 -- !12<br><br>These cycles make it hard to unique the same struct used in two bc files.<br><br>---------------------------<br>How to fix:<br><br>We attach a hash value to types to help type uniquing and we also replace<br>references to types with their hash values.<br>For the above struct "Base", we now have the following MDNodes:<br>!4 = metadata !{i32 786451, metadata !5, null, metadata !"Base", i32 1, i64<br>32, i64 32, i32 0, i32 0, null, metadata !6, i32 0, i32 0, null, i32<br>915398439} ; [ DW_TAG_structure_type ] [Base] [line 1, size 32, align 32,<br>offset 0] [from ]<br>!6 = metadata !{metadata !7, metadata !9}<br>!7 = metadata !{i32 786445, metadata !5, i32 915398439, metadata !"a", i32<br>2, i64 32, i64 32, i64 0, i32 0, metadata !8} ; [ DW_TAG_member ] [a] [line<br>2, size 32, align 32, offset 0] [from int]<br>!9 = metadata !{i32 786478, metadata !5, i32 915398439, metadata !"Base",<br>metadata !"Base", metadata !"", i32 1, metadata !10, i1 false, i1 false, i32<br>0, i32 0, null, i32 320, i1 false, null, null, i32 0, metadata !13, i32 1} ;<br>[ DW_TAG_subprogram ] [line 1] [Base]<br><br>Note that the cycles are gone and !4 has a hash value of 915398439, and the<br>references to !4 are replaced with 915398439.<br>Thanks Eric for suggesting replacing MD reference with a hash value.<br><br><br>In particular I recommended this:<br><br>a) For C++ odr replace it with the "hash" that's just a string<br>representing the type name.<br>b) For Internal C++ types and all C types replace it with a string<br>that's a concatenation of the type name and the name of the compile<br>unit.<br><br>Yes, that is what we agreed on over email.<br><br><br><br>There are a few issues:<br>1> How to generate the hash for a given type?<br>With C++'s ODR, it should be enough by using the context and the name for<br>non-internal c++ types.<br>For internal c++ types and types of other languages, hash will not be used.<br><br><br>Explain this?<br><br><br>For a while, I am going to support both hash and MD reference, once<br>everything is working with hash,<br>I will update all debug info testing cases, turn -gtype-uniquing on, and<br>remove the other path.<br><br>For internal c++ types, initially they will follow the path of using MD<br>references without a hash.<br><br><br>My current implementation is to add a few static member functions in MDNode<br>to profile DI nodes differently.<br>+ /// If the array of Vals is for debug info, profile it specially and<br>return true.<br>+ /// If the DI node has a hash value, generate the profile using only the<br>hash value and the declaration flag.<br>+ static bool profileDebugInfoNode(ArrayRef<Value*> Vals, FoldingSetNodeID<br>&ID);<br><br>+ /// If the MDNode is for debug info, profile it specially and return true.<br>+ /// If the DI node has a hash value, generate the profile using only the<br>hash value and the declaration flag.<br>+ static bool profileDebugInfoNode(const MDNode *M, FoldingSetNodeID &ID);<br><br>+ /// Given a hash value and a flag, generate the profile for later lookup.<br>+ static bool profileDebugInfoNode(unsigned Hash, bool Declaration,<br>FoldingSetNodeID &ID);<br><br>These static functions are called in Metadata.cpp:<br>void MDNode::Profile(FoldingSetNodeID &ID) const {<br>+ if (profileDebugInfoNode(this, ID))<br>+ return;<br>+<br><br>There are other examples of these in MDNode for handling of specific<br>metadata.<br>/// Methods for metadata merging.<br>static MDNode *getMostGenericTBAA(MDNode *A, MDNode *B);<br>static MDNode *getMostGenericFPMath(MDNode *A, MDNode *B);<br>static MDNode *getMostGenericRange(MDNode *A, MDNode *B);<br><br>Comments are welcome on whether this violates any layering rule.<br><br><br>As I've said many times in email, I don't think this is a good idea<br>and would prefer either a or b below. a) is a much simpler solution.<br><br>Any reason that why it is not a good idea?<br><br><br>Other choices are:<br>a> Keep a map in DwarfDebug<br>Keep in mind that the map is used at many stages, and it has to be in sync<br>with MDNodeSet.<br>b> Generalize MDNode to be aware of hash (David can provide more details)<br>c> Extend MDNode to DINode and modify streamers (bitcode reader|writer, ll<br>reader|writer) to be aware of DINode<br>We can provide DINode::get(…) to create a DINode. DINode can have its own<br>Profile function.<br>Other suggestions are welcome.<br><br><br>a or b please.<br><br>Option a> will require a DwarfDebug pointer in every stage of the compiler,<br>and passing the map to the DI classes.<br>A rough estimation is around 100 places.<br>Is it reasonable to pass a DwarfDebug pointer to DIBuilder and llvm linker?<br>Also the map needs to be in sync with MDNodeSet, maybe using ValueHandle can<br>solve the problem.<br><br><br>What about putting the map in LLVMContextImpl?<br>It already has a few things specifically for debug info:<br>std::vector<DebugRecVH> ScopeRecords;<br>DenseMap<std::pair<MDNode*, MDNode*>, int> ScopeInlinedAt;<br>…<br><br>I remember David mentioned it once and I forgot about the conclusion.<br><br><br>I mentioned it only as speculation as to how you were implementing it<br>already (but you were doing the profile-changing stuff).<br><br>I don't think it should be necessary to have the map (in option (a))<br>in such a central location as LLVMContext. It should be usable just<br>from DwarfDebug for generation, and DIBuilder can have its own,<br>separate map to do similar things during DI building.<br><br><br>We also need the map during llvm linking since linking will create new<br>MDNodes.<br><br><br>I don't understand what you mean by this. IR linking shouldn't need to<br>do anything debug-info-specific, it should just be the normal IR<br>approach.<br><br>The declaration-v-definition resolution can be done at codegen-time.<br>We'll have to walk all the lists of retained types anyway to build the<br>map, so we can do declaration-v-definition (keep definitions over<br>declarations when we see both) at that point.<br><br><br>Yes, you are right that at codegen-time, we can generate the map from the<br>lists<br>of retained types.<br><br>But dumping the linked ll file requires the map when outputting comments of<br>the MDNode :]<br></blockquote><br>Depending on which things we print out, but yes, in some cases<br>(derived types) we do print out the type referenced. I assume the<br>AsmPrinter can build such a map, then. (in fact, with a few clients<br>like this, it might be nice to build a bit of an abstraction around it<br>rather than just using a raw map - something that has a ctor (or I<br>suppose it could be a factory function) that reads in the right<br>metadata, walks the compile units, etc, and builds the mapping)<br><br><blockquote type="cite"><br>Thanks,<br>Manman<br><br><br>So any other opinion on putting it in LLVMContext other than it being<br>central?<br><br>Thanks,<br>Manman<br><br><br><br>Thanks,<br>Manman<br><br><br>More details for option b from David<br><br>< The alternative I have in mind is a more complete version of what<br>< you're proposing - a full MD feature, not an MD feature that's just<br>< barely enough to support the needs of debug info. What we could do is<br>< allow the insertion of these MDHash things you spoke about but take it<br>< a step further and have MDNode::getOperand walk through the hash &<br>< give the value (in this way, DebugInfo wouldn't have to change at all<br>< to handle hashes - if the Metadata APIs are going to be aware of the<br>< hashes anyway, they might as well provide this convenience<br>< functionality) the metadata feature would also have to have some<br>< blessed top-level named metadata that would have a list of hash+MDNode<br>< to keep those MDNodes alive (so you wouldn't have to stuff all the<br>< types in the retained types list - metadata would provide the full<br>< support, not just half of it).<br><br><br><br>Transition from current DI Metadata:<br>To have a smooth transition, I will add a flag "-gtype-hashing" for the type<br>uniquing work and turn it on by default when we are ready.<br><br><br>I'd prefer just make the change to have the front end emit the "hash"<br>(it's not really a hash, it's just a string).<br><br>Are you saying no transition period? A single patch to have correct handling<br>of "hash" and to update all existing testing cases?<br><br><br>-----------------------------<br>Patches:<br>Expect the following patches:<br>1> add flag -gtype-hashing<br>2> add hash field to DI types<br>3> modify DIBuilder to use hash instead of MD reference<br>4> related to issue 3<br><br><br>These can all be a single patch since it shouldn't be very large if we<br>go with a) above. If we go with b) then the MDNode work should be done<br>in isolation first and then the debug info on top of it.<br><br>What is wrong with smaller patches?<br>My estimation for all the above with a) is about 30K + testing cases.<br><br><br>5> backend change (in DwarfDebug|CompileUnit) to support types shared among<br>compile units<br>requires gdwarf-2 gdwarf-3 gdwarf-4 support for issues related to ref_addr<br><br><br>#5 can and should be done before the rest of them.<br><br>I prefer to submit patches according to the flow of the compiler, starting<br>from the frontend, then IR, then backend.<br>The testing cases will be added for front end, llvm-link and backend.<br>Any reason why #5 should be done first?<br><br><br>All changes should be local to debug info classes except patch #4.<br><br><br>What's patch #4?<br><br>Patch #4 above: related to issue 3 (changes corresponding to how to solve<br>issue #3)<br><br>-Manman<br><br><br>-eric<br><br><br><br>_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br><br><br><br>_______________________________________________<br>llvm-commits mailing list<br>llvm-commits@cs.uiuc.edu<br>http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits</blockquote></blockquote></blockquote></blockquote></blockquote></blockquote></blockquote></div></blockquote></div><br></body></html>