Treat branch on poison as immediate UB (under an off by default flag)

[reames]

Summary

The LangRef clearly states that branching on a poison value is immediate undefined behavior, but historically, we have not been consistent about implementing that interpretation in the optimizer. Historically, we used (in some cases) a more relaxed model which essentially looked for provable UB along both paths which was control dependent on the condition. However, we've never been 100% consistent here. For instance SCEV uses the strong model for increments which form AddRecs (and only addrecs).

At the moment, the last big blocker for finally making this switch is enabling the fix landed in D106041. Loop unswitching (in it's classic form) is incorrect as it creates many "branch on poisons" when unswitching conditions originally unreachable within the loop.

This change adds a flag to value tracking which allows to easily test the optimization potential of treating branch on poison as immediate UB. It's intended to help ease work on getting us finally through this transition and avoid multiple independent rediscovers of the same issues.

D111246 shows the test diff impact of enabling this.

[fhahn]

Having a flag seems like a good first step to get things going!

Perhaps it would be worth to add the flag to one of the tests from D111246.

[reames]

In D112026#3071193, @fhahn wrote:

Perhaps it would be worth to add the flag to one of the tests from D111246.

Thought about it, but only the SCEV tests are really clear as to *why* the impact happens, and those tests are already complicated enough. Having to version one which happens to change doesn't really seem to add much value as there's a *bunch* of SCEV implementation details you have to dance around, and any one of them could change at any time. Just as an example, SCEV currently handrolls exactly this logic, but applies it only to expressions which happen to be addrecs. An unrelated change to say trip count logic could totally change whether an expression folded to an addrec or not.

[reames]

ping

[nikic]

LG

[fhahn]

In D112026#3071195, @reames wrote:

In D112026#3071193, @fhahn wrote:

Perhaps it would be worth to add the flag to one of the tests from D111246.

Thought about it, but only the SCEV tests are really clear as to *why* the impact happens, and those tests are already complicated enough. Having to version one which happens to change doesn't really seem to add much value as there's a *bunch* of SCEV implementation details you have to dance around, and any one of them could change at any time. Just as an example, SCEV currently handrolls exactly this logic, but applies it only to expressions which happen to be addrecs. An unrelated change to say trip count logic could totally change whether an expression folded to an addrec or not.

Agreed, it's no ideal to have this flag for the more complicated tests.

But I think it would still be good to have at least minimal test coverage for the new flag & code. Perhaps you could add new test with a single function that uses the flag?

llvm/lib/Analysis/ValueTracking.cpp

 using namespace llvm;
 using namespace llvm::PatternMatch;
 
 // Controls the number of uses of the value searched for possible
 // dominating comparisons.
 static cl::opt<unsigned> DomConditionsMaxUses("dom-conditions-max-uses",
                                               cl::Hidden, cl::init(20));
 
+// According to the LangRef, branching on a poison condition is absolutely
+// immediate full UB.  However, historically we haven't implemented that
+// consistently as we have an important transformation (non-trivial unswitch)
+// which introduces instances of branch on poison/undef to otherwise well
+// defined programs.  This flag exists to let us test optimization benefit
+// of exploiting the specified behavior (in combination with enabling the
+// unswitch fix.)
+static cl::opt<bool> BranchOnPoisonAsUB("branch-on-poison-as-ub",
+                                        cl::Hidden, cl::init(false));
+
+
 /// Returns the bitwidth of the given scalar or pointer type. For vector types,
 /// returns the element type's bitwidth.
 static unsigned getBitWidth(Type *Ty, const DataLayout &DL) {
   if (unsigned BitWidth = Ty->getScalarSizeInBits())
     return BitWidth;
 
   return DL.getPointerTypeSizeInBits(Ty);
 }
void llvm::getGuaranteedNonPoisonOps(const Instruction *I,
   switch (I->getOpcode()) {
   // Divisors of these operations are allowed to be partially undef.
   case Instruction::UDiv:
   case Instruction::SDiv:
   case Instruction::URem:
   case Instruction::SRem:
     Operands.insert(I->getOperand(1));
     break;
-
+  case Instruction::Switch:
+    if (BranchOnPoisonAsUB)
+      Operands.insert(cast<SwitchInst>(I)->getCondition());
+    break;
+  case Instruction::Br: {
+    auto *BR = cast<BranchInst>(I);
+    if (BranchOnPoisonAsUB && BR->isConditional())
+      Operands.insert(BR->getCondition());
+    break;
+  }
   default:
     break;
   }
 }
 
 bool llvm::mustTriggerUB(const Instruction *I,
                          const SmallSet<const Value *, 16>& KnownPoison) {
   SmallPtrSet<const Value *, 4> NonPoisonOps;