Differential D16836
[CodeGenPrepare] Remove load-based heuristic Authored by flyingforyou on Feb 2 2016, 7:27 PM.
Details Both the hardware and LLVM have changed since 2012. There is no regressons and improvements on spec2000/2006. (Cortex-A57, Core i5). But There are two big improvements in test-suite.
And I didn't see notable regressions in test-suite.
Diff Detail Event Timeline
Comment Actions for.body4: ; preds = %for.body4, %for.cond1.preheader %indvars.iv = phi i64 [ 0, %for.cond1.preheader ], [ %indvars.iv.next, %for.body4 ] %j.126 = phi i32 [ -1, %for.cond1.preheader ], [ %j.2, %for.body4 ] %scevgep = getelementptr double, double* getelementptr inbounds (%struct.GlobalData, %struct.GlobalData* @global_data, i32 0, i32 0, i32 0), i64 %indvars.iv %3 = load double, double* %scevgep, align 8, !tbaa !5 %cmp5 = fcmp olt double %3, 0.000000e+00 %tmp = trunc i64 %indvars.iv to i32 %j.2 = select i1 %cmp5, i32 %tmp, i32 %j.126 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 %exitcond = icmp eq i64 32000, %indvars.iv.next br i1 %exitcond, label %for.cond.cleanup3, label %for.body4 In this case, %tmp, %j.126 is target for sinking. This code will translate to arm64 likes below. 40b684: 8b080e69 add x9, x19, x8, lsl #3 40b688: 6d400520 ldp d0, d1, [x9] 40b68c: 1e602008 fcmp d0, #0.0 40b690: 1a94410a csel w10, w8, w20, mi 40b694: 1e602028 fcmp d1, #0.0 40b698: 6d410520 ldp d0, d1, [x9,#16] 40b69c: 91000508 add x8, x8, #0x1 40b6a0: 1a8a410a csel w10, w8, w10, mi 40b6a4: 1e602008 fcmp d0, #0.0 40b6a8: fd401120 ldr d0, [x9,#32] 40b6ac: 1a88554a csinc w10, w10, w8, pl 40b6b0: 1e602028 fcmp d1, #0.0 40b6b4: 91000908 add x8, x8, #0x2 40b6b8: 1a8a410a csel w10, w8, w10, mi 40b6bc: 1e602008 fcmp d0, #0.0 40b6c0: 1a885554 csinc w20, w10, w8, pl 40b6c4: 91000908 add x8, x8, #0x2 40b6c8: eb1b011f cmp x8, x27 40b6cc: 54fffdc1 b.ne 40b684 <s331+0xb4> before patch 40b684: fc697a60 ldr d0, [x19,x9,lsl #3] 40b688: 2a0903e0 mov w0, w9 40b68c: 1e602008 fcmp d0, #0.0 40b690: 54000044 b.mi 40b698 <s331+0xc8> 40b694: 2a1403e0 mov w0, w20 40b698: 8b090e68 add x8, x19, x9, lsl #3 40b69c: 91000529 add x9, x9, #0x1 40b6a0: 2a0903e1 mov w1, w9 40b6a4: fd400500 ldr d0, [x8,#8] 40b6a8: 1e602008 fcmp d0, #0.0 40b6ac: 54000044 b.mi 40b6b4 <s331+0xe4> 40b6b0: 2a0003e1 mov w1, w0 40b6b4: fd400900 ldr d0, [x8,#16] 40b6b8: 91000529 add x9, x9, #0x1 40b6bc: 2a0903e0 mov w0, w9 40b6c0: 1e602008 fcmp d0, #0.0 40b6c4: 54000044 b.mi 40b6cc <s331+0xfc> 40b6c8: 2a0103e0 mov w0, w1 40b6cc: fd400d00 ldr d0, [x8,#24] 40b6d0: 91000529 add x9, x9, #0x1 40b6d4: 2a0903e1 mov w1, w9 40b6d8: 1e602008 fcmp d0, #0.0 40b6dc: 54000044 b.mi 40b6e4 <s331+0x114> 40b6e0: 2a0003e1 mov w1, w0 40b6e4: fd401100 ldr d0, [x8,#32] 40b6e8: 91000528 add x8, x9, #0x1 40b6ec: 2a0803f4 mov w20, w8 40b6f0: 1e602008 fcmp d0, #0.0 40b6f4: 54000044 b.mi 40b6fc <s331+0x12c> 40b6f8: 2a0103f4 mov w20, w1 40b6fc: 91000509 add x9, x8, #0x1 40b700: eb1b013f cmp x9, x27 40b704: 54fffc01 b.ne 40b684 <s331+0xb4> We transform just for hiding mov instruction. I don't think it's proper transformation regarding performance. But I will consider adding some limitation as you said Hal. If you have any sugesstions, please let me know. Comment Actions // Sink expensive instructions into the conditional blocks to avoid executing
// them speculatively.
if (sinkSelectOperand(TTI, SI->getTrueValue())) {
TrueBlock = BasicBlock::Create(SI->getContext(), "select.true.sink",
EndBlock->getParent(), EndBlock);
auto *TrueBranch = BranchInst::Create(EndBlock, TrueBlock);
auto *TrueInst = cast<Instruction>(SI->getTrueValue());
TrueInst->moveBefore(TrueBranch);
}
if (sinkSelectOperand(TTI, SI->getFalseValue())) {
FalseBlock = BasicBlock::Create(SI->getContext(), "select.false.sink",
EndBlock->getParent(), EndBlock);
auto *FalseBranch = BranchInst::Create(EndBlock, FalseBlock);
auto *FalseInst = cast<Instruction>(SI->getFalseValue());
FalseInst->moveBefore(FalseBranch);
}After investigating more, Select optimization only consider just one instruction. So without this patch, we do transform, even if we don't have sinking instruction. Comment Actions ...
This makes perfect sense, thanks! Here's the thing: There are several reasons why the cost of an IR instruction might be "free". One reason is that the instruction represents something we already have (like a PHI or an Argument). One reason is that it represents something that can be implicitly folded (like a truncation). Constants that can be used directly as operands also fall into this category. In this loop, the select has two operands. One is a PHI (free because it represents results already in registers), and the other is a truncation. This truncation is free because it can be folded with its user. The truncation, however, is also of a PHI. And that's the important part. I think that what you want to do here is, for each operand, walk back through "free" CastInsts, and see if you find a PHI, an Argument. These things should already be in registers, and it is not worth branching. Comment Actions Hi Junmo - You're correct that the select optimization only considers one expensive instruction rather than following a chain. This was a hack to get the bug ( https://llvm.org/bugs/show_bug.cgi?id=24818 ) fixed quickly. Expanding that transform to look at more than one instruction was mentioned as a follow-on here: It was my mistake to not include a 'TODO' comment in the code about that. I agree with Hal's point: the sinking of an expensive operand is not the converse of not sinking a cheap operand. If I'm understanding this patch, it is bypassing the transform created by http://reviews.llvm.org/rL156234 and could regress whatever test motivated that patch. After thinking about what that patch is trying to do and considering Mehdi's comments about hampering DAG transforms in D13297, I wonder if the correct solution is to redo r156234 at the machine-level (MachineCombiner pass?). I think that would solve the problem you're seeing. Ie, the problem is that the sinking transform is firing because of the *load* in your test case, but in your benchmarks, the loads are cheap, so we're causing a slowdown by removing selects. Comment Actions Addressed Hal's comment. Thanks, Hal. It is great advice. Sanjay, Thank you for sharing long history of releated commit. I agree with your concern also. But first commit was merged on 2012. It's almost 4 years ago. Recent OoO core has more logic for avoiding cache-miss. (Something likes HW prefetcher..) As you said, this approach can bypass load-cmp heuristic. But it might be very minimum portion. I give more limitation which is Hal's suguesstion on this patch. Can we try to apply this heuristic also? I also get some improvements on commercial benchmark both of X86, AArch64. Comment Actions I don't think the patch implements what Hal suggested. You're checking if the direct operands of a "free" instruction are not Arg/Phi/Const. The suggestion was to recurse/loop until we are sure that no operands in the chain are not free.
Please correct me if I am not understanding: the fact that HW may have gotten *better* at caching is more reason to remove the heuristic-based load "optimization"; it means that a load is more likely to be cheap. In any case, I don't think we should be reasoning about target-specific optimizations at this level (IR) without better target hooks to restrict the transform. And in this particular case, I think it is impossible for the compiler to know whether the load is expensive or not. This is why I suggest pushing that transform down to the DAG or machine-level where it could be limited more easily. Maybe this is something that only OoO x86 would like to do?
I think we're mixing up 2 independent issues now. The load transform and the TCC_Expensive transform have the same goal: don't execute an expensive instruction unnecessarily. But the first is driven by a heuristic (a single use load is expensive) while the second is driven by the fixed and known TTI cost of an instruction such as division.
I would be very interested to know the perf results of completely removing the heuristic-based load transform. I'm not sure what LLVM policy is for this type of situation. I've cc'd @bkramer in case it is possible to know which app/benchmark was improved by r156234. Clearly, it was driven by an improvement for OoO x86-64. Comment Actions ... True, although it occurs to me that we actually can't be more-sophisticated here than the sinking logic. The sinking logic should also sink the whole chain of free instructions (bitcasts, truncs, etc.) to get to the expensive one (should one exist). But it doesn't. Also, now I feel like I'm missing something. isFormingBranchFromSelectProfitable should only return true if at least one of the operands is expensive or a load. Here you're checking that both operands are free. In that state, isFormingBranchFromSelectProfitable should always have returned false (unless, perhaps, one of them was a "free" load). Comment Actions I'd like to echo Sanjay's concern regarding bypassing of the CMP heuristics. Whether we agree that the CMP heuristics are useful or not, they are there, and the proposed changes preempt it based on the assumption that "if the true and false side of the branch are cheap, then the compare doesn't matter." I think this is fundamentally wrong. Even if both sides of the branch are NOPs, if we have high latency (yes, it's debatable whether a load falls into this category) instructions feeding into the comparison, the new conditional move has to sit and wait until the compare is resolved. With branches, the latency is completely hidden by the prediction (assuming it's correct). I'm not sure about ARM, but this is true for X86, at least. I think the two options are : (1) If you feel the compare heuristics are wrong, then move/change them, or (2) Move some of these smarts down into the machine level, as Sanjay suggested. I'd lean more toward (2), personally, since I'd be a little uncomfortable with (1), unless we can come up with some decent heuristics. I'd actually argue that the CMP heuristics need to be beefed up more to have more checks for high latency instructions (and I don't fully agree with the single-use check on the load), and that's always better to do lower down. Comment Actions I think that (2) is the right answer. Consider the case highlighted: The values were phis (or truncs of phis where the truncation is implicit and thus free). Function arguments are the same (at least those passed in registers). The fact is that the value is probably already in a register, so this conversion is not profitable. However, if this happens to be a spilled-value reload, then it might be a good idea, and we won't know that until quite late. For function arguments, at the IR level, we don't yet know if they'll be in registers or loaded from the stack (and even for the register arguments, we don't know if the register value was spilled). And furthermore, since we don't (yet) have global instruction selection, breaking apart blocks like this early is almost always a bad idea (because it hampers instruction selection and scheduling, both are which are block local). Comment Actions Thanks, Sanjay, Hal, Zia. I think I couldn't explain what I really wanted to do. What I wanted to do is do not make branch(apart blocks) when test case is seen. Zia,
I agree with your mention regarding CMP heuristics which want to hide load's execution cycles.
I think recent OoO core's pipeline is deep enought to execute another uops which have no dependency with conditional move. And I think Sanjay's second sugesstion is only about singking expensive instructions. I also think this is good idea, but the main problem is that I don't want to make branches. Hal,
I also agree with your opinion. With this patch, we don't break basic block(making branch) for hiding select's stall when select's two operand's are cheap enough. I saw a little improvement on lua. Sanjay,
-> in AArch64 // Prefer likely predicted branches to selects on out-of-order cores. if (Subtarget->isCortexA57()) PredictableSelectIsExpensive = true; -> X86 // A predictable cmov does not hurt on an in-order CPU. // FIXME: Use a CPU attribute to trigger this, not a CPU model. PredictableSelectIsExpensive = !Subtarget.isAtom(); As you said, most of OoO X86 CPU turn on the flag. When I ran "llc -mcpu=corei7 -mtriple=x86_64-linux < test/CodeGen/AArch64/arm64-select.ll", I can get result likes below. .Ltmp3:
.cfi_offset %rbx, -24
.Ltmp4:
.cfi_offset %r14, -16
movq %rsi, %r14
movq %rdi, %rbx
callq _Z6getvalv
movss (%r14), %xmm1 # xmm1 = mem[0],zero,zero,zero
ucomiss %xmm0, %xmm1
jbe .LBB0_2
# BB#1:
addq $4, %rbx
jmp .LBB0_3
.LBB0_2: # %select.false
addq $8, %rbx
.LBB0_3: # %select.end
movl (%rbx), %eax
addq $8, %rsp
popq %rbx
popq %r14
retq
.Lfunc_end0:
.size test, .Lfunc_end0-test
.cfi_endprocWith this patch, .Ltmp3:
.cfi_offset %rbx, -24
.Ltmp4:
.cfi_offset %r14, -16
movq %rsi, %r14
movq %rdi, %rbx
callq _Z6getvalv
movss (%r14), %xmm1 # xmm1 = mem[0],zero,zero,zero
leaq 4(%rbx), %rax
addq $8, %rbx
ucomiss %xmm0, %xmm1
cmovaq %rax, %rbx
movl (%rbx), %eax
addq $8, %rsp
popq %rbx
popq %r14
retq
.Lfunc_end0:
.size test, .Lfunc_end0-test
.cfi_endprocI am not sure that making branch is better than using cmov.
Thanks for sugesstion this, I will run several benchmarks and share the data soon. Anyway, If we can't modify CMP heuristic, How can we modify EarlyIfConversion's likes below? bool EarlyIfConverter::shouldConvertIf() {
....
// Look at all the tail phis, and compute the critical path extension caused
// by inserting select instructions.
MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail);
for (unsigned i = 0, e = IfConv.PHIs.size(); i != e; ++i) {
SSAIfConv::PHIInfo &PI = IfConv.PHIs[i];
unsigned Slack = TailTrace.getInstrSlack(PI.PHI);
unsigned MaxDepth = Slack + TailTrace.getInstrCycles(PI.PHI).Depth;
DEBUG(dbgs() << "Slack " << Slack << ":\t" << *PI.PHI);
// The condition is pulled into the critical path.
unsigned CondDepth = adjCycles(BranchDepth, PI.CondCycles);
if (CondDepth > MaxDepth) {
unsigned Extra = CondDepth - MaxDepth;
DEBUG(dbgs() << "Condition adds " << Extra << " cycles.\n");
if (Extra > CritLimit) {
DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
return false;
}
}
// The TBB value is pulled into the critical path.
unsigned TDepth = adjCycles(TBBTrace.getPHIDepth(PI.PHI), PI.TCycles);
if (TDepth > MaxDepth) {
unsigned Extra = TDepth - MaxDepth;
DEBUG(dbgs() << "TBB data adds " << Extra << " cycles.\n");
if (Extra > CritLimit) {
DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
return false;
}
}
// The FBB value is pulled into the critical path.
unsigned FDepth = adjCycles(FBBTrace.getPHIDepth(PI.PHI), PI.FCycles);
if (FDepth > MaxDepth) {
unsigned Extra = FDepth - MaxDepth;
DEBUG(dbgs() << "FBB data adds " << Extra << " cycles.\n");
if (Extra > CritLimit) {
DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n');
return false;
}
}
}
return true;
}This is opposite pass of "select to branch". -Junmo. Comment Actions Back then this had significant effects on the LLVM test suite on 2012-class x86_64 hardware. The heuristic is extremely dumb though because LLVM was/is lacking infrastructure to do it properly.
If I were to implement it properly I would start by adding branch weights to selects, we currently lose a lot of profile data in SimplifyCFG. Then we can drive the transform by transforming biased selects into branches first, maybe with a TTI-based version of the current heuristic as a fall back if no info is there. If you don't see any regressions from disabling the load-based heuristic feel free to throw it out. Both the hardware and LLVM have changed since 2012 so maybe the problems I was papering over with the load-based heuristic aren't there anymore. Comment Actions Thank you for the background! I'll do some perf testing on AMD Jaguar (2013-class small core) with the current test-suite and report back. I filed the branch weight metadata propagation enhancement here: Comment Actions I'm looking into resurrecting the nonlocal dead store elimination in http://reviews.llvm.org/D13363, One technique for recouping most of these drops is to relax the load-feeding-cmp heuristic in Is it worth pursuing more tuning in isFormingBranchFromSelectProfitable, regards,
Comment Actions In this case there could be another issue coming into play. Some of the discussions centering around the IR heuristics assume but don’t check that the target is OoO. What if the core is in-order? Or is this a non-issue anymore for x86 even in the embedded space? Overall I think Sanjay’s thought about pushing the optimization/tuning down to the MachineCombiner goes in the right direction. As a local peephole this kind of tuning always seems to end up giving mixed performance results over time. I have seen this before on Itanium and more recently on ARM64 where for some time a local patch for tuning the sFormingBranchFromSelectProfitable heuristics gave some gains on “commercial benchmarks” for a few months before they vanished again because of changes to the instruction mix. -Gerolf Comment Actions Hi Gerolf. Below is what I answered about Sanjay's opinion in D17288. I think this could be answer about your opinion also. We already consider that we apply "select to branch opt" for which one. // Do we have efficient codegen support for this kind of 'selects' ?
if (TLI->isSelectSupported(SelectKind)) {
// We have efficient codegen support for the select instruction.
// Check if it is profitable to keep this 'select'.
if (!TLI->isPredictableSelectExpensive() ||
!isFormingBranchFromSelectProfitable(TTI, SI))
return false;
}We already check through TLI->isPredictableSelectExpensive(). This can be set in X86ISelLowering.cpp. // A predictable cmov does not hurt on an in-order CPU. // FIXME: Use a CPU attribute to trigger this, not a CPU model. PredictableSelectIsExpensive = !Subtarget.isAtom(); If PredictableSelectIsExpensive is not true, we don't transform "select to branch" opt. And I think we can use getSchedModel().isOutOfOrder() for setting the flag PredictableSelectIsExpensive. Junmo. Comment Actions Remove Load-CMP heuristic result. I didn't find notable regression. Comment Actions Thanks, Junmo. I didn't realize that was possible, but that solves a problem. We shouldn't be using bogus predicates which approximate the necessary condition...the correct predicate is already available! Index: lib/Target/ARM/ARMISelLowering.cpp =================================================================== --- lib/Target/ARM/ARMISelLowering.cpp (revision 261182) +++ lib/Target/ARM/ARMISelLowering.cpp (working copy) @@ -1042,7 +1042,7 @@ setMinStackArgumentAlignment(4); // Prefer likely predicted branches to selects on out-of-order cores. - PredictableSelectIsExpensive = Subtarget->isLikeA9(); + PredictableSelectIsExpensive = Subtarget->getSchedModel().isOutOfOrder(); setMinFunctionAlignment(Subtarget->isThumb() ? 1 : 2); } And I see now that PredictableSelectIsExpensive defaults to 'false', so that means targets must opt-in to this transform. That makes me feel better about doing this transform in general, but it doesn't solve the problem raised by this patch. The transform is based on a heuristic, and this patch may limit when that heuristic fires, but Zia and Mitch have suggested the opposite: they'd like to do this transform more often for their targets. If we're going to solve that tension here in CGP, we're going to need another target hook or make PredictableSelectIsExpensive more than a bool value. To solve this at the machine-level, you'd either need to customize the transform per target or add that same target hook to be used from a common codegen pass. I'm not sure which is the better option. As Mitch pointed out, there's certainly demand to do the transform(s) here because it's easier. And now that I realize we have access to the same SchedModel info that we would use at the machine-level anyway, it seems more reasonable. However, as Hal and Mehdi have noted, breaking up a basic block may harm isel/scheduling. Comment Actions Here's test-suite raw data after removing the branch-on-load heuristic completely while running on AMD Jaguar 1.5 GHz. I ran each config 3 times. I'm filtering out anything with more than 1% relative std dev in a google spreadsheet while reviewing the numbers. Like Junmo's SandyBridge experiment summary (it looks like the actual data is encrypted?), I don't see any real regressions. There was a similar (+14%) win for MultiSource/Benchmarks/TSVC/Searching-flt/Searching-flt as Junmo reported testing with Cortex-A57, however, there was only a slight (+1.5%) win for MultiSource/Benchmarks/TSVC/Searching-dbl/Searching-dbl. The average perf of the filtered tests is +0.2% after removing the branch-on-load transform. Comment Actions Thanks Sanjay.
I totally agree with this. I will change this patch soon. Thanks for pointing ARMISelLowering.cpp. Comment Actions Junmo - your patch will cause these existing regression tests to fail: LLVM :: CodeGen/AArch64/a57-csel.ll LLVM :: CodeGen/X86/cmov-into-branch.ll LLVM :: Transforms/CodeGenPrepare/X86/select.ll Please update the check-lines in those tests and add those diffs to this patch. The existing tests cover the functionality that you are proposing to change, so I don't think there is a need to add a new test file. We've covered a lot of ground in this review, so let me try to summarize:
Did I miss anything? :) Comment Actions Hi. Mitch. I'm looking into resurrecting the nonlocal dead store elimination in http://reviews.llvm.org/D13363, but one of the snags is a performance issue related to select-vs-branch choices. That change enables more selects, which unfortunately incur a 10 to 20% perf drop on some benchmarks in the EEMBC automotive suite, on various X86 architectures. This patch will make select to branch lesser. But I uploaded other patch(D17288) for applying select to branch optimization when obvious case. If you see some regressions regarding this patch(D16836), could you let us know, please? Junmo. Comment Actions
Just back from a break, so I apologize for getting to the party late. Looks like we see some minor perf drops on our side from this, but I think I'm willing to deal with that through plans of beefing up our heuristics after isel. At a high level, the changes do look like they have potential to introduce cases that may cause regressions, but I don't think that the existing heuristic made much sense to begin with.... So, lgmt.. Comment Actions Thanks for all. Especially, Sanjay, I really appreciate your review & comments with great summary. Commited in r261809. Junmo. | ||||||||||||||||||||||||
I don't understand what's going on here. So what if they fold away? They could be bitcasts, or free extensions/truncations, etc. Wouldn't you need to recurse up the use/def chain to find the non-free operand and making some determination based on that?