Index: llvm/lib/Transforms/Scalar/GVNHoist.cpp =================================================================== --- llvm/lib/Transforms/Scalar/GVNHoist.cpp +++ llvm/lib/Transforms/Scalar/GVNHoist.cpp @@ -306,40 +306,37 @@ } // Return true when all paths from HoistBB to the end of the function pass - // through one of the blocks in WL. - bool hoistingFromAllPaths(const BasicBlock *HoistBB, - SmallPtrSetImpl &WL) { - - // Copy WL as the loop will remove elements from it. - SmallPtrSet WorkList(WL.begin(), WL.end()); - - for (auto It = df_begin(HoistBB), E = df_end(HoistBB); It != E;) { - // There exists a path from HoistBB to the exit of the function if we are - // still iterating in DF traversal and we removed all instructions from - // the work list. - if (WorkList.empty()) - return false; - - const BasicBlock *BB = *It; - if (WorkList.erase(BB)) { - // Stop DFS traversal when BB is in the work list. - It.skipChildren(); + // through one of the blocks in WL. Check for anticipability via graph + // reachability when dominance (HoistBB dominates WL) has already been + // established. If a leaf node in CFG can be reached from HoistBB without + // crossing an element from WL, that means any expression in WL cannot be + // anticipable at HoistBB. We do not check for availability of operands at + // this stage because in some cases operands can be made available. + bool anticReachable(const BasicBlock *HoistBB, + const SmallPtrSetImpl &WL) { + SmallPtrSet Remaining; + SmallVector Queue; + Queue.push_back(HoistBB); + // Perform BFS from HoistBB on its successors until an element from + // WL is found. A path where no element from WL is found indicates + // it may be unsafe to hoist to HoistBB i.e., not-anticipable. + while(!Queue.empty()) { + const BasicBlock *BB = Queue.back(); + Queue.pop_back(); + if (WL.count(BB)) continue; - } // We reached the leaf Basic Block => not all paths have this instruction. if (!BB->getTerminator()->getNumSuccessors()) return false; - // When reaching the back-edge of a loop, there may be a path through the - // loop that does not pass through B or C before exiting the loop. - if (successorDominate(BB, HoistBB)) - return false; - - // Increment DFS traversal when not skipping children. - ++It; + for (const BasicBlock *Succ : BB->getTerminator()->successors()) { + if (Remaining.count(Succ)) // Loop. + return false; + Queue.push_back(Succ); + Remaining.insert(Succ); + } } - return true; } @@ -537,7 +534,7 @@ SmallPtrSetImpl &WL, int &NBBsOnAllPaths) { // Check that the hoisted expression is needed on all paths. - if (!hoistingFromAllPaths(HoistBB, WL)) + if (!anticReachable(HoistBB, WL)) return false; for (const BasicBlock *BB : WL) @@ -614,7 +611,7 @@ // loading from the same address: for instance there may be a branch on // which the address of the load may not be initialized. if ((HoistBB == NewHoistBB || BB == NewHoistBB || - hoistingFromAllPaths(NewHoistBB, WL)) && + anticReachable(NewHoistBB, WL)) && // Also check that it is safe to move the load or store from HoistPt // to NewHoistPt, and from Insn to NewHoistPt. safeToHoistLdSt(NewHoistPt, HoistPt, UD, K, NumBBsOnAllPaths) && Index: llvm/test/Transforms/GVNHoist/infinite-loop.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/GVNHoist/infinite-loop.ll @@ -0,0 +1,72 @@ +; RUN: opt -S -gvn-hoist < %s | FileCheck %s + +; Check that nothing is hoisted in this case. +; CHECK: @bazv +; CHECK: if.then.i: +; CHECK: bitcast +; CHECK-NEXT: load +; CHECK: if.then4.i: +; CHECK: bitcast +; CHECK-NEXT: load + +%class.bar = type { i8*, %class.base* } +%class.base = type { i32 (...)** } + +; Function Attrs: noreturn nounwind uwtable +define void @bazv() local_unnamed_addr #0 { +entry: + %agg.tmp = alloca %class.bar, align 8 + %x.sroa.2.0..sroa_idx2 = getelementptr inbounds %class.bar, %class.bar* %agg.tmp, i64 0, i32 1 + store %class.base* null, %class.base** %x.sroa.2.0..sroa_idx2, align 8 + call void @_Z3foo3bar(%class.bar* nonnull %agg.tmp) #2 + %0 = load %class.base*, %class.base** %x.sroa.2.0..sroa_idx2, align 8, !tbaa !1 + %1 = bitcast %class.bar* %agg.tmp to %class.base* + %cmp.i = icmp eq %class.base* %0, %1 + br i1 %cmp.i, label %if.then.i, label %if.else.i + +if.then.i: ; preds = %entry + %2 = bitcast %class.base* %0 to void (%class.base*)*** + %vtable.i = load void (%class.base*)**, void (%class.base*)*** %2, align 8, !tbaa !6 + %vfn.i = getelementptr inbounds void (%class.base*)*, void (%class.base*)** %vtable.i, i64 2 + %3 = load void (%class.base*)*, void (%class.base*)** %vfn.i, align 8 + call void %3(%class.base* %0) #2 + br label %while.cond.preheader + +if.else.i: ; preds = %entry + %tobool.i = icmp eq %class.base* %0, null + br i1 %tobool.i, label %while.cond.preheader, label %if.then4.i + +if.then4.i: ; preds = %if.else.i + %4 = bitcast %class.base* %0 to void (%class.base*)*** + %vtable6.i = load void (%class.base*)**, void (%class.base*)*** %4, align 8, !tbaa !6 + %vfn7.i = getelementptr inbounds void (%class.base*)*, void (%class.base*)** %vtable6.i, i64 3 + %5 = load void (%class.base*)*, void (%class.base*)** %vfn7.i, align 8 + call void %5(%class.base* nonnull %0) #2 + br label %while.cond.preheader + +while.cond.preheader: ; preds = %if.then.i, %if.else.i, %if.then4.i + br label %while.cond + +while.cond: ; preds = %while.cond.preheader, %while.cond + %call = call i32 @sleep(i32 10) #2 + br label %while.cond +} + +declare void @_Z3foo3bar(%class.bar*) local_unnamed_addr #1 + +declare i32 @sleep(i32) local_unnamed_addr #1 + +attributes #0 = { noreturn nounwind uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } +attributes #2 = { nounwind } + +!llvm.ident = !{!0} + +!0 = !{!"clang version 5.0.0 (llvm/trunk 301510)"} +!1 = !{!2, !3, i64 8} +!2 = !{!"_ZTS3bar", !3, i64 0, !3, i64 8} +!3 = !{!"any pointer", !4, i64 0} +!4 = !{!"omnipotent char", !5, i64 0} +!5 = !{!"Simple C++ TBAA"} +!6 = !{!7, !7, i64 0} +!7 = !{!"vtable pointer", !5, i64 0}