Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -431,22 +431,82 @@ Value *RHSVal; ConstantInt *RHSC; - // Pattern match a special case - // (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))) + ); + 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() | Mask)); + UsedICmps++; + return true; + } + } + + // Pattern match a special case: + /* + QUERY( (y | mask = y) => + ((x | mask = y) <=> (x = y OR x = (y & ~mask))) + ); + */ + if (match(ICI->getOperand(0), + m_Or(m_Value(RHSVal), m_ConstantInt(RHSC)))) { + 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)); + C->getValue() & ~Mask)); UsedICmps++; return true; } Index: test/Transforms/SimplifyCFG/switch_create.ll =================================================================== --- test/Transforms/SimplifyCFG/switch_create.ll +++ test/Transforms/SimplifyCFG/switch_create.ll @@ -579,3 +579,82 @@ ; 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 +} + +; Form a switch when or'ing a power of two +; CHECK-LABEL: define void @test21 +; CHECK: i32 32, label %else +; CHECK: i32 13, label %else +; CHECK: i32 12, label %else +define void @test21(i32 %arg) { + %and = or i32 %arg, 1 + %cmp1 = icmp ne i32 %and, 13 + %cmp2 = icmp ne i32 %arg, 32 + %pred = and 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 @test22 +; CHECK-NOT: switch +; CHECK: ret void +define void @test22(i32 %arg) { + %and = or i32 %arg, 1 + %cmp1 = icmp ne i32 %and, 12 + %cmp2 = icmp ne i32 %arg, 32 + %pred = and 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