From b38d3411064bb59641714fde981564cf51217308 Mon Sep 17 00:00:00 2001 From: Nico Weber Date: Mon, 24 Oct 2016 14:52:04 +0000 Subject: [PATCH] Revert 284971. It seems to break selfhost on some bots, see e.g. http://lab.llvm.org:8011/builders/clang-x86-windows-msvc2015/builds/21 http://lab.llvm.org:8011/builders/clang-ppc64be-linux-multistage/builds/20 http://lab.llvm.org:8011/builders/clang-ppc64be-linux-lnt/builds/22 llvm-svn: 284979 --- .../include/llvm/Transforms/Scalar/JumpThreading.h | 2 - llvm/lib/Transforms/Scalar/JumpThreading.cpp | 111 +++++++-------------- .../JumpThreading/unfold-selects-same-cond.ll | 23 ----- 3 files changed, 38 insertions(+), 98 deletions(-) delete mode 100644 llvm/test/Transforms/JumpThreading/unfold-selects-same-cond.ll diff --git a/llvm/include/llvm/Transforms/Scalar/JumpThreading.h b/llvm/include/llvm/Transforms/Scalar/JumpThreading.h index 306f0b6..f96741c 100644 --- a/llvm/include/llvm/Transforms/Scalar/JumpThreading.h +++ b/llvm/include/llvm/Transforms/Scalar/JumpThreading.h @@ -129,8 +129,6 @@ private: BasicBlock *NewBB, BasicBlock *SuccBB); /// Check if the block has profile metadata for its outgoing edges. bool doesBlockHaveProfileData(BasicBlock *BB); - SelectInst *getSelectFedByPhi(PHINode *PN); - void expandSelect(SelectInst *SI); }; } // end namespace llvm diff --git a/llvm/lib/Transforms/Scalar/JumpThreading.cpp b/llvm/lib/Transforms/Scalar/JumpThreading.cpp index 07b3c3c..ddad300 100644 --- a/llvm/lib/Transforms/Scalar/JumpThreading.cpp +++ b/llvm/lib/Transforms/Scalar/JumpThreading.cpp @@ -1963,96 +1963,61 @@ bool JumpThreadingPass::TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB) { return false; } -/// GetSelectFedByPhi - Look for PHI/Select in the same BB of the form +/// TryToUnfoldSelectInCurrBB - Look for PHI/Select in the same BB of the form /// bb: /// %p = phi [false, %bb1], [true, %bb2], [false, %bb3], [true, %bb4], ... /// %s = select p, trueval, falseval /// -/// And return the select. Unfolding it into a branch structure later enables +/// And expand the select into a branch structure. This later enables /// jump-threading over bb in this pass. /// -/// Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), return -/// select if the associated PHI has at least one constant. -SelectInst *JumpThreadingPass::getSelectFedByPhi(PHINode *PN) { - - unsigned NumPHIValues = PN->getNumIncomingValues(); - if (NumPHIValues == 0 || !PN->hasOneUse()) - return nullptr; - - SelectInst *SI = dyn_cast(PN->user_back()); - BasicBlock *BB = PN->getParent(); - if (!SI || SI->getParent() != BB) - return nullptr; - - Value *Cond = SI->getCondition(); - if (!Cond || Cond != PN || !Cond->getType()->isIntegerTy(1)) - return nullptr; - - for (unsigned i = 0; i != NumPHIValues; ++i) { - if (PN->getIncomingBlock(i) == BB) - return nullptr; - if (isa(PN->getIncomingValue(i))) - return SI; - } - - return nullptr; -} - -/// ExpandSelect - Expand a select into an if-then-else construct. -void JumpThreadingPass::expandSelect(SelectInst *SI) { - - BasicBlock *BB = SI->getParent(); - TerminatorInst *Term = - SplitBlockAndInsertIfThen(SI->getCondition(), SI, false); - PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI); - NewPN->addIncoming(SI->getTrueValue(), Term->getParent()); - NewPN->addIncoming(SI->getFalseValue(), BB); - SI->replaceAllUsesWith(NewPN); - SI->eraseFromParent(); -} - -/// TryToUnfoldSelectInCurrBB - Unfold selects that could be jump-threaded were -/// they if-then-elses. If the unfolded selects are not jump-threaded, it will -/// be folded again in the later optimizations. +/// Using the similar approach of SimplifyCFG::FoldCondBranchOnPHI(), unfold +/// select if the associated PHI has at least one constant. If the unfolded +/// select is not jump-threaded, it will be folded again in the later +/// optimizations. bool JumpThreadingPass::TryToUnfoldSelectInCurrBB(BasicBlock *BB) { - // If threading this would thread across a loop header, don't thread the edge. // See the comments above FindLoopHeaders for justifications and caveats. if (LoopHeaders.count(BB)) return false; - bool Changed = false; - for (auto &I : *BB) { - - // Look for a Phi/Select pair in the same basic block. The Phi feeds the - // condition of the Select and at least one of the incoming values is a - // constant. - PHINode *PN; - SelectInst *SI; - if ((PN = dyn_cast(&I)) && (SI = getSelectFedByPhi(PN))) { - expandSelect(SI); - Changed = true; + // Look for a Phi/Select pair in the same basic block. The Phi feeds the + // condition of the Select and at least one of the incoming values is a + // constant. + for (BasicBlock::iterator BI = BB->begin(); + PHINode *PN = dyn_cast(BI); ++BI) { + unsigned NumPHIValues = PN->getNumIncomingValues(); + if (NumPHIValues == 0 || !PN->hasOneUse()) continue; - } - if (I.getType()->isIntegerTy(1)) { + SelectInst *SI = dyn_cast(PN->user_back()); + if (!SI || SI->getParent() != BB) + continue; - SmallVector Selects; + Value *Cond = SI->getCondition(); + if (!Cond || Cond != PN || !Cond->getType()->isIntegerTy(1)) + continue; - // Look for scalar booleans used in selects as conditions. If there are - // several selects that use the same boolean, they are candidates for jump - // threading and therefore we should unfold them. - for (Value *U : I.users()) - if (auto *SI = dyn_cast(U)) - Selects.push_back(SI); - if (Selects.size() <= 1) - continue; + bool HasConst = false; + for (unsigned i = 0; i != NumPHIValues; ++i) { + if (PN->getIncomingBlock(i) == BB) + return false; + if (isa(PN->getIncomingValue(i))) + HasConst = true; + } - Changed = true; - for (auto *SI : Selects) - expandSelect(SI); + if (HasConst) { + // Expand the select. + TerminatorInst *Term = + SplitBlockAndInsertIfThen(SI->getCondition(), SI, false); + PHINode *NewPN = PHINode::Create(SI->getType(), 2, "", SI); + NewPN->addIncoming(SI->getTrueValue(), Term->getParent()); + NewPN->addIncoming(SI->getFalseValue(), BB); + SI->replaceAllUsesWith(NewPN); + SI->eraseFromParent(); + return true; } } - - return Changed; + + return false; } diff --git a/llvm/test/Transforms/JumpThreading/unfold-selects-same-cond.ll b/llvm/test/Transforms/JumpThreading/unfold-selects-same-cond.ll deleted file mode 100644 index 12aee10..0000000 --- a/llvm/test/Transforms/JumpThreading/unfold-selects-same-cond.ll +++ /dev/null @@ -1,23 +0,0 @@ -; RUN: opt < %s -jump-threading -instcombine -simplifycfg -S | FileCheck %s - -; The three selects are jump-threaded so that instcombine can optimize, and -; simplifycfg should turn the result into a single select. -define i32 @f(i32 %a, i32 %b) { -; CHECK: select -; CHECK-NOT: select -entry: - %0 = and i32 %a, 1 - %1 = and i32 %b, 1 - %xor = xor i32 %1, %a - %shr32 = lshr i32 %a, 1 - %cmp10 = icmp eq i32 %xor, 1 - %2 = xor i32 %b, 12345 - %b.addr.1 = select i1 %cmp10, i32 %2, i32 %b - %shr1633 = lshr i32 %b.addr.1, 1 - %3 = or i32 %shr1633, 54321 - %b.addr.2 = select i1 %cmp10, i32 %3, i32 %shr1633 - %shr1634 = lshr i32 %b.addr.2, 2 - %4 = or i32 %shr1634, 54320 - %b.addr.3 = select i1 %cmp10, i32 %4, i32 %shr1634 - ret i32 %b.addr.3 -} -- 2.7.4