This is an archive of the discontinued LLVM Phabricator instance.

Differential D84818

[JumpThreading] Fold br(freeze(undef))
ClosedPublic

Authored by aqjune on Jul 28 2020, 6:47 PM.

Details

Reviewers
efriedma
nikic
kazu
Commits
rG111a02decd4f: [JumpThreading] Fold br(freeze(undef))
Summary

This patch makes JumpThreading fold br(freeze(undef)) if the freeze instruction
is only used by the branch.

Diff Detail

Event Timeline

aqjune created this revision.Jul 28 2020, 6:47 PM
Herald added a project: Restricted Project. · View Herald TranscriptJul 28 2020, 6:47 PM
Herald added subscribers: llvm-commits, hiraditya. · View Herald Transcript
aqjune requested review of this revision.Jul 28 2020, 6:47 PM
Harbormaster completed remote builds in B66146: Diff 281450.Jul 28 2020, 9:37 PM
efriedma accepted this revision.Jul 29 2020, 10:38 AM

I'm a little surprised this is relevant, but sure, LGTM.

This revision is now accepted and ready to land.Jul 29 2020, 10:38 AM
Closed by commit rG111a02decd4f: [JumpThreading] Fold br(freeze(undef)) (authored by aqjune). · Explain WhyJul 29 2020, 5:39 PM
This revision was automatically updated to reflect the committed changes.
aqjune added a commit: rG111a02decd4f: [JumpThreading] Fold br(freeze(undef)).
aqjune mentioned this in D84948: [InstCombine] Fold freeze(undef) into a proper constant.Jul 31 2020, 1:21 AM

Revision Contents

PathSize
llvm/
lib/
Transforms/
Scalar/
10 lines
test/
Transforms/
JumpThreading/
14 lines

Diff 281774

llvm/lib/Transforms/Scalar/JumpThreading.cpp

Show First 20 Lines • Show All 1,051 Lines • ▼ Show 20 Lines if (Instruction *I = dyn_cast<Instruction>(Condition)) {
if (SimpleVal) { if (SimpleVal) {
I->replaceAllUsesWith(SimpleVal); I->replaceAllUsesWith(SimpleVal);
if (isInstructionTriviallyDead(I, TLI)) if (isInstructionTriviallyDead(I, TLI))
I->eraseFromParent(); I->eraseFromParent();
Condition = SimpleVal; Condition = SimpleVal;
} }
} }
// If the terminator is branching on an undef, we can pick any of the // If the terminator is branching on an undef or freeze undef, we can pick any
// successors to branch to. Let GetBestDestForJumpOnUndef decide. // of the successors to branch to. Let GetBestDestForJumpOnUndef decide.
if (isa<UndefValue>(Condition)) { auto *FI = dyn_cast<FreezeInst>(Condition);
if (isa<UndefValue>(Condition) ||
(FI && isa<UndefValue>(FI->getOperand(0)) && FI->hasOneUse())) {
unsigned BestSucc = GetBestDestForJumpOnUndef(BB); unsigned BestSucc = GetBestDestForJumpOnUndef(BB);
std::vector<DominatorTree::UpdateType> Updates; std::vector<DominatorTree::UpdateType> Updates;
// Fold the branch/switch. // Fold the branch/switch.
Instruction *BBTerm = BB->getTerminator(); Instruction *BBTerm = BB->getTerminator();
Updates.reserve(BBTerm->getNumSuccessors()); Updates.reserve(BBTerm->getNumSuccessors());
for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) { for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
if (i == BestSucc) continue; if (i == BestSucc) continue;
BasicBlock *Succ = BBTerm->getSuccessor(i); BasicBlock *Succ = BBTerm->getSuccessor(i);
Succ->removePredecessor(BB, true); Succ->removePredecessor(BB, true);
Updates.push_back({DominatorTree::Delete, BB, Succ}); Updates.push_back({DominatorTree::Delete, BB, Succ});
} }
LLVM_DEBUG(dbgs() << " In block '" << BB->getName() LLVM_DEBUG(dbgs() << " In block '" << BB->getName()
<< "' folding undef terminator: " << *BBTerm << '\n'); << "' folding undef terminator: " << *BBTerm << '\n');
BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm); BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
BBTerm->eraseFromParent(); BBTerm->eraseFromParent();
DTU->applyUpdatesPermissive(Updates); DTU->applyUpdatesPermissive(Updates);
if (FI)
FI->eraseFromParent();
return true; return true;
} }
// If the terminator of this block is branching on a constant, simplify the // If the terminator of this block is branching on a constant, simplify the
// terminator to an unconditional branch. This can occur due to threading in // terminator to an unconditional branch. This can occur due to threading in
// other blocks. // other blocks.
if (getKnownConstant(Condition, Preference)) { if (getKnownConstant(Condition, Preference)) {
LLVM_DEBUG(dbgs() << " In block '" << BB->getName() LLVM_DEBUG(dbgs() << " In block '" << BB->getName()
▲ Show 20 Lines • Show All 1,905 Lines • Show Last 20 Lines

llvm/test/Transforms/JumpThreading/freeze.ll

Show First 20 Lines • Show All 122 Lines • ▼ Show 20 LinesT2:
ret i32 %B ret i32 %B
F2: F2:
ret i32 %B ret i32 %B
} }
define i32 @test1_undef(i1 %cond) { define i32 @test1_undef(i1 %cond) {
; CHECK-LABEL: @test1_undef( ; CHECK-LABEL: @test1_undef(
; CHECK-NEXT: br i1 [[COND:%.*]], label [[MERGE_THREAD:%.*]], label [[MERGE:%.*]] ; CHECK-NEXT: br i1 [[COND:%.*]], label [[T2:%.*]], label [[F2:%.*]]
; CHECK: Merge.thread:
; CHECK-NEXT: [[V1:%.*]] = call i32 @f1()
; CHECK-NEXT: br label [[T2:%.*]]
; CHECK: Merge:
; CHECK-NEXT: [[V2:%.*]] = call i32 @f2()
; CHECK-NEXT: [[A_FR:%.*]] = freeze i1 undef
; CHECK-NEXT: br i1 [[A_FR]], label [[T2]], label [[F2:%.*]]
; CHECK: T2: ; CHECK: T2:
; CHECK-NEXT: [[B4:%.*]] = phi i32 [ [[V1]], [[MERGE_THREAD]] ], [ [[V2]], [[MERGE]] ] ; CHECK-NEXT: [[V1:%.*]] = call i32 @f1()
; CHECK-NEXT: call void @f3() ; CHECK-NEXT: call void @f3()
; CHECK-NEXT: ret i32 [[B4]] ; CHECK-NEXT: ret i32 [[V1]]
; CHECK: F2: ; CHECK: F2:
; CHECK-NEXT: [[V2:%.*]] = call i32 @f2()
; CHECK-NEXT: ret i32 [[V2]] ; CHECK-NEXT: ret i32 [[V2]]
; ;
br i1 %cond, label %T1, label %F1 br i1 %cond, label %T1, label %F1
T1: T1:
%v1 = call i32 @f1() %v1 = call i32 @f1()
br label %Merge br label %Merge
▲ Show 20 Lines • Show All 58 Lines • Show Last 20 Lines