Index: llvm/include/llvm/Analysis/LogicCombine.h =================================================================== --- /dev/null +++ llvm/include/llvm/Analysis/LogicCombine.h @@ -0,0 +1,69 @@ +//===------------------ LogicCombine.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 LogicCombineHelper; + +class LogicalOpNode { +private: + LogicCombineHelper *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(LogicCombineHelper *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 LogicCombineHelper { +public: + LogicCombineHelper() {} + ~LogicCombineHelper() { 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,155 @@ +//===------------------- 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 +/// a set of bitset. +/// +/// For a logical expression represented by bitset, the "and" logic +/// operator represented by "&" is translated to "*" and is then evaluated as +/// the "or" of the bitset. 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 are two exceptions: +/// If one of the operands is constant 0, the entire bitset represents 0. +/// If one of the operands is constant -1, the result is the other one. +/// +/// 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 +/// Calculate multiplication: +/// 011 + 111 + 011 + 001 + 100 + 111 + 001 +/// Calculate addition: +/// 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 BitSet : AddChain) + LeafMask |= BitSet; + } + +public: + static const uint64_t ExprAllOne = 0x8000000000000000; + + LogicalExpr() {} + LogicalExpr(uint64_t BitSet) { + AddChain.insert(BitSet); + LeafMask = BitSet; + } + 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 LHS : AddChain) { + // a & 0 -> 0 + if (LHS == 0) + continue; + for (auto RHS : RHS.AddChain) { + // 0 & a -> 0 + if (RHS == 0) + continue; + + uint64_t NewBitSet; + // Except the speical case one value "*" -1 is just return itself, the + // other "*" operation is actually "|" LHS and RHS 's bitset. For + // example: ab * bd = abd The expression ab * bd convert to bitset will + // be 0b0011 * 0b1010. The result abd convert to bitset will become + // 0b1011. + if (LHS == ExprAllOne) + NewBitSet = RHS; + else if (RHS == ExprAllOne) + NewBitSet = LHS; + else + NewBitSet = LHS | RHS; + assert(NewBitSet == ExprAllOne || (NewBitSet & ExprAllOne) == 0); + // a ^ a -> 0 + if (!NewChain.insert(NewBitSet).second) + NewChain.erase(NewBitSet); + } + } + + AddChain = NewChain; + updateLeafMask(); + return *this; + } + + LogicalExpr &operator+=(const LogicalExpr &RHS) { + for (auto RHS : RHS.AddChain) { + // a ^ a -> 0 + if (!AddChain.insert(RHS).second) + AddChain.erase(RHS); + } + 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 @@ -87,6 +87,7 @@ Lint.cpp Loads.cpp Local.cpp + LogicCombine.cpp LoopAccessAnalysis.cpp LoopAnalysisManager.cpp LoopCacheAnalysis.cpp Index: llvm/lib/Analysis/LogicCombine.cpp =================================================================== --- /dev/null +++ llvm/lib/Analysis/LogicCombine.cpp @@ -0,0 +1,214 @@ +//===--------------------- LogicCombine.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} +// Finally we need to rebuild the simplest pattern from the expression. +// +// Reference: https://en.wikipedia.org/wiki/Boolean_ring +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/LogicCombine.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 "logic-combine" + +STATISTIC(NumLogicalOpsSimplified, "Number of logical operations simplified"); + +static cl::opt MaxLogicOpLeafsToScan( + "logic-combine-max-leafs", cl::init(8), cl::Hidden, + cl::desc("Max leafs of logic ops to scan for logical combine.")); + +static cl::opt MaxDepthLogicOpsToScan( + "logic-combine-max-depth", cl::init(8), cl::Hidden, + cl::desc("Max depth of logic ops to scan for 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; + } + + if (LeafBits == 0) + return; + + unsigned LeafCnt = popcount(LeafBits); + if (LeafCnt == 1) { + printValue(OS, Helper->LeafValues[Log2_64(LeafBits)]); + return; + } + + unsigned LeafIdx; + for (unsigned I = 1; I < LeafCnt; I++) { + LeafIdx = countr_zero(LeafBits); + printValue(OS, Helper->LeafValues[LeafIdx]); + OS << " * "; + LeafBits -= (1ULL << LeafIdx); + } + LeafIdx = 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 LogicCombineHelper::clear() { + for (auto node : LogicalOpNodes) + delete node.second; + LogicalOpNodes.clear(); + LeafSet.clear(); + LeafValues.clear(); +} + +LogicalOpNode *LogicCombineHelper::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 *LogicCombineHelper::visitBinOp(BinaryOperator *BO, + unsigned Depth) { + // We can only to simpilfy and, or , xor in the binary operator + if (!BO->isBitwiseLogicOp()) + 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 *LogicCombineHelper::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 *LogicCombineHelper::logicalOpToValue(LogicalOpNode *Node) { + const LogicalExpr &Expr = Node->getExpr(); + // Empty when all leaf bits are erased 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 (popcount(LeafBits) == 1) + return LeafValues[Log2_64(LeafBits)]; + } + + // TODO: complex pattern simpilify + + return nullptr; +} + +Value *LogicCombineHelper::simplify(Value *Root) { + assert(MaxLogicOpLeafsToScan <= 63 && + "Logical leaf node can't be larger than 63."); + LogicalOpNode *RootNode = getLogicalOpNode(Root); + if (RootNode == nullptr) + return nullptr; + + Value *NewRoot = logicalOpToValue(RootNode); + if (NewRoot == Root) + return nullptr; + + if (NewRoot != nullptr) + NumLogicalOpsSimplified++; + return NewRoot; +} Index: llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp =================================================================== --- llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp +++ llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp @@ -19,6 +19,7 @@ #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/LogicCombine.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/ValueTracking.h" @@ -824,6 +825,17 @@ return true; } +// Use LogicalOpsHelper to simplify complex logic +static bool foldComplexLogic(LogicCombineHelper &Helper, Instruction &I) { + if (I.isBitwiseLogicOp()) { + Value *NewV = Helper.simplify(&I); + if (NewV) + I.replaceAllUsesWith(NewV); + return NewV != nullptr; + } + return false; +} + /// This is the entry point for folds that could be implemented in regular /// InstCombine, but they are separated because they are not expected to /// occur frequently and/or have more than a constant-length pattern match. @@ -838,6 +850,15 @@ const DataLayout &DL = F.getParent()->getDataLayout(); + // There are 2 limitations to be trade off here. The higher level the + // LogicalOpsHelper create, the more logical node cached, which means it can + // save more cpu timing. But it will maintain more leaf nodes. By default + // the max of leaf node is 8 , which is not enough for whole function I + // guess. We can improve it later. Like split the helper based on types to + // make the code more efficient, adjust the default value of max leaf node + // number, use APInt to support more bits. + LogicCombineHelper Helper; + // 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 +875,7 @@ // needs to be called at the end of this sequence, otherwise we may make // bugs. MadeChange |= foldSqrt(I, TTI, TLI); + MadeChange |= foldComplexLogic(Helper, I); } } Index: llvm/test/Transforms/AggressiveInstCombine/complex-logic.ll =================================================================== --- llvm/test/Transforms/AggressiveInstCombine/complex-logic.ll +++ /dev/null @@ -1,214 +0,0 @@ -; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt < %s -passes=aggressive-instcombine -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]] -; - %and.aa = and i1 %a, %a - 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]] -; - %xor.aa = xor i1 %a, %a - ret i1 %xor.aa -} - -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]] -; - %not.a = xor i1 %a, true - %and = and i1 %a, %not.a - ret i1 %and -} - -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]] -; - %not.a = xor i1 %a, true - %or = or i1 %a, %not.a - ret i1 %or -} - -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]] -; - %ab = xor i1 %a, %b - %xor.ab.a = xor i1 %ab, %a - ret i1 %xor.ab.a -} - -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]] -; - %xor.ab = xor i1 %a, %b - %xor.ab.a = xor i1 %xor.ab, %a - %xor.ab.a.b = xor i1 %xor.ab.a, %b - ret i1 %xor.ab.a.b -} - -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]] -; - %or.ab = or i1 %a, %b - %and.ab = and i1 %a, %b - %xor1 = xor i1 %or.ab, %and.ab - %xor2 = xor i1 %xor1, %a - ret i1 %xor2 -} - -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]] -; - %or.ab = or i1 %a, %b - %and.ab = and i1 %a, %b - %xor1 = xor i1 %or.ab, %and.ab - %xor2 = xor i1 %xor1, %a - %xor3 = xor i1 %xor1, %b - ret i1 %xor3 -} - -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]] -; - %xor.ab = xor i4 %a, %b - %not.a = xor i4 %a, -1 - %xor2 = xor i4 %not.a, %b - %or = or i4 %xor2, %xor.ab - ret i4 %or -} - -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]] -; - %ab = or i1 %a, %b - %abc = or i1 %ab, %c - %not.abc = xor i1 %abc, true - %r = and i1 %not.abc, %a - ret i1 %r -} - -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]] -; - %ab = and i1 %a, %b - %bc = and i1 %b, %c - %xor.ac = xor i1 %a, %c - %or = or i1 %ab, %xor.ac - %not.bc = xor i1 %bc, true - %and = and i1 %not.bc, %a - %cond = xor i1 %and, %or - ret i1 %cond -} - -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]] -; - %bd = and i1 %b, %d - %not.bd = xor i1 %bd, true - %xor.ab = xor i1 %a, %b - %or1 = or i1 %xor.ab, %c - %or2 = or i1 %or1, %not.bd - %or3 = or i1 %or2, %a - ret i1 %or3 -} - -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]] -; - %bd = and i1 %b, %d - %xor = xor i1 %bd, %c - %not.bd = xor i1 %xor, true - %xor.ab = xor i1 %a, %b - %or1 = or i1 %xor.ab, %c - %or2 = or i1 %or1, %not.bd - %or3 = or i1 %or2, %a - %and = and i1 %or3, %b - ret i1 %and -} - -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]] -; - %bd = and i1 %b, %d - %xor = xor i1 %bd, %c - %not.bd = xor i1 %xor, true - %xor.ab = xor i1 %a, %b - %or1 = or i1 %xor.ab, %c - %or2 = or i1 %or1, %not.bd - %or3 = or i1 %or2, %a - %and = and i1 %or3, %b - ret i1 %and -} Index: llvm/test/Transforms/AggressiveInstCombine/logic-combine.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/AggressiveInstCombine/logic-combine.ll @@ -0,0 +1,165 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -passes=aggressive-instcombine -S | FileCheck %s + +define i8 @leaf1_and_aa(i8 %a) { +; CHECK-LABEL: @leaf1_and_aa( +; CHECK-NEXT: ret i8 [[A:%.*]] +; + %and.aa = and i8 %a, %a + ret i8 %and.aa +} + +define i8 @leaf1_and_a_false(i8 %a) { +; CHECK-LABEL: @leaf1_and_a_false( +; CHECK-NEXT: ret i8 0 +; + %and.aa = and i8 %a, 0 + ret i8 %and.aa +} + +define i8 @leaf1_xor_aa(i8 %a) { +; CHECK-LABEL: @leaf1_xor_aa( +; CHECK-NEXT: ret i8 0 +; + %xor.aa = xor i8 %a, %a + ret i8 %xor.aa +} + +define i8 @leaf1_and_not(i8 %a) { +; CHECK-LABEL: @leaf1_and_not( +; CHECK-NEXT: ret i8 0 +; + %not.a = xor i8 %a, -1 + %and = and i8 %a, %not.a + ret i8 %and +} + +define i8 @leaf1_or_not(i8 %a) { +; CHECK-LABEL: @leaf1_or_not( +; CHECK-NEXT: ret i8 -1 +; + %not.a = xor i8 %a, -1 + %or = or i8 %a, %not.a + ret i8 %or +} + +define i8 @leaf2_xor(i8 %a, i8 %b) { +; CHECK-LABEL: @leaf2_xor( +; CHECK-NEXT: ret i8 [[B:%.*]] +; + %ab = xor i8 %a, %b + %xor.ab.a = xor i8 %ab, %a + ret i8 %xor.ab.a +} + +define i8 @leaf2_xor_ret_const_false(i8 %a, i8 %b) { +; CHECK-LABEL: @leaf2_xor_ret_const_false( +; CHECK-NEXT: ret i8 0 +; + %xor.ab = xor i8 %a, %b + %xor.ab.a = xor i8 %xor.ab, %a + %xor.ab.a.b = xor i8 %xor.ab.a, %b + ret i8 %xor.ab.a.b +} + +define i8 @leaf2_or_ret_leaf(i8 %a, i8 %b) { +; CHECK-LABEL: @leaf2_or_ret_leaf( +; CHECK-NEXT: ret i8 [[B:%.*]] +; + %or.ab = or i8 %a, %b + %and.ab = and i8 %a, %b + %xor1 = xor i8 %or.ab, %and.ab + %xor2 = xor i8 %xor1, %a + ret i8 %xor2 +} + +define i8 @leaf2_or_ret_const_false(i8 %a, i8 %b) { +; CHECK-LABEL: @leaf2_or_ret_const_false( +; CHECK-NEXT: ret i8 [[A:%.*]] +; + %or.ab = or i8 %a, %b + %and.ab = and i8 %a, %b + %xor1 = xor i8 %or.ab, %and.ab + %xor2 = xor i8 %xor1, %a + %xor3 = xor i8 %xor1, %b + ret i8 %xor3 +} + +define i1 @leaf2_type_is_i1(i1 %a, i1 %b) { +; CHECK-LABEL: @leaf2_type_is_i1( +; CHECK-NEXT: ret i1 true +; + %xor.ab = xor i1 %a, %b + %not.a = xor i1 %a, true + %xor2 = xor i1 %not.a, %b + %or = or i1 %xor2, %xor.ab + ret i1 %or +} + +define i8 @leaf3_complex_ret_const_false(i8 %a, i8 %b, i8 %c) { +; CHECK-LABEL: @leaf3_complex_ret_const_false( +; CHECK-NEXT: ret i8 0 +; + %ab = or i8 %a, %b + %abc = or i8 %ab, %c + %not.abc = xor i8 %abc, -1 + %r = and i8 %not.abc, %a + ret i8 %r +} + +define i8 @leaf3_complex_ret_leaf(i8 %a, i8 %b, i8 %c) { +; CHECK-LABEL: @leaf3_complex_ret_leaf( +; CHECK-NEXT: ret i8 [[C:%.*]] +; + %ab = and i8 %a, %b + %bc = and i8 %b, %c + %xor.ac = xor i8 %a, %c + %or = or i8 %ab, %xor.ac + %not.bc = xor i8 %bc, -1 + %and = and i8 %not.bc, %a + %cond = xor i8 %and, %or + ret i8 %cond +} + +define i8 @leaf4_ret_const_true(i8 %a, i8 %b, i8 %c, i8 %d) { +; CHECK-LABEL: @leaf4_ret_const_true( +; CHECK-NEXT: ret i8 -1 +; + %bd = and i8 %b, %d + %not.bd = xor i8 %bd, -1 + %xor.ab = xor i8 %a, %b + %or1 = or i8 %xor.ab, %c + %or2 = or i8 %or1, %not.bd + %or3 = or i8 %or2, %a + ret i8 %or3 +} + +define i8 @leaf4_ret_leaf(i8 %a, i8 %b, i8 %c, i8 %d) { +; CHECK-LABEL: @leaf4_ret_leaf( +; CHECK-NEXT: ret i8 [[B:%.*]] +; + %bd = and i8 %b, %d + %xor = xor i8 %bd, %c + %not.bd = xor i8 %xor, -1 + %xor.ab = xor i8 %a, %b + %or1 = or i8 %xor.ab, %c + %or2 = or i8 %or1, %not.bd + %or3 = or i8 %or2, %a + %and = and i8 %or3, %b + ret i8 %and +} + +define i8 @leaf4_ret_leaf2(i8 %a, i8 %b, i8 %c, i8 %d) { +; CHECK-LABEL: @leaf4_ret_leaf2( +; CHECK-NEXT: ret i8 [[B:%.*]] +; + %bd = and i8 %b, %d + %xor = xor i8 %bd, %c + %not.bd = xor i8 %xor, -1 + %xor.ab = xor i8 %a, %b + %or1 = or i8 %xor.ab, %c + %or2 = or i8 %or1, %not.bd + %or3 = or i8 %or2, %a + %and = and i8 %or3, %b + ret i8 %and +}