Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Create a pass which, given a class with bases, tries to replace uses of it with uses of it's bases #261

Open
mizvekov opened this issue Sep 19, 2023 · 9 comments

Comments

@mizvekov
Copy link
Contributor

I have observed that sometimes reduction results in deep class hierarchies:

.......................
class p : o {
  using bj = o;
  using bj::bj;
};
class J : p {
  using bj = p;
  using bj::bj;
};
class q : J {
  using bj = J;
  using bj::bj;
};
class r : q {
  using bj = q;
  using bj::bj;
};
class s : r {
  using bj = r;
  using bj::bj;
};
class t : s {
  using bj = s;
  using bj::bj;
};
class F {
public:
  template <a<c<1>::d, int> = 0> F() : bt(g<0>) {}
  t bt;
};
int main() { F k; }

I think the simplest thing here would be to try replacing uses of a class with uses of the bases of that class.

@regehr
Copy link
Member

regehr commented Sep 20, 2023

yes that would be desirable. I'll just add that we're not too likely to get to this anytime soon since we don't have people working on C-Reduce at the moment.

@mpflanzer
Copy link
Contributor

There is already a very similar pass, currently restricted to base class templates:

"This pass tries to replace a class with its base class if \n\

@regehr what do you think of making this pass more generic? Or would you prefer a separate pass?

@regehr
Copy link
Member

regehr commented Sep 20, 2023

if there's no loss of reduction power, I think keeping it all in the same pass is great. thanks!

@mpflanzer
Copy link
Contributor

Yesterday I actually overlooked that there is already another pass removing base classes:

static const char *DescriptionMsg =

On the example above it does remove p and J if I just run clang_delta in a loop on it. But on the third iteration it messes up the class structure and produces an invalid file. 🤔 If I find some more time I'll dig a bit more into it.

@mizvekov could you try to run c-reduce again on your example? I'm surprised that it didn't manage to produce a slightly smaller file based on the pass I found. Could it be that your interestingness test is actually preventing it from getting smaller?

@mizvekov
Copy link
Contributor Author

I have used creduce 2.11.0, provided by the msys2 environment.

Here is the full resulting reduced file:

template <bool, class> using a = int;
template <int b> struct c {
  static const int d = b;
};
template <size_t> struct e {};
template <size_t f> e<f> g;
struct h {
  template <class ak> static auto j(ak) {
    auto a = l<ak>;
    a();
  }
  template <class> static auto l() {}
};
class m {
public:
  template <size_t i> m(e<i>) {}
};
class n : m {
  using bj = m;

public:
  using bj::bj;
  ~n() {
    h::j([] {});
  }
};
class o : n {
  using bj = n;
  using bj::bj;
};
class p : o {
  using bj = o;
  using bj::bj;
};
class J : p {
  using bj = p;
  using bj::bj;
};
class q : J {
  using bj = J;
  using bj::bj;
};
class r : q {
  using bj = q;
  using bj::bj;
};
class s : r {
  using bj = r;
  using bj::bj;
};
class t : s {
  using bj = s;
  using bj::bj;
};
class F {
public:
  template <a<c<1>::d, int> = 0> F() : bt(g<0>) {}
  t bt;
};
int main() { F k; }

Running creduce another time on it produces no changes.

Here is the full output of that:

===< 35026 >===
running 1 interestingness test in parallel
===< pass_unifdef :: 0 >===
===< pass_comments :: 0 >===
===< pass_ifs :: 0 >===
===< pass_includes :: 0 >===
===< pass_line_markers :: 0 >===
===< pass_blank :: 0 >===
(0.2 %, 924 bytes)
===< pass_clang_binsrch :: replace-function-def-with-decl >===
===< pass_clang_binsrch :: remove-unused-function >===
===< pass_lines :: 0 >===
(3.2 %, 896 bytes)
===< pass_lines :: 1 >===
(-6.6 %, 987 bytes)
===< pass_lines :: 2 >===
(-14.3 %, 1058 bytes)
===< pass_lines :: 3 >===
(-21.2 %, 1122 bytes)
===< pass_lines :: 4 >===
(-28.0 %, 1185 bytes)
===< pass_lines :: 6 >===
(-34.8 %, 1248 bytes)
===< pass_lines :: 8 >===
(-41.6 %, 1311 bytes)
===< pass_lines :: 10 >===
(-48.4 %, 1374 bytes)
===< pass_clang_binsrch :: replace-function-def-with-decl >===
===< pass_clang_binsrch :: remove-unused-function >===
===< pass_clang :: remove-unused-function >===
===< pass_balanced :: curly >===
===< pass_balanced :: curly2 >===
===< pass_balanced :: curly3 >===
===< pass_balanced :: parens-to-zero >===
===< pass_clang :: callexpr-to-value >===
===< pass_clang :: replace-callexpr >===
===< pass_clang :: simplify-callexpr >===
===< pass_clang :: remove-unused-enum-member >===
===< pass_clang :: remove-enum-member-value >===
===< pass_clang_binsrch :: remove-unused-var >===
===< pass_special :: a >===
===< pass_special :: b >===
===< pass_special :: c >===
===< pass_include_includes :: 0 >===
===< pass_ternary :: b >===
===< pass_ternary :: c >===
===< pass_balanced :: curly >===
(cache hit for /home/mizve/clang_bugs/funsan/test.cc)
===< pass_balanced :: curly2 >===
(cache hit for /home/mizve/clang_bugs/funsan/test.cc)
===< pass_balanced :: curly3 >===
(cache hit for /home/mizve/clang_bugs/funsan/test.cc)
===< pass_balanced :: parens >===
===< pass_balanced :: angles >===
===< pass_balanced :: square >===
===< pass_balanced :: curly-inside >===
(-47.5 %, 1366 bytes)
(-46.8 %, 1359 bytes)
(-46.0 %, 1352 bytes)
(-45.4 %, 1346 bytes)
(-44.6 %, 1339 bytes)
===< pass_balanced :: parens-inside >===
===< pass_balanced :: angles-inside >===
===< pass_balanced :: square-inside >===
===< pass_balanced :: curly-only >===
===< pass_balanced :: angles-only >===
===< pass_balanced :: square-only >===
===< pass_clang :: remove-namespace >===
===< pass_clang :: aggregate-to-scalar >===
===< pass_clang :: param-to-global >===
===< pass_clang :: param-to-local >===
===< pass_clang :: remove-nested-function >===
===< pass_clang :: union-to-struct >===
===< pass_clang :: return-void >===
===< pass_clang :: simple-inliner >===
Assertion failed: !isa<CXXConstructorDecl>(D) && "Use other ctor with ctor decls!", file D:/a/msys64/mingw64/include/clang/AST/GlobalDecl.h, line 61

***************************************************

pass_clang::simple-inliner has encountered a bug:
crashed: "/mingw64/libexec/clang_delta" --transformation=simple-inliner --counter=1 /tmp/creduce-AzKxm4/test.cc

Please consider tarring up /home/mizve/clang_bugs/funsan/creduce_bug_009
and mailing it to [email protected] and we will try to fix
the bug.

This bug is not fatal, C-Reduce will continue to execute.

***************************************************

===< pass_clang :: reduce-pointer-level >===
===< pass_clang :: lift-assignment-expr >===
===< pass_clang :: copy-propagation >===
===< pass_clang :: callexpr-to-value >===
===< pass_clang :: replace-callexpr >===
===< pass_clang :: simplify-callexpr >===
===< pass_clang :: remove-unused-function >===
===< pass_clang :: remove-unused-enum-member >===
===< pass_clang :: remove-enum-member-value >===
===< pass_clang_binsrch :: remove-unused-var >===
===< pass_clang :: simplify-if >===
===< pass_clang :: reduce-array-dim >===
===< pass_clang :: reduce-array-size >===
===< pass_clang :: move-function-body >===
===< pass_clang :: simplify-comma-expr >===
===< pass_clang :: simplify-dependent-typedef >===
===< pass_clang :: replace-simple-typedef >===
===< pass_clang :: replace-dependent-typedef >===
===< pass_clang :: replace-one-level-typedef-type >===
===< pass_clang :: remove-unused-field >===
===< pass_clang :: instantiate-template-type-param-to-int >===
===< pass_clang :: instantiate-template-param >===
===< pass_clang :: template-arg-to-int >===
===< pass_clang :: template-non-type-arg-to-int >===
===< pass_clang :: reduce-class-template-param >===
===< pass_clang :: remove-trivial-base-template >===
===< pass_clang :: class-template-to-class >===
===< pass_clang :: remove-base-class >===
===< pass_clang :: replace-derived-class >===
===< pass_clang :: remove-unresolved-base >===
===< pass_clang :: remove-ctor-initializer >===
===< pass_clang :: replace-class-with-base-template-spec >===
===< pass_clang :: simplify-nested-class >===
===< pass_clang :: remove-unused-outer-class >===
===< pass_clang :: empty-struct-to-int >===
===< pass_clang :: remove-pointer >===
===< pass_clang :: reduce-pointer-pairs >===
===< pass_clang :: remove-array >===
===< pass_clang :: remove-addr-taken >===
===< pass_clang :: simplify-struct >===
===< pass_clang :: replace-undefined-function >===
===< pass_clang :: replace-array-index-var >===
===< pass_clang :: replace-array-access-with-index >===
===< pass_clang :: replace-dependent-name >===
===< pass_clang :: simplify-recursive-template-instantiation >===
===< pass_clang :: vector-to-array >===
===< pass_lines :: 0 >===
(-41.6 %, 1311 bytes)
===< pass_lines :: 1 >===
(-51.4 %, 1402 bytes)
===< pass_lines :: 2 >===
(-59.1 %, 1473 bytes)
===< pass_lines :: 3 >===
(-66.0 %, 1537 bytes)
===< pass_lines :: 4 >===
(-72.8 %, 1600 bytes)
===< pass_lines :: 6 >===
(-79.6 %, 1663 bytes)
===< pass_lines :: 8 >===
(-86.4 %, 1726 bytes)
===< pass_lines :: 10 >===
(-93.2 %, 1789 bytes)
===< pass_unifdef :: 0 >===
===< pass_comments :: 0 >===
===< pass_ifs :: 0 >===
===< pass_special :: b >===
===< pass_special :: c >===
===< pass_indent :: regular >===
(-3.0 %, 954 bytes)
===< pass_balanced :: parens-to-zero >===
===< pass_clex :: rm-toks-1 >===
===< pass_clex :: rm-toks-2 >===
===< pass_clex :: rm-toks-3 >===
===< pass_clex :: rm-toks-4 >===
===< pass_clex :: rm-toks-5 >===
===< pass_clex :: rm-toks-6 >===
===< pass_clex :: rm-toks-7 >===
===< pass_clex :: rm-toks-8 >===
===< pass_clex :: rm-toks-9 >===
===< pass_clex :: rm-toks-10 >===
===< pass_clex :: rm-toks-11 >===
===< pass_clex :: rm-toks-12 >===
===< pass_clex :: rm-toks-13 >===
===< pass_clex :: rm-toks-14 >===
===< pass_clex :: rm-toks-15 >===
===< pass_clex :: rm-toks-16 >===
===< pass_clex :: rm-tok-pattern-4 >===
===< pass_clang :: local-to-global >===
===< pass_peep :: a >===
===< pass_peep :: c >===
===< pass_ints :: a >===
===< pass_ints :: b >===
===< pass_ints :: c >===
===< pass_ints :: d >===
===< pass_ints :: e >===
===< pass_balanced :: parens-only >===
===< pass_clex :: rename-toks >===
(-3.0 %, 954 bytes)
===< pass_clex :: delete-string >===
===< pass_clex :: define >===
Termination check: size was 926; now 954
===< pass_clang :: rename-fun >===
===< pass_clang :: rename-param >===
===< pass_clang :: rename-var >===
===< pass_clang :: rename-class >===
(-3.0 %, 954 bytes)
(-3.0 %, 954 bytes)
(-3.0 %, 954 bytes)
(-3.0 %, 954 bytes)
(-3.0 %, 954 bytes)
(-3.0 %, 954 bytes)
(-3.0 %, 954 bytes)
(-3.0 %, 954 bytes)
(-3.0 %, 954 bytes)
(-3.0 %, 954 bytes)
(-3.0 %, 954 bytes)
(-3.0 %, 954 bytes)
===< pass_clang :: rename-cxx-method >===
(-4.8 %, 970 bytes)
===< pass_clang :: combine-global-var >===
===< pass_clang :: combine-local-var >===
===< pass_clang :: simplify-struct-union-decl >===
===< pass_clang :: move-global-var >===
===< pass_clang :: unify-function-decl >===
===< pass_lines :: 0 >===
(-1.6 %, 941 bytes)
===< pass_clex :: rename-toks >===
(-1.6 %, 941 bytes)
(-1.6 %, 941 bytes)
(-1.6 %, 941 bytes)
(-0.8 %, 933 bytes)
(0.1 %, 925 bytes)
(0.1 %, 925 bytes)
(0.1 %, 925 bytes)
(0.1 %, 925 bytes)
(0.1 %, 925 bytes)
(0.1 %, 925 bytes)
(0.1 %, 925 bytes)
(0.1 %, 925 bytes)
(0.1 %, 925 bytes)
===< pass_clex :: delete-string >===
===< pass_indent :: final >===
(0.0 %, 926 bytes)
===================== done ====================

pass statistics:
  method pass_clang :: rename-cxx-method worked 1 times and failed 0 times
  method pass_blank :: 0 worked 1 times and failed 0 times
  method pass_indent :: final worked 1 times and failed 0 times
  method pass_indent :: regular worked 1 times and failed 0 times
  method pass_lines :: 10 worked 2 times and failed 268 times
  method pass_lines :: 8 worked 2 times and failed 268 times
  method pass_lines :: 2 worked 2 times and failed 212 times
  method pass_lines :: 6 worked 2 times and failed 268 times
  method pass_lines :: 3 worked 2 times and failed 268 times
  method pass_lines :: 1 worked 2 times and failed 188 times
  method pass_lines :: 4 worked 2 times and failed 268 times
  method pass_lines :: 0 worked 3 times and failed 108 times
  method pass_balanced :: curly-inside worked 5 times and failed 15 times
  method pass_clang :: rename-class worked 12 times and failed 0 times
  method pass_clex :: rename-toks worked 14 times and failed 6 times

You can see that it produced a single failure on simple-inliner clang pass. I have already submitted this bug report.
Even if that worked, I don't see how it could have helped though.

Here is my interestingness test:

#!/usr/bin/fish

export LLVM_SYMBOLIZER_PATH=/usr/bin/true

set -l clang "C:/PROGRA~1/LLVM/bin/CLANG_~1.EXE"
set -l args "-D_LIBCPP_NO_AUTO_LINK" "-std=gnu++23" "--target=x86_64-pc-windows-msvc" "-fno-exceptions" "-fsanitize=function" "-flto=thin" "-ggdb3" "-O0" "-fuse-ld=lld" "-o" "test.exe"

if ! $clang $args "test.cc" 2>&1;
  exit 1
end

set output (./test.exe 2>&1)
if test $status != 0;
  exit 1
end

if ! string match --quiet --regex "through pointer to incorrect function type" "$output";
  exit 1
end

This is running on llvm 17.0.1, but the bug this is looking for is present on llvm master as of today.

FWIW, I reduced this further manually to:

static auto l() {}
int main() {
  auto a = l;
  a();
}

And this is the MR that fixes this bug: llvm/llvm-project#66816

@regehr
Copy link
Member

regehr commented Sep 21, 2023

let's tag in @chenyang78 here on the off chance he has a minute to think about this!

@chenyang78
Copy link
Member

Hi folks, thank you for the discussion! It's probably due to that RemoveBaseClass pass does not really work well with templates. I am quite busy recently, but let me see if I could find some time later next month and play with it a bit.

@mpflanzer
Copy link
Contributor

I found one bug in the RemoveBaseClass pass which probably rendered it pretty much useless. 🤔 #263

Since I currently don't have a Windows setup ready with c-reduce I could not test if that also improves the reduction result in the case above.

@mizvekov
Copy link
Contributor Author

I tested again with newer version including #263 , but I get the same results.
Thanks for the effort though!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants