This is an archive of the discontinued LLVM Phabricator instance.

Differential D41494

[InlineCost] Find more free binary operations
ClosedPublic

Authored by haicheng on Dec 21 2017, 8:04 AM.

Details

Reviewers
chandlerc
eraman
mcrosier
junbuml
hfinkel
Commits
rG6d14dfe8f376: [InlineCost] Find more free binary operations
rL321366: [InlineCost] Find more free binary operations
Summary

Currently, inline cost model considers a binary operator as free only if both its operands are constants. Some simple cases are missing such as a + 0, a - a, etc. This patch modifies visitBinaryOperator() to call SimplifyBinOp() without going through simplifyInstruction() to get rid of the constant restriction. Thus, visitAnd() and visitOr() are not needed.

Here is the impact on code size and performance (spec20xx)

BenchmarkCode Size (%)Perf (%)
(+ is bigger)(+ is faster)
spec2000/gcc0.022.26
spec2006/gcc0.042.18
spec2017/imagick0.031.02
spec2006/perlbench0.000.60
spec2000/crafty0.430.58
spec2017/parest0.010.16
spec2017/gcc-0.010.14
spec2006/xalancbmk0.000.12
spec2006/dealII0.040.10
spec2017/blender0.00-0.04
spec2017/povray-1.46-0.12
spec2017/xalancbmk0.61-0.14
spec2006/povray-1.35-0.15

Diff Detail

Repository
rL LLVM

Event Timeline

haicheng created this revision.Dec 21 2017, 8:04 AM
Herald added a subscriber: javed.absar. · View Herald TranscriptDec 21 2017, 8:04 AM
hfinkel accepted this revision.Dec 21 2017, 9:40 AM
hfinkel added a subscriber: hfinkel.

LGTM

It looks like we could do a similar thing in visitCmpInst too (and visitCallSite, however, we'd also need to fix the FIXME about interface inefficiency in CallAnalyzer::simplifyCallSite first?).

This revision is now accepted and ready to land.Dec 21 2017, 9:40 AM
Closed by commit rL321366: [InlineCost] Find more free binary operations (authored by haicheng). · Explain WhyDec 22 2017, 9:10 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
trunk/
lib/
Analysis/
58 lines
test/
Transforms/
Inline/
AArch64/
291 lines

Diff 128035

llvm/trunk/lib/Analysis/InlineCost.cpp

Show First 20 Lines • Show All 243 Lines • ▼ Show 20 Linesclass CallAnalyzer : public InstVisitor<CallAnalyzer, bool> {
bool visitPHI(PHINode &I); bool visitPHI(PHINode &I);
bool visitGetElementPtr(GetElementPtrInst &I); bool visitGetElementPtr(GetElementPtrInst &I);
bool visitBitCast(BitCastInst &I); bool visitBitCast(BitCastInst &I);
bool visitPtrToInt(PtrToIntInst &I); bool visitPtrToInt(PtrToIntInst &I);
bool visitIntToPtr(IntToPtrInst &I); bool visitIntToPtr(IntToPtrInst &I);
bool visitCastInst(CastInst &I); bool visitCastInst(CastInst &I);
bool visitUnaryInstruction(UnaryInstruction &I); bool visitUnaryInstruction(UnaryInstruction &I);
bool visitCmpInst(CmpInst &I); bool visitCmpInst(CmpInst &I);
bool visitAnd(BinaryOperator &I);
bool visitOr(BinaryOperator &I);
bool visitSub(BinaryOperator &I); bool visitSub(BinaryOperator &I);
bool visitBinaryOperator(BinaryOperator &I); bool visitBinaryOperator(BinaryOperator &I);
bool visitLoad(LoadInst &I); bool visitLoad(LoadInst &I);
bool visitStore(StoreInst &I); bool visitStore(StoreInst &I);
bool visitExtractValue(ExtractValueInst &I); bool visitExtractValue(ExtractValueInst &I);
bool visitInsertValue(InsertValueInst &I); bool visitInsertValue(InsertValueInst &I);
bool visitCallSite(CallSite CS); bool visitCallSite(CallSite CS);
bool visitReturnInst(ReturnInst &RI); bool visitReturnInst(ReturnInst &RI);
▲ Show 20 Lines • Show All 754 Lines • ▼ Show 20 Lines if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) {
} }
disableSROA(CostIt); disableSROA(CostIt);
} }
return false; return false;
} }
bool CallAnalyzer::visitOr(BinaryOperator &I) {
// This is necessary because the generic simplify instruction only works if
// both operands are constants.
for (unsigned i = 0; i < 2; ++i) {
if (ConstantInt *C = dyn_cast_or_null<ConstantInt>(
SimplifiedValues.lookup(I.getOperand(i))))
if (C->isAllOnesValue()) {
SimplifiedValues[&I] = C;
return true;
}
}
return Base::visitOr(I);
}
bool CallAnalyzer::visitAnd(BinaryOperator &I) {
// This is necessary because the generic simplify instruction only works if
// both operands are constants.
for (unsigned i = 0; i < 2; ++i) {
if (ConstantInt *C = dyn_cast_or_null<ConstantInt>(
SimplifiedValues.lookup(I.getOperand(i))))
if (C->isZero()) {
SimplifiedValues[&I] = C;
return true;
}
}
return Base::visitAnd(I);
}
bool CallAnalyzer::visitSub(BinaryOperator &I) { bool CallAnalyzer::visitSub(BinaryOperator &I) {
// Try to handle a special case: we can fold computing the difference of two // Try to handle a special case: we can fold computing the difference of two
// constant-related pointers. // constant-related pointers.
Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
Value *LHSBase, *RHSBase; Value *LHSBase, *RHSBase;
APInt LHSOffset, RHSOffset; APInt LHSOffset, RHSOffset;
std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS); std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS);
if (LHSBase) { if (LHSBase) {
Show All 13 Linesbool CallAnalyzer::visitSub(BinaryOperator &I) {
// Otherwise, fall back to the generic logic for simplifying and handling // Otherwise, fall back to the generic logic for simplifying and handling
// instructions. // instructions.
return Base::visitSub(I); return Base::visitSub(I);
} }
bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) { bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) {
Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
auto Evaluate = [&](SmallVectorImpl<Constant *> &COps) { Constant *CLHS = dyn_cast<Constant>(LHS);
if (!CLHS)
CLHS = SimplifiedValues.lookup(LHS);
Constant *CRHS = dyn_cast<Constant>(RHS);
if (!CRHS)
CRHS = SimplifiedValues.lookup(RHS);
Value *SimpleV = nullptr; Value *SimpleV = nullptr;
if (auto FI = dyn_cast<FPMathOperator>(&I)) if (auto FI = dyn_cast<FPMathOperator>(&I))
SimpleV = SimplifyFPBinOp(I.getOpcode(), COps[0], COps[1], SimpleV = SimplifyFPBinOp(I.getOpcode(), CLHS ? CLHS : LHS,
FI->getFastMathFlags(), DL); CRHS ? CRHS : RHS, FI->getFastMathFlags(), DL);
else else
SimpleV = SimplifyBinOp(I.getOpcode(), COps[0], COps[1], DL); SimpleV =
return dyn_cast_or_null<Constant>(SimpleV); SimplifyBinOp(I.getOpcode(), CLHS ? CLHS : LHS, CRHS ? CRHS : RHS, DL);
};
if (Constant *C = dyn_cast_or_null<Constant>(SimpleV))
SimplifiedValues[&I] = C;
if (simplifyInstruction(I, Evaluate)) if (SimpleV)
return true; return true;
// Disable any SROA on arguments to arbitrary, unsimplified binary operators. // Disable any SROA on arguments to arbitrary, unsimplified binary operators.
disableSROA(LHS); disableSROA(LHS);
disableSROA(RHS); disableSROA(RHS);
// If the instruction is floating point, and the target says this operation // If the instruction is floating point, and the target says this operation
// is expensive, this may eventually become a library call. Treat the cost // is expensive, this may eventually become a library call. Treat the cost
▲ Show 20 Lines • Show All 1,034 Lines • Show Last 20 Lines

llvm/trunk/test/Transforms/Inline/AArch64/binop.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 @outer_add1(i32 %a) {
; CHECK-LABEL: @outer_add1(
; CHECK-NOT: call i32 @add
%C = call i32 @add(i32 %a, i32 0)
ret i32 %C
}
define i32 @outer_add2(i32 %a) {
; CHECK-LABEL: @outer_add2(
; CHECK-NOT: call i32 @add
%C = call i32 @add(i32 0, i32 %a)
ret i32 %C
}
define i32 @add(i32 %a, i32 %b) {
%add = add i32 %a, %b
call void @pad()
store i32 0, i32* @glbl
ret i32 %add
}
define i32 @outer_sub1(i32 %a) {
; CHECK-LABEL: @outer_sub1(
; CHECK-NOT: call i32 @sub1
%C = call i32 @sub1(i32 %a, i32 0)
ret i32 %C
}
define i32 @sub1(i32 %a, i32 %b) {
%sub = sub i32 %a, %b
call void @pad()
store i32 0, i32* @glbl
ret i32 %sub
}
define i32 @outer_sub2(i32 %a) {
; CHECK-LABEL: @outer_sub2(
; CHECK-NOT: call i32 @sub2
%C = call i32 @sub2(i32 %a)
ret i32 %C
}
define i32 @sub2(i32 %a) {
%sub = sub i32 %a, %a
call void @pad()
ret i32 %sub
}
define i32 @outer_mul1(i32 %a) {
; CHECK-LABEL: @outer_mul1(
; CHECK-NOT: call i32 @mul
%C = call i32 @mul(i32 %a, i32 0)
ret i32 %C
}
define i32 @outer_mul2(i32 %a) {
; CHECK-LABEL: @outer_mul2(
; CHECK-NOT: call i32 @mul
%C = call i32 @mul(i32 %a, i32 1)
ret i32 %C
}
define i32 @mul(i32 %a, i32 %b) {
%mul = mul i32 %a, %b
call void @pad()
store i32 0, i32* @glbl
ret i32 %mul
}
define i32 @outer_div1(i32 %a) {
; CHECK-LABEL: @outer_div1(
; CHECK-NOT: call i32 @div1
%C = call i32 @div1(i32 0, i32 %a)
ret i32 %C
}
define i32 @outer_div2(i32 %a) {
; CHECK-LABEL: @outer_div2(
; CHECK-NOT: call i32 @div1
%C = call i32 @div1(i32 %a, i32 1)
ret i32 %C
}
define i32 @div1(i32 %a, i32 %b) {
%div = sdiv i32 %a, %b
call void @pad()
store i32 0, i32* @glbl
ret i32 %div
}
define i32 @outer_div3(i32 %a) {
; CHECK-LABEL: @outer_div3(
; CHECK-NOT: call i32 @div
%C = call i32 @div2(i32 %a)
ret i32 %C
}
define i32 @div2(i32 %a) {
%div = sdiv i32 %a, %a
call void @pad()
ret i32 %div
}
define i32 @outer_rem1(i32 %a) {
; CHECK-LABEL: @outer_rem1(
; CHECK-NOT: call i32 @rem
%C = call i32 @rem1(i32 0, i32 %a)
ret i32 %C
}
define i32 @outer_rem2(i32 %a) {
; CHECK-LABEL: @outer_rem2(
; CHECK-NOT: call i32 @rem
%C = call i32 @rem1(i32 %a, i32 1)
ret i32 %C
}
define i32 @rem1(i32 %a, i32 %b) {
%rem = urem i32 %a, %b
call void @pad()
store i32 0, i32* @glbl
ret i32 %rem
}
define i32 @outer_rem3(i32 %a) {
; CHECK-LABEL: @outer_rem3(
; CHECK-NOT: call i32 @rem
%C = call i32 @rem2(i32 %a)
ret i32 %C
}
define i32 @rem2(i32 %a) {
%rem = urem i32 %a, %a
call void @pad()
ret i32 %rem
}
define i32 @outer_shl1(i32 %a) {
; CHECK-LABEL: @outer_shl1(
; CHECK-NOT: call i32 @shl
%C = call i32 @shl(i32 %a, i32 0)
ret i32 %C
}
define i32 @shl(i32 %a, i32 %b) {
%shl = shl i32 %a, %b
call void @pad()
store i32 0, i32* @glbl
ret i32 %shl
}
define i32 @outer_shr1(i32 %a) {
; CHECK-LABEL: @outer_shr1(
; CHECK-NOT: call i32 @shr
%C = call i32 @shr(i32 %a, i32 0)
ret i32 %C
}
define i32 @shr(i32 %a, i32 %b) {
%shr = ashr i32 %a, %b
call void @pad()
store i32 0, i32* @glbl
ret i32 %shr
}
define i1 @outer_and1(i1 %a) {
; check-label: @outer_and1(
; check-not: call i1 @and1
%c = call i1 @and1(i1 %a, i1 false)
ret i1 %c
}
define i1 @outer_and2(i1 %a) {
; check-label: @outer_and2(
; check-not: call i1 @and1
%c = call i1 @and1(i1 %a, i1 true)
ret i1 %c
}
define i1 @and1(i1 %a, i1 %b) {
%and = and i1 %a, %b
call void @pad()
store i32 0, i32* @glbl
ret i1 %and
}
define i1 @outer_and3(i1 %a) {
; check-label: @outer_and3(
; check-not: call i1 @and2
%c = call i1 @and2(i1 %a)
ret i1 %c
}
define i1 @and2(i1 %a) {
%and = and i1 %a, %a
call void @pad()
ret i1 %and
}
define i1 @outer_or1(i1 %a) {
; check-label: @outer_or1(
; check-not: call i1 @or1
%c = call i1 @or1(i1 %a, i1 false)
ret i1 %c
}
define i1 @outer_or2(i1 %a) {
; check-label: @outer_or2(
; check-not: call i1 @or1
%c = call i1 @or1(i1 %a, i1 true)
ret i1 %c
}
define i1 @or1(i1 %a, i1 %b) {
%or = or i1 %a, %b
call void @pad()
store i32 0, i32* @glbl
ret i1 %or
}
define i1 @outer_or3(i1 %a) {
; check-label: @outer_or3(
; check-not: call i1 @or2
%c = call i1 @or2(i1 %a)
ret i1 %c
}
define i1 @or2(i1 %a) {
%or = or i1 %a, %a
call void @pad()
ret i1 %or
}
define i1 @outer_xor1(i1 %a) {
; check-label: @outer_xor1(
; check-not: call i1 @xor
%c = call i1 @xor1(i1 %a, i1 false)
ret i1 %c
}
define i1 @xor1(i1 %a, i1 %b) {
%xor = xor i1 %a, %b
call void @pad()
store i32 0, i32* @glbl
ret i1 %xor
}
define i1 @outer_xor3(i1 %a) {
; check-label: @outer_xor3(
; check-not: call i1 @xor
%c = call i1 @xor2(i1 %a)
ret i1 %c
}
define i1 @xor2(i1 %a) {
%xor = xor i1 %a, %a
call void @pad()
ret i1 %xor
}