From 76df706bca14affdcf0dd91561c8e6805035608f Mon Sep 17 00:00:00 2001 From: "chenglin.bi" Date: Tue, 14 Mar 2023 08:59:53 +0800 Subject: [PATCH] Revert "[LogicCombine 1/?] Implement a general way to simplify logical operations." This reverts commit 97dcbea63e11d566cff0cd3a758cf1114cf1f633. --- llvm/include/llvm/Analysis/LogicCombine.h | 73 -------- llvm/include/llvm/Analysis/LogicalExpr.h | 145 --------------- llvm/lib/Analysis/CMakeLists.txt | 1 - llvm/lib/Analysis/LogicCombine.cpp | 207 --------------------- .../AggressiveInstCombine.cpp | 30 +-- .../AggressiveInstCombine/logic-combine.ll | 177 ++++++++---------- 6 files changed, 76 insertions(+), 557 deletions(-) delete mode 100644 llvm/include/llvm/Analysis/LogicCombine.h delete mode 100644 llvm/include/llvm/Analysis/LogicalExpr.h delete mode 100644 llvm/lib/Analysis/LogicCombine.cpp diff --git a/llvm/include/llvm/Analysis/LogicCombine.h b/llvm/include/llvm/Analysis/LogicCombine.h deleted file mode 100644 index 53eda1f..0000000 --- a/llvm/include/llvm/Analysis/LogicCombine.h +++ /dev/null @@ -1,73 +0,0 @@ -//===------------------ 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 -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_LOGICCOMBINE_H -#define LLVM_ANALYSIS_LOGICCOMBINE_H - -#include "LogicalExpr.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SetVector.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/IR/InstrTypes.h" -#include "llvm/IR/Instruction.h" -#include "llvm/Support/Allocator.h" - -namespace llvm { - -class LogicCombiner; - -class LogicalOpNode { -private: - LogicCombiner *Helper; - Value *Val; - LogicalExpr Expr; - // TODO: Add weight to measure cost for more than one use value - - void printAndChain(raw_ostream &OS, uint64_t LeafBits) const; - -public: - LogicalOpNode(LogicCombiner *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 LogicCombiner { -public: - LogicCombiner() {} - ~LogicCombiner() { clear(); } - - Value *simplify(Value *Root); - -private: - friend class LogicalOpNode; - - SpecificBumpPtrAllocator Alloc; - SmallDenseMap LogicalOpNodes; - SmallSetVector 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 - -#endif // LLVM_ANALYSIS_LOGICCOMBINE_H diff --git a/llvm/include/llvm/Analysis/LogicalExpr.h b/llvm/include/llvm/Analysis/LogicalExpr.h deleted file mode 100644 index 4c99d28..0000000 --- a/llvm/include/llvm/Analysis/LogicalExpr.h +++ /dev/null @@ -1,145 +0,0 @@ -//===------------------- 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 bitsets. -/// -/// 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. An 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 -//===----------------------------------------------------------------------===// - -#ifndef LLVM_ANALYSIS_LOGICALEXPR_H -#define LLVM_ANALYSIS_LOGICALEXPR_H - -#include "llvm/ADT/DenseSet.h" - -namespace llvm { -// TODO: can we use APInt define the mask to enlarge the max leaf number? -typedef SmallDenseSet ExprAddChain; - -class LogicalExpr { -private: - ExprAddChain AddChain; - -public: - static const uint64_t ExprAllOne = 0x8000000000000000; - - LogicalExpr() {} - LogicalExpr(uint64_t BitSet) { - if (BitSet != 0) - AddChain.insert(BitSet); - } - LogicalExpr(const ExprAddChain &SrcAddChain) : AddChain(SrcAddChain) { - } - - 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) { - for (auto RHS : RHS.AddChain) { - uint64_t NewBitSet; - // Except the special 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 - auto InsertPair = NewChain.insert(NewBitSet); - if (!InsertPair.second) - NewChain.erase(InsertPair.first); - } - } - - AddChain = NewChain; - return *this; - } - - LogicalExpr &operator+=(const LogicalExpr &RHS) { - for (auto RHS : RHS.AddChain) { - // a ^ a -> 0 - auto InsertPair = AddChain.insert(RHS); - if (!InsertPair.second) - AddChain.erase(InsertPair.first); - } - 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 - -#endif // LLVM_ANALYSIS_LOGICALEXPR_H diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt index 531787f..d25eb5c 100644 --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -87,7 +87,6 @@ add_llvm_component_library(LLVMAnalysis Lint.cpp Loads.cpp Local.cpp - LogicCombine.cpp LoopAccessAnalysis.cpp LoopAnalysisManager.cpp LoopCacheAnalysis.cpp diff --git a/llvm/lib/Analysis/LogicCombine.cpp b/llvm/lib/Analysis/LogicCombine.cpp deleted file mode 100644 index ffe4c34..0000000 --- a/llvm/lib/Analysis/LogicCombine.cpp +++ /dev/null @@ -1,207 +0,0 @@ -//===--------------------- 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 -// -//===----------------------------------------------------------------------===// -/// \file -/// This file attempts to find the simplest expression for a bitwise 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 --> {0b111} -/// a & b ^ c & a --> {0b011, 0b101} -/// a & b ^ c & a ^ b --> {0b011, 0b101, 0b010} -/// 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) -> -/// {0b111, 0b101, 0b110} -/// 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/ADT/StringExtras.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::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) { - Helper->LeafValues[Log2_64(LeafBits)]->printAsOperand(OS, false); - return; - } - - unsigned LeafIdx; - ListSeparator LS(" * "); - for (unsigned I = 0; I < LeafCnt; I++) { - LeafIdx = countr_zero(LeafBits); - OS << LS; - Helper->LeafValues[LeafIdx]->printAsOperand(OS, false); - LeafBits -= (1ULL << LeafIdx); - } -} - -void LogicalOpNode::print(raw_ostream &OS) const { - Val->printAsOperand(OS, false); - OS << " --> "; - if (Expr.size() == 0) { - OS << "0\n"; - return; - } - - ListSeparator LS(" + "); - for (auto I = Expr.begin(); I != Expr.end(); I++) { - OS << LS; - printAndChain(OS, *I); - } - - OS << "\n"; -} - -void LogicCombiner::clear() { - LogicalOpNodes.clear(); - LeafValues.clear(); -} - -LogicalOpNode *LogicCombiner::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 || LeafValues.size() >= MaxLogicOpLeafsToScan) - return nullptr; - - uint64_t ExprVal = 1ULL << LeafValues.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) - LeafValues.insert(Val); - LogicalOpNode *Node = - new (Alloc.Allocate()) LogicalOpNode(this, Val, LogicalExpr(ExprVal)); - LogicalOpNodes[Val] = Node; - return Node; -} - -LogicalOpNode *LogicCombiner::visitBinOp(BinaryOperator *BO, unsigned Depth) { - 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 (Alloc.Allocate()) - LogicalOpNode(this, BO, LHS->getExpr() & RHS->getExpr()); - else if (BO->getOpcode() == Instruction::Or) - Node = new (Alloc.Allocate()) - LogicalOpNode(this, BO, LHS->getExpr() | RHS->getExpr()); - else - Node = new (Alloc.Allocate()) - LogicalOpNode(this, BO, LHS->getExpr() ^ RHS->getExpr()); - LogicalOpNodes[BO] = Node; - return Node; -} - -LogicalOpNode *LogicCombiner::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 *LogicCombiner::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: find the simplest form from logical expression when it is not - // only an "and" chain. - - return nullptr; -} - -Value *LogicCombiner::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 == nullptr || NewRoot == Root) - return nullptr; - - LogicalOpNodes.erase(Root); - NumLogicalOpsSimplified++; - return NewRoot; -} diff --git a/llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp b/llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp index 615d201..473b412 100644 --- a/llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp +++ b/llvm/lib/Transforms/AggressiveInstCombine/AggressiveInstCombine.cpp @@ -19,7 +19,6 @@ #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" @@ -825,40 +824,13 @@ static bool foldConsecutiveLoads(Instruction &I, const DataLayout &DL, return true; } -/// Reduce bitwise logic sequences. -static bool foldBitwiseLogic(Function &F, DominatorTree &DT) { - bool MadeChange = false; - for (BasicBlock &BB : F) { - // Ignore unreachable basic blocks. - if (!DT.isReachableFromEntry(&BB)) - continue; - - // TODO: Combining at the function-level would allow more caching of nodes - // which saves on compile-time, but it may hit the max value limits before - // finding a solution. We could split the combiner based on types to make - // the code more efficient, adjust the value of max depth/values, or use - // APInt to support tracking more than 63 leaf values. - LogicCombiner LC; - for (Instruction &I : BB) { - if (I.isBitwiseLogicOp()) { - Value *NewV = LC.simplify(&I); - if (NewV) { - MadeChange = true; - I.replaceAllUsesWith(NewV); - } - } - } - } - return MadeChange; -} - /// 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. static bool foldUnusualPatterns(Function &F, DominatorTree &DT, TargetTransformInfo &TTI, TargetLibraryInfo &TLI, AliasAnalysis &AA) { - bool MadeChange = foldBitwiseLogic(F, DT); + bool MadeChange = false; for (BasicBlock &BB : F) { // Ignore unreachable basic blocks. if (!DT.isReachableFromEntry(&BB)) diff --git a/llvm/test/Transforms/AggressiveInstCombine/logic-combine.ll b/llvm/test/Transforms/AggressiveInstCombine/logic-combine.ll index e08834d..291963b 100644 --- a/llvm/test/Transforms/AggressiveInstCombine/logic-combine.ll +++ b/llvm/test/Transforms/AggressiveInstCombine/logic-combine.ll @@ -1,9 +1,10 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt < %s -passes=aggressive-instcombine -logic-combine-max-depth=6 -S | FileCheck %s +; 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:%.*]] +; CHECK-NEXT: [[AND_AA:%.*]] = and i8 [[A:%.*]], [[A]] +; CHECK-NEXT: ret i8 [[AND_AA]] ; %and.aa = and i8 %a, %a ret i8 %and.aa @@ -11,7 +12,8 @@ define i8 @leaf1_and_aa(i8 %a) { define i8 @leaf1_and_a_false(i8 %a) { ; CHECK-LABEL: @leaf1_and_a_false( -; CHECK-NEXT: ret i8 0 +; CHECK-NEXT: [[AND_AA:%.*]] = and i8 [[A:%.*]], 0 +; CHECK-NEXT: ret i8 [[AND_AA]] ; %and.aa = and i8 %a, 0 ret i8 %and.aa @@ -19,7 +21,8 @@ define i8 @leaf1_and_a_false(i8 %a) { define i8 @leaf1_xor_aa(i8 %a) { ; CHECK-LABEL: @leaf1_xor_aa( -; CHECK-NEXT: ret i8 0 +; CHECK-NEXT: [[XOR_AA:%.*]] = xor i8 [[A:%.*]], [[A]] +; CHECK-NEXT: ret i8 [[XOR_AA]] ; %xor.aa = xor i8 %a, %a ret i8 %xor.aa @@ -27,7 +30,9 @@ define i8 @leaf1_xor_aa(i8 %a) { define i8 @leaf1_and_not(i8 %a) { ; CHECK-LABEL: @leaf1_and_not( -; CHECK-NEXT: ret i8 0 +; CHECK-NEXT: [[NOT_A:%.*]] = xor i8 [[A:%.*]], -1 +; CHECK-NEXT: [[AND:%.*]] = and i8 [[A]], [[NOT_A]] +; CHECK-NEXT: ret i8 [[AND]] ; %not.a = xor i8 %a, -1 %and = and i8 %a, %not.a @@ -36,7 +41,9 @@ define i8 @leaf1_and_not(i8 %a) { define i8 @leaf1_or_not(i8 %a) { ; CHECK-LABEL: @leaf1_or_not( -; CHECK-NEXT: ret i8 -1 +; CHECK-NEXT: [[NOT_A:%.*]] = xor i8 [[A:%.*]], -1 +; CHECK-NEXT: [[OR:%.*]] = or i8 [[A]], [[NOT_A]] +; CHECK-NEXT: ret i8 [[OR]] ; %not.a = xor i8 %a, -1 %or = or i8 %a, %not.a @@ -45,7 +52,9 @@ define i8 @leaf1_or_not(i8 %a) { define i8 @leaf2_xor(i8 %a, i8 %b) { ; CHECK-LABEL: @leaf2_xor( -; CHECK-NEXT: ret i8 [[B:%.*]] +; CHECK-NEXT: [[AB:%.*]] = xor i8 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: [[XOR_AB_A:%.*]] = xor i8 [[AB]], [[A]] +; CHECK-NEXT: ret i8 [[XOR_AB_A]] ; %ab = xor i8 %a, %b %xor.ab.a = xor i8 %ab, %a @@ -54,7 +63,10 @@ define i8 @leaf2_xor(i8 %a, i8 %b) { define i8 @leaf2_xor_ret_const_false(i8 %a, i8 %b) { ; CHECK-LABEL: @leaf2_xor_ret_const_false( -; CHECK-NEXT: ret i8 0 +; CHECK-NEXT: [[XOR_AB:%.*]] = xor i8 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: [[XOR_AB_A:%.*]] = xor i8 [[XOR_AB]], [[A]] +; CHECK-NEXT: [[XOR_AB_A_B:%.*]] = xor i8 [[XOR_AB_A]], [[B]] +; CHECK-NEXT: ret i8 [[XOR_AB_A_B]] ; %xor.ab = xor i8 %a, %b %xor.ab.a = xor i8 %xor.ab, %a @@ -64,7 +76,11 @@ define i8 @leaf2_xor_ret_const_false(i8 %a, i8 %b) { define i8 @leaf2_or_ret_leaf(i8 %a, i8 %b) { ; CHECK-LABEL: @leaf2_or_ret_leaf( -; CHECK-NEXT: ret i8 [[B:%.*]] +; CHECK-NEXT: [[OR_AB:%.*]] = or i8 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: [[AND_AB:%.*]] = and i8 [[A]], [[B]] +; CHECK-NEXT: [[XOR1:%.*]] = xor i8 [[OR_AB]], [[AND_AB]] +; CHECK-NEXT: [[XOR2:%.*]] = xor i8 [[XOR1]], [[A]] +; CHECK-NEXT: ret i8 [[XOR2]] ; %or.ab = or i8 %a, %b %and.ab = and i8 %a, %b @@ -75,19 +91,28 @@ define i8 @leaf2_or_ret_leaf(i8 %a, i8 %b) { define i8 @leaf2_or_ret_const_false(i8 %a, i8 %b) { ; CHECK-LABEL: @leaf2_or_ret_const_false( -; CHECK-NEXT: ret i8 0 +; CHECK-NEXT: [[OR_AB:%.*]] = or i8 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: [[AND_AB:%.*]] = and i8 [[A]], [[B]] +; CHECK-NEXT: [[XOR1:%.*]] = xor i8 [[OR_AB]], [[AND_AB]] +; CHECK-NEXT: [[XOR2:%.*]] = xor i8 [[XOR1]], [[A]] +; CHECK-NEXT: [[XOR3:%.*]] = xor i8 [[XOR1]], [[B]] +; CHECK-NEXT: ret i8 [[XOR3]] ; %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 %xor2, %b + %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 +; CHECK-NEXT: [[XOR_AB:%.*]] = xor i1 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: [[NOT_A:%.*]] = xor i1 [[A]], true +; CHECK-NEXT: [[XOR2:%.*]] = xor i1 [[NOT_A]], [[B]] +; CHECK-NEXT: [[OR:%.*]] = or i1 [[XOR2]], [[XOR_AB]] +; CHECK-NEXT: ret i1 [[OR]] ; %xor.ab = xor i1 %a, %b %not.a = xor i1 %a, true @@ -98,7 +123,11 @@ define i1 @leaf2_type_is_i1(i1 %a, i1 %b) { 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 +; CHECK-NEXT: [[AB:%.*]] = or i8 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: [[ABC:%.*]] = or i8 [[AB]], [[C:%.*]] +; CHECK-NEXT: [[NOT_ABC:%.*]] = xor i8 [[ABC]], -1 +; CHECK-NEXT: [[R:%.*]] = and i8 [[NOT_ABC]], [[A]] +; CHECK-NEXT: ret i8 [[R]] ; %ab = or i8 %a, %b %abc = or i8 %ab, %c @@ -109,7 +138,14 @@ define i8 @leaf3_complex_ret_const_false(i8 %a, i8 %b, i8 %c) { define i8 @leaf3_complex_ret_leaf(i8 %a, i8 %b, i8 %c) { ; CHECK-LABEL: @leaf3_complex_ret_leaf( -; CHECK-NEXT: ret i8 [[C:%.*]] +; CHECK-NEXT: [[AB:%.*]] = and i8 [[A:%.*]], [[B:%.*]] +; CHECK-NEXT: [[BC:%.*]] = and i8 [[B]], [[C:%.*]] +; CHECK-NEXT: [[XOR_AC:%.*]] = xor i8 [[A]], [[C]] +; CHECK-NEXT: [[OR:%.*]] = or i8 [[AB]], [[XOR_AC]] +; CHECK-NEXT: [[NOT_BC:%.*]] = xor i8 [[BC]], -1 +; CHECK-NEXT: [[AND:%.*]] = and i8 [[NOT_BC]], [[A]] +; CHECK-NEXT: [[COND:%.*]] = xor i8 [[AND]], [[OR]] +; CHECK-NEXT: ret i8 [[COND]] ; %ab = and i8 %a, %b %bc = and i8 %b, %c @@ -123,7 +159,13 @@ define i8 @leaf3_complex_ret_leaf(i8 %a, i8 %b, i8 %c) { 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 +; CHECK-NEXT: [[BD:%.*]] = and i8 [[B:%.*]], [[D:%.*]] +; CHECK-NEXT: [[NOT_BD:%.*]] = xor i8 [[BD]], -1 +; CHECK-NEXT: [[XOR_AB:%.*]] = xor i8 [[A:%.*]], [[B]] +; CHECK-NEXT: [[OR1:%.*]] = or i8 [[XOR_AB]], [[C:%.*]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[OR1]], [[NOT_BD]] +; CHECK-NEXT: [[OR3:%.*]] = or i8 [[OR2]], [[A]] +; CHECK-NEXT: ret i8 [[OR3]] ; %bd = and i8 %b, %d %not.bd = xor i8 %bd, -1 @@ -136,7 +178,15 @@ define i8 @leaf4_ret_const_true(i8 %a, i8 %b, i8 %c, i8 %d) { define i8 @leaf4_ret_leaf(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @leaf4_ret_leaf( -; CHECK-NEXT: ret i8 [[B:%.*]] +; CHECK-NEXT: [[BD:%.*]] = and i8 [[B:%.*]], [[D:%.*]] +; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[BD]], [[C:%.*]] +; CHECK-NEXT: [[NOT_BD:%.*]] = xor i8 [[XOR]], -1 +; CHECK-NEXT: [[XOR_AB:%.*]] = xor i8 [[A:%.*]], [[B]] +; CHECK-NEXT: [[OR1:%.*]] = or i8 [[XOR_AB]], [[C]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[OR1]], [[NOT_BD]] +; CHECK-NEXT: [[OR3:%.*]] = or i8 [[OR2]], [[A]] +; CHECK-NEXT: [[AND:%.*]] = and i8 [[OR3]], [[B]] +; CHECK-NEXT: ret i8 [[AND]] ; %bd = and i8 %b, %d %xor = xor i8 %bd, %c @@ -151,7 +201,15 @@ define i8 @leaf4_ret_leaf(i8 %a, i8 %b, i8 %c, i8 %d) { define i8 @leaf4_ret_leaf2(i8 %a, i8 %b, i8 %c, i8 %d) { ; CHECK-LABEL: @leaf4_ret_leaf2( -; CHECK-NEXT: ret i8 [[B:%.*]] +; CHECK-NEXT: [[BD:%.*]] = and i8 [[B:%.*]], [[D:%.*]] +; CHECK-NEXT: [[XOR:%.*]] = xor i8 [[BD]], [[C:%.*]] +; CHECK-NEXT: [[NOT_BD:%.*]] = xor i8 [[XOR]], -1 +; CHECK-NEXT: [[XOR_AB:%.*]] = xor i8 [[A:%.*]], [[B]] +; CHECK-NEXT: [[OR1:%.*]] = or i8 [[XOR_AB]], [[C]] +; CHECK-NEXT: [[OR2:%.*]] = or i8 [[OR1]], [[NOT_BD]] +; CHECK-NEXT: [[OR3:%.*]] = or i8 [[OR2]], [[A]] +; CHECK-NEXT: [[AND:%.*]] = and i8 [[OR3]], [[B]] +; CHECK-NEXT: ret i8 [[AND]] ; %bd = and i8 %b, %d %xor = xor i8 %bd, %c @@ -163,88 +221,3 @@ define i8 @leaf4_ret_leaf2(i8 %a, i8 %b, i8 %c, i8 %d) { %and = and i8 %or3, %b ret i8 %and } - -; Negative test case 1 for max leaf number: -; This case's max leaf number is 9, if we adjust max depth limitation -; to larger than 8, it will return %a1 - -define i8 @leaf8_negative_leafnum(i8 %a1, i8 %a2, i8 %a3, i8 %a4, i8 %a5, i8 %a6, i8 %a7, i8 %a8, i8 %a9) { -; CHECK-LABEL: @leaf8_negative_leafnum( -; CHECK-NEXT: [[A12:%.*]] = xor i8 [[A1:%.*]], [[A2:%.*]] -; CHECK-NEXT: [[A34:%.*]] = xor i8 [[A3:%.*]], [[A4:%.*]] -; CHECK-NEXT: [[A56:%.*]] = xor i8 [[A5:%.*]], [[A6:%.*]] -; CHECK-NEXT: [[A78:%.*]] = xor i8 [[A7:%.*]], [[A8:%.*]] -; CHECK-NEXT: [[A14:%.*]] = xor i8 [[A12]], [[A34]] -; CHECK-NEXT: [[A58:%.*]] = xor i8 [[A56]], [[A78]] -; CHECK-NEXT: [[A18:%.*]] = xor i8 [[A14]], [[A58]] -; CHECK-NEXT: [[A19:%.*]] = xor i8 [[A18]], [[A9:%.*]] -; CHECK-NEXT: [[A23:%.*]] = xor i8 [[A2]], [[A3]] -; CHECK-NEXT: [[A45:%.*]] = xor i8 [[A4]], [[A5]] -; CHECK-NEXT: [[A67:%.*]] = xor i8 [[A6]], [[A7]] -; CHECK-NEXT: [[A89:%.*]] = xor i8 [[A8]], [[A9]] -; CHECK-NEXT: [[A25:%.*]] = xor i8 [[A23]], [[A45]] -; CHECK-NEXT: [[A69:%.*]] = xor i8 [[A67]], [[A89]] -; CHECK-NEXT: [[A29:%.*]] = xor i8 [[A25]], [[A69]] -; CHECK-NEXT: [[R:%.*]] = xor i8 [[A19]], [[A29]] -; CHECK-NEXT: ret i8 [[R]] -; - %a12 = xor i8 %a1, %a2 - %a34 = xor i8 %a3, %a4 - %a56 = xor i8 %a5, %a6 - %a78 = xor i8 %a7, %a8 - %a14 = xor i8 %a12, %a34 - %a58 = xor i8 %a56, %a78 - %a18 = xor i8 %a14, %a58 - %a19 = xor i8 %a18, %a9 - %a23 = xor i8 %a2, %a3 - %a45 = xor i8 %a4, %a5 - %a67 = xor i8 %a6, %a7 - %a89 = xor i8 %a8, %a9 - %a25 = xor i8 %a23, %a45 - %a69 = xor i8 %a67, %a89 - %a29 = xor i8 %a25, %a69 - %r = xor i8 %a19, %a29 - ret i8 %r -} - -; Negative test case 2 for max leaf number: -; Constant value is also a leaf node. - -define i8 @leaf8_negative_leafnum_const(i8 %a1, i8 %a2) { -; CHECK-LABEL: @leaf8_negative_leafnum_const( -; CHECK-NEXT: [[AND1:%.*]] = and i8 [[A1:%.*]], 1 -; CHECK-NEXT: call void @use8(i8 [[AND1]]) -; CHECK-NEXT: [[AND2:%.*]] = and i8 [[A1]], 2 -; CHECK-NEXT: call void @use8(i8 [[AND2]]) -; CHECK-NEXT: [[AND3:%.*]] = and i8 [[A1]], 3 -; CHECK-NEXT: call void @use8(i8 [[AND3]]) -; CHECK-NEXT: [[AND4:%.*]] = and i8 [[A1]], 4 -; CHECK-NEXT: call void @use8(i8 [[AND4]]) -; CHECK-NEXT: [[AND5:%.*]] = and i8 [[A1]], 5 -; CHECK-NEXT: call void @use8(i8 [[AND5]]) -; CHECK-NEXT: [[AND6:%.*]] = and i8 [[A1]], 6 -; CHECK-NEXT: call void @use8(i8 [[AND6]]) -; CHECK-NEXT: [[AND7:%.*]] = and i8 [[A1]], 7 -; CHECK-NEXT: call void @use8(i8 [[AND7]]) -; CHECK-NEXT: [[R:%.*]] = xor i8 [[A2:%.*]], [[A2]] -; CHECK-NEXT: ret i8 [[R]] -; - %and1 = and i8 %a1, 1 - call void @use8(i8 %and1) - %and2 = and i8 %a1, 2 - call void @use8(i8 %and2) - %and3 = and i8 %a1, 3 - call void @use8(i8 %and3) - %and4 = and i8 %a1, 4 - call void @use8(i8 %and4) - %and5 = and i8 %a1, 5 - call void @use8(i8 %and5) - %and6 = and i8 %a1, 6 - call void @use8(i8 %and6) - %and7 = and i8 %a1, 7 - call void @use8(i8 %and7) - %r = xor i8 %a2, %a2 - ret i8 %r -} - -declare void @use8(i8) -- 2.7.4