Page MenuHomePhabricator

[CHR] Don't run ControlHeightReduction if any BB has address taken
ClosedPublic

Authored by lxfind on Mon, Jun 7, 10:16 PM.

Details

Summary

This patch is to address https://bugs.llvm.org/show_bug.cgi?id=50610.
In computed goto pattern, there are usually a list of basic blocks that are all targets of indirectbr instruction, and each basic block also has address taken and stored in a variable.
CHR pass could potentially clone these basic blocks, which would generate a cloned version of the indirectbr and clonved version of all basic blocks in the list.
However these basic blocks will not have their addresses taken and stored anywhere. So latter SimplifyCFG pass will simply remove all tehse cloned basic blocks, resulting in incorrect code.
To fix this, when searching for scopes, we skip scopes that contains BBs with addresses taken.
Added a few test cases.

Diff Detail

Event Timeline

lxfind created this revision.Mon, Jun 7, 10:16 PM
lxfind requested review of this revision.Mon, Jun 7, 10:16 PM
Herald added a project: Restricted Project. · View Herald TranscriptMon, Jun 7, 10:16 PM
lxfind edited the summary of this revision. (Show Details)Mon, Jun 7, 10:26 PM

do all passes that clone BBs have to worry about this?

as for a test, can you take an existing CHR test and take the address of a block, then make sure that CHR doesn't trigger?

lxfind added a comment.Tue, Jun 8, 3:34 PM

do all passes that clone BBs have to worry about this?

I think so, as long as the cloned BB is in the same module as the original one, we need to worry about this (there are legit cloning in some tools such as llvm-extract, llvm-reduce..)

lxfind updated this revision to Diff 350750.Tue, Jun 8, 5:46 PM

Add test case

lxfind updated this revision to Diff 350776.Tue, Jun 8, 10:01 PM

Only skip regions that contain BBs with address taken

lxfind updated this revision to Diff 350777.Tue, Jun 8, 10:02 PM

more test

This revision is now accepted and ready to land.Fri, Jun 11, 11:53 AM
hoy accepted this revision.Fri, Jun 11, 12:17 PM

do all passes that clone BBs have to worry about this?

I think so. We've seen a similar case in inlining where an address-taken block was inlined. The inlining should be disabled as well.

LGTM, thanks for the fix.

hoy added a comment.Fri, Jun 11, 12:19 PM

Nit: adjust the summary for the part of testing and the disabling logic.

wenlei accepted this revision.Fri, Jun 11, 4:33 PM

LGTM.

do all passes that clone BBs have to worry about this?

I think so. We've seen a similar case in inlining where an address-taken block was inlined. The inlining should be disabled as well.

Poking around it looks like this should be handled for inlining, not sure why the previous case we ran into wasn't covered by that code below from CallAnalyzer::analyze()

// Disallow inlining a blockaddress with uses other than strictly callbr.
// A blockaddress only has defined behavior for an indirect branch in the
// same function, and we do not currently support inlining indirect
// branches.  But, the inliner may not see an indirect branch that ends up
// being dead code at a particular call site. If the blockaddress escapes
// the function, e.g., via a global variable, inlining may lead to an
// invalid cross-function reference.
// FIXME: pr/39560: continue relaxing this overt restriction.
if (BB->hasAddressTaken())
  for (User *U : BlockAddress::get(&*BB)->users())
    if (!isa<CallBrInst>(*U))
      return InlineResult::failure("blockaddress used outside of callbr");

LGTM, thanks for the fix.

Poking around it looks like this should be handled for inlining, not sure why the previous case we ran into wasn't covered by that code below from CallAnalyzer::analyze()

// Disallow inlining a blockaddress with uses other than strictly callbr.
// A blockaddress only has defined behavior for an indirect branch in the
// same function, and we do not currently support inlining indirect
// branches.  But, the inliner may not see an indirect branch that ends up
// being dead code at a particular call site. If the blockaddress escapes
// the function, e.g., via a global variable, inlining may lead to an
// invalid cross-function reference.
// FIXME: pr/39560: continue relaxing this overt restriction.
if (BB->hasAddressTaken())
  for (User *U : BlockAddress::get(&*BB)->users())
    if (!isa<CallBrInst>(*U))
      return InlineResult::failure("blockaddress used outside of callbr");

LGTM, thanks for the fix.

I think because that code is only checking for CallBrInst users. But in a computed goto pattern, the addresses are usually just stored in a global variable.

Poking around it looks like this should be handled for inlining, not sure why the previous case we ran into wasn't covered by that code below from CallAnalyzer::analyze()

// Disallow inlining a blockaddress with uses other than strictly callbr.
// A blockaddress only has defined behavior for an indirect branch in the
// same function, and we do not currently support inlining indirect
// branches.  But, the inliner may not see an indirect branch that ends up
// being dead code at a particular call site. If the blockaddress escapes
// the function, e.g., via a global variable, inlining may lead to an
// invalid cross-function reference.
// FIXME: pr/39560: continue relaxing this overt restriction.
if (BB->hasAddressTaken())
  for (User *U : BlockAddress::get(&*BB)->users())
    if (!isa<CallBrInst>(*U))
      return InlineResult::failure("blockaddress used outside of callbr");

LGTM, thanks for the fix.

I think because that code is only checking for CallBrInst users. But in a computed goto pattern, the addresses are usually just stored in a global variable.

Taking address of a block and storing it in a jump table does not introduce a use in the IR, however, if we use indirect branch to access the jump table like computed goto, we do count the indirect branch as use of the address taken labels, which in turns blocks inlining. See https://godbolt.org/z/8jYxzq867 (If we comment out the check for disallowing all indirbranch, it would be caught by the check quoted above)..

lxfind edited the summary of this revision. (Show Details)Sat, Jun 12, 10:28 AM

Late to this, but LGTM.

hoy added a comment.Fri, Jun 18, 6:58 PM

Poking around it looks like this should be handled for inlining, not sure why the previous case we ran into wasn't covered by that code below from CallAnalyzer::analyze()

// Disallow inlining a blockaddress with uses other than strictly callbr.
// A blockaddress only has defined behavior for an indirect branch in the
// same function, and we do not currently support inlining indirect
// branches.  But, the inliner may not see an indirect branch that ends up
// being dead code at a particular call site. If the blockaddress escapes
// the function, e.g., via a global variable, inlining may lead to an
// invalid cross-function reference.
// FIXME: pr/39560: continue relaxing this overt restriction.
if (BB->hasAddressTaken())
  for (User *U : BlockAddress::get(&*BB)->users())
    if (!isa<CallBrInst>(*U))
      return InlineResult::failure("blockaddress used outside of callbr");

LGTM, thanks for the fix.

I think because that code is only checking for CallBrInst users. But in a computed goto pattern, the addresses are usually just stored in a global variable.

Taking address of a block and storing it in a jump table does not introduce a use in the IR, however, if we use indirect branch to access the jump table like computed goto, we do count the indirect branch as use of the address taken labels, which in turns blocks inlining. See https://godbolt.org/z/8jYxzq867 (If we comment out the check for disallowing all indirbranch, it would be caught by the check quoted above)..

The following example can be used to tell the difference between GCC and LLVM regarding inlining. GCC won't inline function foo into bar while clang will. I was thinking this can be fixed in LLVM by enforcing a noinline attribute to functions of which the code labels are used in a static variable initializer. Fixing in the inliner might be better.

char *g;
void go();
void   foo(char *p)
{
   static const void* array[] = {&&L};
L:
   if (p) {
   p--;
   go();
   goto L;
   }
   return;
}
void bar()
{
  foo(g);
}

Poking around it looks like this should be handled for inlining, not sure why the previous case we ran into wasn't covered by that code below from CallAnalyzer::analyze()

// Disallow inlining a blockaddress with uses other than strictly callbr.
// A blockaddress only has defined behavior for an indirect branch in the
// same function, and we do not currently support inlining indirect
// branches.  But, the inliner may not see an indirect branch that ends up
// being dead code at a particular call site. If the blockaddress escapes
// the function, e.g., via a global variable, inlining may lead to an
// invalid cross-function reference.
// FIXME: pr/39560: continue relaxing this overt restriction.
if (BB->hasAddressTaken())
  for (User *U : BlockAddress::get(&*BB)->users())
    if (!isa<CallBrInst>(*U))
      return InlineResult::failure("blockaddress used outside of callbr");

LGTM, thanks for the fix.

I think because that code is only checking for CallBrInst users. But in a computed goto pattern, the addresses are usually just stored in a global variable.

Taking address of a block and storing it in a jump table does not introduce a use in the IR, however, if we use indirect branch to access the jump table like computed goto, we do count the indirect branch as use of the address taken labels, which in turns blocks inlining. See https://godbolt.org/z/8jYxzq867 (If we comment out the check for disallowing all indirbranch, it would be caught by the check quoted above)..

The following example can be used to tell the difference between GCC and LLVM regarding inlining. GCC won't inline function foo into bar while clang will. I was thinking this can be fixed in LLVM by enforcing a noinline attribute to functions of which the code labels are used in a static variable initializer. Fixing in the inliner might be better.

char *g;
void go();
void   foo(char *p)
{
   static const void* array[] = {&&L};
L:
   if (p) {
   p--;
   go();
   goto L;
   }
   return;
}
void bar()
{
  foo(g);
}

Yeah, this case differentiates gcc and llvm, because there's no indir branch. Also since there's no indir branch through the jump table, the inlining isn't buggy. However, as soon as you add indir branch through the jump table, inlining would be blocked in llvm like the case from the godbolt link above. It looks to me that there's attempt/effort try to cover such cases to prevent bad inlining, perhaps it's not strong enough - we can pass jump table address to a callee of foo, then that callee calls the address though indirect branch, so from foo, we still don't see a indirect branch.. The more robust way of preventing such bad inlining is as you said, gate it on storing code label into a static/global variable.