[SCCP] Resolve indirect branch target when possible.

[trentxintong]

Summary

Resolve indirect branch target when possible.
This potentially eliminates more basicblocks and result in better evaluation for phi and other things.

[davide]

lib/Transforms/Scalar/SCCP.cpp

1531–1548 ↗

(On Diff #89606)

I'm very wary of adding more code here, as it caused a fair amount of pain in the past. This, tho, seems to be in line with what was already there.

1895–1896 ↗

(On Diff #89606)

Can this assertion ever fire?

[trentxintong]

lib/Transforms/Scalar/SCCP.cpp

1531–1548 ↗

(On Diff #89606)

I feel getting rid of this undef resolver is the way to go for SCCP. When I read this pass, I do not feel very good about how undef is resolved, especially the ordering terminators and its input is resolved does not seem to be bullet-proof. And it does have bugs.

However this is what we need to get indirectbr simplification working for now =).

1895–1896 ↗

(On Diff #89606)

TBH, I do not think IndirectBrInst, BranchInst, SwitchInst (2+ case) with Undef as input is possible at this point. As we always default-fold terminator to one target in ResolvedUndefsIn and set the input accordingly.

SwitchInst with only default-case is a slightly different, its input may not have resolved to constantint/blockaddress or overdefined state. But in such case, we make default-target always executable.

So we should only have constantint/blockaddress or constant(not int nor blockaddress)/overdefined here.

Maybe the check we really do is assert(Fold && "Must be able to fold terminator on constantint or blockaddress"); If this fails, that could mean 2 things.

1. ConstantFoldTerminator is doing something unexpected, i.e. not folding on constantint or blockaddress and not making blocks that should be dead dead.
2. This is not a terminator on constantint or blockaddress. Its on a constant or overdefined, then this block should not be dead.

In both cases, we should assert.

[davide]

lib/Transforms/Scalar/SCCP.cpp

1531–1548 ↗

(On Diff #89606)

I really agree, and in fact I discussed this on the mailing lists (and with Dan Berlin and David Majnemer). I have a patch for that, but needs some performance testing. If you care about this, maybe you can run on your benchmarks? (I'm going to clean up the branch and send the patch to you).

[trentxintong]

@davide I am more than happy to run your patch on some Facebook internal server workloads.

[trentxintong]

Rebase.

[trentxintong]

Gentle ping.

[davide]

I really apologize for the delay in providing you the patch. I'm at GDC this week and that limits my ability to work on LLVM upstream things. I will provide the patch to you next week, and if I don't because I forget, feel free to ping me again.

[trentxintong]

Gentle ping.

[trentxintong]

Gentle Ping ?

[trentxintong]

@davide do you think its OK to land this patch first and I will help you to run your patch once you have it ready ? Thanks !

llvm/trunk/lib/Transforms/Scalar/SCCP.cpp

public:
   /// getConstantInt - If this is a constant with a ConstantInt value, return it
   /// otherwise return null.
   ConstantInt *getConstantInt() const {
     if (isConstant())
       return dyn_cast<ConstantInt>(getConstant());
     return nullptr;
   }
 
+  /// getBlockAddress - If this is a constant with a BlockAddress value, return
+  /// it, otherwise return null.
+  BlockAddress *getBlockAddress() const {
+    if (isConstant())
+      return dyn_cast<BlockAddress>(getConstant());
+    return nullptr;
+  }
+
   void markForcedConstant(Constant *V) {
     assert(isUnknown() && "Can't force a defined value!");
     Val.setInt(forcedconstant);
     Val.setPointer(V);
   }
 };
 } // end anonymous namespace.
 
if (!CI) {   // Overdefined or unknown condition?
         Succs.assign(TI.getNumSuccessors(), true);
       return;
     }
 
     Succs[SI->findCaseValue(CI).getSuccessorIndex()] = true;
     return;
   }
 
-  // TODO: This could be improved if the operand is a [cast of a] BlockAddress.
-  if (isa<IndirectBrInst>(&TI)) {
-    // Just mark all destinations executable!
+  // In case of indirect branch and its address is a blockaddress, we mark
+  // the target as executable.
+  if (auto *IBR = dyn_cast<IndirectBrInst>(&TI)) {
+    // Casts are folded by visitCastInst.
+    LatticeVal IBRValue = getValueState(IBR->getAddress());
+    BlockAddress *Addr = IBRValue.getBlockAddress();
+    if (!Addr) {   // Overdefined or unknown condition?
+      // All destinations are executable!
+      if (!IBRValue.isUnknown())
         Succs.assign(TI.getNumSuccessors(), true);
       return;
     }
 
+    BasicBlock* T = Addr->getBasicBlock();
+    assert(Addr->getFunction() == T->getParent() &&
+           "Block address of a different function ?");
+    for (unsigned i = 0; i < IBR->getNumSuccessors(); ++i) {
+      // This is the target.
+      if (IBR->getDestination(i) == T) {
+        Succs[i] = true;
+        return;
+      }
+    }
+
+    // If we didn't find our destination in the IBR successor list, then we
+    // have undefined behavior. Its ok to assume no successor is executable.
+    return;
+  }
+
   DEBUG(dbgs() << "Unknown terminator instruction: " << TI << '\n');
   llvm_unreachable("SCCP: Don't know how to handle this terminator!");
 }
 
 
 // isEdgeFeasible - Return true if the control flow edge from the 'From' basic
 // block to the 'To' basic block is currently feasible.
 //
if (auto *SI = dyn_cast<SwitchInst>(TI)) {
     ConstantInt *CI = SCValue.getConstantInt();
 
     if (!CI)
       return !SCValue.isUnknown();
 
     return SI->findCaseValue(CI).getCaseSuccessor() == To;
   }
 
-  // Just mark all destinations executable!
-  // TODO: This could be improved if the operand is a [cast of a] BlockAddress.
-  if (isa<IndirectBrInst>(TI))
-    return true;
+  // In case of indirect branch and its address is a blockaddress, we mark
+  // the target as executable.
+  if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) {
+    LatticeVal IBRValue = getValueState(IBR->getAddress());
+    BlockAddress *Addr = IBRValue.getBlockAddress();
+
+    if (!Addr)
+      return !IBRValue.isUnknown();
+
+    // At this point, the indirectbr is branching on a blockaddress.
+    return Addr->getBasicBlock() == To;
+  }
 
   DEBUG(dbgs() << "Unknown terminator instruction: " << *TI << '\n');
   llvm_unreachable("SCCP: Don't know how to handle this terminator!");
 }
 
 // visit Implementations - Something changed in this instruction, either an
 // operand made a transition, or the instruction is newly executable.  Change
 // the value type of I to reflect these changes if appropriate.  This method
if (auto *BI = dyn_cast<BranchInst>(TI)) {
       // Otherwise, it is a branch on a symbolic value which is currently
       // considered to be undef.  Handle this by forcing the input value to the
       // branch to false.
       markForcedConstant(BI->getCondition(),
                          ConstantInt::getFalse(TI->getContext()));
       return true;
     }
 
+   if (auto *IBR = dyn_cast<IndirectBrInst>(TI)) {
+      // Indirect branch with no successor ?. Its ok to assume it branches
+      // to no target.
+      if (IBR->getNumSuccessors() < 1)
+        continue;
+
+      if (!getValueState(IBR->getAddress()).isUnknown())
+        continue;
+
+      // If the input to SCCP is actually branch on undef, fix the undef to
+      // the first successor of the indirect branch.
+      if (isa<UndefValue>(IBR->getAddress())) {
+        IBR->setAddress(BlockAddress::get(IBR->getSuccessor(0)));
+        markEdgeExecutable(&BB, IBR->getSuccessor(0));
+        return true;
+      }
+
+      // Otherwise, it is a branch on a symbolic value which is currently
+      // considered to be undef.  Handle this by forcing the input value to the
+      // branch to the first successor.
+      markForcedConstant(IBR->getAddress(),
+                         BlockAddress::get(IBR->getSuccessor(0)));
+      return true;
+    }
+
     if (auto *SI = dyn_cast<SwitchInst>(TI)) {
       if (!SI->getNumCases() || !getValueState(SI->getCondition()).isUnknown())
         continue;
 
       // If the input to SCCP is actually switch on undef, fix the undef to
       // the first constant.
       if (isa<UndefValue>(SI->getCondition())) {
         SI->setCondition(SI->case_begin().getCaseValue());

llvm/trunk/test/Transforms/SCCP/indirectbr.ll

+; RUN: opt -S -sccp < %s | FileCheck %s
+
+declare void @BB0_f()
+declare void @BB1_f()
+
+; Make sure we can eliminate what is in BB0 as we know that the indirectbr is going to BB1.
+;
+; CHECK-LABEL: define void @indbrtest1(
+; CHECK-NOT: call void @BB0_f()
+; CHECK: ret void
+define void @indbrtest1() {
+entry:
+  indirectbr i8* blockaddress(@indbrtest1, %BB1), [label %BB0, label %BB1]
+BB0:
+  call void @BB0_f()
+  br label %BB1
+BB1:
+  call void @BB1_f()
+  ret void
+}
+
+; Make sure we can eliminate what is in BB0 as we know that the indirectbr is going to BB1
+; by looking through the casts. The casts should be folded away when they are visited
+; before the indirectbr instruction.
+;
+; CHECK-LABEL: define void @indbrtest2(
+; CHECK-NOT: call void @BB0_f()
+; CHECK: ret void
+define void @indbrtest2() {
+entry:
+  %a = ptrtoint i8* blockaddress(@indbrtest2, %BB1) to i64
+  %b = inttoptr i64 %a to i8*
+  %c = bitcast i8* %b to i8*
+  indirectbr i8* %b, [label %BB0, label %BB1]
+BB0:
+  call void @BB0_f()
+  br label %BB1
+BB1:
+  call void @BB1_f()
+  ret void
+}
+
+; Make sure we can not eliminate BB0 as we do not know the target of the indirectbr.
+;
+; CHECK-LABEL: define void @indbrtest3(
+; CHECK: call void @BB0_f()
+; CHECK: ret void
+define void @indbrtest3(i8** %Q) {
+entry:
+  %t = load i8*, i8** %Q
+  indirectbr i8* %t, [label %BB0, label %BB1]
+BB0:
+  call void @BB0_f()
+  br label %BB1
+BB1:
+  call void @BB1_f()
+  ret void
+}
+
+; Make sure we eliminate BB1 as we pick the first successor on undef.
+;
+; CHECK-LABEL: define void @indbrtest4(
+; CHECK: call void @BB0_f()
+; CHECK: ret void
+define void @indbrtest4(i8** %Q) {
+entry:
+  indirectbr i8* undef, [label %BB0, label %BB1]
+BB0:
+  call void @BB0_f()
+  br label %BB1
+BB1:
+  call void @BB1_f()
+  ret void
+}
+
+