C++ optimization problem

[gitoleg]

I would like to discuss the next problem connected with CIR C++ optimizations and CIR in general.

We started to develop an optimization for the next simple case (but it's common for large C++ codebases): once a vector instance is created on every loop iteration, we may want to hoist it from the loop and call the clear method every time instead.

Example:

for (...) {
    vector<int> v;
    ...
}

Replace with:

{ // add extra scope
  vector<int> v;
  for (...) {
    v.clear();
    ...
  }
}

Instead of N allocations we would have only one. Extra scope is added in order to preserve the semantics, so the ~vector() will be called as soon as possible and no impact on the following code would happen. It looks pretty clear and easy, right?

There are several problems though. We need to attach attributes to vector ctor and dtor in order to identify them later. (maybe we start to mangle too early?)

But the most significant problem we faced is that clear method is not instantiated in the toy example - so it may be the same case for the real code, i.e. I can not just insert it in the loop body region.

And here are some approaches I can think of:

1. The most easiest one - just apply the optimization once the method exists in the translation unit. This may work only if there is a vector instantiated with the same type and the clear method is called. I would not rely on it.
2. Use two stage compilation - first find if the optimization makes sense, dump some info in file (e.g. json: "vector" : ["clear"]) and then read it on the second stage and force the method instantiation, and apply the code transformation. But we need to patch AST generation somehow - so the method will appear in CIR after. I have some doubts here either.

I believe that it's not some special case and soon or later someone else will face with the similar problem - many CIR C++ related optimizations will be different from common LLVM IR ones - probably we will add, remove and replace something basing on our knowledge of stdlib.

So what do you think about how to do it? Are there any better approaches? Or steps to perform? Any thoughts would be helpful :)

[bcardosolopes]

Thanks for the write up, very excited to see the path beginning to get paved here.

It looks pretty clear and easy, right?

I'm always skeptical on "easy" when it's related to C++ lol

We need to attach attributes to vector ctor and dtor in order to identify them later. (maybe we start to mangle too early?)

Have you looked into clang/lib/CIR/Dialect/Transforms/IdiomRecognizer.cpp? My suggestion is to (1) raise vector ctor and dtor in that pass, to perhaps something like cir.std.vector.ctor, etc (see StdFindOp and others in clang/include/clang/CIR/Dialect/IR/CIRStdOps.td). It's possible you might need to add an input argument attribute to keep the mangled name around. We had discussions in the past about having more generic higher level operations for ctors and dtor calls, but perhaps we should start with specific ones before we generalize.

Once it's raised, then it's time to teach (2) clang/lib/CIR/Dialect/Transforms/LibOpt.cpp to check for the optimization opportunity and apply it if it makes sense.

The most easiest one - just apply the optimization once the method exists in the translation unit

I would start with this and reject the optimization in case it isn't available. You could raise it to cir.std.vector.clear operations during idiom recognition to make it easier to use it in case it's profitable to apply.

Use two stage compilation ... I believe that it's not some special case and soon or later someone else will face with the similar problem ....

Super agree, but my two cents is to go incremental and experiment with the easier cases before we get into harder ones. A possible list of other ideas:

• Have a hardcoded list of mangled names based on the known libraries (libc++, libstdc++, etc) and types (int, char, etc) and emit cir.std.vector.clear with those names attached for later lowering into calls. Provide the actual body for the function in another module you can link to later. (this is more or less your JSON idea, but without the two step compilation).
• Codegen the templated functions into "generic" CIR functions we could use for later instantiating into "specific" CIR function. We could trigger codegen for these "generic" functions based on a list of methods we care about (e.g. like vector<T>::clear). This is probably hard to implement, given that we have no support for in CIR to build a "generic" function, but it could be one possible future.
• Create fake AST nodes that call into vector::clear and ask Sema to solve it, codegen the result. This is even more complicated because at CIRGen time Sema is gone, with all the complex state it has to reason on how instantiations might affect other parts of the code. If we'd do this it would have to be early somehow.

So what do you think about how to do it? Are there any better approaches? Or steps to perform? Any thoughts would be helpful

Something else that comes to mind is correctness guarantees on the language side (you will be changing program semantics by potentially changing the order of side effects). This will probably be a whole set of optimizations that the user needs to buy-in to the level of aggressiveness they might want their compiler to perform - not super worried about that because it's not something that will be on by default, but just a heads up of potential concerns (and bikeshedding with purists).

More folks that might be interested in the topic: @xlauko @andykaylor @lanza @dkolsen-pgi @philnik777 @erichkeane

[dkolsen-pgi]

To me this seems like an optimization that should be done by clang-tidy or a similar tool, so the user has a chance to accept or reject the optimization. That way the user can learn to recognize this pattern and write the optimized code from the beginning in the future.

If the v.clear() call is inserted at the beginning of the loop body, then the elements in the vector from one iteration aren't destroyed until the next iteration has started, after the increment code and comparison code has run. That's a very subtle change in semantics that is unlikely to affect anything; but if it does affect the behavior the user will be absolutely furious at the compiler for doing that. To destroy the elements at the correct time, all the calls to the vector destructor within the loop should be replaced by a call to v.clear().

If the calls to clear() are done correctly, then the only other semantic change that concerns me is that the pattern of calls to the allocator will change. That could be noticeable if the vector has a custom allocator. So I think this optimization should be done only when the vector uses std::allocator, in which case the changes to the pattern of allocations is not observable.

Unfortunately I don't have suggestions for how to actually implement this. It will be challenging.

first find if the optimization makes sense, dump some info in file (e.g. json: "vector" : ["clear"]) and then read it on the second stage

No. Neither side files nor running the compiler (or parts thereof) multiple times will be acceptable.

[gitoleg]

good, thank you guys!

I think we'll start from something simple, and maybe will have hardcoded list of mangled names or names provided by command line interface, will see.

To me this seems like an optimization that should be done by clang-tidy

well, there are more optimizations I can think of, and the suggested one is just a simplest one. And we need to find an approach and move forward in order to make it possible to implement more complex optimizations in future.

To destroy the elements at the correct time ...

Awesome, thanks for this point!