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

[lxfind]

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.

[aeubanks]

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]

In D103867#2806612, @aeubanks wrote:

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]

Add test case

[lxfind]

Only skip regions that contain BBs with address taken

[lxfind]

more test

[aeubanks]

lgtm

[hoy]

In D103867#2806612, @aeubanks wrote:

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]

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

[wenlei]

LGTM.

In D103867#2814096, @hoy wrote:

In D103867#2806612, @aeubanks wrote:

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.

[lxfind]

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.

[wenlei]

In D103867#2814684, @lxfind wrote:

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)..

[hjyamauchi]

Late to this, but LGTM.

[hoy]

In D103867#2814911, @wenlei wrote:

In D103867#2814684, @lxfind wrote:

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);
}

[wenlei]

In D103867#2828561, @hoy wrote:

In D103867#2814911, @wenlei wrote:

In D103867#2814684, @lxfind wrote:

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.

llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp

 
 static inline
 raw_ostream &operator<<(raw_ostream &OS, const CHRScope &Scope) {
   Scope.print(OS);
   return OS;
 }
 
 static bool shouldApply(Function &F, ProfileSummaryInfo& PSI) {
+  // If any of the basic blocks have address taken, we should skip this pass
+  // because the cloned blocks by this pass will not have address taken, and
+  // hence they may be optimized out by SimplifyCFG if they are targets of
+  // indirect branches.
+  bool HasBBAddressTaken =
+      llvm::any_of(F.getBasicBlockList(),
+                   [](const BasicBlock &BB) { return BB.hasAddressTaken(); });
+  if (HasBBAddressTaken)
+    return false;
+
   if (ForceCHR)
     return true;
 
   if (!CHRModuleList.empty() || !CHRFunctionList.empty()) {
     if (CHRModules.count(F.getParent()->getName()))
       return true;
     return CHRFunctions.count(F.getName());
   }