From 6f1d7994155c535455b7543e2af6dce5b65de37b Mon Sep 17 00:00:00 2001 From: Duncan Sands Date: Fri, 9 Mar 2012 13:45:18 +0000 Subject: [PATCH] Eliminate switch cases that can never match, for example removes all negative switch cases if the branch condition is known to be positive. Inspired by a recent improvement to GCC's VRP. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@152405 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Scalar/CorrelatedValuePropagation.cpp | 86 ++++++++++++++++++ .../Transforms/CorrelatedValuePropagation/basic.ll | 101 ++++++++++++++++++++- 2 files changed, 186 insertions(+), 1 deletion(-) diff --git a/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp b/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp index e275268fc4e..ffe499135eb 100644 --- a/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp +++ b/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp @@ -37,6 +37,7 @@ namespace { bool processPHI(PHINode *P); bool processMemAccess(Instruction *I); bool processCmp(CmpInst *C); + bool processSwitch(SwitchInst *SI); public: static char ID; @@ -173,6 +174,84 @@ bool CorrelatedValuePropagation::processCmp(CmpInst *C) { return true; } +/// processSwitch - Simplify a switch instruction by removing cases which can +/// never fire. If the uselessness of a case could be determined locally then +/// constant propagation would already have figured it out. Instead, walk the +/// predecessors and statically evaluate cases based on information available +/// on that edge. Cases that cannot fire no matter what the incoming edge can +/// safely be removed. If a case fires on every incoming edge then the entire +/// switch can be removed and replaced with a branch to the case destination. +bool CorrelatedValuePropagation::processSwitch(SwitchInst *SI) { + Value *Cond = SI->getCondition(); + BasicBlock *BB = SI->getParent(); + + // If the condition was defined in same block as the switch then LazyValueInfo + // currently won't say anything useful about it, though in theory it could. + if (isa(Cond) && cast(Cond)->getParent() == BB) + return false; + + // If the switch is unreachable then trying to improve it is a waste of time. + pred_iterator PB = pred_begin(BB), PE = pred_end(BB); + if (PB == PE) return false; + + // Analyse each switch case in turn. This is done in reverse order so that + // removing a case doesn't cause trouble for the iteration. + bool Changed = false; + for (SwitchInst::CaseIt CI = SI->caseEnd(), CE = SI->caseBegin(); CI-- != CE; + ) { + ConstantInt *Case = CI.getCaseValue(); + + // Check to see if the switch condition is equal to/not equal to the case + // value on every incoming edge, equal/not equal being the same each time. + LazyValueInfo::Tristate State = LazyValueInfo::Unknown; + for (pred_iterator PI = PB; PI != PE; ++PI) { + // Is the switch condition equal to the case value? + LazyValueInfo::Tristate Value = LVI->getPredicateOnEdge(CmpInst::ICMP_EQ, + Cond, Case, *PI, BB); + // Give up on this case if nothing is known. + if (Value == LazyValueInfo::Unknown) { + State = LazyValueInfo::Unknown; + break; + } + + // If this was the first edge to be visited, record that all other edges + // need to give the same result. + if (PI == PB) { + State = Value; + continue; + } + + // If this case is known to fire for some edges and known not to fire for + // others then there is nothing we can do - give up. + if (Value != State) { + State = LazyValueInfo::Unknown; + break; + } + } + + if (State == LazyValueInfo::False) { + // This case never fires - remove it. + CI.getCaseSuccessor()->removePredecessor(BB); + SI->removeCase(CI); // Does not invalidate the iterator. + Changed = true; + } else if (State == LazyValueInfo::True) { + // This case always fires. Arrange for the switch to be turned into an + // unconditional branch by replacing the switch condition with the case + // value. + SI->setCondition(Case); + Changed = true; + break; + } + } + + if (Changed) + // If the switch has been simplified to the point where it can be replaced + // by a branch then do so now. + ConstantFoldTerminator(BB); + + return Changed; +} + bool CorrelatedValuePropagation::runOnFunction(Function &F) { LVI = &getAnalysis(); @@ -200,6 +279,13 @@ bool CorrelatedValuePropagation::runOnFunction(Function &F) { } } + Instruction *Term = FI->getTerminator(); + switch (Term->getOpcode()) { + case Instruction::Switch: + BBChanged |= processSwitch(cast(Term)); + break; + } + FnChanged |= BBChanged; } diff --git a/test/Transforms/CorrelatedValuePropagation/basic.ll b/test/Transforms/CorrelatedValuePropagation/basic.ll index 270c048e2f9..475cd8d772e 100644 --- a/test/Transforms/CorrelatedValuePropagation/basic.ll +++ b/test/Transforms/CorrelatedValuePropagation/basic.ll @@ -79,4 +79,103 @@ Impossible: LessThanOrEqualToTwo: ret i32 0 -} \ No newline at end of file +} + +define i32 @switch1(i32 %s) { +; CHECK: @switch1 +entry: + %cmp = icmp slt i32 %s, 0 + br i1 %cmp, label %negative, label %out + +negative: + switch i32 %s, label %out [ +; CHECK: switch i32 %s, label %out + i32 0, label %out +; CHECK-NOT: i32 0 + i32 1, label %out +; CHECK-NOT: i32 1 + i32 -1, label %next +; CHECK: i32 -1, label %next + i32 -2, label %next +; CHECK: i32 -2, label %next + i32 2, label %out +; CHECK-NOT: i32 2 + i32 3, label %out +; CHECK-NOT: i32 3 + ] + +out: + %p = phi i32 [ 1, %entry ], [ -1, %negative ], [ -1, %negative ], [ -1, %negative ], [ -1, %negative ] + ret i32 %p + +next: + %q = phi i32 [ 0, %negative ], [ 0, %negative ] + ret i32 %q +} + +define i32 @switch2(i32 %s) { +; CHECK: @switch2 +entry: + %cmp = icmp sgt i32 %s, 0 + br i1 %cmp, label %positive, label %out + +positive: + switch i32 %s, label %out [ + i32 0, label %out + i32 -1, label %next + i32 -2, label %next + ] +; CHECK: br label %out + +out: + %p = phi i32 [ -1, %entry ], [ 1, %positive ], [ 1, %positive ] + ret i32 %p + +next: + %q = phi i32 [ 0, %positive ], [ 0, %positive ] + ret i32 %q +} + +define i32 @switch3(i32 %s) { +; CHECK: @switch3 +entry: + %cmp = icmp sgt i32 %s, 0 + br i1 %cmp, label %positive, label %out + +positive: + switch i32 %s, label %out [ + i32 -1, label %out + i32 -2, label %next + i32 -3, label %next + ] +; CHECK: br label %out + +out: + %p = phi i32 [ -1, %entry ], [ 1, %positive ], [ 1, %positive ] + ret i32 %p + +next: + %q = phi i32 [ 0, %positive ], [ 0, %positive ] + ret i32 %q +} + +define void @switch4(i32 %s) { +; CHECK: @switch4 +entry: + %cmp = icmp eq i32 %s, 0 + br i1 %cmp, label %zero, label %out + +zero: + switch i32 %s, label %out [ + i32 0, label %next + i32 1, label %out + i32 -1, label %out + ] +; CHECK: br label %next + +out: + ret void + +next: + ret void +} -- 2.11.0