Page MenuHomePhabricator

Optimize sext/zext insertion algorithm in back-end
ClosedPublic

Authored by Jiangning on Sep 8 2014, 8:01 PM.

Details

Summary

This is the updated patch for reverted patch "r216066 - Optimize ZERO_EXTEND and SIGN_EXTEND in both SelectionDAG Builder and type".

The solution of r216066 slowed down a huge case reported by Rafael, so it was reverted. The root cause is CopyValueToVirtualRegisters in SelectionDAGBuilder is called too many times in back-end, and my original algorithm was to check all users for a value, so the time complexity could increase from O(n) to O(n^2) specifically for this feature.

The new solution tries to do early decision making before real ISEL stage, and get the sext/zext preferences stored into FuncInfo. We can do this because deciding preferred sext/zext doesn't depend on SDNode but LLVM IR. This way, we will be able to calculate the info once and use it many times in real ISEL stage.

With this patch, we won't see any slowdown for the test case at https://drive.google.com/file/d/0B7iRtublysV6RVpFUGNxaUcwc1E/edit?usp=sharing, which is a huge one.

Thanks,
-Jiangning

Diff Detail

Event Timeline

Jiangning updated this revision to Diff 13438.Sep 8 2014, 8:01 PM
Jiangning retitled this revision from to Optimize sext/zext insertion algorithm in back-end.
Jiangning updated this object.
Jiangning edited the test plan for this revision. (Show Details)
Jiangning added a reviewer: t.p.northover.
Jiangning set the repository for this revision to rL LLVM.
Jiangning added a subscriber: Unknown Object (MLST).
majnemer added inline comments.
lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp
68

int is redundant.

70

CmpInst is redundant with the dyn_cast, auto would be more concise.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
867–868

You'd save some space by declaring OpL and OpR while defining them.

Jiangning updated this revision to Diff 13692.Sep 14 2014, 10:00 PM

Patch is updated following feedbacks.

Hi majnemer,

All feedbacks are accepted and patch is updated.

Thanks,
-Jiangning

lib/CodeGen/SelectionDAG/FunctionLoweringInfo.cpp
68

OK.

70

OK.

lib/CodeGen/SelectionDAG/LegalizeIntegerTypes.cpp
867–868

OK.

jmolloy accepted this revision.Sep 18 2014, 7:46 AM
jmolloy added a reviewer: jmolloy.
jmolloy added a subscriber: jmolloy.

Hi Jiangning,

This looks good to me, with the two minor comments addressed.

Cheers,

James

include/llvm/CodeGen/FunctionLoweringInfo.h
112

s/Perferred/Preferred/

test/CodeGen/AArch64/atomic-ops.ll
512

Why the changes to this file?

This revision is now accepted and ready to land.Sep 18 2014, 7:46 AM
Jiangning added inline comments.Sep 18 2014, 9:26 PM
include/llvm/CodeGen/FunctionLoweringInfo.h
112

OK. I will fix that.

test/CodeGen/AArch64/atomic-ops.ll
512

This is just because this instruction is in the 2nd basic block, and the operand is in the 1st basic block. Previously, the algorithm simply uses ZEXT for all scenarios, and it implies passing a zero-extended value crossing basic block. Now with this patch, the algorithm will prefer to use SEXT, because there is a compare instruction following sxtb generated for LLVM IR "atomicrmw min i8* @var8, i8 %offset acquire" and it is with sign predicate, so now we will prefer to pass sign-extended value crossing basic block.

committed as r218101.

mcrosier closed this revision.Sep 22 2014, 10:50 AM