[InlineCost] add visitSelectInst()

[haicheng]

Summary

This patch adds visitSelectInst() to find free Select IRs and continue the propagation of SimplifiedValues, ConstantOffsetPtrs, and SROAArgValues.

We don't need all operands of Select IR to be constants to fold it, so I don't use the generic CallAnalyzer::simplifyInstruction().

The impact on SPEC20xx is below

Benchmark	Code Size (%)	Perf (%)
	(+ is bigger)	(+ is faster)
spec2000/gcc	0.01	1.08
spec2000/mesa	0.04	2.2
spec2000/twolf	-0.15	-0.01
spec2006/gcc	0.02	-0.19
spec2006/h264ref	0.33	0.18
spec2017/blender	0.01	0.5
spec2017/gcc	0.01	0.09
spec2017/imagick	0.02	0.01
spec2017/parest	0	-0.05
spec2017/perlbench	0.1	0.56

[mcrosier]

Overall, the logic of the patch is in good shape. However, I'd suggest some minor refactoring to delineate the select of constants/values vs. GEPs for SROA.

Maybe something like this:

bool CallAnalyzer::visitSelectInst(SelectInst &SI) {
  Value *TrueVal = SI.getTrueValue();
  Value *FalseVal = SI.getFalseValue();

  Constant *TrueC = isa<Constant>(TrueVal) ? cast<Constant>(TrueVal)
                                           : SimplifiedValues.lookup(TrueVal);
  Constant *FalseC = isa<Constant>(FalseVal)
                         ? cast<Constant>(FalseVal)
                         : SimplifiedValues.lookup(FalseVal);
  // Select C, X, X => X
  if (TrueC && FalseC && TrueC == FalseC) {
    SimplifiedValues[&SI] = TrueC;
    return true;
  }

  Type *ValTy = FalseVal->getType();
  assert(TrueVal->getType() == FalseVal->getType() &&
         "Expected matching types.");

  Constant *CondC =
      dyn_cast_or_null<Constant>(SimplifiedValues.lookup(SI.getCondition()));
  // Select condition is a constant.
  if (CondC && !ValTy->isPointerTy()) {
    // Select True, X, Y => X
    if (CondC->isAllOnesValue() && TrueC)
      SimplifiedValues[&SI] = TrueC;
    // Select False, X, Y => Y
    if (CondC->isNullValue() && FalseC)
      SimplifiedValues[&SI] = FalseC;
    // If all operands are constants.  ConstantExpr::getSelect() can handle
    // rest cases such as select vectors.
    if (TrueC && FalseC)
      if (Constant *C = ConstantExpr::getSelect(CondC, TrueC, FalseC))
        SimplifiedValues[&SI] = C;
    return true;
  }

  // Logic for SROA follows
  // Select C, X, X => X
  // Select True, X, Y => X
  // Select False, X, Y => Y

  return Base::visitSelectInst(SI);
}

IMHO this is a little easier to read.

[haicheng]

Move code around as suggested by Chad. Thank you.

[haicheng]

Kindly PIng

[mcrosier]

lib/Analysis/InlineCost.cpp

1190 ↗

(On Diff #113429)

Not sure it matters a great deal, but this could also be written as

if ((TrueC || FalseC) && TrueC == FalseC) {

Feel free to take it or leave it; either way is probably fine.

1211 ↗

(On Diff #113429)

can handle the rest of the cases, such as select vectors.

1220 ↗

(On Diff #113429)

toi -> to

[eraman]

lib/Analysis/InlineCost.cpp

1182 ↗

(On Diff #113429)

I added simplifyInstruction to handle instruction simplification with constant values. Now, it handles cases only when all the operands are constants - either as such or after looking up SimplifiedValues. It can be extended to handle cases like this where you don't need all operands to be constants. May be add a bool to indicate whether it should call the Callable even if all operands are not constants and use that here?

[haicheng]

Extend simplifyInstruction() to handle the cases that not all operands are constants. Use SimplifySelectInst() to process Select.

Thank you.

Haicheng

[eraman]

lib/Analysis/InlineCost.cpp

496 ↗

(On Diff #115570)

Sorry, I should have thought through this carefully. My bad. I feel this version is worse than before. Most callers of simplifyInstruction pass a callable that takes a vector of Value * and implicitly treats it as a vector of Constant *. Feel free to go back the the previous version or come up with a better way to refactor simplifyInstruction. My main motivation for the refactoring was to keep accesses to SimplifiedValues in one location, so that we can get data on how often does inlining actually simplifies a value to a constant.

[chandlerc]

Just wanted to say thanks so much for working on this -- its a huge improvement to the inline cost.

lib/Analysis/InlineCost.cpp

496 ↗

(On Diff #115570)

FWIW, I agree. I looked at both versions, and I think the custom select handling is better. It's hard to tell ahead of time, so still, thanks for exploring whether this helps.

1201 ↗

(On Diff #113429)

No need to separately test for true and false once you know the condition is a constant. Just check isNullValue(). It's either false, or true. =]

1212–1217 ↗

(On Diff #113429)

I feel like we should handle this above when handling TrueC == FalseC.

1222–1249 ↗

(On Diff #113429)

I think this code will be substantially simpler if you refactor it in the following way.

First, check if the condition is a constant. If *not* a constant, then handle the only cases we can handle in that world: equal (or constant expr-able) inputs, or matching SROA args like here. Then return.

Rest of the function only handling when it *is* a constant. Then assign the input the constant will select to a variable, and only do all the checks on that one variable rather on both true and false variants.

[haicheng]

Thank you, Chandler. I will update the patch shortly.

lib/Analysis/InlineCost.cpp

1201 ↗

(On Diff #113429)

The vector constant condition can be <i1 true, i1 false>. It is neither AllOnesValue or NullValue.

[chandlerc]

lib/Analysis/InlineCost.cpp

1201 ↗

(On Diff #113429)

Ah, I see.

But if you have a constant condition, even if a vector with a mixture of true and false elements, you can fully simulate the select (and we should). The test should be "is it a constant". Once we know that it is, we should be able to get at each element and test whether that element is a null value or not. And then the scalar case will just be the same as a 1-element vector.

[haicheng]

Back to the customized implementation, reorganized the code, rewrote the test cases.

Please take a look. Thank you.

[chandlerc]

Mostly minor suggestions below...

lib/Analysis/InlineCost.cpp

1186–1190 ↗

(On Diff #116367)

I'd still use dyn_cast here:

Constant *TrueC = dyn_cast<Constant>(TrueVal);
if (!TrueC)
  TrueC = SimplifiedValues.lookup(TrueVal);

1196 ↗

(On Diff #116367)

I'd simplify this as: TrueC == FalseC && TrueC.

1230 ↗

(On Diff #116367)

auto?

1238–1239 ↗

(On Diff #116367)

I think just dyn_cast<Constant>(SelectedV) is easier to read and no more expensive.

[haicheng]

Address Chandler's comments. Please take a look. Thank you.

[chandlerc]

This is looking pretty good. Some nit-picky improvements below. I'd love for Easwaran to get another chance to look at this too though...

lib/Analysis/InlineCost.cpp

1202 ↗

(On Diff #116451)

Prefer early exit here, and below:

if (!CheckSROA)
  return Base::visitSelectInst(SI);

1207–1208 ↗

(On Diff #116451)

Similar to the above, this can be:

if (TrueBaseAndOffset == FalseBaseAndOffset && TrueBaseAndOffset.first)

1245 ↗

(On Diff #116451)

Early return here as well.

[haicheng]

Address Chandler's comments. Please take a look. Thank you.

[eraman]

LGTM

[chandlerc]

(Marking as accepted now that Easwaran has had a chance to look as well)

llvm/trunk/lib/Analysis/InlineCost.cpp

class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
   bool visitBinaryOperator(BinaryOperator &I);
   bool visitLoad(LoadInst &I);
   bool visitStore(StoreInst &I);
   bool visitExtractValue(ExtractValueInst &I);
   bool visitInsertValue(InsertValueInst &I);
   bool visitCallSite(CallSite CS);
   bool visitReturnInst(ReturnInst &RI);
   bool visitBranchInst(BranchInst &BI);
+  bool visitSelectInst(SelectInst &SI);
   bool visitSwitchInst(SwitchInst &SI);
   bool visitIndirectBrInst(IndirectBrInst &IBI);
   bool visitResumeInst(ResumeInst &RI);
   bool visitCleanupReturnInst(CleanupReturnInst &RI);
   bool visitCatchReturnInst(CatchReturnInst &RI);
   bool visitUnreachableInst(UnreachableInst &I);
 
 public:
bool CallAnalyzer::visitBranchInst(BranchInst &BI) {
   // shouldn't exist at all, but handling them makes the behavior of the
   // inliner more regular and predictable. Interestingly, conditional branches
   // which will fold away are also free.
   return BI.isUnconditional() || isa<ConstantInt>(BI.getCondition()) ||
          dyn_cast_or_null<ConstantInt>(
              SimplifiedValues.lookup(BI.getCondition()));
 }
 
+bool CallAnalyzer::visitSelectInst(SelectInst &SI) {
+  bool CheckSROA = SI.getType()->isPointerTy();
+  Value *TrueVal = SI.getTrueValue();
+  Value *FalseVal = SI.getFalseValue();
+
+  Constant *TrueC = dyn_cast<Constant>(TrueVal);
+  if (!TrueC)
+    TrueC = SimplifiedValues.lookup(TrueVal);
+  Constant *FalseC = dyn_cast<Constant>(FalseVal);
+  if (!FalseC)
+    FalseC = SimplifiedValues.lookup(FalseVal);
+  Constant *CondC =
+      dyn_cast_or_null<Constant>(SimplifiedValues.lookup(SI.getCondition()));
+
+  if (!CondC) {
+    // Select C, X, X => X
+    if (TrueC == FalseC && TrueC) {
+      SimplifiedValues[&SI] = TrueC;
+      return true;
+    }
+
+    if (!CheckSROA)
+      return Base::visitSelectInst(SI);
+
+    std::pair<Value *, APInt> TrueBaseAndOffset =
+        ConstantOffsetPtrs.lookup(TrueVal);
+    std::pair<Value *, APInt> FalseBaseAndOffset =
+        ConstantOffsetPtrs.lookup(FalseVal);
+    if (TrueBaseAndOffset == FalseBaseAndOffset && TrueBaseAndOffset.first) {
+      ConstantOffsetPtrs[&SI] = TrueBaseAndOffset;
+
+      Value *SROAArg;
+      DenseMap<Value *, int>::iterator CostIt;
+      if (lookupSROAArgAndCost(TrueVal, SROAArg, CostIt))
+        SROAArgValues[&SI] = SROAArg;
+      return true;
+    }
+
+    return Base::visitSelectInst(SI);
+  }
+
+  // Select condition is a constant.
+  Value *SelectedV = CondC->isAllOnesValue()
+                         ? TrueVal
+                         : (CondC->isNullValue()) ? FalseVal : nullptr;
+  if (!SelectedV) {
+    // Condition is a vector constant that is not all 1s or all 0s.  If all
+    // operands are constants, ConstantExpr::getSelect() can handle the cases
+    // such as select vectors.
+    if (TrueC && FalseC) {
+      if (auto *C = ConstantExpr::getSelect(CondC, TrueC, FalseC)) {
+        SimplifiedValues[&SI] = C;
+        return true;
+      }
+    }
+    return Base::visitSelectInst(SI);
+  }
+
+  // Condition is either all 1s or all 0s. SI can be simplified.
+  if (Constant *SelectedC = dyn_cast<Constant>(SelectedV)) {
+    SimplifiedValues[&SI] = SelectedC;
+    return true;
+  }
+
+  if (!CheckSROA)
+    return true;
+
+  std::pair<Value *, APInt> BaseAndOffset =
+      ConstantOffsetPtrs.lookup(SelectedV);
+  if (BaseAndOffset.first) {
+    ConstantOffsetPtrs[&SI] = BaseAndOffset;
+
+    Value *SROAArg;
+    DenseMap<Value *, int>::iterator CostIt;
+    if (lookupSROAArgAndCost(SelectedV, SROAArg, CostIt))
+      SROAArgValues[&SI] = SROAArg;
+  }
+
+  return true;
+}
+
 bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) {
   // We model unconditional switches as free, see the comments on handling
   // branches.
   if (isa<ConstantInt>(SI.getCondition()))
     return true;
   if (Value *V = SimplifiedValues.lookup(SI.getCondition()))
     if (isa<ConstantInt>(V))
       return true;

llvm/trunk/test/Transforms/Inline/AArch64/select.ll

+; RUN: opt -inline -mtriple=aarch64--linux-gnu -S -o - < %s -inline-threshold=0 | FileCheck %s
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64--linux-gnu"
+
+declare void @pad()
+@glbl = external global i32
+
+define i32 @outer1(i1 %cond) {
+; CHECK-LABEL: @outer1(
+; CHECK-NOT: call i32 @inner1
+  %C = call i32 @inner1(i1 %cond, i32 1)
+  ret i32 %C
+}
+
+define i32 @inner1(i1 %cond, i32 %val) {
+  %select = select i1 %cond, i32 1, i32 %val       ; Simplified to 1
+  call void @pad()
+  store i32 0, i32* @glbl
+  ret i32 %select                                  ; Simplifies to ret i32 1
+}
+
+
+define i32 @outer2(i32 %val) {
+; CHECK-LABEL: @outer2(
+; CHECK-NOT: call i32 @inner2
+  %C = call i32 @inner2(i1 true, i32 %val)
+  ret i32 %C
+}
+
+define i32 @inner2(i1 %cond, i32 %val) {
+  %select = select i1 %cond, i32 1, i32 %val       ; Simplifies to 1
+  call void @pad()
+  store i32 0, i32* @glbl
+  ret i32 %select                                  ; Simplifies to ret i32 1
+}
+
+
+define i32 @outer3(i32 %val) {
+; CHECK-LABEL: @outer3(
+; CHECK-NOT: call i32 @inner3
+  %C = call i32 @inner3(i1 false, i32 %val)
+  ret i32 %C
+}
+
+define i32 @inner3(i1 %cond, i32 %val) {
+  %select = select i1 %cond, i32 %val, i32 -1      ; Simplifies to -1
+  call void @pad()
+  store i32 0, i32* @glbl
+  ret i32 %select                                  ; Simplifies to ret i32 -1
+}
+
+
+define i32 @outer4() {
+; CHECK-LABEL: @outer4(
+; CHECK-NOT: call i32 @inner4
+  %C = call i32 @inner4(i1 true, i32 1, i32 -1)
+  ret i32 %C
+}
+
+define i32 @inner4(i1 %cond, i32 %val1, i32 %val2) {
+  %select = select i1 %cond, i32 %val1, i32 %val2  ; Simplifies to 1
+  call void @pad()
+  store i32 0, i32* @glbl
+  store i32 1, i32* @glbl
+  ret i32 %select                                  ; Simplifies to ret i32 1
+}
+
+
+define i1 @outer5() {
+; CHECK-LABEL: @outer5(
+; CHECK-NOT: call i1 @inner5
+  %C = call i1 @inner5(i1 true, i1 true, i1 false)
+  ret i1 %C
+}
+
+declare void @dead()
+
+define i1 @inner5(i1 %cond, i1 %val1, i1 %val2) {
+  %select = select i1 %cond, i1 %val1, i1 %val2    ; Simplifies to true
+  br i1 %select, label %exit, label %isfalse       ; Simplifies to br label %end
+
+isfalse:                                           ; This block is unreachable once inlined
+  call void @dead()
+  br label %exit
+
+exit:
+  store i32 0, i32* @glbl
+  ret i1 %select                                   ; Simplifies to ret i1 true
+}
+
+
+define i32 @outer6(i1 %cond) {
+; CHECK-LABEL: @outer6(
+; CHECK-NOT: call i32 @inner6
+  %A = alloca i32
+  %C = call i32 @inner6(i1 %cond, i32* %A)
+  ret i32 %C
+}
+
+define i32 @inner6(i1 %cond, i32* %ptr) {
+  %G1 = getelementptr inbounds i32, i32* %ptr, i32 1
+  %G2 = getelementptr inbounds i32, i32* %G1, i32 1
+  %G3 = getelementptr inbounds i32, i32* %ptr, i32 2
+  %select = select i1 %cond, i32* %G2, i32* %G3    ; Simplified to %A[2]
+  %load = load i32, i32* %select                   ; SROA'ed
+  call void @pad()
+  ret i32 %load                                    ; Simplified
+}
+
+
+define i32 @outer7(i32* %ptr) {
+; CHECK-LABEL: @outer7(
+; CHECK-NOT: call i32 @inner7
+  %A = alloca i32
+  %C = call i32 @inner7(i1 true, i32* %A, i32* %ptr)
+  ret i32 %C
+}
+
+define i32 @inner7(i1 %cond, i32* %p1, i32* %p2) {
+  %select = select i1 %cond, i32* %p1, i32* %p2    ; Simplifies to %A
+  %load = load i32, i32* %select                   ; SROA'ed
+  call void @pad()
+  store i32 0, i32* @glbl
+  ret i32 %load                                    ; Simplified
+}
+
+
+define i32 @outer8(i32* %ptr) {
+; CHECK-LABEL: @outer8(
+; CHECK-NOT: call i32 @inner8
+  %A = alloca i32
+  %C = call i32 @inner8(i1 false, i32* %ptr, i32* %A)
+  ret i32 %C
+}
+
+define i32 @inner8(i1 %cond, i32* %p1, i32* %p2) {
+  %select = select i1 %cond, i32* %p1, i32* %p2    ; Simplifies to %A
+  %load = load i32, i32* %select                   ; SROA'ed
+  call void @pad()
+  store i32 0, i32* @glbl
+  ret i32 %load                                    ; Simplified
+}
+
+
+define <2 x i32> @outer9(<2 x i32> %val) {
+; CHECK-LABEL: @outer9(
+; CHECK-NOT: call <2 x i32> @inner9
+  %C = call <2 x i32> @inner9(<2 x i1> <i1 true, i1 true>, <2 x i32> %val)
+  ret <2 x i32> %C
+}
+
+define <2 x i32> @inner9(<2 x i1> %cond, <2 x i32> %val) {
+  %select = select <2 x i1> %cond, <2 x i32> <i32 1, i32 1>, <2 x i32> %val              ; Simplifies to <1, 1>
+  call void @pad()
+  store i32 0, i32* @glbl
+  ret <2 x i32> %select                                                                  ; Simplifies to ret <2 x i32> <1, 1>
+}
+
+
+define <2 x i32> @outer10(<2 x i32> %val) {
+; CHECK-LABEL: @outer10(
+; CHECK-NOT: call <2 x i32> @inner10
+  %C = call <2 x i32> @inner10(<2 x i1> <i1 false, i1 false>, <2 x i32> %val)
+  ret <2 x i32> %C
+}
+
+define <2 x i32> @inner10(<2 x i1> %cond, <2 x i32> %val) {
+  %select = select <2 x i1> %cond, < 2 x i32> %val, <2 x i32> <i32 -1, i32 -1>           ; Simplifies to <-1, -1>
+  call void @pad()
+  store i32 0, i32* @glbl
+  ret <2 x i32> %select                                                                  ; Simplifies to ret <2 x i32> <-1, -1>
+}
+
+
+define <2 x i32> @outer11() {
+; CHECK-LABEL: @outer11(
+; CHECK-NOT: call <2 x i32> @inner11
+  %C = call <2 x i32> @inner11(<2 x i1> <i1 true, i1 false>)
+  ret <2 x i32> %C
+}
+
+define <2 x i32> @inner11(<2 x i1> %cond) {
+  %select = select <2 x i1> %cond, <2 x i32> <i32 1, i32 1>, < 2 x i32> <i32 -1, i32 -1> ; Simplifies to <1, -1>
+  call void @pad()
+  ret <2 x i32> %select                                                                  ; Simplifies to ret <2 x i32> <1, -1>
+}
+
+
+define i1 @outer12(i32* %ptr) {
+; CHECK-LABEL: @outer12(
+; CHECK-NOT: call i1 @inner12
+  %C = call i1 @inner12(i1 true, i32* @glbl, i32* %ptr)
+  ret i1 %C
+}
+
+define i1 @inner12(i1 %cond, i32* %ptr1, i32* %ptr2) {
+  %select = select i1 %cond, i32* %ptr1, i32* %ptr2 ; Simplified to @glbl
+  %cmp = icmp eq i32* %select, @glbl                ; Simplified to true
+  call void @pad()
+  store i32 0, i32* @glbl
+  ret i1 %cmp                                       ; Simplifies to ret i1 true
+}
+
+
+define <2 x i32> @outer13(<2 x i32> %val1, <2 x i32> %val2) {
+; CHECK-LABEL: @outer13(
+; CHECK: call <2 x i32> @inner13
+  %C = call <2 x i32> @inner13(<2 x i1> <i1 true, i1 false>, <2 x i32> %val1, <2 x i32> %val2)
+  ret <2 x i32> %C
+}
+
+define <2 x i32> @inner13(<2 x i1> %cond, <2 x i32> %val1, < 2 x i32> %val2) {
+  %select = select <2 x i1> %cond, <2 x i32> %val1, < 2 x i32> %val2 ; Cannot be Simplified
+  call void @pad()
+  store i32 0, i32* @glbl
+  store i32 1, i32* @glbl
+  ret <2 x i32> %select                                              ; Simplified
+}
+
+
+define i32 @outer14(i32 %val1, i32 %val2) {
+; CHECK-LABEL: @outer14(
+; CHECK-NOT: call i32 @inner14
+  %C = call i32 @inner14(i1 true, i32 %val1, i32 %val2)
+  ret i32 %C
+}
+
+define i32 @inner14(i1 %cond, i32 %val1, i32 %val2) {
+  %select = select i1 %cond, i32 %val1, i32 %val2   ; Simplified to %val1
+  call void @pad()
+  store i32 0, i32* @glbl
+  store i32 1, i32* @glbl
+  ret i32 %select                                   ; Simplifies to ret i32 %val1
+}
+
+
+define i32 @outer15(i32 %val1, i32 %val2) {
+; CHECK-LABEL: @outer15(
+; CHECK-NOT: call i32 @inner15
+  %C = call i32 @inner15(i1 false, i32 %val1, i32 %val2)
+  ret i32 %C
+}
+
+define i32 @inner15(i1 %cond, i32 %val1, i32 %val2) {
+  %select = select i1 %cond, i32 %val1, i32 %val2   ; Simplified to %val2
+  call void @pad()
+  store i32 0, i32* @glbl
+  store i32 1, i32* @glbl
+  ret i32 %select                                   ; Simplifies to ret i32 %val2
+}