Index: llvm/lib/Transforms/Scalar/LICM.cpp =================================================================== --- llvm/lib/Transforms/Scalar/LICM.cpp +++ llvm/lib/Transforms/Scalar/LICM.cpp @@ -117,6 +117,11 @@ cl::desc("Max num uses visited for identifying load " "invariance in loop using invariant start (default = 8)")); +static cl::opt DivergenceThreshold( + "licm-divergence-threshold", + cl::desc("Max number of divergent paths from loop header to target block"), + cl::init(50), cl::Hidden); + // Experimental option to allow imprecision in LICM in pathological cases, in // exchange for faster compile. This is to be removed if MemorySSA starts to // address the same issue. This flag applies only when LICM uses MemorySSA @@ -824,12 +829,32 @@ // block. static bool worthSinkOrHoistInst(Instruction &I, BasicBlock *DstBlock, OptimizationRemarkEmitter *ORE, - BlockFrequencyInfo *BFI) { + BlockFrequencyInfo *BFI, DominatorTree *DT, + const Loop *CurLoop) { // Check block frequency only when runtime profile is available // to avoid pathological cases. With static profile, lean towards // hosting because it helps canonicalize the loop for vectorizer. - if (!DstBlock->getParent()->hasProfileData()) + if (!DstBlock->getParent()->hasProfileData()) { + // If the control flow is divergent too much inside loop, it could be better + // to avoid to move instructions outside loop. For example, let's say there + // is a switch instruction with big number of cases inside loop and the + // instruction is located in one of the case block. In this case, it is not + // easy to say the instruction is executed. Let's check the number of + // divergent paths from loop header to block which has the instruction. + auto *DN = DT->getNode(I.getParent()); + unsigned NumDivergentPathToBB = 0; + while (CurLoop->getHeader() != DN->getBlock()) { + DN = DN->getIDom(); + NumDivergentPathToBB += DN->getNumChildren(); + } + + // If the number of divergent paths is bigger than threshold, do not move + // the instruction. + if (NumDivergentPathToBB > DivergenceThreshold) + return false; + return true; + } if (!HoistSinkColdnessThreshold || !BFI) return true; @@ -909,7 +934,8 @@ if (CurLoop->hasLoopInvariantOperands(&I) && canSinkOrHoistInst(I, AA, DT, CurLoop, /*CurAST*/ nullptr, MSSAU, true, &Flags, ORE) && - worthSinkOrHoistInst(I, CurLoop->getLoopPreheader(), ORE, BFI) && + worthSinkOrHoistInst(I, CurLoop->getLoopPreheader(), ORE, BFI, DT, + CurLoop) && isSafeToExecuteUnconditionally( I, DT, TLI, CurLoop, SafetyInfo, ORE, CurLoop->getLoopPreheader()->getTerminator())) { @@ -1752,7 +1778,7 @@ PHINode *PN = cast(User); assert(ExitBlockSet.count(PN->getParent()) && "The LCSSA PHI is not in an exit block!"); - if (!worthSinkOrHoistInst(I, PN->getParent(), ORE, BFI)) { + if (!worthSinkOrHoistInst(I, PN->getParent(), ORE, BFI, DT, CurLoop)) { return Changed; } Index: llvm/test/Transforms/LICM/divergent-path-in-loop.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/LICM/divergent-path-in-loop.ll @@ -0,0 +1,795 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -S -licm < %s | FileCheck %s + +; Below loop invariant gep should not be hoisted because the path is divergent +; too much from loop header to the BB which has the gep. +; %56 = getelementptr inbounds %struct.info, %struct.info* %0, i64 0, i32 2 + +%struct.info = type { i8*, i8*, i8* } + +define void @test(%struct.info* %0, i1 %cond, i32 %input32, i8 %input8, i8* %input8ptr) { +; CHECK-LABEL: @test( +; CHECK-NEXT: br label [[DOTCRITEDGE56:%.*]] +; CHECK: .critedge56.loopexit: +; CHECK-NEXT: br label [[DOTCRITEDGE56_BACKEDGE:%.*]] +; CHECK: .critedge56.loopexit6: +; CHECK-NEXT: br label [[DOTCRITEDGE56_BACKEDGE]] +; CHECK: .critedge56: +; CHECK-NEXT: br label [[TMP2:%.*]] +; CHECK: 2: +; CHECK-NEXT: br label [[TMP3:%.*]] +; CHECK: .loopexit: +; CHECK-NEXT: br label [[TMP3]] +; CHECK: 3: +; CHECK-NEXT: br i1 [[COND:%.*]], label [[DOTCRITEDGE239_LOOPEXIT5:%.*]], label [[DOTCRITEDGE1_PREHEADER:%.*]] +; CHECK: .critedge1.preheader: +; CHECK-NEXT: br label [[DOTCRITEDGE1:%.*]] +; CHECK: .critedge1: +; CHECK-NEXT: switch i32 [[INPUT32:%.*]], label [[TMP58:%.*]] [ +; CHECK-NEXT: i32 2, label [[TMP4:%.*]] +; CHECK-NEXT: i32 3, label [[TMP5:%.*]] +; CHECK-NEXT: i32 7, label [[TMP6:%.*]] +; CHECK-NEXT: i32 90, label [[DOTCRITEDGE167_LOOPEXIT:%.*]] +; CHECK-NEXT: i32 133, label [[DOTCRITEDGE13:%.*]] +; CHECK-NEXT: i32 5, label [[TMP7:%.*]] +; CHECK-NEXT: i32 4, label [[TMP8:%.*]] +; CHECK-NEXT: i32 6, label [[TMP9:%.*]] +; CHECK-NEXT: i32 17, label [[TMP10:%.*]] +; CHECK-NEXT: i32 18, label [[TMP11:%.*]] +; CHECK-NEXT: i32 16, label [[TMP12:%.*]] +; CHECK-NEXT: i32 73, label [[TMP13:%.*]] +; CHECK-NEXT: i32 72, label [[TMP13]] +; CHECK-NEXT: i32 95, label [[TMP14:%.*]] +; CHECK-NEXT: i32 32, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 31, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 34, label [[TMP17:%.*]] +; CHECK-NEXT: i32 38, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 37, label [[TMP17]] +; CHECK-NEXT: i32 35, label [[TMP17]] +; CHECK-NEXT: i32 39, label [[TMP17]] +; CHECK-NEXT: i32 36, label [[TMP17]] +; CHECK-NEXT: i32 33, label [[TMP17]] +; CHECK-NEXT: i32 13, label [[TMP18:%.*]] +; CHECK-NEXT: i32 9, label [[TMP18]] +; CHECK-NEXT: i32 12, label [[TMP19:%.*]] +; CHECK-NEXT: i32 8, label [[TMP19]] +; CHECK-NEXT: i32 15, label [[DOTCRITEDGE17:%.*]] +; CHECK-NEXT: i32 11, label [[DOTCRITEDGE17]] +; CHECK-NEXT: i32 14, label [[TMP20:%.*]] +; CHECK-NEXT: i32 10, label [[TMP20]] +; CHECK-NEXT: i32 20, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 19, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 26, label [[TMP21:%.*]] +; CHECK-NEXT: i32 22, label [[TMP21]] +; CHECK-NEXT: i32 25, label [[TMP22:%.*]] +; CHECK-NEXT: i32 21, label [[TMP22]] +; CHECK-NEXT: i32 28, label [[TMP23:%.*]] +; CHECK-NEXT: i32 24, label [[TMP24:%.*]] +; CHECK-NEXT: i32 27, label [[TMP25:%.*]] +; CHECK-NEXT: i32 23, label [[TMP25]] +; CHECK-NEXT: i32 29, label [[TMP31:%.*]] +; CHECK-NEXT: i32 58, label [[DOTCRITEDGE34:%.*]] +; CHECK-NEXT: i32 60, label [[DOTCRITEDGE34]] +; CHECK-NEXT: i32 59, label [[DOTCRITEDGE34]] +; CHECK-NEXT: i32 57, label [[DOTCRITEDGE34]] +; CHECK-NEXT: i32 56, label [[DOTCRITEDGE34]] +; CHECK-NEXT: i32 53, label [[TMP32:%.*]] +; CHECK-NEXT: i32 55, label [[TMP32]] +; CHECK-NEXT: i32 54, label [[TMP32]] +; CHECK-NEXT: i32 52, label [[TMP32]] +; CHECK-NEXT: i32 51, label [[TMP32]] +; CHECK-NEXT: i32 40, label [[TMP59:%.*]] +; CHECK-NEXT: i32 41, label [[TMP59]] +; CHECK-NEXT: i32 77, label [[DOTCRITEDGE167_LOOPEXIT]] +; CHECK-NEXT: i32 76, label [[DOTCRITEDGE167_LOOPEXIT]] +; CHECK-NEXT: i32 68, label [[TMP33:%.*]] +; CHECK-NEXT: i32 96, label [[TMP60:%.*]] +; CHECK-NEXT: i32 97, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 49, label [[DOTCRITEDGE56_LOOPEXIT:%.*]] +; CHECK-NEXT: i32 50, label [[DOTCRITEDGE56_LOOPEXIT]] +; CHECK-NEXT: i32 83, label [[TMP34:%.*]] +; CHECK-NEXT: i32 67, label [[DOTCRITEDGE56_LOOPEXIT]] +; CHECK-NEXT: i32 78, label [[DOTCRITEDGE56_LOOPEXIT]] +; CHECK-NEXT: i32 79, label [[DOTCRITEDGE56_LOOPEXIT]] +; CHECK-NEXT: i32 80, label [[DOTCRITEDGE56_LOOPEXIT]] +; CHECK-NEXT: i32 66, label [[DOTCRITEDGE56_LOOPEXIT]] +; CHECK-NEXT: i32 70, label [[DOTCRITEDGE56_LOOPEXIT]] +; CHECK-NEXT: i32 47, label [[DOTCRITEDGE167_LOOPEXIT]] +; CHECK-NEXT: i32 98, label [[TMP60]] +; CHECK-NEXT: i32 99, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 48, label [[DOTCRITEDGE167_LOOPEXIT]] +; CHECK-NEXT: i32 106, label [[TMP60]] +; CHECK-NEXT: i32 108, label [[TMP60]] +; CHECK-NEXT: i32 109, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 103, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 101, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 105, label [[DOTCRITEDGE167_LOOPEXIT]] +; CHECK-NEXT: i32 107, label [[TMP35:%.*]] +; CHECK-NEXT: i32 62, label [[DOTCRITEDGE167_LOOPEXIT]] +; CHECK-NEXT: i32 30, label [[DOTCRITEDGE167_LOOPEXIT]] +; CHECK-NEXT: i32 89, label [[DOTCRITEDGE167_LOOPEXIT]] +; CHECK-NEXT: i32 131, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 110, label [[TMP60]] +; CHECK-NEXT: i32 111, label [[TMP36:%.*]] +; CHECK-NEXT: i32 69, label [[DOTCRITEDGE56_LOOPEXIT]] +; CHECK-NEXT: i32 46, label [[TMP37:%.*]] +; CHECK-NEXT: i32 112, label [[TMP38:%.*]] +; CHECK-NEXT: i32 113, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 115, label [[TMP42:%.*]] +; CHECK-NEXT: i32 42, label [[TMP43:%.*]] +; CHECK-NEXT: i32 43, label [[TMP43]] +; CHECK-NEXT: i32 45, label [[TMP43]] +; CHECK-NEXT: i32 44, label [[TMP43]] +; CHECK-NEXT: i32 119, label [[TMP48:%.*]] +; CHECK-NEXT: i32 121, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 123, label [[DOTCRITEDGE148:%.*]] +; CHECK-NEXT: i32 0, label [[TMP50:%.*]] +; CHECK-NEXT: i32 1, label [[TMP60]] +; CHECK-NEXT: i32 65, label [[DOTCRITEDGE167_LOOPEXIT]] +; CHECK-NEXT: i32 64, label [[TMP51:%.*]] +; CHECK-NEXT: i32 63, label [[TMP51]] +; CHECK-NEXT: i32 117, label [[TMP52:%.*]] +; CHECK-NEXT: i32 116, label [[TMP52]] +; CHECK-NEXT: i32 61, label [[DOTCRITEDGE56_LOOPEXIT]] +; CHECK-NEXT: i32 88, label [[DOTCRITEDGE167_LOOPEXIT]] +; CHECK-NEXT: i32 85, label [[DOTCRITEDGE167_LOOPEXIT]] +; CHECK-NEXT: i32 125, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 82, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 86, label [[DOTCRITEDGE167_LOOPEXIT]] +; CHECK-NEXT: i32 126, label [[TMP60]] +; CHECK-NEXT: i32 127, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 87, label [[TMP53:%.*]] +; CHECK-NEXT: i32 129, label [[TMP54:%.*]] +; CHECK-NEXT: i32 91, label [[TMP57:%.*]] +; CHECK-NEXT: ] +; CHECK: 4: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE56_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE:%.*]] +; CHECK: .critedge1.backedge: +; CHECK-NEXT: br label [[DOTCRITEDGE1]] +; CHECK: 5: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE56_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 6: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE56_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 7: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8:%.*]], label [[DOTCRITEDGE56_BACKEDGE]] +; CHECK: .critedge56.backedge: +; CHECK-NEXT: br label [[DOTCRITEDGE56]] +; CHECK: 8: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE56_BACKEDGE]] +; CHECK: 9: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE56_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 10: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE160:%.*]] +; CHECK: 11: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE56_BACKEDGE]] +; CHECK: 12: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE160]] +; CHECK: 13: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE7:%.*]], label [[DOTCRITEDGE6_PREHEADER:%.*]] +; CHECK: .critedge6.preheader: +; CHECK-NEXT: br label [[DOTCRITEDGE6:%.*]] +; CHECK: .critedge6: +; CHECK-NEXT: br i1 false, label [[DOTCRITEDGE7_LOOPEXIT:%.*]], label [[DOTCRITEDGE6]] +; CHECK: .critedge7.loopexit: +; CHECK-NEXT: br label [[DOTCRITEDGE7]] +; CHECK: .critedge7: +; CHECK-NEXT: switch i32 [[INPUT32]], label [[DOTCRITEDGE239_LOOPEXIT:%.*]] [ +; CHECK-NEXT: i32 8, label [[DOTCRITEDGE13]] +; CHECK-NEXT: i32 18, label [[DOTLOOPEXIT2:%.*]] +; CHECK-NEXT: i32 6, label [[DOTCRITEDGE13]] +; CHECK-NEXT: ] +; CHECK: 14: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT7:%.*]], label [[DOTPREHEADER3:%.*]] +; CHECK: .preheader3: +; CHECK-NEXT: br label [[TMP15:%.*]] +; CHECK: 15: +; CHECK-NEXT: br i1 false, label [[DOTLOOPEXIT4:%.*]], label [[TMP15]] +; CHECK: .loopexit2: +; CHECK-NEXT: br label [[TMP16:%.*]] +; CHECK: .loopexit4: +; CHECK-NEXT: br label [[TMP16]] +; CHECK: 16: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE167:%.*]], label [[DOTCRITEDGE10_PREHEADER:%.*]] +; CHECK: .critedge10.preheader: +; CHECK-NEXT: br label [[DOTCRITEDGE10:%.*]] +; CHECK: .critedge10: +; CHECK-NEXT: br label [[DOTCRITEDGE10]] +; CHECK: 17: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE56_BACKEDGE]] +; CHECK: 18: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE56_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 19: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE56_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: .critedge17: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE56_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 20: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE56_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 21: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE30:%.*]] +; CHECK: 22: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE24:%.*]] +; CHECK: 23: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE160]] +; CHECK: 24: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE24]] +; CHECK: .critedge24: +; CHECK-NEXT: br label [[DOTCRITEDGE56_BACKEDGE]] +; CHECK: 25: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE30]] +; CHECK: .critedge30: +; CHECK-NEXT: switch i8 [[INPUT8:%.*]], label [[TMP30:%.*]] [ +; CHECK-NEXT: i8 10, label [[TMP26:%.*]] +; CHECK-NEXT: i8 11, label [[TMP27:%.*]] +; CHECK-NEXT: i8 12, label [[TMP28:%.*]] +; CHECK-NEXT: i8 15, label [[TMP29:%.*]] +; CHECK-NEXT: ] +; CHECK: 26: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE32:%.*]] +; CHECK: 27: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE32]] +; CHECK: 28: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE32]] +; CHECK: 29: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE32]] +; CHECK: 30: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE32]] +; CHECK: .critedge32: +; CHECK-NEXT: br label [[DOTCRITEDGE56_BACKEDGE]] +; CHECK: 31: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE56_BACKEDGE]] +; CHECK: .critedge34: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 32: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 33: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE167]], label [[DOTCRITEDGE56_LOOPEXIT6:%.*]] +; CHECK: 34: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239:%.*]], label [[DOTCRITEDGE_PREHEADER:%.*]] +; CHECK: .critedge.preheader: +; CHECK-NEXT: br label [[DOTCRITEDGE:%.*]] +; CHECK: .critedge: +; CHECK-NEXT: br label [[DOTCRITEDGE]] +; CHECK: 35: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE167_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 36: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT]], label [[DOTCRITEDGE59:%.*]] +; CHECK: .critedge59: +; CHECK-NEXT: switch i8 [[INPUT8]], label [[DOTCRITEDGE13]] [ +; CHECK-NEXT: i8 30, label [[DOTLOOPEXIT:%.*]] +; CHECK-NEXT: i8 62, label [[DOTLOOPEXIT]] +; CHECK-NEXT: ] +; CHECK: 37: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE61:%.*]], label [[DOTCRITEDGE167_LOOPEXIT]] +; CHECK: 38: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE167_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: .critedge61: +; CHECK-NEXT: switch i8 [[INPUT8]], label [[DOTCRITEDGE62:%.*]] [ +; CHECK-NEXT: i8 90, label [[TMP39:%.*]] +; CHECK-NEXT: i8 69, label [[TMP39]] +; CHECK-NEXT: i8 49, label [[TMP39]] +; CHECK-NEXT: i8 50, label [[TMP39]] +; CHECK-NEXT: i8 68, label [[TMP39]] +; CHECK-NEXT: i8 65, label [[TMP39]] +; CHECK-NEXT: i8 63, label [[TMP39]] +; CHECK-NEXT: i8 43, label [[TMP39]] +; CHECK-NEXT: ] +; CHECK: 39: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE167_LOOPEXIT]], label [[DOTPREHEADER:%.*]] +; CHECK: .preheader: +; CHECK-NEXT: br label [[TMP40:%.*]] +; CHECK: 40: +; CHECK-NEXT: switch i8 [[INPUT8]], label [[DOTCRITEDGE62_LOOPEXIT:%.*]] [ +; CHECK-NEXT: i8 49, label [[TMP41:%.*]] +; CHECK-NEXT: i8 50, label [[TMP41]] +; CHECK-NEXT: i8 65, label [[TMP41]] +; CHECK-NEXT: i8 43, label [[TMP41]] +; CHECK-NEXT: i8 63, label [[TMP41]] +; CHECK-NEXT: i8 68, label [[TMP41]] +; CHECK-NEXT: i8 69, label [[TMP41]] +; CHECK-NEXT: i8 90, label [[TMP41]] +; CHECK-NEXT: ] +; CHECK: 41: +; CHECK-NEXT: br label [[TMP40]] +; CHECK: .critedge62.loopexit: +; CHECK-NEXT: br label [[DOTCRITEDGE62]] +; CHECK: .critedge62: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE167_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 42: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT7]], label [[DOTCRITEDGE167]] +; CHECK: 43: +; CHECK-NEXT: switch i8 [[INPUT8]], label [[DOTCRITEDGE90:%.*]] [ +; CHECK-NEXT: i8 90, label [[TMP44:%.*]] +; CHECK-NEXT: i8 69, label [[TMP44]] +; CHECK-NEXT: i8 49, label [[TMP44]] +; CHECK-NEXT: i8 50, label [[TMP44]] +; CHECK-NEXT: i8 68, label [[TMP44]] +; CHECK-NEXT: i8 65, label [[TMP44]] +; CHECK-NEXT: i8 63, label [[TMP44]] +; CHECK-NEXT: i8 43, label [[TMP44]] +; CHECK-NEXT: ] +; CHECK: 44: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE167_LOOPEXIT]], label [[DOTPREHEADER1:%.*]] +; CHECK: .preheader1: +; CHECK-NEXT: br label [[TMP45:%.*]] +; CHECK: 45: +; CHECK-NEXT: switch i8 [[INPUT8]], label [[DOTCRITEDGE90_LOOPEXIT:%.*]] [ +; CHECK-NEXT: i8 49, label [[TMP46:%.*]] +; CHECK-NEXT: i8 50, label [[TMP46]] +; CHECK-NEXT: i8 65, label [[TMP46]] +; CHECK-NEXT: i8 43, label [[TMP46]] +; CHECK-NEXT: i8 63, label [[TMP46]] +; CHECK-NEXT: i8 68, label [[TMP46]] +; CHECK-NEXT: i8 69, label [[TMP46]] +; CHECK-NEXT: i8 90, label [[TMP46]] +; CHECK-NEXT: ] +; CHECK: 46: +; CHECK-NEXT: br label [[TMP45]] +; CHECK: .critedge90.loopexit: +; CHECK-NEXT: br label [[DOTCRITEDGE90]] +; CHECK: .critedge90: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE167_LOOPEXIT]], label [[TMP47:%.*]] +; CHECK: 47: +; CHECK-NEXT: switch i32 [[INPUT32]], label [[DOTCRITEDGE239_LOOPEXIT]] [ +; CHECK-NEXT: i32 116, label [[TMP49:%.*]] +; CHECK-NEXT: i32 6, label [[DOTCRITEDGE13]] +; CHECK-NEXT: ] +; CHECK: 48: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239]], label [[DOTCRITEDGE105_PREHEADER:%.*]] +; CHECK: .critedge105.preheader: +; CHECK-NEXT: br label [[DOTCRITEDGE105:%.*]] +; CHECK: .critedge105: +; CHECK-NEXT: br label [[DOTCRITEDGE105]] +; CHECK: 49: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE167_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: .critedge148: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE167_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 50: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT7]], label [[DOTCRITEDGE167]] +; CHECK: 51: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE167_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 52: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 53: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE56_LOOPEXIT6]], label [[DOTCRITEDGE167]] +; CHECK: 54: +; CHECK-NEXT: br i1 [[COND]], label [[TMP55:%.*]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 55: +; CHECK-NEXT: [[TMP56:%.*]] = getelementptr inbounds [[STRUCT_INFO:%.*]], %struct.info* [[TMP0:%.*]], i64 0, i32 2 +; CHECK-NEXT: store i8* [[INPUT8PTR:%.*]], i8** [[TMP56]], align 8 +; CHECK-NEXT: br label [[DOTCRITEDGE13]] +; CHECK: 57: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE56_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: 58: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT8]], label [[DOTCRITEDGE160]] +; CHECK: .critedge160: +; CHECK-NEXT: br label [[DOTCRITEDGE56_BACKEDGE]] +; CHECK: 59: +; CHECK-NEXT: br label [[DOTCRITEDGE56_BACKEDGE]] +; CHECK: .critedge167.loopexit: +; CHECK-NEXT: br label [[DOTCRITEDGE167]] +; CHECK: .critedge167: +; CHECK-NEXT: br label [[TMP2]] +; CHECK: 60: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: .critedge13: +; CHECK-NEXT: br i1 [[COND]], label [[DOTCRITEDGE239_LOOPEXIT]], label [[DOTCRITEDGE1_BACKEDGE]] +; CHECK: .critedge239.loopexit: +; CHECK-NEXT: br label [[DOTCRITEDGE239]] +; CHECK: .critedge239.loopexit5: +; CHECK-NEXT: br label [[DOTCRITEDGE239]] +; CHECK: .critedge239.loopexit7: +; CHECK-NEXT: br label [[DOTCRITEDGE239]] +; CHECK: .critedge239.loopexit8: +; CHECK-NEXT: br label [[DOTCRITEDGE239]] +; CHECK: .critedge239: +; CHECK-NEXT: ret void +; + br label %.critedge56 + +.critedge56: ; preds = %59, %.critedge160, %57, %53, %33, %31, %.critedge32, %.critedge24, %20, %.critedge17, %19, %18, %17, %11, %9, %8, %7, %6, %5, %4, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %1 + br label %2 + +2: ; preds = %.critedge167, %.critedge56 + br label %3 + +3: ; preds = %.critedge59, %.critedge59, %2 + br i1 %cond, label %.critedge239, label %.critedge1 + +.critedge1: ; preds = %.critedge13, %60, %57, %54, %52, %51, %.critedge148, %49, %.critedge62, %38, %35, %32, %.critedge34, %20, %.critedge17, %19, %18, %9, %6, %5, %4, %3 + switch i32 %input32, label %58 [ + i32 2, label %4 + i32 3, label %5 + i32 7, label %6 + i32 90, label %.critedge167 + i32 133, label %.critedge13 + i32 5, label %7 + i32 4, label %8 + i32 6, label %9 + i32 17, label %10 + i32 18, label %11 + i32 16, label %12 + i32 73, label %13 + i32 72, label %13 + i32 95, label %14 + i32 32, label %.critedge13 + i32 31, label %.critedge13 + i32 34, label %17 + i32 38, label %.critedge13 + i32 37, label %17 + i32 35, label %17 + i32 39, label %17 + i32 36, label %17 + i32 33, label %17 + i32 13, label %18 + i32 9, label %18 + i32 12, label %19 + i32 8, label %19 + i32 15, label %.critedge17 + i32 11, label %.critedge17 + i32 14, label %20 + i32 10, label %20 + i32 20, label %.critedge13 + i32 19, label %.critedge13 + i32 26, label %21 + i32 22, label %21 + i32 25, label %22 + i32 21, label %22 + i32 28, label %23 + i32 24, label %24 + i32 27, label %25 + i32 23, label %25 + i32 29, label %31 + i32 58, label %.critedge34 + i32 60, label %.critedge34 + i32 59, label %.critedge34 + i32 57, label %.critedge34 + i32 56, label %.critedge34 + i32 53, label %32 + i32 55, label %32 + i32 54, label %32 + i32 52, label %32 + i32 51, label %32 + i32 40, label %59 + i32 41, label %59 + i32 77, label %.critedge167 + i32 76, label %.critedge167 + i32 68, label %33 + i32 96, label %60 + i32 97, label %.critedge13 + i32 49, label %.critedge56 + i32 50, label %.critedge56 + i32 83, label %34 + i32 67, label %.critedge56 + i32 78, label %.critedge56 + i32 79, label %.critedge56 + i32 80, label %.critedge56 + i32 66, label %.critedge56 + i32 70, label %.critedge56 + i32 47, label %.critedge167 + i32 98, label %60 + i32 99, label %.critedge13 + i32 48, label %.critedge167 + i32 106, label %60 + i32 108, label %60 + i32 109, label %.critedge13 + i32 103, label %.critedge13 + i32 101, label %.critedge13 + i32 105, label %.critedge167 + i32 107, label %35 + i32 62, label %.critedge167 + i32 30, label %.critedge167 + i32 89, label %.critedge167 + i32 131, label %.critedge13 + i32 110, label %60 + i32 111, label %36 + i32 69, label %.critedge56 + i32 46, label %37 + i32 112, label %38 + i32 113, label %.critedge13 + i32 115, label %42 + i32 42, label %43 + i32 43, label %43 + i32 45, label %43 + i32 44, label %43 + i32 119, label %48 + i32 121, label %.critedge13 + i32 123, label %.critedge148 + i32 0, label %50 + i32 1, label %60 + i32 65, label %.critedge167 + i32 64, label %51 + i32 63, label %51 + i32 117, label %52 + i32 116, label %52 + i32 61, label %.critedge56 + i32 88, label %.critedge167 + i32 85, label %.critedge167 + i32 125, label %.critedge13 + i32 82, label %.critedge13 + i32 86, label %.critedge167 + i32 126, label %60 + i32 127, label %.critedge13 + i32 87, label %53 + i32 129, label %54 + i32 91, label %57 + ] + +4: ; preds = %.critedge1 + br i1 %cond, label %.critedge56, label %.critedge1 + +5: ; preds = %.critedge1 + br i1 %cond, label %.critedge56, label %.critedge1 + +6: ; preds = %.critedge1 + br i1 %cond, label %.critedge56, label %.critedge1 + +7: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge56 + +8: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge56 + +9: ; preds = %.critedge1 + br i1 %cond, label %.critedge56, label %.critedge1 + +10: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge160 + +11: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge56 + +12: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge160 + +13: ; preds = %.critedge1, %.critedge1 + br i1 %cond, label %.critedge7, label %.critedge6 + +.critedge6: ; preds = %.critedge6, %13 + br i1 false, label %.critedge7, label %.critedge6 + +.critedge7: ; preds = %.critedge6, %13 + switch i32 %input32, label %.critedge239 [ + i32 8, label %.critedge13 + i32 18, label %16 + i32 6, label %.critedge13 + ] + +14: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %15 + +15: ; preds = %15, %14 + br i1 false, label %16, label %15 + +16: ; preds = %15, %.critedge7 + br i1 %cond, label %.critedge167, label %.critedge10 + +.critedge10: ; preds = %.critedge10, %16 + br label %.critedge10 + +17: ; preds = %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge56 + +18: ; preds = %.critedge1, %.critedge1 + br i1 %cond, label %.critedge56, label %.critedge1 + +19: ; preds = %.critedge1, %.critedge1 + br i1 %cond, label %.critedge56, label %.critedge1 + +.critedge17: ; preds = %.critedge1, %.critedge1 + br i1 %cond, label %.critedge56, label %.critedge1 + +20: ; preds = %.critedge1, %.critedge1 + br i1 %cond, label %.critedge56, label %.critedge1 + +21: ; preds = %.critedge1, %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge30 + +22: ; preds = %.critedge1, %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge24 + +23: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge160 + +24: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge24 + +.critedge24: ; preds = %24, %22 + br label %.critedge56 + +25: ; preds = %.critedge1, %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge30 + +.critedge30: ; preds = %25, %21 + switch i8 %input8, label %30 [ + i8 10, label %26 + i8 11, label %27 + i8 12, label %28 + i8 15, label %29 + ] + +26: ; preds = %.critedge30 + br i1 %cond, label %.critedge239, label %.critedge32 + +27: ; preds = %.critedge30 + br i1 %cond, label %.critedge239, label %.critedge32 + +28: ; preds = %.critedge30 + br i1 %cond, label %.critedge239, label %.critedge32 + +29: ; preds = %.critedge30 + br i1 %cond, label %.critedge239, label %.critedge32 + +30: ; preds = %.critedge30 + br i1 %cond, label %.critedge239, label %.critedge32 + +.critedge32: ; preds = %30, %29, %28, %27, %26 + br label %.critedge56 + +31: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge56 + +.critedge34: ; preds = %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge1 + +32: ; preds = %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge1 + +33: ; preds = %.critedge1 + br i1 %cond, label %.critedge167, label %.critedge56 + +34: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge + +.critedge: ; preds = %.critedge, %34 + br label %.critedge + +35: ; preds = %.critedge1 + br i1 %cond, label %.critedge167, label %.critedge1 + +36: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge59 + +.critedge59: ; preds = %36 + switch i8 %input8, label %.critedge13 [ + i8 30, label %3 + i8 62, label %3 + ] + +37: ; preds = %.critedge1 + br i1 %cond, label %.critedge61, label %.critedge167 + +38: ; preds = %.critedge1 + br i1 %cond, label %.critedge167, label %.critedge1 + +.critedge61: ; preds = %37 + switch i8 %input8, label %.critedge62 [ + i8 90, label %39 + i8 69, label %39 + i8 49, label %39 + i8 50, label %39 + i8 68, label %39 + i8 65, label %39 + i8 63, label %39 + i8 43, label %39 + ] + +39: ; preds = %.critedge61, %.critedge61, %.critedge61, %.critedge61, %.critedge61, %.critedge61, %.critedge61, %.critedge61 + br i1 %cond, label %.critedge167, label %40 + +40: ; preds = %41, %39 + switch i8 %input8, label %.critedge62 [ + i8 49, label %41 + i8 50, label %41 + i8 65, label %41 + i8 43, label %41 + i8 63, label %41 + i8 68, label %41 + i8 69, label %41 + i8 90, label %41 + ] + +41: ; preds = %40, %40, %40, %40, %40, %40, %40, %40 + br label %40 + +.critedge62: ; preds = %40, %.critedge61 + br i1 %cond, label %.critedge167, label %.critedge1 + +42: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge167 + +43: ; preds = %.critedge1, %.critedge1, %.critedge1, %.critedge1 + switch i8 %input8, label %.critedge90 [ + i8 90, label %44 + i8 69, label %44 + i8 49, label %44 + i8 50, label %44 + i8 68, label %44 + i8 65, label %44 + i8 63, label %44 + i8 43, label %44 + ] + +44: ; preds = %43, %43, %43, %43, %43, %43, %43, %43 + br i1 %cond, label %.critedge167, label %45 + +45: ; preds = %46, %44 + switch i8 %input8, label %.critedge90 [ + i8 49, label %46 + i8 50, label %46 + i8 65, label %46 + i8 43, label %46 + i8 63, label %46 + i8 68, label %46 + i8 69, label %46 + i8 90, label %46 + ] + +46: ; preds = %45, %45, %45, %45, %45, %45, %45, %45 + br label %45 + +.critedge90: ; preds = %45, %43 + br i1 %cond, label %.critedge167, label %47 + +47: ; preds = %.critedge90 + switch i32 %input32, label %.critedge239 [ + i32 116, label %49 + i32 6, label %.critedge13 + ] + +48: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge105 + +.critedge105: ; preds = %.critedge105, %48 + br label %.critedge105 + +49: ; preds = %47 + br i1 %cond, label %.critedge167, label %.critedge1 + +.critedge148: ; preds = %.critedge1 + br i1 %cond, label %.critedge167, label %.critedge1 + +50: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge167 + +51: ; preds = %.critedge1, %.critedge1 + br i1 %cond, label %.critedge167, label %.critedge1 + +52: ; preds = %.critedge1, %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge1 + +53: ; preds = %.critedge1 + br i1 %cond, label %.critedge56, label %.critedge167 + +54: ; preds = %.critedge1 + br i1 %cond, label %55, label %.critedge1 + +55: ; preds = %54 + %56 = getelementptr inbounds %struct.info, %struct.info* %0, i64 0, i32 2 + store i8* %input8ptr, i8** %56, align 8 + br label %.critedge13 + +57: ; preds = %.critedge1 + br i1 %cond, label %.critedge56, label %.critedge1 + +58: ; preds = %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge160 + +.critedge160: ; preds = %58, %23, %12, %10 + br label %.critedge56 + +59: ; preds = %.critedge1, %.critedge1 + br label %.critedge56 + +.critedge167: ; preds = %53, %51, %50, %.critedge148, %49, %.critedge90, %44, %42, %.critedge62, %39, %38, %37, %35, %33, %16, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1 + br label %2 + +60: ; preds = %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge1 + +.critedge13: ; preds = %55, %47, %.critedge59, %.critedge7, %.critedge7, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1, %.critedge1 + br i1 %cond, label %.critedge239, label %.critedge1 + +.critedge239: ; preds = %.critedge13, %60, %58, %52, %50, %48, %47, %42, %36, %34, %32, %.critedge34, %31, %30, %29, %28, %27, %26, %25, %24, %23, %22, %21, %17, %14, %.critedge7, %12, %11, %10, %8, %7, %3 + ret void +} +