[CGP] transform select instructions into branches and sink expensive operands

[spatel]

Summary

This is a follow-up to the discussion in D12882.

Ideally, we would like SimplifyCFG to be able to form select instructions even when the operands are expensive (as defined by the TTI cost model) because that may expose further optimizations. However, we would then like a later pass like CodeGenPrepare to undo that transformation if the target would likely benefit from not speculatively executing an expensive op (this patch).

Once we have this safety mechanism in place, we can adjust SimplifyCFG to restore its select-formation behavior that changed with r248439.

[mehdi_amini]

knowing that SelectionDAG operates per basic-block, this makes me worried about implications on the ability of SelectionDAG to combine. I feel this is something that would better be done at the MI level.

[mehdi_amini]

Did you check what is the performance impact on the test suite? (if any)

[spatel]

In D13297#256946, @joker.eph wrote:

Did you check what is the performance impact on the test suite? (if any)

Not yet - I'm collecting data now.

Note: my test-suite system has an AMD Jaguar CPU; it would be great if someone else could try this patch on a recent Intel-based system.

[spatel]

In D13297#256971, @spatel wrote:

In D13297#256946, @joker.eph wrote:

Did you check what is the performance impact on the test suite? (if any)

Not yet - I'm collecting data now.

Note: my test-suite system has an AMD Jaguar CPU; it would be great if someone else could try this patch on a recent Intel-based system.

Or better still for the sake of variety: a non-x86 system.

[spatel]

In D13297#256940, @joker.eph wrote:

knowing that SelectionDAG operates per basic-block, this makes me worried about implications on the ability of SelectionDAG to combine. I feel this is something that would better be done at the MI level.

I've learned that the longstanding existence of something in LLVM does not make it right. :)
However, I want to note for the record that we have similar 'undo' transforms already in IR and/or DAG. These are the cases that I'm aware of:

1. SimplifyCFG creates selects from branches using TTI (this behavior was toggled for some cases at r228826 and r248439).
2. SimplifyCFG combines branches with logic ops in FoldBranchToCommonDest() using a target-independent heuristic.
3. SelectionDAGBuilder may undo #2 in visitBr() using TLI.
4. CGP may undo #2 in splitBranchCondition() using TLI (and has a FIXME stating #3 should be removed).
5. CGP may undo #1 in optimizeSelectInst() using TLI (that's the code this patch is building on).

I wonder if any of these raise the same concern? Again, I don't know what the right answer is...just asking a question. Also, note that this patch was proposed in D12882, and I thought there was some consensus for it. I may have misunderstood.

[mehdi_amini]

In D13297#257035, @spatel wrote:

In D13297#256940, @joker.eph wrote:

knowing that SelectionDAG operates per basic-block, this makes me worried about implications on the ability of SelectionDAG to combine. I feel this is something that would better be done at the MI level.

I've learned that the longstanding existence of something in LLVM does not make it right. :)

Definitively. This is not something "right" this is a limitation of SelectionDAG and I know people are actively working on getting rid of it.

However, I want to note for the record that we have similar 'undo' transforms already in IR and/or DAG. These are the cases that I'm aware of:

1. SimplifyCFG creates selects from branches using TTI (this behavior was toggled for some cases at r228826 and r248439).
2. SimplifyCFG combines branches with logic ops in FoldBranchToCommonDest() using a target-independent heuristic.
3. SelectionDAGBuilder may undo #2 in visitBr() using TLI.
4. CGP may undo #2 in splitBranchCondition() using TLI (and has a FIXME stating #3 should be removed).
5. CGP may undo #1 in optimizeSelectInst() using TLI (that's the code this patch is building on).

I wonder if any of these raise the same concern? Again, I don't know what the right answer is...just asking a question. Also, note that this patch was proposed in D12882, and I thought there was some consensus for it. I may have misunderstood.

Indeed the "correct" approach may be to not "optimize" for the way SelectionDAG work and its limitation, and instead relying on MI-level combine pass to figure out later combine across basic blocks.

[reames]

Overall, I think this is the right direction. I might consider enhancing it slightly by sinking operands of the select's operands as long as there's only a single use, but that's gravy. It would be entirely reasonable to do that in a separate change.

Trying to do this at the MI layer would be more complicated, less in alignment with how similar issues are already handled, and doesn't seem to give any real advantage.

I would like to see some performance numbers before submission.

lib/CodeGen/CodeGenPrepare.cpp

3845

This would seem better structured as a boolean predicate on the Value.

3881

clarify comment: expensive and only needed on one side of the select

3929

I'd suggest revising this example. In principal, we might create if/else/end blocks and sink into both if and else blocks. I'd suggest formulating it that way and then mentioning that we optimize away one of the blocks if we can.

3960

auto would be fine here.

3971

!landing pad. That has a very specific meaning in LLVM which this is not. "input value", or "incoming edge" would be fine.

3972

I'd add an assert inside this that TrueBlock == EndBlock just to make it obvious.

3986

I think that if you start the true and false blocks as being StartBlock you can simplify away this code entirely?

[mehdi_amini]

While I agree that it is something that seems to be done at the IR level "conceptually", I think you are underestimating the importance of the MI level: there are many things the DAG can fold if it has a view on it, and something that seems costly at the IR level can become "free" in some cases with target knowledge.
As mentioned previously, doing this at the IR level stresses a bit more a limitation of SelectionDAG, which does not mean it is not the right thing to do, but on the other side we should just make sure the MI level combine is able to cope with it (it becomes a target problem to deal with it). A global instruction selection instead of SelectionDAG wouldn't have such issue.
Now maybe x86 and/or ARM either does not have much DAG combine that would be lost in this process, or have a strong enough MI layer to recover, so my concern may not have any practical implication. In the end, let's just run a few benchmarks and see :)
I'll try to run the test-suite on Haswell and ARM64, hopefully this week.

[spatel]

cgp_sink - perf.csv10 KBDownload

These are test-suite benchmarking subset exec_time results for 3 baseline runs (r248957) followed by 3 runs with this patch applied running on an otherwise quiet AMD Jaguar 1.5GHz Ubuntu 14.04 system.

I don't see anything outside of the noise.

This is what I expected given that SimplifyCFG is not currently forming the TCC_Expensive selects that would be undone by this patch. I'll try again with r248439 reverted.

[spatel]

simplifycfg_expensive - perf.csv10 KBDownload

This data comes from the same system and has the same baseline as before (r248957) but reverts r248439, so if there are expensive ops (div/rem) that can be speculatively executed and folded into selects, this data should show the perf effect.

But again, I don't see any differences.

[spatel]

lib/CodeGen/CodeGenPrepare.cpp

3986

We can't do that because we want to use these as the labels for the branch, so they have to start off pointing to the EndBlock. This is more confusing that it needs to be. I'll just init these to nullptr instead, and then we'll change them as needed and create the branch at the same time. It's a couple of extra lines of code, but easier to follow IMO.

[spatel]

Patch updated based on Philip's feedback (thanks!).

[spatel]

[Patch rebased; also, the new test case file was missing in the last revision.]

Ping.

Mehdi, did you run any perf tests?

[mehdi_amini]

Sorry I haven't had time to setup an ARM device yet, too many other things came up :(
That said, don't consider it a blocker for committing, this LGTM (if Philip is OK with the patch).

[reames]

LGTM

lib/CodeGen/CodeGenPrepare.cpp

for (Use &U : Src->uses()) {
     U = InsertedTrunc;
     ++NumExtUses;
     MadeChange = true;
   }
 
   return MadeChange;
 }
 
+/// Check if V (an operand of a select instruction) is an expensive instruction
+/// that is only used once.
+static bool sinkSelectOperand(const TargetTransformInfo *TTI, Value *V) {
+  auto *I = dyn_cast<Instruction>(V);
+  if (I && I->hasOneUse() &&
+      TTI->getUserCost(I) == TargetTransformInfo::TCC_Expensive)
+    return true;
+
+  return false;
+}
+
 /// Returns true if a SelectInst should be turned into an explicit branch.
-static bool isFormingBranchFromSelectProfitable(SelectInst *SI) {
+static bool isFormingBranchFromSelectProfitable(const TargetTransformInfo *TTI,
+                                                SelectInst *SI) {
   // FIXME: This should use the same heuristics as IfConversion to determine
   // whether a select is better represented as a branch.  This requires that
   // branch probability metadata is preserved for the select, which is not the
   // case currently.
 
   CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
 
   // If a branch is predictable, an out-of-order CPU can avoid blocking on its
   // comparison condition. If the compare has more than one use, there's
   // probably another cmov or setcc around, so it's not worth emitting a branch.
   if (!Cmp || !Cmp->hasOneUse())
     return false;
 
   Value *CmpOp0 = Cmp->getOperand(0);
   Value *CmpOp1 = Cmp->getOperand(1);
 
   // Emit "cmov on compare with a memory operand" as a branch to avoid stalls
   // on a load from memory. But if the load is used more than once, do not
   // change the select to a branch because the load is probably needed
   // regardless of whether the branch is taken or not.
-  return ((isa<LoadInst>(CmpOp0) && CmpOp0->hasOneUse()) ||
-          (isa<LoadInst>(CmpOp1) && CmpOp1->hasOneUse()));
+  if ((isa<LoadInst>(CmpOp0) && CmpOp0->hasOneUse()) ||
+      (isa<LoadInst>(CmpOp1) && CmpOp1->hasOneUse()))
+    return true;
+
+  // If either operand of the select is expensive and only needed on one side
+  // of the select, we should form a branch.
+  if (sinkSelectOperand(TTI, SI->getTrueValue()) ||
+      sinkSelectOperand(TTI, SI->getFalseValue()))
+    return true;
+
+  return false;
 }
 
 
 /// If we have a SelectInst that will likely profit from branch prediction,
 /// turn it into a branch.
 bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI) {
   bool VectorCond = !SI->getCondition()->getType()->isIntegerTy(1);
 
bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI) {
   else
     SelectKind = TargetLowering::ScalarValSelect;
 
   // 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(SI))
+        !isFormingBranchFromSelectProfitable(TTI, SI))
       return false;
   }
 
   ModifiedDT = true;
 
+  // Transform a sequence like this:
+  //    start:
+  //       %cmp = cmp uge i32 %a, %b
+  //       %sel = select i1 %cmp, i32 %c, i32 %d
+  //
+  // Into:
+  //    start:
+  //       %cmp = cmp uge i32 %a, %b
+  //       br i1 %cmp, label %select.true, label %select.false
+  //    select.true:
+  //       br label %select.end
+  //    select.false:
+  //       br label %select.end
+  //    select.end:
+  //       %sel = phi i32 [ %c, %select.true ], [ %d, %select.false ]
+  //
+  // In addition, we may sink instructions that produce %c or %d from
+  // the entry block into the destination(s) of the new branch.
+  // If the true or false blocks do not contain a sunken instruction, that
+  // block and its branch may be optimized away. In that case, one side of the
+  // branch will point directly to select.end, and the corresponding PHI
+  // predecessor block will be the start block.
+
   // First, we split the block containing the select into 2 blocks.
   BasicBlock *StartBlock = SI->getParent();
   BasicBlock::iterator SplitPt = ++(BasicBlock::iterator(SI));
-  BasicBlock *NextBlock = StartBlock->splitBasicBlock(SplitPt, "select.end");
-
-  // Create a new block serving as the landing pad for the branch.
-  BasicBlock *SmallBlock = BasicBlock::Create(SI->getContext(), "select.mid",
-                                             NextBlock->getParent(), NextBlock);
+  BasicBlock *EndBlock = StartBlock->splitBasicBlock(SplitPt, "select.end");
 
-  // Move the unconditional branch from the block with the select in it into our
-  // landing pad block.
+  // Delete the unconditional branch that was just created by the split.
   StartBlock->getTerminator()->eraseFromParent();
-  BranchInst::Create(NextBlock, SmallBlock);
+
+  // These are the new basic blocks for the conditional branch.
+  // At least one will become an actual new basic block.
+  BasicBlock *TrueBlock = nullptr;
+  BasicBlock *FalseBlock = nullptr;
+
+  // 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);
+  }
+
+  // If there was nothing to sink, then arbitrarily choose the 'false' side
+  // for a new input value to the PHI.
+  if (TrueBlock == FalseBlock) {
+    assert(TrueBlock == nullptr &&
+           "Unexpected basic block transform while optimizing select");
+
+    FalseBlock = BasicBlock::Create(SI->getContext(), "select.false",
+                                    EndBlock->getParent(), EndBlock);
+    BranchInst::Create(EndBlock, FalseBlock);
+  }
 
   // Insert the real conditional branch based on the original condition.
-  BranchInst::Create(NextBlock, SmallBlock, SI->getCondition(), SI);
+  // If we did not create a new block for one of the 'true' or 'false' paths
+  // of the condition, it means that side of the branch goes to the end block
+  // directly and the path originates from the start block from the point of
+  // view of the new PHI.
+  if (TrueBlock == nullptr) {
+    BranchInst::Create(EndBlock, FalseBlock, SI->getCondition(), SI);
+    TrueBlock = StartBlock;
+  } else if (FalseBlock == nullptr) {
+    BranchInst::Create(TrueBlock, EndBlock, SI->getCondition(), SI);
+    FalseBlock = StartBlock;
+  } else {
+    BranchInst::Create(TrueBlock, FalseBlock, SI->getCondition(), SI);
+  }
 
   // The select itself is replaced with a PHI Node.
-  PHINode *PN = PHINode::Create(SI->getType(), 2, "", NextBlock->begin());
+  PHINode *PN = PHINode::Create(SI->getType(), 2, "", EndBlock->begin());
   PN->takeName(SI);
-  PN->addIncoming(SI->getTrueValue(), StartBlock);
-  PN->addIncoming(SI->getFalseValue(), SmallBlock);
+  PN->addIncoming(SI->getTrueValue(), TrueBlock);
+  PN->addIncoming(SI->getFalseValue(), FalseBlock);
   SI->replaceAllUsesWith(PN);
   SI->eraseFromParent();
 
   // Instruct OptimizeBlock to skip to the next block.
   CurInstIterator = StartBlock->end();
   ++NumSelectsExpanded;
   return true;
 }