diff options
| -rw-r--r-- | llvm/lib/Transforms/Utils/SimplifyCFG.cpp | 46 | ||||
| -rw-r--r-- | llvm/test/Transforms/SimplifyCFG/switch_create.ll | 40 |
2 files changed, 82 insertions, 4 deletions
diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp index 8f35f887c0b..4f0dc5a6b35 100644 --- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -448,18 +448,56 @@ private: // (x & ~2^z) == y --> x == y || x == y|2^z // This undoes a transformation done by instcombine to fuse 2 compares. if (ICI->getPredicate() == (isEQ ? ICmpInst::ICMP_EQ : ICmpInst::ICMP_NE)) { + + // It's a little bit hard to see why the following transformations are + // correct. Here is a CVC3 program to verify them for 64-bit values: + + /* + ONE : BITVECTOR(64) = BVZEROEXTEND(0bin1, 63); + x : BITVECTOR(64); + y : BITVECTOR(64); + z : BITVECTOR(64); + mask : BITVECTOR(64) = BVSHL(ONE, z); + QUERY( (y & ~mask = y) => + ((x & ~mask = y) <=> (x = y OR x = (y | mask))) + ); + */ + + // Please note that each pattern must be a dual implication (<--> or + // iff). One directional implication can create spurious matches. If the + // implication is only one-way, an unsatisfiable condition on the left + // side can imply a satisfiable condition on the right side. Dual + // implication ensures that satisfiable conditions are transformed to + // other satisfiable conditions and unsatisfiable conditions are + // transformed to other unsatisfiable conditions. + + // Here is a concrete example of a unsatisfiable condition on the left + // implying a satisfiable condition on the right: + // + // mask = (1 << z) + // (x & ~mask) == y --> (x == y || x == (y | mask)) + // + // Substituting y = 3, z = 0 yields: + // (x & -2) == 3 --> (x == 3 || x == 2) + + // Pattern match a special case: + /* + QUERY( (y & ~mask = y) => + ((x & ~mask = y) <=> (x = y OR x = (y | mask))) + ); + */ if (match(ICI->getOperand(0), m_And(m_Value(RHSVal), m_ConstantInt(RHSC)))) { - APInt Not = ~RHSC->getValue(); - if (Not.isPowerOf2() && C->getValue().isPowerOf2() && - Not != C->getValue()) { + APInt Mask = ~RHSC->getValue(); + if (Mask.isPowerOf2() && (C->getValue() & ~Mask) == C->getValue()) { // If we already have a value for the switch, it has to match! if (!setValueOnce(RHSVal)) return false; Vals.push_back(C); Vals.push_back( - ConstantInt::get(C->getContext(), C->getValue() | Not)); + ConstantInt::get(C->getContext(), + C->getValue() | Mask)); UsedICmps++; return true; } diff --git a/llvm/test/Transforms/SimplifyCFG/switch_create.ll b/llvm/test/Transforms/SimplifyCFG/switch_create.ll index 60802d8599b..75498faaa29 100644 --- a/llvm/test/Transforms/SimplifyCFG/switch_create.ll +++ b/llvm/test/Transforms/SimplifyCFG/switch_create.ll @@ -579,3 +579,43 @@ if.end29: ; preds = %entry ; CHECK: %or.cond = and i1 %tobool5, %tobool23 ; CHECK: %or.cond1 = and i1 %cmp17, %or.cond ; CHECK: br i1 %or.cond1, label %if.end29, label %if.then27 + +; Form a switch when and'ing a negated power of two +; CHECK-LABEL: define void @test19 +; CHECK: switch i32 %arg, label %else [ +; CHECK: i32 32, label %if +; CHECK: i32 13, label %if +; CHECK: i32 12, label %if +define void @test19(i32 %arg) { + %and = and i32 %arg, -2 + %cmp1 = icmp eq i32 %and, 12 + %cmp2 = icmp eq i32 %arg, 32 + %pred = or i1 %cmp1, %cmp2 + br i1 %pred, label %if, label %else + +if: + call void @foo1() + ret void + +else: + ret void +} + +; Since %cmp1 is always false, a switch is never formed +; CHECK-LABEL: define void @test20 +; CHECK-NOT: switch +; CHECK: ret void +define void @test20(i32 %arg) { + %and = and i32 %arg, -2 + %cmp1 = icmp eq i32 %and, 13 + %cmp2 = icmp eq i32 %arg, 32 + %pred = or i1 %cmp1, %cmp2 + br i1 %pred, label %if, label %else + +if: + call void @foo1() + ret void + +else: + ret void +}
\ No newline at end of file |
