From b436b77ccf9848264368cce81f66ef1a1dc80b5d Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Fri, 16 Oct 2015 23:00:29 +0000 Subject: [PATCH] Revert "This is a follow-up to the discussion in D12882." Breaks clang selfhost, see PR25222. This reverts commits r250527 and r250528. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@250570 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/CodeGenPrepare.cpp | 116 +++---------------- test/Transforms/CodeGenPrepare/X86/select.ll | 114 ------------------ 2 files changed, 16 insertions(+), 214 deletions(-) delete mode 100644 test/Transforms/CodeGenPrepare/X86/select.ll diff --git a/lib/CodeGen/CodeGenPrepare.cpp b/lib/CodeGen/CodeGenPrepare.cpp index 2eeaabed2eb..27bf83a3c7b 100644 --- a/lib/CodeGen/CodeGenPrepare.cpp +++ b/lib/CodeGen/CodeGenPrepare.cpp @@ -3846,20 +3846,8 @@ bool CodeGenPrepare::optimizeExtUses(Instruction *I) { 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(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(const TargetTransformInfo *TTI, - SelectInst *SI) { +static bool isFormingBranchFromSelectProfitable(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 @@ -3880,17 +3868,8 @@ static bool isFormingBranchFromSelectProfitable(const TargetTransformInfo *TTI, // 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. - if ((isa(CmpOp0) && CmpOp0->hasOneUse()) || - (isa(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; + return ((isa(CmpOp0) && CmpOp0->hasOneUse()) || + (isa(CmpOp1) && CmpOp1->hasOneUse())); } @@ -3916,97 +3895,34 @@ bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI) { // We have efficient codegen support for the select instruction. // Check if it is profitable to keep this 'select'. if (!TLI->isPredictableSelectExpensive() || - !isFormingBranchFromSelectProfitable(TTI, SI)) + !isFormingBranchFromSelectProfitable(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 - // first 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 *EndBlock = StartBlock->splitBasicBlock(SplitPt, "select.end"); - - // Delete the unconditional branch that was just created by the split. - StartBlock->getTerminator()->eraseFromParent(); - - // 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(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(SI->getFalseValue()); - FalseInst->moveBefore(FalseBranch); - } + BasicBlock *NextBlock = StartBlock->splitBasicBlock(SplitPt, "select.end"); - // 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"); + // Create a new block serving as the landing pad for the branch. + BasicBlock *SmallBlock = BasicBlock::Create(SI->getContext(), "select.mid", + NextBlock->getParent(), NextBlock); - FalseBlock = BasicBlock::Create(SI->getContext(), "select.false", - EndBlock->getParent(), EndBlock); - BranchInst::Create(EndBlock, FalseBlock); - } + // Move the unconditional branch from the block with the select in it into our + // landing pad block. + StartBlock->getTerminator()->eraseFromParent(); + BranchInst::Create(NextBlock, SmallBlock); // Insert the real conditional branch based on the original condition. - // 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); - } + BranchInst::Create(NextBlock, SmallBlock, SI->getCondition(), SI); // The select itself is replaced with a PHI Node. - PHINode *PN = PHINode::Create(SI->getType(), 2, "", &EndBlock->front()); + PHINode *PN = PHINode::Create(SI->getType(), 2, "", &NextBlock->front()); PN->takeName(SI); - PN->addIncoming(SI->getTrueValue(), TrueBlock); - PN->addIncoming(SI->getFalseValue(), FalseBlock); - + PN->addIncoming(SI->getTrueValue(), StartBlock); + PN->addIncoming(SI->getFalseValue(), SmallBlock); SI->replaceAllUsesWith(PN); SI->eraseFromParent(); diff --git a/test/Transforms/CodeGenPrepare/X86/select.ll b/test/Transforms/CodeGenPrepare/X86/select.ll deleted file mode 100644 index 5b1a0bafe06..00000000000 --- a/test/Transforms/CodeGenPrepare/X86/select.ll +++ /dev/null @@ -1,114 +0,0 @@ -; RUN: opt -codegenprepare -S < %s | FileCheck %s - -target triple = "x86_64-unknown-unknown" - -; Nothing to sink here, but this gets converted to a branch to -; avoid stalling an out-of-order CPU on a predictable branch. - -define i32 @no_sink(double %a, double* %b, i32 %x, i32 %y) { -entry: - %load = load double, double* %b, align 8 - %cmp = fcmp olt double %load, %a - %sel = select i1 %cmp, i32 %x, i32 %y - ret i32 %sel - -; CHECK-LABEL: @no_sink( -; CHECK: %load = load double, double* %b, align 8 -; CHECK: %cmp = fcmp olt double %load, %a -; CHECK: br i1 %cmp, label %select.end, label %select.false -; CHECK: select.false: -; CHECK: br label %select.end -; CHECK: select.end: -; CHECK: %sel = phi i32 [ %x, %entry ], [ %y, %select.false ] -; CHECK: ret i32 %sel -} - - -; An 'fdiv' is expensive, so sink it rather than speculatively execute it. - -define float @fdiv_true_sink(float %a, float %b) { -entry: - %div = fdiv float %a, %b - %cmp = fcmp ogt float %a, 1.0 - %sel = select i1 %cmp, float %div, float 2.0 - ret float %sel - -; CHECK-LABEL: @fdiv_true_sink( -; CHECK: %cmp = fcmp ogt float %a, 1.0 -; CHECK: br i1 %cmp, label %select.true.sink, label %select.end -; CHECK: select.true.sink: -; CHECK: %div = fdiv float %a, %b -; CHECK: br label %select.end -; CHECK: select.end: -; CHECK: %sel = phi float [ %div, %select.true.sink ], [ 2.000000e+00, %entry ] -; CHECK: ret float %sel -} - -define float @fdiv_false_sink(float %a, float %b) { -entry: - %div = fdiv float %a, %b - %cmp = fcmp ogt float %a, 3.0 - %sel = select i1 %cmp, float 4.0, float %div - ret float %sel - -; CHECK-LABEL: @fdiv_false_sink( -; CHECK: %cmp = fcmp ogt float %a, 3.0 -; CHECK: br i1 %cmp, label %select.end, label %select.false.sink -; CHECK: select.false.sink: -; CHECK: %div = fdiv float %a, %b -; CHECK: br label %select.end -; CHECK: select.end: -; CHECK: %sel = phi float [ 4.000000e+00, %entry ], [ %div, %select.false.sink ] -; CHECK: ret float %sel -} - -define float @fdiv_both_sink(float %a, float %b) { -entry: - %div1 = fdiv float %a, %b - %div2 = fdiv float %b, %a - %cmp = fcmp ogt float %a, 5.0 - %sel = select i1 %cmp, float %div1, float %div2 - ret float %sel - -; CHECK-LABEL: @fdiv_both_sink( -; CHECK: %cmp = fcmp ogt float %a, 5.0 -; CHECK: br i1 %cmp, label %select.true.sink, label %select.false.sink -; CHECK: select.true.sink: -; CHECK: %div1 = fdiv float %a, %b -; CHECK: br label %select.end -; CHECK: select.false.sink: -; CHECK: %div2 = fdiv float %b, %a -; CHECK: br label %select.end -; CHECK: select.end: -; CHECK: %sel = phi float [ %div1, %select.true.sink ], [ %div2, %select.false.sink ] -; CHECK: ret float %sel -} - -; An 'fadd' is not too expensive, so it's ok to speculate. - -define float @fadd_no_sink(float %a, float %b) { - %add = fadd float %a, %b - %cmp = fcmp ogt float 6.0, %a - %sel = select i1 %cmp, float %add, float 7.0 - ret float %sel - -; CHECK-LABEL: @fadd_no_sink( -; CHECK: %sel = select i1 %cmp, float %add, float 7.0 -} - -; Possible enhancement: sinkability is only calculated with the direct -; operand of the select, so we don't try to sink this. The fdiv cost is not -; taken into account. - -define float @fdiv_no_sink(float %a, float %b) { -entry: - %div = fdiv float %a, %b - %add = fadd float %div, %b - %cmp = fcmp ogt float %a, 1.0 - %sel = select i1 %cmp, float %add, float 8.0 - ret float %sel - -; CHECK-LABEL: @fdiv_no_sink( -; CHECK: %sel = select i1 %cmp, float %add, float 8.0 -} - -- 2.34.1