This is an archive of the discontinued LLVM Phabricator instance.

[IROutliner][IRSim] Add all outlined region basic blocks to canonical numbering to add basic blocks to generated PHINode numbering generation.
ClosedPublic

Authored by AndrewLitteken on Mar 21 2022, 8:39 PM.

Details

Summary

Issue: https://github.com/llvm/llvm-project/issues/54431

PHINodes that need to be generated to accommodate a PHINode outside the region due to different output paths need to have their own numbering to determine the number of output schemes required to properly handle all the outlined regions. This numbering was previously only determined by the order and values of the incoming values, as well as the parent block of the PHINode. This adds the incoming blocks to the calculation of a hash value for these PHINodes as well, and the supporting infrastructure to give each block in a region a corresponding canonical numbering.

Diff Detail

Event Timeline

AndrewLitteken created this revision.Mar 21 2022, 8:39 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 21 2022, 8:39 PM
AndrewLitteken requested review of this revision.Mar 21 2022, 8:39 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 21 2022, 8:39 PM
paquette added inline comments.Mar 23 2022, 3:45 PM
llvm/lib/Analysis/IRSimilarityIdentifier.cpp
1025
1032

I think we can have more descriptive names for the variables here?

1034
1039

Can we use a more descriptive name than V?

1046

Nit: We can use the ternary operator for the assignment here.

Value *V = BB == getStartBB() ? frontInstruction() : &BB->front();
1047

I think we can be more descriptive than This<Thing> for the names here. Is there a way to link the name back to what you described in the comment above?

llvm/lib/Transforms/IPO/IROutliner.cpp
1192

nit: Maybe in a follow-up, it'd be good to rename OGVN to something like CanonicalNum, just to be clearer as to what it really is.

paquette accepted this revision.Apr 13 2022, 2:30 PM

I think this is fine.

This revision is now accepted and ready to land.Apr 13 2022, 2:30 PM

I applied this patch locally and tried to run the test suite at -O2 with it with asserts enabled. It fell over building fpcmp.

Assertion failed: (V != nullptr && "Value is a nullptr?"), function getGVN, file IRSimilarityIdentifier.h, line 896.

Reduced reproducer here: https://godbolt.org/z/4jW3KsEns

Reduced reproducer here: https://godbolt.org/z/4jW3KsEns

I tried to replicate this on my side, but I can't. I applied the patch posted here and applied it to the current main branch as well rather than using my branch and still couldn't reproduce it on a standard debug build of Clang. I also tried to build the test suite with -O2 and the outliner with and without the cost model on, but still couldn't reproduce the bug shown here :/. I'm not sure if I'm missing something, or what I am doing differently.

paquette accepted this revision.Apr 14 2022, 10:10 AM

You know what, I think I wonked something up somehow on my end, because I rebuilt + reran the test suite overnight with -Oz + -O2 and it seems fine.

I think this is good to go!

This revision was landed with ongoing or failed builds.Apr 14 2022, 10:14 AM
This revision was automatically updated to reflect the committed changes.
bjope added a subscriber: bjope.Apr 16 2022, 10:49 AM

Seen assertion failures downstream with this patch. Here is a reproducer:

; ModuleID = 'irsimilarity_crash.ll'
source_filename = "irsimilarity_crash.ll"

@v_13 = external dso_local global ptr, align 1

; Function Attrs: nocallback nofree nosync nounwind readnone speculatable willreturn
declare void @llvm.dbg.declare(metadata, metadata, metadata) #0

define dso_local i16 @main() {
entry:
  %indirect-arg-temp537 = alloca { float, float }, align 1
  %0 = load ptr, ptr @v_13, align 1
  br label %for.cond108

for.cond108:                                      ; preds = %for.body110, %entry
  br i1 undef, label %for.body110, label %for.end122

for.body110:                                      ; preds = %for.cond108
  br label %for.cond108

for.end122:                                       ; preds = %for.cond108
  call void @llvm.dbg.declare(metadata ptr undef, metadata !1, metadata !DIExpression()), !dbg !11
  store i32 30, ptr undef, align 1
  br label %for.cond123

for.cond123:                                      ; preds = %for.end122
  br i1 undef, label %for.body125, label %for.end146

for.body125:                                      ; preds = %for.cond123
  unreachable

for.end146:                                       ; preds = %for.cond123
  br label %for.cond148

for.cond148:                                      ; preds = %for.end146
  br label %for.cond167

for.cond167:                                      ; preds = %for.body169, %for.cond148
  br i1 undef, label %for.body169, label %for.end246

for.body169:                                      ; preds = %for.cond167
  br label %for.cond167

for.end246:                                       ; preds = %for.cond167
  store i32 0, ptr undef, align 1
  unreachable
}

attributes #0 = { nocallback nofree nosync nounwind readnone speculatable willreturn }

!llvm.dbg.cu = !{}
!llvm.module.flags = !{!0}

!0 = !{i32 2, !"Debug Info Version", i32 3}
!1 = !DILocalVariable(name: "v_68", scope: !2, file: !3, line: 522, type: !10)
!2 = distinct !DILexicalBlock(scope: !4, file: !3, line: 522, column: 9)
!3 = !DIFile(filename: "41097217.c", directory: "rt.outdir")
!4 = distinct !DISubprogram(name: "main", scope: !3, file: !3, line: 480, type: !5, scopeLine: 481, spFlags: DISPFlagDefinition, unit: !8, retainedNodes: !9)
!5 = !DISubroutineType(types: !6)
!6 = !{!7}
!7 = !DIBasicType(name: "int", size: 16, encoding: DW_ATE_signed)
!8 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3, producer: "clang version 15.0.0.prerel", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, retainedTypes: !9, globals: !9, splitDebugInlining: false, nameTableKind: None)
!9 = !{}
!10 = !DIBasicType(name: "long", size: 32, encoding: DW_ATE_signed)
!11 = !DILocation(line: 522, column: 23, scope: !2)

Hits an assertion if using a build with asserts when running

opt -passes='require<ir-similarity>' -S -o - irsimilarity_crash.ll

Part of stack trace:

opt: ../include/llvm/ADT/Optional.h:195: T &llvm::optional_detail::OptionalStorage<unsigned int, true>::getValue() & [T = unsigned int]: Assertion `hasVal' failed.
Stack dump:
0.      Program arguments: build-all/bin/opt -passes=require<ir-similarity> -S -o - irsimilarity_crash.ll
 #0 0x0000000002f2be08 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (build-all/bin/opt+0x2f2be08)
 #1 0x0000000002f29a7e llvm::sys::RunSignalHandlers() (build-all/bin/opt+0x2f29a7e)
 #2 0x0000000002f2c4a6 SignalHandler(int) Signals.cpp:0:0
 #3 0x00007f76ba600630 __restore_rt sigaction.c:0:0
 #4 0x00007f76b7d47387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007f76b7d48a78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00007f76b7d401a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
 #7 0x00007f76b7d40252 (/lib64/libc.so.6+0x2f252)
 #8 0x0000000001d57f8c llvm::IRSimilarity::IRSimilarityCandidate::createCanonicalRelationFrom(llvm::IRSimilarity::IRSimilarityCandidate&, llvm::DenseMap<unsigned int, llvm::DenseSet<unsigned int, llvm::DenseMapInfo<unsigned int, void> >, llvm::DenseMapInfo<unsigned int, void>, llvm::detail::DenseMapPair<unsigned int, llvm::DenseSet<unsigned int, llvm::DenseMapInfo<unsigned int, void> > > >&, llvm::DenseMap<unsigned int, llvm::DenseSet<unsigned int, llvm::DenseMapInfo<unsigned int, void> >, llvm::DenseMapInfo<unsigned int, void>, llvm::detail::DenseMapPair<unsigned int, llvm::DenseSet<unsigned int, llvm::DenseMapInfo<unsigned int, void> > > >&) (build-all/bin/opt+0x1d57f8c)
 #9 0x0000000001d59141 llvm::IRSimilarity::IRSimilarityIdentifier::findCandidates(std::vector<llvm::IRSimilarity::IRInstructionData*, std::allocator<llvm::IRSimilarity::IRInstructionData*> >&, std::vector<unsigned int, std::allocator<unsigned int> >&) (build-all/bin/opt+0x1d59141)
#10 0x0000000001d59fbc llvm::IRSimilarity::IRSimilarityIdentifier::findSimilarity(llvm::Module&) (build-all/bin/opt+0x1d59fbc)

Seen assertion failures downstream with this patch. Here is a reproducer:

Here is a patch that fixes this issue.

Hi!

The following starts to crash with this patch, and it still crashes on current top of tree 036aeac36c:

opt -passes='require<ir-similarity>' -o /dev/null bbi-68950.ll

We get

opt: ../include/llvm/Support/Casting.h:269: typename cast_retty<X, Y *>::ret_type llvm::cast(Y *) [X = llvm::Instruction, Y = llvm::Value]: Assertion `isa<X>(Val) && "cast<Ty>() argument of incompatible type!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: build-all/bin/opt -passes=require<ir-similarity> -o /dev/null /home/uabelho/bbi-68950.ll
Stack dump without symbol names (ensure you have llvm-symbolizer in your PATH or set the environment var `LLVM_SYMBOLIZER_PATH` to point to it):
build-all/bin/opt(_ZN4llvm3sys15PrintStackTraceERNS_11raw_ostreamEi+0x23)[0x2cbf503]
build-all/bin/opt(_ZN4llvm3sys17RunSignalHandlersEv+0xee)[0x2cbd17e]
build-all/bin/opt[0x2cbf886]
/lib64/libpthread.so.0(+0xf630)[0x7f7bebb82630]
/lib64/libc.so.6(gsignal+0x37)[0x7f7be92c9387]
/lib64/libc.so.6(abort+0x148)[0x7f7be92caa78]
/lib64/libc.so.6(+0x2f1a6)[0x7f7be92c21a6]
/lib64/libc.so.6(+0x2f252)[0x7f7be92c2252]
build-all/bin/opt(_ZN4llvm12IRSimilarity21IRSimilarityCandidate27createCanonicalRelationFromERS1_RNS_8DenseMapIjNS_8DenseSetIjNS_12DenseMapInfoIjvEEEES6_NS_6detail12DenseMapPairIjS7_EEEESC_+0x11e6)[0x1b835d6]
build-all/bin/opt(_ZN4llvm12IRSimilarity22IRSimilarityIdentifier14findCandidatesERSt6vectorIPNS0_17IRInstructionDataESaIS4_EERS2_IjSaIjEE+0xa51)[0x1b84631]
build-all/bin/opt(_ZN4llvm12IRSimilarity22IRSimilarityIdentifier14findSimilarityERNS_6ModuleE+0xec)[0x1b854ac]
build-all/bin/opt(_ZN4llvm20IRSimilarityAnalysis3runERNS_6ModuleERNS_15AnalysisManagerIS1_JEEE+0x181)[0x1b85a81]
build-all/bin/opt[0x2fe4320]
build-all/bin/opt(_ZN4llvm15AnalysisManagerINS_6ModuleEJEE13getResultImplEPNS_11AnalysisKeyERS1_+0x20e)[0x245fb1e]
build-all/bin/opt[0x2ff1258]
build-all/bin/opt[0x2ff109d]
build-all/bin/opt(_ZN4llvm11PassManagerINS_6ModuleENS_15AnalysisManagerIS1_JEEEJEE3runERS1_RS3_+0x208)[0x245d3d8]
build-all/bin/opt(_ZN4llvm15runPassPipelineENS_9StringRefERNS_6ModuleEPNS_13TargetMachineEPNS_21TargetLibraryInfoImplEPNS_14ToolOutputFileES8_S8_S0_NS_8ArrayRefIS0_EENS9_INS_10PassPluginEEENS_8opt_tool10OutputKindENSD_12VerifierKindEbbbbb+0x3f9f)[0x78657f]
build-all/bin/opt(main+0x3fad)[0x7972cd]
/lib64/libc.so.6(__libc_start_main+0xf5)[0x7f7be92b5555]
build-all/bin/opt[0x780ec0]

Hi!

The following starts to crash with this patch, and it still crashes on current top of tree 036aeac36c:

opt -passes='require<ir-similarity>' -o /dev/null bbi-68950.ll

We get

opt: ../include/llvm/Support/Casting.h:269: typename cast_retty<X, Y *>::ret_type llvm::cast(Y *) [X = llvm::Instruction, Y = llvm::Value]: Assertion `isa<X>(Val) && "cast<Ty>() argument of incompatible type!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: build-all/bin/opt -passes=require<ir-similarity> -o /dev/null /home/uabelho/bbi-68950.ll
Stack dump without symbol names (ensure you have llvm-symbolizer in your PATH or set the environment var `LLVM_SYMBOLIZER_PATH` to point to it):
build-all/bin/opt(_ZN4llvm3sys15PrintStackTraceERNS_11raw_ostreamEi+0x23)[0x2cbf503]
build-all/bin/opt(_ZN4llvm3sys17RunSignalHandlersEv+0xee)[0x2cbd17e]
build-all/bin/opt[0x2cbf886]
/lib64/libpthread.so.0(+0xf630)[0x7f7bebb82630]
/lib64/libc.so.6(gsignal+0x37)[0x7f7be92c9387]
/lib64/libc.so.6(abort+0x148)[0x7f7be92caa78]
/lib64/libc.so.6(+0x2f1a6)[0x7f7be92c21a6]
/lib64/libc.so.6(+0x2f252)[0x7f7be92c2252]
build-all/bin/opt(_ZN4llvm12IRSimilarity21IRSimilarityCandidate27createCanonicalRelationFromERS1_RNS_8DenseMapIjNS_8DenseSetIjNS_12DenseMapInfoIjvEEEES6_NS_6detail12DenseMapPairIjS7_EEEESC_+0x11e6)[0x1b835d6]
build-all/bin/opt(_ZN4llvm12IRSimilarity22IRSimilarityIdentifier14findCandidatesERSt6vectorIPNS0_17IRInstructionDataESaIS4_EERS2_IjSaIjEE+0xa51)[0x1b84631]
build-all/bin/opt(_ZN4llvm12IRSimilarity22IRSimilarityIdentifier14findSimilarityERNS_6ModuleE+0xec)[0x1b854ac]
build-all/bin/opt(_ZN4llvm20IRSimilarityAnalysis3runERNS_6ModuleERNS_15AnalysisManagerIS1_JEEE+0x181)[0x1b85a81]
build-all/bin/opt[0x2fe4320]
build-all/bin/opt(_ZN4llvm15AnalysisManagerINS_6ModuleEJEE13getResultImplEPNS_11AnalysisKeyERS1_+0x20e)[0x245fb1e]
build-all/bin/opt[0x2ff1258]
build-all/bin/opt[0x2ff109d]
build-all/bin/opt(_ZN4llvm11PassManagerINS_6ModuleENS_15AnalysisManagerIS1_JEEEJEE3runERS1_RS3_+0x208)[0x245d3d8]
build-all/bin/opt(_ZN4llvm15runPassPipelineENS_9StringRefERNS_6ModuleEPNS_13TargetMachineEPNS_21TargetLibraryInfoImplEPNS_14ToolOutputFileES8_S8_S0_NS_8ArrayRefIS0_EENS9_INS_10PassPluginEEENS_8opt_tool10OutputKindENSD_12VerifierKindEbbbbb+0x3f9f)[0x78657f]
build-all/bin/opt(main+0x3fad)[0x7972cd]
/lib64/libc.so.6(__libc_start_main+0xf5)[0x7f7be92b5555]
build-all/bin/opt[0x780ec0]

@AndrewLitteken: I wrote an issue about this new crash here:
https://github.com/llvm/llvm-project/issues/55131

uabelho added inline comments.Mar 14 2023, 10:43 PM
llvm/lib/Analysis/IRSimilarityIdentifier.cpp
1049

Hi @AndrewLitteken ,

The following command crashes on this cast:

opt -passes="function(loop-mssa(loop-rotate,licm<allowspeculation>,simple-loop-unswitch<nontrivial;trivial>)),require<ir-similarity>" bbi-80271.ll -o /dev/null

When it crashes SourceV is this:

(gdb) p SourceV->dump()
i16 1

The input is reduced with llvm-reduce and I've tried to shorten the command with utils/reduce_pipeline.py but it's still rather large and ugly.

AndrewLitteken added inline comments.Mar 15 2023, 9:39 AM
llvm/lib/Analysis/IRSimilarityIdentifier.cpp
1049

Can you check if this patch: https://reviews.llvm.org/D139337 fixes the issue? This was fixed in a future refactoring for compilation speed and seems to work on my build.

AndrewLitteken added inline comments.Mar 15 2023, 2:33 PM
llvm/lib/Analysis/IRSimilarityIdentifier.cpp
1049

Sorry, this is not correct, it should be this patch: https://reviews.llvm.org/D139336

uabelho added inline comments.Mar 15 2023, 10:35 PM
llvm/lib/Analysis/IRSimilarityIdentifier.cpp
1049

Yes, with https://reviews.llvm.org/D139336 the crash I see goes away.