nhaehnle added a comment. In D83088#2225415 <https://reviews.llvm.org/D83088#2225415>, @dblaikie wrote:
>>> But I guess coming back to the original/broader design: What problems is >>> this intended to solve? The inability to write non-template algorithms over >>> graphs? What cost does that come with? Are there algorithms that are a bit >>> too complicated/unwieldy when done as templates? >>> If it's specifically the static/dynamic dispatch issue - I'm not sure the >>> type erasure and runtime overhead may be worth the tradeoff here, though if >>> it is - it'd be good to keep the non-dynamic version common, rather than >>> now having GraphTraits and CfgTraits done a bit differently, etc. >> >> It's not just over graphs, but taking SSA values into account as well -- >> that is the key distinction between GraphTraits and CfgTraits. > > Not sure I follow - could you give an example of a graph where the > GraphTraits concept of the Graph and the CfgTraits concept of the graph (or, > perhaps more importantly - features of the graph/API surface area/properties > you can expose through the CFG API/concept/thing but not through GraphTraits? See below. >> The most immediate problem is divergence analysis, which is extremely >> complex and difficult to get right. If I had tried to fight the accidental >> complexity that comes with attempting to write such an algorithm as C++ >> templates in addition to the inherent complexity of the algorithm at the >> same time, I'm not sure I would have been able to produce anything workable >> at all. >> >> Frankly, I suspect that our dominator tree implementation also suffer >> because of this, though at least dominator trees are much more well studied >> in the academic literature, so that helps keep the inherent complexity under >> control. > > I'm totally open to discussing making APIs more usable, for sure - though I'm > thinking it's likely a concept (like containers in the C++ standard library) > might be the better direction. > > Perhaps some code samples showing how one would interact (probably not whole > algorithms - maybe something simple like generating a dot diagram for a > graph) with these things given different APIs (traits, concepts, and runtime > polymorphism) - and implementations of each kind too. Take a look here for example: https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/lib/Analysis/GenericConvergenceUtils.cpp#L499 -- this is obviously still fairly simple, but it's an example of printing out the results of an analysis in a way that's generic over the underlying CFG and SSA form. A statically polymorphic wrapper is here: https://github.com/nhaehnle/llvm-project/blob/715450fa7f968ceefaf9c3b04b47066866c97206/llvm/include/llvm/Analysis/GenericConvergenceUtils.h#L569 The simple example might be bearable writing as a template, precisely because it's simple -- so only looking at simple examples is unlikely to really capture the motivation. Really what the motivation boils down to is stuff like this: https://github.com/nhaehnle/llvm-project/blob/controlflow-wip-v7/llvm/lib/Analysis/GenericUniformAnalysis.cpp -- I don't fancy writing all this as a template. Thid motivation would essentially go away if C++ could type-check against traits in the way that Rust and other languages like it can -- but it can't, so here we are. Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D83088/new/ https://reviews.llvm.org/D83088 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
