This is an archive of the discontinued LLVM Phabricator instance.

Differential D68809

[MemorySSA] Additional handling of unreachable blocks.
ClosedPublic

Authored by asbirlea on Oct 10 2019, 9:34 AM.

Details

Reviewers
george.burgess.iv
Commits
rG67f0c5c08578: [MemorySSA] Additional handling of unreachable blocks.
rL374447: [MemorySSA] Additional handling of unreachable blocks.
Summary

Whenever we get the previous definition, the assumption is that the
recursion starts ina reachable block.
If the recursion starts in an unreachable block, we may recurse
indefinitely. Handle this case by returning LoE if the block is
unreachable.

Resolves PR43426.

Diff Detail

Event Timeline

asbirlea created this revision.Oct 10 2019, 9:34 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 10 2019, 9:34 AM
Herald added subscribers: sanjoy.google, Prazek. · View Herald Transcript
Harbormaster completed remote builds in B39339: Diff 224388.Oct 10 2019, 9:36 AM
george.burgess.iv accepted this revision.Oct 10 2019, 1:00 PM

Thanks!

test/Analysis/MemorySSA/pr43426.ll
1 ↗(On Diff #224388)

; REQUIRES: asserts?

This revision is now accepted and ready to land.Oct 10 2019, 1:00 PM
asbirlea marked 2 inline comments as done.Oct 10 2019, 1:30 PM

Thank you for the review!

test/Analysis/MemorySSA/pr43426.ll
1 ↗(On Diff #224388)

This occurs without asserts as well. It's an infinite loop.

Closed by commit rG67f0c5c08578: [MemorySSA] Additional handling of unreachable blocks. (authored by asbirlea). · Explain WhyOct 10 2019, 1:46 PM
This revision was automatically updated to reflect the committed changes.
asbirlea marked an inline comment as done.
Herald added a subscriber: hiraditya. · View Herald TranscriptOct 10 2019, 1:46 PM

Revision Contents

PathSize
llvm/
lib/
Analysis/
4 lines
test/
Analysis/
MemorySSA/
40 lines

Diff 224467

llvm/lib/Analysis/MemorySSAUpdater.cpp

Show First 20 Lines • Show All 42 Lines • ▼ Show 20 LinesMemoryAccess *MemorySSAUpdater::getPreviousDefRecursive(
DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) { DenseMap<BasicBlock *, TrackingVH<MemoryAccess>> &CachedPreviousDef) {
// First, do a cache lookup. Without this cache, certain CFG structures // First, do a cache lookup. Without this cache, certain CFG structures
// (like a series of if statements) take exponential time to visit. // (like a series of if statements) take exponential time to visit.
auto Cached = CachedPreviousDef.find(BB); auto Cached = CachedPreviousDef.find(BB);
if (Cached != CachedPreviousDef.end()) { if (Cached != CachedPreviousDef.end()) {
return Cached->second; return Cached->second;
} }
// If this method is called from an unreachable block, return LoE.
if (!MSSA->DT->isReachableFromEntry(BB))
return MSSA->getLiveOnEntryDef();
if (BasicBlock *Pred = BB->getSinglePredecessor()) { if (BasicBlock *Pred = BB->getSinglePredecessor()) {
// Single predecessor case, just recurse, we can only have one definition. // Single predecessor case, just recurse, we can only have one definition.
MemoryAccess *Result = getPreviousDefFromEnd(Pred, CachedPreviousDef); MemoryAccess *Result = getPreviousDefFromEnd(Pred, CachedPreviousDef);
CachedPreviousDef.insert({BB, Result}); CachedPreviousDef.insert({BB, Result});
return Result; return Result;
} }
if (VisitedBlocks.count(BB)) { if (VisitedBlocks.count(BB)) {
▲ Show 20 Lines • Show All 1,371 Lines • Show Last 20 Lines

llvm/test/Analysis/MemorySSA/pr43426.ll

  • This file was added.
; RUN: opt -licm -enable-mssa-loop-dependency -S %s | FileCheck %s
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
; CHECK-LABEL: @d()
define dso_local void @d() {
entry:
br label %header
header:
store i32 1, i32* null, align 4
br i1 true, label %cleanup53, label %body
body:
br i1 undef, label %cleanup31, label %for.cond11
for.cond11: ; Needs branch as is
br i1 undef, label %unreachable, label %latch
cleanup31:
br label %unreachable
deadblock:
br i1 undef, label %unreachable, label %deadblock
cleanup53:
%val = load i32, i32* null, align 4
%cmpv = icmp eq i32 %val, 0
br i1 %cmpv, label %cleanup63, label %latch
latch:
br label %header
cleanup63:
ret void
unreachable:
unreachable
}