[LVI] Constant-propagate a zero extension of the switch condition value through case edges

[hjyamauchi]

Summary

LazyValueInfo currently computes the constant value of the switch condition through case edges, which allows the constant value to be propagated through the case edges.

But we have seen a case where a zero-extended value of the switch condition is used past case edges for which the constant propagation doesn't occur.

This patch adds a small logic to handle such a case in getEdgeValueLocal().

This is motivated by the Python 2.7 eval loop in PyEval_EvalFrameEx() where the lack of the constant propagation causes longer live ranges and more spill code than necessary.

With this patch, we see that the code size of PyEval_EvalFrameEx() decreases by ~5.4% and a performance test improves by ~4.6%.

[davidxl]

This patch needs a test case.

[hjyamauchi]

Added a test.

[hjyamauchi]

Wei, can you review this?

[hjyamauchi]

For more context:

Here's a test C program that demonstrates this issue (reduced from the Python 2.7 runtime eval loop code) :

void bar(int v);

int foo(unsigned char* p, int (*f)(int)) {
  int op;
  void* targets[256];
  int i;
  for (i = 0; i < 256; ++i) {
    targets[i] = &&unknown_op;
  }
  targets[93] = &&TARGET_93;
  targets[145] = &&TARGET_145;
  for (;;) {
    op = *p++;
 dispatch_op:
    switch (op) {
      TARGET_93:
      op = 93;
      case 93: {
        if (op != 93) {
          f(42);
        }
        goto *targets[*p++];
      }

      TARGET_145:
      op = 145;
      case 145: {
        op = *p++;
        goto dispatch_op;
      }

      unknown_op:
      default:
        bar(op);
        break;
    }
  }
  return 0;
}

There's a control merge between "TARGET_93" (that the computed goto may jumps to) and "case 93" (that the normal switch control flow may jump to).

The value of 'op' at "case 93:" would be constant 93 regardless of the control flow.

So, we could eliminate the call to 'f'.

GCC does this whereas LLVM does not.

[hjyamauchi]

I think this situation occurs due to the combination of the following two optimizations that shrink/narrow the width of operands.

They succeed narrowing the width of the switch condition operand "op" (%op.0.in in the test) and its address (%p.addr.0.pn in the test) from i32 to i8.

But since "op" still has a use as an i32 (passed to bar()), the zext remains.

Because of the zext, the current case edge value propagation doesn't perform the value propagation (op==93) on the case edge and the elimination of the call to f.

1. lib/Transforms/InstCombine/InstructionCombining.cpp

Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) {
  ...
  // Shrink the condition operand if the new type is smaller than the old type.
  // This may produce a non-standard type for the switch, but that's ok because
  // the backend should extend back to a legal type for the target.
  if (NewWidth > 0 && NewWidth < Known.getBitWidth()) {
    IntegerType *Ty = IntegerType::get(SI.getContext(), NewWidth);
    Builder.SetInsertPoint(&SI);
    Value *NewCond = Builder.CreateTrunc(Cond, Ty, "trunc");
    SI.setCondition(NewCond);

    for (auto Case : SI.cases()) {
      APInt TruncatedCase = Case.getCaseValue()->getValue().trunc(NewWidth);
      Case.setValue(ConstantInt::get(SI.getContext(), TruncatedCase));
    }
    return &SI;
  }

  return nullptr;
}

2. lib/Transforms/InstCombine/InstCombinePHI.cpp

Instruction *InstCombiner::FoldPHIArgZextsIntoPHI(PHINode &Phi) {
  ...
  // All incoming values are zexts or constants that are safe to truncate.
  // Create a new phi node of the narrow type, phi together all of the new
  // operands, and zext the result back to the original type.
  PHINode *NewPhi = PHINode::Create(NarrowType, NumIncomingValues,
                                    Phi.getName() + ".shrunk");
  for (unsigned i = 0; i != NumIncomingValues; ++i)
    NewPhi->addIncoming(NewIncoming[i], Phi.getIncomingBlock(i));

  InsertNewInstBefore(NewPhi, Phi);
  return CastInst::CreateZExtOrBitCast(NewPhi, Phi.getType());
}

[sanjoy]

lib/Analysis/LazyValueInfo.cpp

1483

s/extention/extension/

1500

This is oddly specific to zero extensions. Can you use some helpers in InstructionSimplify.h to make this more general over other kinds of operations? Something like: if Val has Condition as an operand and if Val is a CastInst or BinaryOperator (say), then invoke SimplifyBinOp / SimplifyFBinOp / SimplifyCastInst (depending on the opcode) with the operand that was Condition replaced with the appropriate constant.

[wmi]

I think we can find many similar problems.

long g;
void foo(int b) {
  int a = b;  
  g  = a;
  if (b == 3) {
    // assume we have `a = b` here, current LVI should be able to find out `a` equals to 3.
    __builtin_printf("%lx\n", a);
  }
}

Is there a way to make LVI more context sensitive, so that when we try to get value info for a and call LazyValueInfoImpl::solveBlockValueCast for a = b to find out the value info for b, we know the context is in the branch instead of the entry block? I just throw out the question and I don't know it is possible or not.

[• dberlin]

NewGVN, and other things will already get such cases.
I have a bug open for LVI to use predicateinfo, which would make it sensitive to this, as well as make it much faster, but that is a big amount of work.

[sanjoy]

lib/Analysis/LazyValueInfo.cpp

152

Can we return an Optional<APInt> here?

1371

You can use User::operands() and llvm::find here.

1377

I think we can return Optional<APInt> here.

Also: how about dropping Edge from the name, since we're not doing anything specific to bblock edges here? How about constantFoldUser?

1382

s/Condition/Op/

1395

In LLVM * aligns with the value. clang-format should fix this.

1480

I think this can be an assert -- switch only allows integer conditions.

1482

Does this logic subsume the logic in line 1431? And can we write the switch case case (no pun intended! :) ) in the same way? If so, I'd suggest pulling this logic out into a function and calling it once here and once from the switch-case block.

1485

Usually LLVM code does not use { for single statement ifs.

[hjyamauchi]

Addressed the comments.

lib/Analysis/LazyValueInfo.cpp

1480

I assume 'Val' can be any value live through the switch for which we're trying to find its value on this edge, and can be of any type?

1482

No, this logic does not subsume the logic in line 1431 (I verified that by commenting it out and running the tests.) This is because the 1431 logic handles the cases where 'Condition' is an operand of 'Val' whereas this logic handles the cases where 'Condition' is *not* an operand of 'Val', but one ('Op') of the operands of 'Val' can be inferred through the value of 'Condition'. Note this logic calls getValueFromCondition for 'Op'.

I moved the 1431 logic here and combined them.

I also factored out some common logic out to constantFoldUser() and simplified its call sites.

[sanjoy]

lgtm with minor comments.

lib/Analysis/LazyValueInfo.cpp

152

I didn't notice this the first time around, but I'd calls this function asConstantInteger (or something else that does not start with get). The getXXX in this class are simple accessors (which this function is not) so it is useful to differentiate this.

154

I think we can have direct returns here, instead of assigning to Result and then return Result;.

1385

This is minor, but LLVM tends to use auto * for assignments whose types are obvious from RHS.

1463

I suspect you can do

if (Optional<APInt> OpConst = OpLatticeVal.getConstantInteger())

1479

The spacing is still off here, clang-format should fix this.

1480

Yes, you're right.

1482

Ok, SGTM.

[hjyamauchi]

Addressed the comments.

lib/Analysis/LazyValueInfo.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LazyValueInfo.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/ConstantFolding.h"
+#include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/AssemblyAnnotationWriter.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
public:
   }
 
   const ConstantRange &getConstantRange() const {
     assert(isConstantRange() &&
            "Cannot get the constant-range of a non-constant-range!");
     return Range;
   }
 
+  Optional<APInt> getConstantInteger() const {
+    Optional<APInt> Result;
+    if (isConstant() && isa<ConstantInt>(Val)) {
+      Result = Val->getUniqueInteger();
+    } else if (isConstantRange() && Range.isSingleElement()) {
+      Result = *Range.getSingleElement();
+    }
+    return Result;
+  }
+
 private:
   void markOverdefined() {
     if (isOverdefined())
       return;
     Tag = overdefined;
   }
 
   void markConstant(Constant *V) {

 }
 
 LVILatticeVal getValueFromCondition(Value *Val, Value *Cond, bool isTrueDest) {
   assert(Cond && "precondition");
   DenseMap<Value*, LVILatticeVal> Visited;
   return getValueFromCondition(Val, Cond, isTrueDest, Visited);
 }
 
+// Return true if Usr has Op as an operand, otherwise false.
+static bool usesOperand(User *Usr, Value *Op) {
+  return find(Usr->operands(), Op) != Usr->op_end();
+}
+
+// Check if Val can be simplified to an integer constant when the value of one
+// of its operands Op is an integer constant OpConstVal. If so, return it as an
+// lattice value range with a single element or otherwise return an overdefined
+// lattice value.
+static LVILatticeVal constantFoldUser(Value *Val, Value *Op,
+                                      const APInt &OpConstVal,
+                                      const DataLayout &DL) {
+  Constant* OpConst = Constant::getIntegerValue(Op->getType(), OpConstVal);
+  // Check if Val can be simplified to a constant.
+  if (auto *CI = dyn_cast<CastInst>(Val)) {
+    assert(CI->getOperand(0) == Op && "Operand 0 isn't Op");
+    if (ConstantInt *C = dyn_cast_or_null<ConstantInt>(
+            SimplifyCastInst(CI->getOpcode(), OpConst,
+                             CI->getDestTy(), DL))) {
+      return LVILatticeVal::getRange(ConstantRange(C->getUniqueInteger()));
+    }
+  } else if (auto *BO = dyn_cast<BinaryOperator>(Val)) {
+    bool Op0Match = BO->getOperand(0) == Op;
+    bool Op1Match = BO->getOperand(1) == Op;
+    assert((Op0Match || Op1Match) &&
+           "Operand 0 nor Operand 1 isn't a match");
+    Value *LHS = Op0Match ? OpConst : BO->getOperand(0);
+    Value *RHS = Op1Match ? OpConst : BO->getOperand(1);
+    if (ConstantInt *C = dyn_cast_or_null<ConstantInt>(
+            SimplifyBinOp(BO->getOpcode(), LHS, RHS, DL))) {
+      return LVILatticeVal::getRange(ConstantRange(C->getUniqueInteger()));
+    }
+  }
+  return LVILatticeVal::getOverdefined();
+}
+
 /// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
 /// Val is not constrained on the edge.  Result is unspecified if return value
 /// is false.
 static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
                               BasicBlock *BBTo, LVILatticeVal &Result) {
   // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
   // know that v != 0.
   if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
     // If this is a conditional branch and only one successor goes to BBTo, then
     // we may be able to infer something from the condition.
     if (BI->isConditional() &&
         BI->getSuccessor(0) != BI->getSuccessor(1)) {
       bool isTrueDest = BI->getSuccessor(0) == BBTo;
       assert(BI->getSuccessor(!isTrueDest) == BBTo &&
              "BBTo isn't a successor of BBFrom");
+      Value *Condition = BI->getCondition();
 
       // If V is the condition of the branch itself, then we know exactly what
       // it is.
-      if (BI->getCondition() == Val) {
+      if (Condition == Val) {
         Result = LVILatticeVal::get(ConstantInt::get(
                               Type::getInt1Ty(Val->getContext()), isTrueDest));
         return true;
       }
 
       // If the condition of the branch is an equality comparison, we may be
       // able to infer the value.
-      Result = getValueFromCondition(Val, BI->getCondition(), isTrueDest);
+      Result = getValueFromCondition(Val, Condition, isTrueDest);
+      if (!Result.isOverdefined())
+        return true;
+
+      if (User *Usr = dyn_cast<User>(Val)) {
+        assert(Result.isOverdefined() && "Result isn't overdefined");
+        if (isa<IntegerType>(Val->getType())) {
+          const DataLayout &DL = BBTo->getModule()->getDataLayout();
+          if (usesOperand(Usr, Condition)) {
+            // If Val has Condition as an operand and Val can be folded into a
+            // constant with either Condition == true or Condition == false,
+            // propagate the constant.
+            // eg.
+            //   ; %Val is true on the edge to %then.
+            //   %Val = and i1 %Condition, true.
+            //   br %Condition, label %then, label %else
+            APInt ConditionVal(1, isTrueDest? 1 : 0);
+            Result = constantFoldUser(Val, Condition, ConditionVal, DL);
+          } else {
+            // If one of Val's operand has an inferred value, we may be able to
+            // infer the value of Val.
+            // eg.
+            //    ; %Val is 94 on the edge to %then.
+            //    %Val = add i8 %Op, 1
+            //    %Condition = icmp eq i8 %Op, 93
+            //    br i1 %Condition, label %then, label %else
+            for (unsigned i = 0; i < Usr->getNumOperands(); ++i) {
+              Value *Op = Usr->getOperand(i);
+              LVILatticeVal OpLatticeVal =
+                  getValueFromCondition(Op, Condition, isTrueDest);
+              Optional<APInt> OpConst = OpLatticeVal.getConstantInteger();
+              if (OpConst.hasValue()) {
+                Result = constantFoldUser(Val, Op, OpConst.getValue(), DL);
+                break;
+              }
+            }
+          }
+        }
+      }
       if (!Result.isOverdefined())
         return true;
     }
   }
 
   // If the edge was formed by a switch on the value, then we may know exactly
   // what it is.
   if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
-    if (SI->getCondition() != Val)
+    Value* Condition = SI->getCondition();
+    if (!isa<IntegerType>(Val->getType()))
+      return false;
+    bool ValUsesCondition = false;
+    if (Condition != Val) {
+      // Check if Val has Condition as an operand.
+      if (User *Usr = dyn_cast<User>(Val))
+        ValUsesCondition = usesOperand(Usr, Condition);
+      if (!ValUsesCondition)
         return false;
+    }
+    assert((Condition == Val || ValUsesCondition) &&
+           "Condition != Val nor Val doesn't use Condition");
 
     bool DefaultCase = SI->getDefaultDest() == BBTo;
     unsigned BitWidth = Val->getType()->getIntegerBitWidth();
     ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
 
     for (auto Case : SI->cases()) {
-      ConstantRange EdgeVal(Case.getCaseValue()->getValue());
+      APInt CaseValue = Case.getCaseValue()->getValue();
+      ConstantRange EdgeVal(CaseValue);
+      if (ValUsesCondition) {
+        const DataLayout &DL = BBTo->getModule()->getDataLayout();
+        LVILatticeVal EdgeLatticeVal =
+            constantFoldUser(Val, Condition, CaseValue, DL);
+        if (EdgeLatticeVal.isOverdefined())
+          return false;
+        EdgeVal = EdgeLatticeVal.getConstantRange();
+      }
       if (DefaultCase) {
         // It is possible that the default destination is the destination of
         // some cases. There is no need to perform difference for those cases.
         if (Case.getCaseSuccessor() != BBTo)
           EdgesVals = EdgesVals.difference(EdgeVal);
       } else if (Case.getCaseSuccessor() == BBTo)
         EdgesVals = EdgesVals.unionWith(EdgeVal);
     }

test/Transforms/CorrelatedValuePropagation/range.ll

 
 then:
   %result = icmp eq i32 %a, 255
   ret i1 %result
 
 else:
   ret i1 false
 }
+
+define i32 @test16(i8 %a) {
+entry:
+  %b = zext i8 %a to i32
+  br label %dispatch
+
+dispatch:
+  %cmp = icmp eq i8 %a, 93
+  br i1 %cmp, label %target93, label %dispatch
+
+; CHECK-LABEL: @test16(
+; CHECK: target93:
+; CHECK-NEXT: ret i32 93
+target93:
+  ret i32 %b
+}
+
+define i32 @test16_i1(i1 %a) {
+entry:
+  %b = zext i1 %a to i32
+  br label %dispatch
+
+dispatch:
+  br i1 %a, label %true, label %dispatch
+
+; CHECK-LABEL: @test16_i1(
+; CHECK: true:
+; CHECK-NEXT: ret i32 1
+true:
+  ret i32 %b
+}
+
+define i8 @test17(i8 %a) {
+entry:
+  %c = add i8 %a, 3
+  br label %dispatch
+
+dispatch:
+  %cmp = icmp eq i8 %a, 93
+  br i1 %cmp, label %target93, label %dispatch
+
+; CHECK-LABEL: @test17(
+; CHECK: target93:
+; CHECK-NEXT: ret i8 96
+target93:
+  ret i8 %c
+}
+
+define i8 @test17_2(i8 %a) {
+entry:
+  %c = add i8 %a, %a
+  br label %dispatch
+
+dispatch:
+  %cmp = icmp eq i8 %a, 93
+  br i1 %cmp, label %target93, label %dispatch
+
+; CHECK-LABEL: @test17_2(
+; CHECK: target93:
+; CHECK-NEXT: ret i8 -70
+target93:
+  ret i8 %c
+}
+
+define i1 @test17_i1(i1 %a) {
+entry:
+  %c = and i1 %a, true
+  br label %dispatch
+
+dispatch:
+  br i1 %a, label %true, label %dispatch
+
+; CHECK-LABEL: @test17_i1(
+; CHECK: true:
+; CHECK-NEXT: ret i1 true
+true:
+  ret i1 %c
+}
+
+define i32 @test18(i8 %a) {
+entry:
+  %b = zext i8 %a to i32
+  br label %dispatch
+
+dispatch:
+  switch i8 %a, label %dispatch [
+    i8 93, label %target93
+    i8 -111, label %dispatch
+  ]
+
+; CHECK-LABEL: @test18(
+; CHECK: target93:
+; CHECK-NEXT: ret i32 93
+target93:
+  ret i32 %b
+}
+
+define i8 @test19(i8 %a) {
+entry:
+  %c = add i8 %a, 3
+  br label %dispatch
+
+dispatch:
+  switch i8 %a, label %dispatch [
+    i8 93, label %target93
+    i8 -111, label %dispatch
+  ]
+
+; CHECK-LABEL: @test19(
+; CHECK: target93:
+; CHECK-NEXT: ret i8 96
+target93:
+  ret i8 %c
+}