[StackProtector] Skip analysing dead users in HasAddressTaken, PR40436

[uabelho]

Summary

The usual SSA rules don't apply for code that isn't reachable from the
entry, so we might find a user like

%user = select i1 %bool, i8* %ai, i8* %user

which is using itself, and then when examining that we would make
HasAddressTaken recurse until it blows the stack.

To determine if the user is in a basic block reachable from entry, we now
require that we have DominatorTree information. That affected a few test
cases checking the pass pipeline.

[uabelho]

Not sure who should review this, I added the three last persons that I think did non-NFC changes to StackProtector.cpp.

[uabelho]

Is this a proper way of solving the problem? Is it ok to require DT?

[mattd]

I like this patch, and I like the DominatorTree clean up/refactor. As you pointed out, your patch does make the DT required, which makes sense because your solution must make use of that analysis. I don't see that as an issue. Overall, this patch makes sense to me, but I'm curious as to what others think.

lib/CodeGen/StackProtector.cpp

161

s/laster/later/

[rnk]

An alternative way to handle this would be to remove unreachable code. I'm surprised unreachable code reaches this pass in a normal pipeline. I thought CGP removed it in normal operation, even at O0. However, removing unreachable code might invalidate the domtree (unless our utility for that updates it?).

[uabelho]

Fixed typo, reformulated a piece of a comment.

[uabelho]

In D57149#1369777, @rnk wrote:

An alternative way to handle this would be to remove unreachable code. I'm surprised unreachable code reaches this pass in a normal pipeline. I thought CGP removed it in normal operation, even at O0. However, removing unreachable code might invalidate the domtree (unless our utility for that updates it?).

An alternative that you would prefer?

I have to say that I think it makes sense that StackProtector can deal with the code on it's own since we never know when some dead code might reach StackProtector anyway, but perhaps there are strong reasons CGP really shouldn't leave dead code around?

I don't know CGP, but from the logs I see that it's after CGP that the dead blocks really get disconnected.
Before CGP:

*** IR Dump Before CodeGen Prepare ***
; Function Attrs: sspreq
define void @f1() #0 {
entry:
  %d = alloca i16, align 1
  br label %for.cond

for.cond:                                         ; preds = %for.cond, %entry
  br i1 true, label %for.cond, label %for.end

for.end:                                          ; preds = %for.cond
  %tobool = icmp ne i16 undef, 0
  br label %for.cond1

for.cond1:                                        ; preds = %for.body2, %for.end
  %d2 = phi i16* [ %spec.select, %for.body2 ], [ undef, %for.end ]
  br label %for.body2

for.body2:                                        ; preds = %for.cond1
  %spec.select = select i1 undef, i16* %d, i16* %d2
  br label %for.cond1
}

And then after:

*** IR Dump After CodeGen Prepare ***
; Function Attrs: sspreq
define void @f1() #0 {
entry:
  %d = alloca i16, align 1
  br label %for.cond

for.cond:                                         ; preds = %for.cond, %entry
  br label %for.cond

for.body2:                                        ; preds = %for.body2
  %spec.select = select i1 undef, i16* %d, i16* %spec.select
  br label %for.body2
}

[uabelho]

Rebased.

[uabelho]

Ping!

Is this ok or is it better to go down the CGP route instead? If so, can we really guarantee that all dead code is always removed when we get to StackProtector so we don't end up with this problem anyway?

[uabelho]

Managed to drop the new testcase when I rebased >.<

[mattd]

Hi @uabelho

The test case in your patch definitely causes a problem, but that's because the -start-before/-stop-after is used. If I run that same test through llc, the UnreachableBlockElim pass kicks-in and drops the dead code.
I took a look at the code in your Janurary 24th comment. I was unable to get the same dead block to surface, but most likely I had the wrong flag set. How did you build the sample in that comment?

[uabelho]

In D57149#1387325, @mattd wrote:

Hi @uabelho

The test case in your patch definitely causes a problem, but that's because the -start-before/-stop-after is used. If I run that same test through llc, the UnreachableBlockElim pass kicks-in and drops the dead code.
I took a look at the code in your Janurary 24th comment. I was unable to get the same dead block to surface, but most likely I had the wrong flag set. How did you build the sample in that comment?

It can be reproduced with the full llc -O1 pipe on current trunk using:
llc -O1 -o - pr40436.ll

pr40436.ll825 BDownload

[uabelho]

Ping!

[mattd]

In D57149#1388361, @uabelho wrote:

In D57149#1387325, @mattd wrote:

Hi @uabelho

The test case in your patch definitely causes a problem, but that's because the -start-before/-stop-after is used. If I run that same test through llc, the UnreachableBlockElim pass kicks-in and drops the dead code.
I took a look at the code in your Janurary 24th comment. I was unable to get the same dead block to surface, but most likely I had the wrong flag set. How did you build the sample in that comment?

It can be reproduced with the full llc -O1 pipe on current trunk using:
llc -O1 -o - pr40436.ll

pr40436.ll825 BDownload

I was able to repro your issue. As pointed out earlier, CGP does not cover this particular case.
It might be useful to eliminate the dead code there, in CGP, if possible. At least we wouldn't be passing the unused statements around to other passes.
In any case I'd suggest tossing an assert in the StackProtector ensuring that such a the pathologic recursion does not occur.

I do see the point of ensuring the sanity of StackProtector, and I'm not opposed to patching that up (as you have done here in this patch); however, I do see benefit in preventing the dead code from reaching the StackProtector in the first place. I'm not sure how others feel.

[uabelho]

In D57149#1401627, @mattd wrote:

I do see the point of ensuring the sanity of StackProtector, and I'm not opposed to patching that up (as you have done here in this patch); however, I do see benefit in preventing the dead code from reaching the StackProtector in the first place. I'm not sure how others feel.

To me there are two different issues.

1. Fixing the immediate problem (in StackProtector)
2. Doing optimizations, e.g. make CGP better in cleaning up the code.

My focus with this patch is to address 1, and if someone wants to do 2 and optimize CGP, then please go ahead with that too.

I didn't think fixing 1 would be controversial, apart from that possibly someone would have an opinion about the DT requirement.

In D57149#1369777, @rnk wrote:

An alternative way to handle this would be to remove unreachable code. I'm surprised unreachable code reaches this pass in a normal pipeline. I thought CGP removed it in normal operation, even at O0. However, removing unreachable code might invalidate the domtree (unless our utility for that updates it?).

I don't know CGP at all, but just from a quick look it seems like it doesn't require DT and it doesn't update it so I've no idea how messy it would be to go down that route.

There is some code in CodeGenPrepare::runOnFunction that tries to remove dead basic blocks, but those blocks are identified by having zero predecessors, so more complex situations with e.g. a loop that is unreachable from entry doesn't seem to be handled.

In this exact case the dead loop consists of several blocks from the beginning and then it's reduced down to

for.body2:                                        ; preds = %for.body2
  %spec.select = select i1 undef, i16* %d, i16* %spec.select
  br label %for.body2

by CodeGenPrepare::eliminateFallThrough but there doesn't seem to be anything after that tries to remove things.

[uabelho]

With r363169 the problem seems to be fixed, so this patch is probably not needed anymore.

lib/CodeGen/StackProtector.cpp

 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
 INITIALIZE_PASS_END(StackProtector, DEBUG_TYPE,
                     "Insert stack protectors", false, true)
 
 FunctionPass *llvm::createStackProtectorPass() { return new StackProtector(); }
 
 void StackProtector::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<TargetPassConfig>();
+  AU.addRequired<DominatorTreeWrapperPass>();
   AU.addPreserved<DominatorTreeWrapperPass>();
 }
 
 bool StackProtector::runOnFunction(Function &Fn) {
   F = &Fn;
   M = F->getParent();
-  DominatorTreeWrapperPass *DTWP =
-      getAnalysisIfAvailable<DominatorTreeWrapperPass>();
-  DT = DTWP ? &DTWP->getDomTree() : nullptr;
+  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
   Trip = TM->getTargetTriple();
   TLI = TM->getSubtargetImpl(Fn)->getTargetLowering();
   HasPrologue = false;
   HasIRCheck = false;
 
   Attribute Attr = Fn.getFnAttribute("stack-protector-buffer-size");
   if (Attr.isStringAttribute() &&
if (ContainsProtectableArray(*I, IsLarge, Strong, true)) {
       NeedsProtector = true;
     }
 
   return NeedsProtector;
 }
 
 bool StackProtector::HasAddressTaken(const Instruction *AI) {
   for (const User *U : AI->users()) {
+    // Don't bother examining the user if it's in a basic block that isn't
+    // reachable from the entry BB. That code will probably be removed later
+    // anyway, and it won't be executed so we don't need to care about it.
+    //
+    // The usual SSA rules don't apply for code that isn't reachable from the
+    // entry, so we might find a user like
+    //
+    //  %user = select i1 %bool, i8* %ai, i8* %user
+    //
+    // which is using itself, and then when examining that we would make
+    // HasAddressTaken recurse until it blows the stack.
+    const Instruction *UI = cast<Instruction>(U);
+    if (!DT->isReachableFromEntry(UI->getParent()))
+      continue;
+
     if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
       if (AI == SI->getValueOperand())
         return true;
     } else if (const PtrToIntInst *SI = dyn_cast<PtrToIntInst>(U)) {
       if (AI == SI->getOperand(0))
         return true;
     } else if (const CallInst *CI = dyn_cast<CallInst>(U)) {
       // Ignore intrinsics that are not calls. TODO: Use isLoweredToCall().
if (Function *GuardCheck = TLI->getSSPStackGuardCheck(*M)) {
       // Create the FailBB. We duplicate the BB every time since the MI tail
       // merge pass will merge together all of the various BB into one including
       // fail BB generated by the stack protector pseudo instruction.
       BasicBlock *FailBB = CreateFailBB();
 
       // Split the basic block before the return instruction.
       BasicBlock *NewBB = BB->splitBasicBlock(RI->getIterator(), "SP_return");
 
-      // Update the dominator tree if we need to.
-      if (DT && DT->isReachableFromEntry(BB)) {
+      // Update the dominator tree.
+      if (DT->isReachableFromEntry(BB)) {
         DT->addNewBlock(NewBB, BB);
         DT->addNewBlock(FailBB, BB);
       }
 
       // Remove default branch instruction to the new BB.
       BB->getTerminator()->eraseFromParent();
 
       // Move the newly created basic block to the point right after the old

test/CodeGen/AArch64/O0-pipeline.ll

 ; CHECK-NEXT:       Instrument function entry/exit with calls to e.g. mcount() (post inlining)
 ; CHECK-NEXT:       Scalarize Masked Memory Intrinsics
 ; CHECK-NEXT:       Expand reduction intrinsics
 ; CHECK-NEXT:     Rewrite Symbols
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Exception handling preparation
 ; CHECK-NEXT:       Safe Stack instrumentation pass
+; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Insert stack protectors
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:       Analysis containing CSE Info
 ; CHECK-NEXT:       IRTranslator
 ; CHECK-NEXT:       AArch64PreLegalizerCombiner
 ; CHECK-NEXT:       Analysis containing CSE Info
 ; CHECK-NEXT:       Legalizer
 ; CHECK-NEXT:       RegBankSelect

test/CodeGen/AArch64/O3-pipeline.ll

 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Exception handling preparation
 ; CHECK-NEXT:     AArch64 Promote Constant
 ; CHECK-NEXT:       Unnamed pass: implement Pass::getPassName()
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Merge internal globals
 ; CHECK-NEXT:       Safe Stack instrumentation pass
+; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Insert stack protectors
 ; CHECK-NEXT:       Module Verifier
-; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Branch Probability Analysis
 ; CHECK-NEXT:       AArch64 Instruction Selection
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       AArch64 Local Dynamic TLS Access Clean-up
 ; CHECK-NEXT:       Expand ISel Pseudo-instructions

test/CodeGen/X86/O0-pipeline.ll

 ; CHECK-NEXT:       Scalarize Masked Memory Intrinsics
 ; CHECK-NEXT:       Expand reduction intrinsics
 ; CHECK-NEXT:       Expand indirectbr instructions
 ; CHECK-NEXT:     Rewrite Symbols
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Exception handling preparation
 ; CHECK-NEXT:       Safe Stack instrumentation pass
+; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Insert stack protectors
 ; CHECK-NEXT:       Module Verifier
 ; CHECK-NEXT:       X86 DAG->DAG Instruction Selection
 ; CHECK-NEXT:       X86 PIC Global Base Reg Initialization
 ; CHECK-NEXT:       Expand ISel Pseudo-instructions
 ; CHECK-NEXT:       Local Stack Slot Allocation
 ; CHECK-NEXT:       X86 speculative load hardening
 ; CHECK-NEXT:       MachineDominator Tree Construction

test/CodeGen/X86/O3-pipeline.ll

 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       CodeGen Prepare
 ; CHECK-NEXT:     Rewrite Symbols
 ; CHECK-NEXT:     FunctionPass Manager
 ; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Exception handling preparation
 ; CHECK-NEXT:       Safe Stack instrumentation pass
+; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Insert stack protectors
 ; CHECK-NEXT:       Module Verifier
-; CHECK-NEXT:       Dominator Tree Construction
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Natural Loop Information
 ; CHECK-NEXT:       Branch Probability Analysis
 ; CHECK-NEXT:       X86 DAG->DAG Instruction Selection
 ; CHECK-NEXT:       MachineDominator Tree Construction
 ; CHECK-NEXT:       Local Dynamic TLS Access Clean-up
 ; CHECK-NEXT:       X86 PIC Global Base Reg Initialization

test/CodeGen/X86/stack-protector-unreachable-code.ll

+; RUN: llc -mtriple=x86_64-unknown-unknown -start-before=stack-protector -stop-after=stack-protector %s -o - | FileCheck %s
+
+; The self-referencing instruction %user shouldn't cause infinite recursion.
+
+define void @f() sspreq {
+entry:
+  %ai = alloca i8, align 1
+  ret void
+
+dead:
+  %user = select i1 undef, i8* %ai, i8* %user
+  unreachable
+}
+
+; CHECK:       @__stack_chk_guard = external global i8*
+
+; CHECK:       define void @f() #0 {
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    %StackGuardSlot = alloca i8*
+; CHECK-NEXT:    %0 = call i8* @llvm.stackguard()
+; CHECK-NEXT:    call void @llvm.stackprotector(i8* %0, i8** %StackGuardSlot)
+; CHECK-NEXT:    %ai = alloca i8, align 1
+; CHECK-NEXT:    ret void
+
+; CHECK:      dead:                                             ; No predecessors!
+; CHECK-NEXT:    %user = select i1 undef, i8* %ai, i8* %user
+; CHECK-NEXT:    unreachable
+; CHECK-NEXT: }