Index: llvm/include/llvm/Analysis/ComplexLogicCombine.h =================================================================== --- /dev/null +++ llvm/include/llvm/Analysis/ComplexLogicCombine.h @@ -0,0 +1,69 @@ +//===----------- ComplexLogicCombine.h --------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "LogicalExpr.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/IR/InstrTypes.h" +#include "llvm/IR/Instruction.h" + +namespace llvm { + +class LogicalOpsHelper; + +class LogicalOpNode { +private: + LogicalOpsHelper *Helper; + Value *Val; + LogicalExpr Expr; + // TODO: Add weight to measure cost for more than one use value + + void printValue(raw_ostream &OS, Value *Val) const; + void printAndChain(raw_ostream &OS, uint64_t LeafBits) const; + +public: + LogicalOpNode(LogicalOpsHelper *OpsHelper, Value *SrcVal, + const LogicalExpr &SrcExpr) + : Helper(OpsHelper), Val(SrcVal), Expr(SrcExpr) {} + ~LogicalOpNode() {} + + Value *getValue() const { return Val; } + const LogicalExpr &getExpr() const { return Expr; } + void print(raw_ostream &OS) const; +}; + +class LogicalOpsHelper { +public: + LogicalOpsHelper() {} + ~LogicalOpsHelper() { clear(); } + + Value *simplify(Value *Root); + +private: + friend class LogicalOpNode; + + SmallDenseMap LogicalOpNodes; + SmallPtrSet LeafSet; + SmallVector LeafValues; + + void clear(); + + LogicalOpNode *visitLeafNode(Value *Val, unsigned Depth); + LogicalOpNode *visitBinOp(BinaryOperator *BO, unsigned Depth); + LogicalOpNode *getLogicalOpNode(Value *Val, unsigned Depth = 0); + Value *logicalOpToValue(LogicalOpNode *Node); +}; + +inline raw_ostream &operator<<(raw_ostream &OS, const LogicalOpNode &I) { + I.print(OS); + return OS; +} + +} // namespace llvm Index: llvm/include/llvm/Analysis/LogicalExpr.h =================================================================== --- /dev/null +++ llvm/include/llvm/Analysis/LogicalExpr.h @@ -0,0 +1,146 @@ +//===------------------- LogicalExpr.h --------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// \file +/// This file defines LogicalExpr, a class that represent a logical value by +/// bitmasks. +/// For a logical expression represented by bitmasks, the "and" logic +/// operator represented by "&" is translated to "*" and is then evaluated as +/// the "or" of the bitmasks. For example, pattern "a & b" is represented by the +/// logical expression "01 * 10", and the expression is reduced to "11". So the +/// operation "&" between two logical expressions (not "xor", only "and" chain) +/// is actually bitwise "or" of the masks. There is one exception: if one of the +/// operands is constant 0, the entire mask represents 0. We do not "or" the +/// masks in that case. +/// The evaluation of a pattern for bitwise "xor" is represented by a "+" math +/// operator. But it also has one exception to normal math rules: if two masks +/// are identical, we remove them. For example with "a ^ a", the logical +/// expression is "1 + 1". We eliminate them from the logical expression. +/// We use commutative, associative, and distributive laws of arithmetic +/// multiplication and addition to reduce the expression. A example for the +/// LogicalExpr caculation: +/// ((a & b) | (a ^ c)) ^ (!(b & c) & a) +/// Mask for the leafs are: a --> 001, b --> 010, c -->100 +/// First step is expand the pattern to: +/// (((a & b) & (a ^ c)) ^ (a & b) ^ (a ^ c)) ^ (((b & c) ^ -1) & a) +/// Use logical expression to represent the pattern: +/// 001 * 010 * (001 + 100) + 001 * 010 + 001 + 100 + (010 * 100 + -1C) * +/// 001 +/// Expression after distributive laws: +/// 001 * 010 * 001 + 001 * 010 * 100 + 001 * 010 + 001 + 100 + 010 * 100 * +/// 001 + -1C * 001 +/// Caculate multiplication: +/// 011 + 111 + 011 + 001 + 100 + 111 + 001 +/// Caculate addiction: +/// 100 +/// Restore to value +/// c +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/DenseSet.h" + +namespace llvm { +typedef SmallDenseSet ExprAddChain; + +class LogicalExpr { +private: + ExprAddChain AddChain; + // TODO: can we use APInt define the mask to enlarge the max leaf number? + uint64_t LeafMask; + + inline void updateLeafMask() { + LeafMask = 0; + for (auto Mask : AddChain) + LeafMask |= Mask; + } + +public: + static const uint64_t ExprAllOne = 0x8000000000000000; + + LogicalExpr() {} + LogicalExpr(uint64_t Mask) { + AddChain.insert(Mask); + LeafMask = Mask; + } + LogicalExpr(const ExprAddChain &SrcAddChain) : AddChain(SrcAddChain) { + updateLeafMask(); + } + + unsigned size() const { return AddChain.size(); } + ExprAddChain::iterator begin() { return AddChain.begin(); } + ExprAddChain::iterator end() { return AddChain.end(); } + ExprAddChain::const_iterator begin() const { return AddChain.begin(); } + ExprAddChain::const_iterator end() const { return AddChain.end(); } + + LogicalExpr &operator*=(const LogicalExpr &RHS) { + ExprAddChain NewChain; + for (auto LHSMask : AddChain) { + // a & 0 -> 0 + if (LHSMask == 0) + continue; + for (auto RHSMask : RHS.AddChain) { + // 0 & a -> 0 + if (RHSMask == 0) + continue; + // The "*" operation is actually "|" LHS and RHS 's masks. + // For example: ab * bd = abd + // The expression ab * bd convert to mask will be 0b0011 * 0b1010. + // The result abd convert to mask will become 0b1011. + uint64_t NewMask = LHSMask | RHSMask; + // a & 1 -> a + if (NewMask != ExprAllOne && ((NewMask & ExprAllOne) != 0)) + NewMask &= ~ExprAllOne; + // a ^ a -> 0 + if (!NewChain.insert(NewMask).second) + NewChain.erase(NewMask); + } + } + + AddChain = NewChain; + updateLeafMask(); + return *this; + } + + LogicalExpr &operator+=(const LogicalExpr &RHS) { + for (auto RHSMask : RHS.AddChain) { + // a ^ a -> 0 + if (!AddChain.insert(RHSMask).second) + AddChain.erase(RHSMask); + } + updateLeafMask(); + return *this; + } +}; + +inline LogicalExpr operator*(LogicalExpr a, const LogicalExpr &b) { + a *= b; + return a; +} + +inline LogicalExpr operator+(LogicalExpr a, const LogicalExpr &b) { + a += b; + return a; +} + +inline LogicalExpr operator&(const LogicalExpr &a, const LogicalExpr &b) { + return a * b; +} + +inline LogicalExpr operator^(const LogicalExpr &a, const LogicalExpr &b) { + return a + b; +} + +inline LogicalExpr operator|(const LogicalExpr &a, const LogicalExpr &b) { + return a * b + a + b; +} + +inline LogicalExpr operator~(const LogicalExpr &a) { + LogicalExpr AllOneExpr(LogicalExpr::ExprAllOne); + return a + AllOneExpr; +} + +} // namespace llvm Index: llvm/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/lib/Analysis/CMakeLists.txt +++ llvm/lib/Analysis/CMakeLists.txt @@ -46,6 +46,7 @@ CmpInstAnalysis.cpp CostModel.cpp CodeMetrics.cpp + ComplexLogicCombine.cpp ConstantFolding.cpp CycleAnalysis.cpp DDG.cpp Index: llvm/lib/Analysis/ComplexLogicCombine.cpp =================================================================== --- /dev/null +++ llvm/lib/Analysis/ComplexLogicCombine.cpp @@ -0,0 +1,215 @@ +//===-------- ComplexLogicalOpsCombine.cpp -------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file attempts to find the simplest expression for a complex logic +// operation chain. We canonicalize all other ops to "&"/"^". +// For example: +// a | b --> (a & b) ^ a ^ b +// c ? a : b --> (c & a) ^ ((c ^ true) & b) +// We use a set of bitset to represent the expression. Any value that is not a +// logic operation is a leaf node. Leaf node is 1 bit in the bitset. For +// example, we have source a, b, c. The bit for a is 1, b is 2 ,c is 4. +// a & b & c --> {7} +// a & b ^ c & a --> {3, 5} +// a & b ^ c & a ^ b --> {3, 5, 2} +// Every bitset is an "&" chain. The set of bitset is a "^" chain. +// Based on boolean ring, We can treat "&" as ring multiplication and "^" as +// ring addition. After that, any logic value can be represented as a chain of +// bitsets. For example: +// r1 = (a | b) & c -> r1 = (a * b * c) + (a * c) + (b * c) -> {7, 5, 6} +// Final we need to rebuild the simplest pattern from the expression. +// +// Reference: https://en.wikipedia.org/wiki/Boolean_ring +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/ComplexLogicCombine.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/IR/Constants.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Support/Debug.h" + +using namespace llvm; + +#define DEBUG_TYPE "complex-logic-combine" + +STATISTIC(NumComplexLogicalOpsSimplified, + "Number of complex logical operations simplified"); + +static cl::opt MaxLogicOpLeafsToScan( + "clc-max-logic-leafs", cl::init(8), cl::Hidden, + cl::desc("Max leafs of logic ops to scan for complex logical combine.")); + +static cl::opt MaxDepthLogicOpsToScan( + "clc-max-depth", cl::init(8), cl::Hidden, + cl::desc("Max depth of logic ops to scan for complex logical combine.")); + +void LogicalOpNode::printValue(raw_ostream &OS, Value *Val) const { + if (auto *ConstVal = dyn_cast(Val)) + OS << *ConstVal; + else + OS << Val->getName(); +} + +void LogicalOpNode::printAndChain(raw_ostream &OS, uint64_t LeafBits) const { + if (LeafBits == LogicalExpr::ExprAllOne) { + OS << "-1"; + return; + } + + unsigned LeafCnt = llvm::popcount(LeafBits); + if (LeafBits == 0 || LeafCnt == 0) + return; + + if (LeafCnt == 1) { + printValue(OS, Helper->LeafValues[llvm::Log2_64(LeafBits)]); + return; + } + + unsigned LeafIdx; + for (unsigned I = 1; I < LeafCnt; I++) { + LeafIdx = llvm::countr_zero(LeafBits); + printValue(OS, Helper->LeafValues[LeafIdx]); + OS << " * "; + LeafBits -= (1ULL << LeafIdx); + } + LeafIdx = llvm::countr_zero(LeafBits); + printValue(OS, Helper->LeafValues[LeafIdx]); +} + +void LogicalOpNode::print(raw_ostream &OS) const { + OS << *Val << " --> "; + if (Expr.size() == 0) { + OS << "0\n"; + return; + } + + for (auto I = ++Expr.begin(); I != Expr.end(); I++) { + printAndChain(OS, *I); + OS << " + "; + } + + printAndChain(OS, *Expr.begin()); + OS << "\n"; +} + +void LogicalOpsHelper::clear() { + for (auto node : LogicalOpNodes) + delete node.second; + LogicalOpNodes.clear(); + LeafSet.clear(); + LeafValues.clear(); +} + +LogicalOpNode *LogicalOpsHelper::visitLeafNode(Value *Val, unsigned Depth) { + // Depth is 0 means the root is not logical operation. We can't + // do anything for that. + if (Depth == 0 || LeafSet.size() > MaxLogicOpLeafsToScan) + return nullptr; + + uint64_t ExprVal = 1ULL << LeafSet.size(); + // Constant Zero,AllOne are special leaf nodes. They involve + // LogicalExpr's calculation so we must detect them at first. + if (auto ConstVal = dyn_cast(Val)) { + if (ConstVal->isZero()) + ExprVal = 0; + else if (ConstVal->isAllOnesValue()) + ExprVal = LogicalExpr::ExprAllOne; + } + if (ExprVal != LogicalExpr::ExprAllOne && ExprVal != 0 && + LeafSet.insert(Val).second) + LeafValues.push_back(Val); + LogicalOpNode *Node = new LogicalOpNode(this, Val, LogicalExpr(ExprVal)); + LogicalOpNodes[Val] = Node; + return Node; +} + +LogicalOpNode *LogicalOpsHelper::visitBinOp(BinaryOperator *BO, + unsigned Depth) { + // We can only to simpilfy and, or , xor in the binary operator + if (BO->getOpcode() != Instruction::And && + BO->getOpcode() != Instruction::Or && BO->getOpcode() != Instruction::Xor) + return visitLeafNode(BO, Depth); + + LogicalOpNode *LHS = getLogicalOpNode(BO->getOperand(0), Depth + 1); + if (LHS == nullptr) + return nullptr; + + LogicalOpNode *RHS = getLogicalOpNode(BO->getOperand(1), Depth + 1); + if (RHS == nullptr) + return nullptr; + + LogicalOpNode *Node; + if (BO->getOpcode() == Instruction::And) + Node = new LogicalOpNode(this, BO, LHS->getExpr() & RHS->getExpr()); + else if (BO->getOpcode() == Instruction::Or) + Node = new LogicalOpNode(this, BO, LHS->getExpr() | RHS->getExpr()); + else + Node = new LogicalOpNode(this, BO, LHS->getExpr() ^ RHS->getExpr()); + LogicalOpNodes[BO] = Node; + return Node; +} + +LogicalOpNode *LogicalOpsHelper::getLogicalOpNode(Value *Val, unsigned Depth) { + if (Depth == MaxDepthLogicOpsToScan) + return nullptr; + + if (LogicalOpNodes.find(Val) == LogicalOpNodes.end()) { + LogicalOpNode *Node; + + // TODO: add select instruction support + if (auto *BO = dyn_cast(Val)) + Node = visitBinOp(BO, Depth); + else + Node = visitLeafNode(Val, Depth); + + if (!Node) + return nullptr; + LLVM_DEBUG(dbgs() << *Node); + } + return LogicalOpNodes[Val]; +} + +Value *LogicalOpsHelper::logicalOpToValue(LogicalOpNode *Node) { + const LogicalExpr &Expr = Node->getExpr(); + // Empty when all leaf bits are earsed from the set because a ^ a = 0. + if (Expr.size() == 0) + return Constant::getNullValue(Node->getValue()->getType()); + + if (Expr.size() == 1) { + uint64_t LeafBits = *Expr.begin(); + if (LeafBits == 0) + return Constant::getNullValue(Node->getValue()->getType()); + // ExprAllOne is not in the LeafValues + if (LeafBits == LogicalExpr::ExprAllOne) + return Constant::getAllOnesValue(Node->getValue()->getType()); + + if (llvm::popcount(LeafBits) == 1) + return LeafValues[llvm::Log2_64(LeafBits)]; + } + + // TODO: complex pattern simpilify + + return nullptr; +} + +Value *LogicalOpsHelper::simplify(Value *Root) { + assert(MaxLogicOpLeafsToScan <= 63 && + "Logical leaf node can't larger than 63."); + LogicalOpNode *RootNode = getLogicalOpNode(Root); + if (RootNode == nullptr) + return nullptr; + + Value *NewRoot = logicalOpToValue(RootNode); + if (NewRoot == Root) + return nullptr; + + if (NewRoot != nullptr) + NumComplexLogicalOpsSimplified++; + return NewRoot; +} Index: llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp =================================================================== --- llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp +++ llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp @@ -18,6 +18,7 @@ #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/ComplexLogicCombine.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" @@ -46,6 +47,10 @@ "aggressive-instcombine-max-scan-instrs", cl::init(64), cl::Hidden, cl::desc("Max number of instructions to scan for aggressive instcombine.")); +static cl::opt EnableClcForAll( + "enable-clc-for-all", cl::Hidden, cl::init(false), + cl::desc("Enable complex logical combine for every logical operation")); + /// Match a pattern for a bitwise funnel/rotate operation that partially guards /// against undefined behavior by branching around the funnel-shift/rotation /// when the shift amount is 0. @@ -838,6 +843,14 @@ const DataLayout &DL = F.getParent()->getDataLayout(); + LogicalOpsHelper Helper; + auto ComplexLogicalSimplify = [](LogicalOpsHelper &Helper, Value *V) { + Value *NewV = Helper.simplify(V); + if (NewV) + V->replaceAllUsesWith(NewV); + return NewV != nullptr; + }; + // Walk the block backwards for efficiency. We're matching a chain of // use->defs, so we're more likely to succeed by starting from the bottom. // Also, we want to avoid matching partial patterns. @@ -854,6 +867,20 @@ // needs to be called at the end of this sequence, otherwise we may make // bugs. MadeChange |= foldSqrt(I, TTI, TLI); + + if (EnableClcForAll) { + if (I.getOpcode() == Instruction::And || + I.getOpcode() == Instruction::Or || + I.getOpcode() == Instruction::Xor) + MadeChange |= ComplexLogicalSimplify(Helper, &I); + } + } + + if (!EnableClcForAll) { + if (auto *BI = dyn_cast(BB.getTerminator())) { + if (BI->isConditional()) + MadeChange |= ComplexLogicalSimplify(Helper, BI->getCondition()); + } } } Index: llvm/test/Transforms/AggressiveInstCombine/complex-logic.ll =================================================================== --- llvm/test/Transforms/AggressiveInstCombine/complex-logic.ll +++ llvm/test/Transforms/AggressiveInstCombine/complex-logic.ll @@ -1,19 +1,25 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt < %s -passes=aggressive-instcombine -S | FileCheck %s +; RUN: opt < %s -passes=aggressive-instcombine -enable-clc-for-all -S | FileCheck %s define i1 @leaf1_and_aa(i1 %a) { ; CHECK-LABEL: @leaf1_and_aa( -; CHECK-NEXT: [[AND_AA:%.*]] = and i1 [[A:%.*]], [[A]] -; CHECK-NEXT: ret i1 [[AND_AA]] +; CHECK-NEXT: ret i1 [[A:%.*]] ; %and.aa = and i1 %a, %a ret i1 %and.aa } +define i1 @leaf1_and_a_false(i1 %a) { +; CHECK-LABEL: @leaf1_and_a_false( +; CHECK-NEXT: ret i1 false +; + %and.aa = and i1 %a, false + ret i1 %and.aa +} + define i1 @leaf1_xor_aa(i1 %a) { ; CHECK-LABEL: @leaf1_xor_aa( -; CHECK-NEXT: [[XOR_AA:%.*]] = xor i1 [[A:%.*]], [[A]] -; CHECK-NEXT: ret i1 [[XOR_AA]] +; CHECK-NEXT: ret i1 false ; %xor.aa = xor i1 %a, %a ret i1 %xor.aa @@ -21,9 +27,7 @@ define i1 @leaf1_and_not(i1 %a) { ; CHECK-LABEL: @leaf1_and_not( -; CHECK-NEXT: [[NOT_A:%.*]] = xor i1 [[A:%.*]], true -; CHECK-NEXT: [[AND:%.*]] = and i1 [[A]], [[NOT_A]] -; CHECK-NEXT: ret i1 [[AND]] +; CHECK-NEXT: ret i1 false ; %not.a = xor i1 %a, true %and = and i1 %a, %not.a @@ -32,9 +36,7 @@ define i1 @leaf1_or_not(i1 %a) { ; CHECK-LABEL: @leaf1_or_not( -; CHECK-NEXT: [[NOT_A:%.*]] = xor i1 [[A:%.*]], true -; CHECK-NEXT: [[OR:%.*]] = or i1 [[A]], [[NOT_A]] -; CHECK-NEXT: ret i1 [[OR]] +; CHECK-NEXT: ret i1 true ; %not.a = xor i1 %a, true %or = or i1 %a, %not.a @@ -43,9 +45,7 @@ define i1 @leaf2_xor(i1 %a, i1 %b) { ; CHECK-LABEL: @leaf2_xor( -; CHECK-NEXT: [[AB:%.*]] = xor i1 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[XOR_AB_A:%.*]] = xor i1 [[AB]], [[A]] -; CHECK-NEXT: ret i1 [[XOR_AB_A]] +; CHECK-NEXT: ret i1 [[B:%.*]] ; %ab = xor i1 %a, %b %xor.ab.a = xor i1 %ab, %a @@ -54,10 +54,7 @@ define i1 @leaf2_xor_ret_const_false(i1 %a, i1 %b) { ; CHECK-LABEL: @leaf2_xor_ret_const_false( -; CHECK-NEXT: [[XOR_AB:%.*]] = xor i1 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[XOR_AB_A:%.*]] = xor i1 [[XOR_AB]], [[A]] -; CHECK-NEXT: [[XOR_AB_A_B:%.*]] = xor i1 [[XOR_AB_A]], [[B]] -; CHECK-NEXT: ret i1 [[XOR_AB_A_B]] +; CHECK-NEXT: ret i1 false ; %xor.ab = xor i1 %a, %b %xor.ab.a = xor i1 %xor.ab, %a @@ -67,11 +64,7 @@ define i1 @leaf2_or_ret_leaf(i1 %a, i1 %b) { ; CHECK-LABEL: @leaf2_or_ret_leaf( -; CHECK-NEXT: [[OR_AB:%.*]] = or i1 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND_AB:%.*]] = and i1 [[A]], [[B]] -; CHECK-NEXT: [[XOR1:%.*]] = xor i1 [[OR_AB]], [[AND_AB]] -; CHECK-NEXT: [[XOR2:%.*]] = xor i1 [[XOR1]], [[A]] -; CHECK-NEXT: ret i1 [[XOR2]] +; CHECK-NEXT: ret i1 [[B:%.*]] ; %or.ab = or i1 %a, %b %and.ab = and i1 %a, %b @@ -82,12 +75,7 @@ define i1 @leaf2_or_ret_const_false(i1 %a, i1 %b) { ; CHECK-LABEL: @leaf2_or_ret_const_false( -; CHECK-NEXT: [[OR_AB:%.*]] = or i1 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[AND_AB:%.*]] = and i1 [[A]], [[B]] -; CHECK-NEXT: [[XOR1:%.*]] = xor i1 [[OR_AB]], [[AND_AB]] -; CHECK-NEXT: [[XOR2:%.*]] = xor i1 [[XOR1]], [[A]] -; CHECK-NEXT: [[XOR3:%.*]] = xor i1 [[XOR1]], [[B]] -; CHECK-NEXT: ret i1 [[XOR3]] +; CHECK-NEXT: ret i1 [[A:%.*]] ; %or.ab = or i1 %a, %b %and.ab = and i1 %a, %b @@ -99,11 +87,7 @@ define i4 @leaf2_type_is_i4(i4 %a, i4 %b) { ; CHECK-LABEL: @leaf2_type_is_i4( -; CHECK-NEXT: [[XOR_AB:%.*]] = xor i4 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[NOT_A:%.*]] = xor i4 [[A]], -1 -; CHECK-NEXT: [[XOR2:%.*]] = xor i4 [[NOT_A]], [[B]] -; CHECK-NEXT: [[OR:%.*]] = or i4 [[XOR2]], [[XOR_AB]] -; CHECK-NEXT: ret i4 [[OR]] +; CHECK-NEXT: ret i4 -1 ; %xor.ab = xor i4 %a, %b %not.a = xor i4 %a, -1 @@ -114,11 +98,7 @@ define i1 @leaf3_complex_ret_const_false(i1 %a, i1 %b, i1 %c) { ; CHECK-LABEL: @leaf3_complex_ret_const_false( -; CHECK-NEXT: [[AB:%.*]] = or i1 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[ABC:%.*]] = or i1 [[AB]], [[C:%.*]] -; CHECK-NEXT: [[NOT_ABC:%.*]] = xor i1 [[ABC]], true -; CHECK-NEXT: [[R:%.*]] = and i1 [[NOT_ABC]], [[A]] -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %ab = or i1 %a, %b %abc = or i1 %ab, %c @@ -129,14 +109,7 @@ define i1 @leaf3_complex_ret_leaf(i1 %a, i1 %b, i1 %c) { ; CHECK-LABEL: @leaf3_complex_ret_leaf( -; CHECK-NEXT: [[AB:%.*]] = and i1 [[A:%.*]], [[B:%.*]] -; CHECK-NEXT: [[BC:%.*]] = and i1 [[B]], [[C:%.*]] -; CHECK-NEXT: [[XOR_AC:%.*]] = xor i1 [[A]], [[C]] -; CHECK-NEXT: [[OR:%.*]] = or i1 [[AB]], [[XOR_AC]] -; CHECK-NEXT: [[NOT_BC:%.*]] = xor i1 [[BC]], true -; CHECK-NEXT: [[AND:%.*]] = and i1 [[NOT_BC]], [[A]] -; CHECK-NEXT: [[COND:%.*]] = xor i1 [[AND]], [[OR]] -; CHECK-NEXT: ret i1 [[COND]] +; CHECK-NEXT: ret i1 [[C:%.*]] ; %ab = and i1 %a, %b %bc = and i1 %b, %c @@ -150,13 +123,7 @@ define i1 @leaf4_ret_const_true(i1 %a, i1 %b, i1 %c, i1 %d) { ; CHECK-LABEL: @leaf4_ret_const_true( -; CHECK-NEXT: [[BD:%.*]] = and i1 [[B:%.*]], [[D:%.*]] -; CHECK-NEXT: [[NOT_BD:%.*]] = xor i1 [[BD]], true -; CHECK-NEXT: [[XOR_AB:%.*]] = xor i1 [[A:%.*]], [[B]] -; CHECK-NEXT: [[OR1:%.*]] = or i1 [[XOR_AB]], [[C:%.*]] -; CHECK-NEXT: [[OR2:%.*]] = or i1 [[OR1]], [[NOT_BD]] -; CHECK-NEXT: [[OR3:%.*]] = or i1 [[OR2]], [[A]] -; CHECK-NEXT: ret i1 [[OR3]] +; CHECK-NEXT: ret i1 true ; %bd = and i1 %b, %d %not.bd = xor i1 %bd, true @@ -169,15 +136,7 @@ define i1 @leaf4_ret_leaf(i1 %a, i1 %b, i1 %c, i1 %d) { ; CHECK-LABEL: @leaf4_ret_leaf( -; CHECK-NEXT: [[BD:%.*]] = and i1 [[B:%.*]], [[D:%.*]] -; CHECK-NEXT: [[XOR:%.*]] = xor i1 [[BD]], [[C:%.*]] -; CHECK-NEXT: [[NOT_BD:%.*]] = xor i1 [[XOR]], true -; CHECK-NEXT: [[XOR_AB:%.*]] = xor i1 [[A:%.*]], [[B]] -; CHECK-NEXT: [[OR1:%.*]] = or i1 [[XOR_AB]], [[C]] -; CHECK-NEXT: [[OR2:%.*]] = or i1 [[OR1]], [[NOT_BD]] -; CHECK-NEXT: [[OR3:%.*]] = or i1 [[OR2]], [[A]] -; CHECK-NEXT: [[AND:%.*]] = and i1 [[OR3]], [[B]] -; CHECK-NEXT: ret i1 [[AND]] +; CHECK-NEXT: ret i1 [[B:%.*]] ; %bd = and i1 %b, %d %xor = xor i1 %bd, %c @@ -192,15 +151,7 @@ define i1 @leaf4_ret_leaf2(i1 %a, i1 %b, i1 %c, i1 %d) { ; CHECK-LABEL: @leaf4_ret_leaf2( -; CHECK-NEXT: [[BD:%.*]] = and i1 [[B:%.*]], [[D:%.*]] -; CHECK-NEXT: [[XOR:%.*]] = xor i1 [[BD]], [[C:%.*]] -; CHECK-NEXT: [[NOT_BD:%.*]] = xor i1 [[XOR]], true -; CHECK-NEXT: [[XOR_AB:%.*]] = xor i1 [[A:%.*]], [[B]] -; CHECK-NEXT: [[OR1:%.*]] = or i1 [[XOR_AB]], [[C]] -; CHECK-NEXT: [[OR2:%.*]] = or i1 [[OR1]], [[NOT_BD]] -; CHECK-NEXT: [[OR3:%.*]] = or i1 [[OR2]], [[A]] -; CHECK-NEXT: [[AND:%.*]] = and i1 [[OR3]], [[B]] -; CHECK-NEXT: ret i1 [[AND]] +; CHECK-NEXT: ret i1 [[B:%.*]] ; %bd = and i1 %b, %d %xor = xor i1 %bd, %c