+/// getSetCondCode - Encode a setcc opcode into a three bit mask. These bits
+/// are carefully arranged to allow folding of expressions such as:
+///
+/// (A < B) | (A > B) --> (A != B)
+///
+/// Bit value '4' represents that the comparison is true if A > B, bit value '2'
+/// represents that the comparison is true if A == B, and bit value '1' is true
+/// if A < B.
+///
+static unsigned getSetCondCode(const SetCondInst *SCI) {
+ switch (SCI->getOpcode()) {
+ // False -> 0
+ case Instruction::SetGT: return 1;
+ case Instruction::SetEQ: return 2;
+ case Instruction::SetGE: return 3;
+ case Instruction::SetLT: return 4;
+ case Instruction::SetNE: return 5;
+ case Instruction::SetLE: return 6;
+ // True -> 7
+ default:
+ assert(0 && "Invalid SetCC opcode!");
+ return 0;
+ }
+}
+
+/// getSetCCValue - This is the complement of getSetCondCode, which turns an
+/// opcode and two operands into either a constant true or false, or a brand new
+/// SetCC instruction.
+static Value *getSetCCValue(unsigned Opcode, Value *LHS, Value *RHS) {
+ switch (Opcode) {
+ case 0: return ConstantBool::False;
+ case 1: return new SetCondInst(Instruction::SetGT, LHS, RHS);
+ case 2: return new SetCondInst(Instruction::SetEQ, LHS, RHS);
+ case 3: return new SetCondInst(Instruction::SetGE, LHS, RHS);
+ case 4: return new SetCondInst(Instruction::SetLT, LHS, RHS);
+ case 5: return new SetCondInst(Instruction::SetNE, LHS, RHS);
+ case 6: return new SetCondInst(Instruction::SetLE, LHS, RHS);
+ case 7: return ConstantBool::True;
+ default: assert(0 && "Illegal SetCCCode!"); return 0;
+ }
+}
+
+// FoldSetCCLogical - Implements (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B)
+struct FoldSetCCLogical {
+ InstCombiner &IC;
+ Value *LHS, *RHS;
+ FoldSetCCLogical(InstCombiner &ic, SetCondInst *SCI)
+ : IC(ic), LHS(SCI->getOperand(0)), RHS(SCI->getOperand(1)) {}
+ bool shouldApply(Value *V) const {
+ if (SetCondInst *SCI = dyn_cast<SetCondInst>(V))
+ return (SCI->getOperand(0) == LHS && SCI->getOperand(1) == RHS ||
+ SCI->getOperand(0) == RHS && SCI->getOperand(1) == LHS);
+ return false;
+ }
+ Instruction *apply(BinaryOperator &Log) const {
+ SetCondInst *SCI = cast<SetCondInst>(Log.getOperand(0));
+ if (SCI->getOperand(0) != LHS) {
+ assert(SCI->getOperand(1) == LHS);
+ SCI->swapOperands(); // Swap the LHS and RHS of the SetCC
+ }
+
+ unsigned LHSCode = getSetCondCode(SCI);
+ unsigned RHSCode = getSetCondCode(cast<SetCondInst>(Log.getOperand(1)));
+ unsigned Code;
+ switch (Log.getOpcode()) {
+ case Instruction::And: Code = LHSCode & RHSCode; break;
+ case Instruction::Or: Code = LHSCode | RHSCode; break;
+ case Instruction::Xor: Code = LHSCode ^ RHSCode; break;
+ default: assert(0 && "Illegal logical opcode!"); return 0;
+ }
+
+ Value *RV = getSetCCValue(Code, LHS, RHS);
+ if (Instruction *I = dyn_cast<Instruction>(RV))
+ return I;
+ // Otherwise, it's a constant boolean value...
+ return IC.ReplaceInstUsesWith(Log, RV);
+ }
+};
+
+
+// OptAndOp - This handles expressions of the form ((val OP C1) & C2). Where
+// the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'. Op is
+// guaranteed to be either a shift instruction or a binary operator.
+Instruction *InstCombiner::OptAndOp(Instruction *Op,
+ ConstantIntegral *OpRHS,
+ ConstantIntegral *AndRHS,
+ BinaryOperator &TheAnd) {
+ Value *X = Op->getOperand(0);
+ Constant *Together = 0;
+ if (!isa<ShiftInst>(Op))
+ Together = ConstantExpr::get(Instruction::And, AndRHS, OpRHS);
+
+ switch (Op->getOpcode()) {
+ case Instruction::Xor:
+ if (Together->isNullValue()) {
+ // (X ^ C1) & C2 --> (X & C2) iff (C1&C2) == 0
+ return BinaryOperator::create(Instruction::And, X, AndRHS);
+ } else if (Op->hasOneUse()) {
+ // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
+ std::string OpName = Op->getName(); Op->setName("");
+ Instruction *And = BinaryOperator::create(Instruction::And,
+ X, AndRHS, OpName);
+ InsertNewInstBefore(And, TheAnd);
+ return BinaryOperator::create(Instruction::Xor, And, Together);
+ }
+ break;
+ case Instruction::Or:
+ // (X | C1) & C2 --> X & C2 iff C1 & C1 == 0
+ if (Together->isNullValue())
+ return BinaryOperator::create(Instruction::And, X, AndRHS);
+ else {
+ if (Together == AndRHS) // (X | C) & C --> C
+ return ReplaceInstUsesWith(TheAnd, AndRHS);
+
+ if (Op->hasOneUse() && Together != OpRHS) {
+ // (X | C1) & C2 --> (X | (C1&C2)) & C2
+ std::string Op0Name = Op->getName(); Op->setName("");
+ Instruction *Or = BinaryOperator::create(Instruction::Or, X,
+ Together, Op0Name);
+ InsertNewInstBefore(Or, TheAnd);
+ return BinaryOperator::create(Instruction::And, Or, AndRHS);
+ }
+ }
+ break;
+ case Instruction::Add:
+ if (Op->hasOneUse()) {
+ // Adding a one to a single bit bit-field should be turned into an XOR
+ // of the bit. First thing to check is to see if this AND is with a
+ // single bit constant.
+ unsigned long long AndRHSV = cast<ConstantInt>(AndRHS)->getRawValue();
+
+ // Clear bits that are not part of the constant.
+ AndRHSV &= (1ULL << AndRHS->getType()->getPrimitiveSize()*8)-1;
+
+ // If there is only one bit set...
+ if ((AndRHSV & (AndRHSV-1)) == 0) {
+ // Ok, at this point, we know that we are masking the result of the
+ // ADD down to exactly one bit. If the constant we are adding has
+ // no bits set below this bit, then we can eliminate the ADD.
+ unsigned long long AddRHS = cast<ConstantInt>(OpRHS)->getRawValue();
+
+ // Check to see if any bits below the one bit set in AndRHSV are set.
+ if ((AddRHS & (AndRHSV-1)) == 0) {
+ // If not, the only thing that can effect the output of the AND is
+ // the bit specified by AndRHSV. If that bit is set, the effect of
+ // the XOR is to toggle the bit. If it is clear, then the ADD has
+ // no effect.
+ if ((AddRHS & AndRHSV) == 0) { // Bit is not set, noop
+ TheAnd.setOperand(0, X);
+ return &TheAnd;
+ } else {
+ std::string Name = Op->getName(); Op->setName("");
+ // Pull the XOR out of the AND.
+ Instruction *NewAnd =
+ BinaryOperator::create(Instruction::And, X, AndRHS, Name);
+ InsertNewInstBefore(NewAnd, TheAnd);
+ return BinaryOperator::create(Instruction::Xor, NewAnd, AndRHS);
+ }
+ }
+ }
+ }
+ break;
+
+ case Instruction::Shl: {
+ // We know that the AND will not produce any of the bits shifted in, so if
+ // the anded constant includes them, clear them now!
+ //
+ Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
+ Constant *CI = ConstantExpr::get(Instruction::And, AndRHS,
+ ConstantExpr::get(Instruction::Shl, AllOne, OpRHS));
+ if (CI != AndRHS) {
+ TheAnd.setOperand(1, CI);
+ return &TheAnd;
+ }
+ break;
+ }
+ case Instruction::Shr:
+ // We know that the AND will not produce any of the bits shifted in, so if
+ // the anded constant includes them, clear them now! This only applies to
+ // unsigned shifts, because a signed shr may bring in set bits!
+ //
+ if (AndRHS->getType()->isUnsigned()) {
+ Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
+ Constant *CI = ConstantExpr::get(Instruction::And, AndRHS,
+ ConstantExpr::get(Instruction::Shr, AllOne, OpRHS));
+ if (CI != AndRHS) {
+ TheAnd.setOperand(1, CI);
+ return &TheAnd;
+ }
+ }
+ break;
+ }
+ return 0;
+}
+