Clang crash due to an invalid comparator used in ScalarEvolution.cpp / GroupByComplexity #147862
Description
Clang built with hardened libc++ (-D_LIBCPP_HARDENING_MODE=_LIBCPP_HARDENING_MODE_DEBUG) crashes on the following input:
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"
%struct.barney = type { %struct.spam, %struct.hoge, %struct.zot, %struct.hoge.18, %struct.widget.57, %struct.baz.65 }
%struct.spam = type { %struct.blam, %struct.foo, %struct.foo, %struct.foo, %struct.eggs, %struct.barney.0, float, float, %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.wombat, %struct.baz, %struct.wibble, %struct.wibble, [3 x float], [3 x float], %struct.bar, %struct.bar, %struct.eggs.1, %struct.eggs.1, %struct.foo, %struct.widget }
%struct.blam = type { float }
%struct.eggs = type { float }
%struct.barney.0 = type { float }
%struct.wombat = type { %struct.ham, float }
%struct.ham = type { float, float }
%struct.baz = type { float, float }
%struct.wibble = type { float, float }
%struct.bar = type { float }
%struct.eggs.1 = type { float, float, float, float, float, float }
%struct.foo = type { float }
%struct.widget = type { i8, %struct.blam, %struct.foo, %struct.foo, %struct.foo, %struct.eggs, %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.barney.0 }
%struct.hoge = type <{ %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.barney.2, %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.hoge.3, %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.wombat.4, %struct.blam.5 }>
%struct.barney.2 = type { %struct.wombat.4, %struct.wombat.4 }
%struct.hoge.3 = type <{ [2 x %struct.wombat.4], [2 x %struct.wombat.4], %struct.wombat.4, i8 }>
%struct.wombat.4 = type { float }
%struct.blam.5 = type { %struct.wombat.4, %struct.wombat.4, %struct.snork, %struct.snork, %struct.snork, %struct.snork }
%struct.snork = type <{ %struct.wombat.4, i8 }>
%struct.zot = type { %struct.widget.7, %struct.widget.7, %struct.hoge.6, %struct.foo, %struct.widget.7, %struct.widget.7, %struct.widget.7, %struct.foo, %struct.baz.9, %struct.pluto, %struct.wibble.10, %struct.wibble.16, %struct.wibble.16, %struct.bar.11, %struct.wibble.16, %struct.wibble.16, i8, %struct.wibble.16, %struct.wibble.16, i8, %struct.wibble.16, %struct.widget.17 }
%struct.hoge.6 = type { float }
%struct.widget.7 = type { %struct.bar.8 }
%struct.bar.8 = type { i64 }
%struct.baz.9 = type { float }
%struct.pluto = type { float }
%struct.wibble.10 = type { float }
%struct.bar.11 = type <{ %struct.hoge.6, [4 x i8], %struct.widget.7, %struct.spam.13, %struct.hoge.12, %struct.hoge.12, %struct.foo.15, %struct.spam.13, %struct.wombat.14, %struct.foo.15, [4 x i8] }>
%struct.hoge.12 = type { %struct.baz.9, %struct.baz.9, i32 }
%struct.spam.13 = type { %struct.foo, %struct.foo, i32 }
%struct.wombat.14 = type { %struct.wibble.10, %struct.wibble.10, i32 }
%struct.foo.15 = type { %struct.wibble.16, %struct.wibble.16, i32 }
%struct.wibble.16 = type { float }
%struct.widget.17 = type { float }
%struct.hoge.18 = type <{ %struct.hoge.19, %struct.barney.20, %struct.barney.22, %struct.wibble.44, %struct.pluto.45, %struct.blam.47, %struct.pluto.48, %struct.wobble.49, %struct.bar.51, %struct.blam.52, %struct.bar.53, %struct.baz.54, i8, i8, i8, i8 }>
%struct.hoge.19 = type { %struct.foo, %struct.hoge.6, %struct.wibble.16, %struct.widget.7, %struct.widget.7, %struct.widget.7 }
%struct.barney.20 = type { %struct.foo, [2 x %struct.wibble.10], [2 x %struct.foo], %struct.foo, %struct.foo, %struct.foo, %struct.foo, [2 x %struct.wibble.10], [2 x %struct.foo], %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.baz.9, %struct.baz.9, %struct.baz.9, i8, i8, [4 x float], [4 x float], float, float, float, float, float, float, float, float, %struct.zot.21, float, i8, %struct.baz.9 }
%struct.zot.21 = type { i16, [4 x %struct.quux] }
%struct.quux = type { float, float, float, float, float }
%struct.barney.22 = type <{ %struct.pluto.23, %struct.blam.31, %struct.baz.9, i8, [3 x i8], %struct.wibble.32, %struct.wibble.35, %struct.pluto.36, %struct.pluto.36, %struct.wibble.10, [4 x i8], %struct.widget.7, i8, i8, [2 x i8], %struct.foo, %struct.wibble.10, %struct.wibble.16, %struct.wibble.10, %struct.foo, %struct.wibble.16, %struct.wibble.10, %struct.wibble.10, %struct.foo, %struct.foo, %struct.wibble.10, %struct.foo, %struct.foo, %struct.foo, %struct.foo, %struct.wibble.10, %struct.foo, %struct.foo, %struct.eggs.37, float, %struct.wibble.16, %struct.wibble.10, %struct.wibble.16, %struct.wombat.38, %struct.hoge.39, %struct.widget.40, %struct.wibble.16, %struct.wibble.10, %struct.wobble.41, %struct.quux.42, %struct.hoge.6, %struct.hoge.6, %struct.wibble.16, %struct.zot.43, [4 x i8] }>
%struct.pluto.23 = type { %struct.pluto.24, %struct.wibble.16, %struct.quux.27, %struct.wobble, %struct.pluto.30 }
%struct.pluto.24 = type { %struct.wibble.26, %struct.pluto.36, float, %struct.snork.25, %struct.wibble.26, float, float, float }
%struct.snork.25 = type { float }
%struct.wibble.26 = type { float }
%struct.quux.27 = type { %struct.baz.28, %struct.hoge.29, %struct.pluto.36, %struct.wibble.16 }
%struct.baz.28 = type { float }
%struct.hoge.29 = type { float }
%struct.wobble = type { %struct.foo, %struct.wibble.10, %struct.wibble.10, %struct.foo, %struct.foo, float }
%struct.pluto.30 = type { %struct.wibble.10, %struct.foo, float, %struct.wibble.16 }
%struct.blam.31 = type { i8, %struct.hoge.6, %struct.wibble.10, %struct.wibble.10, %struct.wibble.16 }
%struct.wibble.32 = type { i8, %struct.eggs.33, %struct.eggs.33, %struct.wibble.10, %struct.wobble.34 }
%struct.eggs.33 = type { float }
%struct.wobble.34 = type { float }
%struct.wibble.35 = type { i8, %struct.foo, %struct.foo, %struct.wibble.16, %struct.wibble.10, %struct.wibble.10, %struct.wibble.10, [2 x %struct.baz.9], [2 x %struct.widget.17], %struct.wibble.26, %struct.wibble.16, %struct.widget.17, %struct.widget.17 }
%struct.pluto.36 = type { float }
%struct.eggs.37 = type { i8, %struct.foo, %struct.foo, %struct.wibble.10, %struct.wibble.10 }
%struct.wombat.38 = type { %struct.foo, %struct.wibble.10 }
%struct.hoge.39 = type { i8, %struct.wibble.16, %struct.wibble.10, %struct.widget.7, %struct.widget.7 }
%struct.widget.40 = type { %struct.hoge.6, %struct.wibble.10, %struct.wibble.16, %struct.wobble.34, %struct.wibble.16, %struct.foo }
%struct.wobble.41 = type <{ float, float, float, %struct.wibble.10, %struct.wibble.10, %struct.wobble.34, %struct.hoge.6, i8, i8, [2 x i8] }>
%struct.quux.42 = type { %struct.wibble.10, %struct.wibble.10, %struct.wibble.16, %struct.wibble.16, %struct.hoge.6 }
%struct.zot.43 = type { %struct.foo, %struct.foo, %struct.hoge.6 }
%struct.wibble.44 = type { float, float, float, float, float, %struct.wobble.34 }
%struct.pluto.45 = type { float, float, float, float, float, float, float, float, float, float, i8, float, float, float, float, float, float, float, i64, i64, float, %struct.spam.46 }
%struct.spam.46 = type { i8, [5 x float], [5 x float] }
%struct.blam.47 = type { float, float, float, float, float, float, float, float, float, float, float, float, float, float, float, float }
%struct.pluto.48 = type { i8, float, float }
%struct.wobble.49 = type <{ i8, [3 x i8], %struct.wibble.10, %struct.baz.50, %struct.wibble.10, float, %struct.hoge.6, %struct.hoge.6, %struct.hoge.6, float, %struct.wibble.10, %struct.baz.50, %struct.baz.50, i8, [3 x i8] }>
%struct.baz.50 = type { float }
%struct.bar.51 = type { float, float, float, float, float, float }
%struct.blam.52 = type { i8, float, float, float, %struct.widget.7, float, float, float, %struct.widget.7, %struct.widget.7 }
%struct.bar.53 = type { i8, %struct.wibble.16, %struct.wibble.10, %struct.wibble.16, %struct.foo, %struct.wibble.10, %struct.widget.17 }
%struct.baz.54 = type { i8, float, float, float, float, float, float, %struct.hoge.6, %struct.hoge.6, float, float, float, %struct.bar.55, %struct.wobble.56 }
%struct.bar.55 = type { [2 x float], [2 x float], [2 x float], [2 x float], [2 x float], [2 x float], float, float, float, float }
%struct.wobble.56 = type { [2 x float], [2 x float], [2 x float], [2 x float], [6 x %struct.wibble.10], [6 x %struct.hoge.6], [2 x %struct.wibble.10], [2 x %struct.hoge.6] }
%struct.widget.57 = type <{ %struct.widget.7, %struct.wibble.10, %struct.baz.9, %struct.wibble.10, %struct.wibble.10, %struct.wibble.10, [4 x i8], %struct.wobble.58, %struct.zot.59, %struct.wombat.62, %struct.bar.63, %struct.snork.64, [4 x i8] }>
%struct.wobble.58 = type { %struct.widget.7, %struct.widget.7 }
%struct.zot.59 = type { %struct.snork.60, float, %struct.quux.61 }
%struct.snork.60 = type <{ %struct.pluto.36, %struct.wibble.26, float, i8, [3 x i8] }>
%struct.quux.61 = type { float }
%struct.wombat.62 = type { %struct.wibble.16, %struct.wibble.16, %struct.wobble.34, %struct.widget.17, %struct.widget.17, %struct.baz.9, %struct.wibble.10 }
%struct.bar.63 = type { %struct.baz.9, %struct.baz.50 }
%struct.snork.64 = type { %struct.wibble.16, %struct.wibble.16, %struct.widget.17, %struct.widget.17, %struct.widget.17, %struct.widget.17 }
%struct.baz.65 = type <{ i8, [3 x i8], %struct.wibble.10, %struct.widget.7, %struct.wobble.34, %struct.wobble.34, %struct.wobble.34, i8, [3 x i8] }>
%struct.zot.66 = type { ptr, i64 }
@global = external global %struct.barney
@global.1 = external global %struct.barney
@global.2 = internal global %struct.barney zeroinitializer
@global.3 = constant [5 x ptr] [ptr null, ptr null, ptr @global, ptr @global.1, ptr @global.2]
define void @pluto(ptr %arg, ptr %arg1) {
bb:
br label %bb2
bb2: ; preds = %bb4, %bb
%phi = phi i64 [ 0, %bb ], [ %add, %bb4 ]
%icmp = icmp eq i64 %phi, 32
br i1 %icmp, label %bb3, label %bb4
bb3: ; preds = %bb2
ret void
bb4: ; preds = %bb2
%load = load ptr, ptr %arg, align 8
%call = call i1 @ham(ptr %load)
%zext = zext i1 %call to i8
store i8 %zext, ptr %arg1, align 1
%add = add i64 %phi, 1
br label %bb2
}
define i1 @ham(ptr %arg) {
bb:
%alloca = alloca %struct.zot.66, align 8
store ptr @global.3, ptr %alloca, align 8
%getelementptr = getelementptr i8, ptr %alloca, i64 8
store i64 5, ptr %getelementptr, align 8
%call = call ptr @blam(ptr %alloca)
%call1 = call ptr @widget(ptr %alloca)
br label %bb2
bb2: ; preds = %bb5, %bb
%phi = phi ptr [ %call, %bb ], [ %getelementptr6, %bb5 ]
%icmp = icmp ne ptr %phi, %call1
br i1 %icmp, label %bb3, label %bb7
bb3: ; preds = %bb2
%load = load ptr, ptr %phi, align 8
%icmp4 = icmp eq ptr %arg, %load
br i1 %icmp4, label %bb7, label %bb5
bb5: ; preds = %bb3
%getelementptr6 = getelementptr i8, ptr %phi, i64 8
br label %bb2
bb7: ; preds = %bb3, %bb2
ret i1 %icmp
}
define ptr @blam(ptr %arg) {
bb:
%load = load ptr, ptr %arg, align 8
ret ptr %load
}
define ptr @widget(ptr %arg) {
bb:
%load = load ptr, ptr %arg, align 8
%getelementptr = getelementptr i8, ptr %arg, i64 8
%load1 = load i64, ptr %getelementptr, align 8
%getelementptr2 = getelementptr ptr, ptr %load, i64 %load1
ret ptr %getelementptr2
}
Stack trace:
* frame #0: 0x00007ffff7cee981 libc.so.6`raise + 161
frame #1: 0x00007ffff7cefdf7 libc.so.6`abort + 247
frame #5: 0x000055557142c9f5 clang`void std::__u::stable_sort<llvm::SCEV const**, GroupByComplexity(llvm::SmallVectorImpl<llvm::SCEV const*>&, llvm::LoopInfo*, llvm::DominatorTree&)::$_0>(__first=0x00005092ffe53000, __last=0x00005092ffe53020, __comp=(unnamed class) @ 0x00007ffffffeb348) at stable_sort.h:311:3
frame #6: 0x000055557142baa4 clang`void llvm::stable_sort<llvm::SmallVectorImpl<llvm::SCEV const*>&, GroupByComplexity(llvm::SmallVectorImpl<llvm::SCEV const*>&, llvm::LoopInfo*, llvm::DominatorTree&)::$_0>(Range=0x00007ffffffec0b8, C=(unnamed class) @ 0x00007ffffffeb388) at STLExtras.h:2083:3
frame #7: 0x000055557142b6d6 clang`GroupByComplexity(Ops=0x00007ffffffec0b8, LI=0x00005092ffe10200, DT=0x00005092ffe32878) at ScalarEvolution.cpp:783:3
frame #8: 0x00005555713ce176 clang`llvm::SCEV const* constantFoldAndGroupOps<llvm::ScalarEvolution::getMinMaxExpr(llvm::SCEVTypes, llvm::SmallVectorImpl<llvm::SCEV const*>&)::$_0, llvm::ScalarEvolution::getMinMaxExpr(llvm::SCEVTypes, llvm::SmallVectorImpl<llvm::SCEV const*>&)::$_1, llvm::ScalarEvolution::getMinMaxExpr(llvm::SCEVTypes, llvm::SmallVectorImpl<llvm::SCEV const*>&)::$_2>(SE=0x00005092ffc82b08, LI=0x00005092ffe10200, DT=0x00005092ffe32878, Ops=0x00007ffffffec0b8, Fold=(unnamed class) @ 0x00007ffffffeb630, IsIdentity=(unnamed class) @ 0x00007ffffffeb650, IsAbsorber=(unnamed class) @ 0x00007ffffffeb660) at ScalarEvolution.cpp:852:3
frame #9: 0x00005555713cd12c clang`llvm::ScalarEvolution::getMinMaxExpr(this=0x00005092ffc82b08, Kind=scUMaxExpr, Ops=0x00007ffffffec0b8) at ScalarEvolution.cpp:3833:24
frame #10: 0x00005555713cd497 clang`llvm::ScalarEvolution::getMinMaxExpr(this=0x00005092ffc82b08, Kind=scUMaxExpr, Ops=0x00007ffffffec0b8) at ScalarEvolution.cpp:3888:14
frame #11: 0x00005555713c4748 clang`llvm::ScalarEvolution::getUMaxExpr(this=0x00005092ffc82b08, Ops=0x00007ffffffec0b8) at ScalarEvolution.cpp:4343:10
frame #12: 0x00005555713d00e5 clang`llvm::ScalarEvolution::getUMaxExpr(this=0x00005092ffc82b08, LHS=0x00005092ffd86670, RHS=0x00005092ffd86600) at ScalarEvolution.cpp:4339:10
frame #13: 0x00005555713e3677 clang`llvm::ScalarEvolution::createSCEV(this=0x00005092ffc82b08, V=0x00005092ffe34820) at ScalarEvolution.cpp:7863:16
frame #14: 0x00005555713d15a8 clang`llvm::ScalarEvolution::createSCEVIter(this=0x00005092ffc82b08, V=0x00005092ffe02720) at ScalarEvolution.cpp:7471:21
frame #15: 0x00005555713c823b clang`llvm::ScalarEvolution::getSCEV(this=0x00005092ffc82b08, V=0x00005092ffe02720) at ScalarEvolution.cpp:4537:10
frame #16: 0x00005555711d4f12 clang`llvm::LoopAccessInfo::isInvariant(this=0x00005092ffe10a80, V=0x00005092ffe02720) const at LoopAccessAnalysis.cpp:2837:23
frame #17: 0x000055556fb3a917 clang`llvm::LoopVectorizationLegality::isInvariant(this=0x00007ffffffeffe0, V=0x00005092ffe02720) const at LoopVectorizationLegality.cpp:472:15
frame #18: 0x000055556fa688ec clang`llvm::LoopVectorizationCostModel::getUniformMemOpCost(this=0x00007ffffffefad8, I=0x00005092ffe32940, VF=ElementCount @ 0x00007ffffffed3f8) at LoopVectorize.cpp:5252:43
frame #19: 0x000055556fa69bcd clang`llvm::LoopVectorizationCostModel::setCostBasedWideningDecision(this=0x00007ffffffefad8, VF=ElementCount @ 0x00007ffffffedc18) at LoopVectorize.cpp:5617:36
frame #20: 0x000055556fab1073 clang`llvm::LoopVectorizationCostModel::collectNonVectorizedAndSetWideningDecisions(this=0x00007ffffffefad8, VF=ElementCount @ 0x00007ffffffedc78) at LoopVectorize.cpp:1198:5
frame #21: 0x000055556fa6fa5c clang`llvm::LoopVectorizationPlanner::plan(this=0x00007ffffffef8b0, UserVF=ElementCount @ 0x00007ffffffedef8, UserIC=0) at LoopVectorize.cpp:6701:8
frame #22: 0x000055556fa8714d clang`llvm::LoopVectorizePass::processLoop(this=0x00005092ffe02cb8, L=0x00005092ffd87000) at LoopVectorize.cpp:10073:7
frame #23: 0x000055556fa8e88f clang`llvm::LoopVectorizePass::runImpl(this=0x00005092ffe02cb8, F=0x00005092ffe32488) at LoopVectorize.cpp:10367:30
frame #24: 0x000055556fa8efbd clang`llvm::LoopVectorizePass::run(this=0x00005092ffe02cb8, F=0x00005092ffe32488, AM=0x00007fffffff2d68) at LoopVectorize.cpp:10404:32
frame #25: 0x000055556d215498 clang`llvm::detail::PassModel<llvm::Function, llvm::LoopVectorizePass, llvm::AnalysisManager<llvm::Function>>::run(this=0x00005092ffe02cb0, IR=0x00005092ffe32488, AM=0x00007fffffff2d68) at PassManagerInternal.h:91:17
frame #26: 0x0000555572330a4e clang`llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(this=0x00005092ffe4e4c8, IR=0x00005092ffe32488, AM=0x00007fffffff2d68) at PassManagerImpl.h:76:38
frame #27: 0x0000555563b05448 clang`llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>, llvm::AnalysisManager<llvm::Function>>::run(this=0x00005092ffe4e4c0, IR=0x00005092ffe32488, AM=0x00007fffffff2d68) at PassManagerInternal.h:91:17
frame #28: 0x000055557232ebc4 clang`llvm::ModuleToFunctionPassAdaptor::run(this=0x00005092ffe54008, M=0x00005092ffc88e00, AM=0x00007fffffff2cd8) at PassManager.cpp:127:38
frame #29: 0x0000555563af3dd8 clang`llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::AnalysisManager<llvm::Module>>::run(this=0x00005092ffe54000, IR=0x00005092ffc88e00, AM=0x00007fffffff2cd8) at PassManagerInternal.h:91:17
frame #30: 0x000055557232f49e clang`llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(this=0x00007fffffff17e0, IR=0x00005092ffc88e00, AM=0x00007fffffff2cd8) at PassManagerImpl.h:76:38
frame #31: 0x0000555563ad5739 clang`(anonymous namespace)::EmitAssemblyHelper::RunOptimizationPipeline(this=0x00007fffffff39d0, Action=Backend_EmitObj, OS=llvm::raw_pwrite_stream @ 0x00005092ffe0d4a0, ThinLinkOS=nullptr, BC=0x0000000000000000) at BackendUtil.cpp:1210:9
frame #32: 0x0000555563accf1c clang`(anonymous namespace)::EmitAssemblyHelper::emitAssembly(this=0x00007fffffff39d0, Action=Backend_EmitObj, OS=llvm::raw_pwrite_stream @ 0x00005092ffe0d4a0, BC=0x0000000000000000) at BackendUtil.cpp:1283:3
frame #33: 0x0000555563acba33 clang`clang::emitBackendOutput(CI=0x00005092ffe0e9a0, CGOpts=0x00005092ffc66018, TDesc=(Data = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128", Length = 79), M=0x00005092ffc88e00, Action=Backend_EmitObj, VFS=IntrusiveRefCntPtr @ 0x00007fffffff3e28, OS=nullptr, BC=0x0000000000000000) at BackendUtil.cpp:1449:13
frame #34: 0x0000555563039ae7 clang`clang::CodeGenAction::ExecuteAction(this=0x00005092ffe28700) at CodeGenAction.cpp:1187:3
frame #35: 0x000055556576cbab clang`clang::FrontendAction::Execute(this=0x00005092ffe28700) at FrontendAction.cpp:1221:3
frame #36: 0x0000555565615e4d clang`clang::CompilerInstance::ExecuteAction(this=0x00005092ffe0e9a0, Act=0x00005092ffe28700) at CompilerInstance.cpp:1055:33
frame #37: 0x0000555563027da5 clang`clang::ExecuteCompilerInvocation(Clang=0x00005092ffe0e9a0) at ExecuteCompilerInvocation.cpp:299:25
...
The problem is the IsLessComplex comparator used in GroupByComplexity in llvm/lib/Analysis/ScalarEvolution.cpp.