#include "llvm/Transforms/Scalar.h"#include "llvm/ADT/DenseMap.h"#include "llvm/ADT/PostOrderIterator.h"#include "llvm/ADT/STLExtras.h"#include "llvm/ADT/SetVector.h"#include "llvm/ADT/Statistic.h"#include "llvm/IR/CFG.h"#include "llvm/IR/Constants.h"#include "llvm/IR/DerivedTypes.h"#include "llvm/IR/Function.h"#include "llvm/IR/IRBuilder.h"#include "llvm/IR/Instructions.h"#include "llvm/IR/IntrinsicInst.h"#include "llvm/IR/ValueHandle.h"#include "llvm/Pass.h"#include "llvm/Support/Debug.h"#include "llvm/Support/raw_ostream.h"#include "llvm/Transforms/Utils/Local.h"#include <algorithm>
Go to the source code of this file.
Define Documentation
| #define DEBUG_TYPE "reassociate" |
Definition at line 44 of file Reassociate.cpp.
Typedef Documentation
| typedef std::pair<Value*, APInt> RepeatedValue |
Definition at line 471 of file Reassociate.cpp.
Function Documentation
| static BinaryOperator* BreakUpSubtract | ( | Instruction * | Sub | ) | [static] |
BreakUpSubtract - If we have (X-Y), and if either X is an add, or if this is only used by an add, transform this into (X+(0-Y)) to promote better reassociation.
Definition at line 992 of file Reassociate.cpp.
References CreateAdd(), llvm::dbgs(), DEBUG, llvm::Constant::getNullValue(), llvm::User::getOperand(), NegateValue(), and llvm::User::setOperand().
| static Value* buildMultiplyTree | ( | IRBuilder<> & | Builder, |
| SmallVectorImpl< Value * > & | Ops | ||
| ) | [static] |
Build a tree of multiplies, computing the product of Ops.
Definition at line 1736 of file Reassociate.cpp.
References llvm::SmallVectorTemplateCommon< T, typename >::back(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateFMul(), llvm::IRBuilder< preserveNames, T, Inserter >::CreateMul(), llvm::SmallVectorBase::empty(), llvm::Value::getType(), llvm::Type::isIntegerTy(), llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateCommon< T, typename >::size().
| static unsigned CarmichaelShift | ( | unsigned | Bitwidth | ) | [static] |
CarmichaelShift - Returns k such that lambda(2^Bitwidth) = 2^k, where lambda is the Carmichael function. This means that x^(2^k) === 1 mod 2^Bitwidth for every odd x, i.e. x^(2^k) = 1 for every odd x in Bitwidth-bit arithmetic. Note that 0 <= k < Bitwidth, and if Bitwidth > 3 then x^(2^k) = 0 for every even x in Bitwidth-bit arithmetic.
Definition at line 385 of file Reassociate.cpp.
Referenced by IncorporateWeight().
| static BinaryOperator* ConvertShiftToMul | ( | Instruction * | Shl | ) | [static] |
ConvertShiftToMul - If this is a shift of a reassociable multiply or is used by one, change this into a multiply by a constant to assist with further reassociation.
Definition at line 1016 of file Reassociate.cpp.
References CreateMul(), llvm::ConstantInt::get(), llvm::UndefValue::get(), llvm::Instruction::getDebugLoc(), llvm::User::getOperand(), llvm::ConstantExpr::getShl(), llvm::Value::getType(), llvm::Value::replaceAllUsesWith(), llvm::Instruction::setDebugLoc(), llvm::User::setOperand(), and llvm::Value::takeName().
| static BinaryOperator* CreateAdd | ( | Value * | S1, |
| Value * | S2, | ||
| const Twine & | Name, | ||
| Instruction * | InsertBefore, | ||
| Value * | FlagsOp | ||
| ) | [static] |
Definition at line 330 of file Reassociate.cpp.
References llvm::Value::getType(), llvm::Type::isIntegerTy(), and llvm::Instruction::setFastMathFlags().
Referenced by BreakUpSubtract(), EmitAddTreeOfValues(), llvm::X86AsmPrinter::EmitInstruction(), llvm::AsmPrinter::EmitLabelOffsetDifference(), llvm::AsmPrinter::EmitLabelPlusOffset(), llvm::ARMAsmPrinter::EmitMachineConstantPoolValue(), llvm::SystemZMCInstLower::getExpr(), llvm::X86_64MCAsmInfoDarwin::getExprForPersonalitySymbol(), llvm::X86_64MachoTargetObjectFile::getTTypeGlobalReference(), LLVMBuildAdd(), nvptx::LowerConstant(), llvm::AArch64ExternalSymbolizer::tryAddingSymbolicOperand(), llvm::MCExternalSymbolizer::tryAddingSymbolicOperand(), llvm::InstCombiner::visitAdd(), llvm::InstCombiner::visitExtractValueInst(), llvm::InstCombiner::visitMul(), llvm::InstCombiner::visitSelectInst(), llvm::InstCombiner::visitSub(), and llvm::InstCombiner::visitXor().
| static Value* createAndInstr | ( | Instruction * | InsertBefore, |
| Value * | Opnd, | ||
| const APInt & | ConstOpnd | ||
| ) | [static] |
Helper funciton of CombineXorOpnd(). It creates a bitwise-and instruction with the given two operands, and return the resulting instruction. There are two special cases: 1) if the constant operand is 0, it will return NULL. 2) if the constant is ~0, the symbolic operand will be returned.
Definition at line 1204 of file Reassociate.cpp.
References llvm::ConstantInt::get(), llvm::Type::getContext(), llvm::Instruction::getDebugLoc(), llvm::Value::getType(), I, llvm::APInt::isAllOnesValue(), and llvm::Instruction::setDebugLoc().
| static BinaryOperator* CreateMul | ( | Value * | S1, |
| Value * | S2, | ||
| const Twine & | Name, | ||
| Instruction * | InsertBefore, | ||
| Value * | FlagsOp | ||
| ) | [static] |
Definition at line 342 of file Reassociate.cpp.
References llvm::Value::getType(), llvm::Type::isIntegerTy(), and llvm::Instruction::setFastMathFlags().
Referenced by ConvertShiftToMul(), createMalloc(), llvm::InstCombiner::FoldShiftByConstant(), LLVMBuildMul(), nvptx::LowerConstant(), LowerNegateToMultiply(), llvm::InstCombiner::visitExtractValueInst(), and llvm::InstCombiner::visitMul().
| static BinaryOperator* CreateNeg | ( | Value * | S1, |
| const Twine & | Name, | ||
| Instruction * | InsertBefore, | ||
| Value * | FlagsOp | ||
| ) | [static] |
Definition at line 354 of file Reassociate.cpp.
References llvm::BinaryOperator::CreateFNeg(), llvm::BinaryOperator::CreateNeg(), llvm::Value::getType(), llvm::Type::isIntegerTy(), and llvm::Instruction::setFastMathFlags().
Referenced by LLVMBuildNeg(), NegateValue(), llvm::InstCombiner::visitAdd(), llvm::InstCombiner::visitMul(), and llvm::InstCombiner::visitSDiv().
| static Value* EmitAddTreeOfValues | ( | Instruction * | I, |
| SmallVectorImpl< WeakVH > & | Ops | ||
| ) | [static] |
EmitAddTreeOfValues - Emit a tree of add instructions, summing Ops together and returning the result. Insert the tree before I.
Definition at line 1049 of file Reassociate.cpp.
References llvm::SmallVectorTemplateCommon< T, typename >::back(), CreateAdd(), llvm::SmallVectorTemplateBase< T, isPodLike >::pop_back(), llvm::SmallVectorTemplateCommon< T, typename >::size(), and llvm::NVPTX::PTXLdStInstCode::V2.
| static unsigned FindInOperandList | ( | SmallVectorImpl< ValueEntry > & | Ops, |
| unsigned | i, | ||
| Value * | X | ||
| ) | [static] |
FindInOperandList - Scan backwards and forwards among values with the same rank as element i to see if X exists. If X does not exist, return i. This is useful when scanning for 'x' when we see '-x' because they both get the same rank.
Definition at line 1033 of file Reassociate.cpp.
References llvm::SmallVectorTemplateCommon< T >::size().
Referenced by OptimizeAndOrXor().
| static void FindSingleUseMultiplyFactors | ( | Value * | V, |
| SmallVectorImpl< Value * > & | Factors, | ||
| const SmallVectorImpl< ValueEntry > & | Ops | ||
| ) | [static] |
FindSingleUseMultiplyFactors - If V is a single-use multiply, recursively add its operands as factors, otherwise add V to the list of factors.
Ops is the top-level list of add operands we're trying to factor.
Definition at line 1136 of file Reassociate.cpp.
References llvm::User::getOperand(), isReassociableOp(), and llvm::SmallVectorTemplateBase< T, isPodLike >::push_back().
| static void IncorporateWeight | ( | APInt & | LHS, |
| const APInt & | RHS, | ||
| unsigned | Opcode | ||
| ) | [static] |
IncorporateWeight - Add the extra weight 'RHS' to the existing weight 'LHS', reducing the combined weight using any special properties of the operation. The existing weight LHS represents the computation X op X op ... op X where X occurs LHS times. The combined weight represents X op X op ... op X with X occurring LHS + RHS times. If op is "Xor" for example then the combined operation is equivalent to X if LHS + RHS is odd, or 0 if LHS + RHS is even; the routine returns 1 in LHS in the first case, and 0 in LHS in the second.
CM - The value of Carmichael's lambda function.
Definition at line 398 of file Reassociate.cpp.
References CarmichaelShift(), llvm::APInt::getBitWidth(), llvm::APInt::getOneBitSet(), llvm::APInt::getZExtValue(), llvm::Instruction::isIdempotent(), llvm::APInt::isMinValue(), llvm::Instruction::isNilpotent(), Threshold, and llvm::APInt::ult().
Referenced by LinearizeExprTree().
| INITIALIZE_PASS | ( | Reassociate | , |
| "reassociate" | , | ||
| "Reassociate expressions" | , | ||
| false | , | ||
| false | |||
| ) |
Definition at line 230 of file Reassociate.cpp.
| static BinaryOperator* isReassociableOp | ( | Value * | V, |
| unsigned | Opcode | ||
| ) | [static] |
isReassociableOp - Return true if V is an instruction of the specified opcode and if it only has one use.
Definition at line 238 of file Reassociate.cpp.
References llvm::Value::hasOneUse().
Referenced by FindSingleUseMultiplyFactors(), LinearizeExprTree(), NegateValue(), and ShouldBreakUpSubtract().
| static BinaryOperator* isReassociableOp | ( | Value * | V, |
| unsigned | Opcode1, | ||
| unsigned | Opcode2 | ||
| ) | [static] |
Definition at line 245 of file Reassociate.cpp.
References llvm::Value::hasOneUse().
| static bool isUnmovableInstruction | ( | Instruction * | I | ) | [static] |
Definition at line 254 of file Reassociate.cpp.
References llvm::Alloca, llvm::Call, llvm::Instruction::getOpcode(), I, llvm::LandingPad, llvm::SPII::Load, and llvm::TargetOpcode::PHI.
| static bool LinearizeExprTree | ( | BinaryOperator * | I, |
| SmallVectorImpl< RepeatedValue > & | Ops | ||
| ) | [static] |
LinearizeExprTree - Given an associative binary expression, return the leaf nodes in Ops along with their weights (how many times the leaf occurs). The original expression is the same as (Ops[0].first op Ops[0].first op ... Ops[0].first) <- Ops[0].second times op (Ops[1].first op Ops[1].first op ... Ops[1].first) <- Ops[1].second times op ... op (Ops[N].first op Ops[N].first op ... Ops[N].first) <- Ops[N].second times
Note that the values Ops[0].first, ..., Ops[N].first are all distinct.
This routine may modify the function, in which case it returns 'true'. The changes it makes may well be destructive, changing the value computed by 'I' to something completely different. Thus if the routine returns 'true' then you MUST either replace I with a new expression computed from the Ops array, or use RewriteExprTree to put the values back in.
A leaf node is either not a binary operation of the same kind as the root node 'I' (i.e. is not a binary operator at all, or is, but with a different opcode), or is the same kind of binary operator but has a use which either does not belong to the expression, or does belong to the expression but is a leaf node. Every leaf node has at least one use that is a non-leaf node of the expression, while for non-leaf nodes (except for the root 'I') every use is a non-leaf node of the expression.
For example: expression graph node names
+ | I / \ | + + | A, B / \ / \ | + * | C, D, E / \ / \ / \ | + * | F, G
The leaf nodes are C, E, F and G. The Ops array will contain (maybe not in that order) (C, 1), (E, 1), (F, 2), (G, 2).
The expression is maximal: if some instruction is a binary operator of the same kind as 'I', and all of its uses are non-leaf nodes of the expression, then the instruction also belongs to the expression, is not a leaf node of it, and its operands also belong to the expression (but may be leaf nodes).
NOTE: This routine will set operands of non-leaf non-root nodes to undef in order to ensure that every non-root node in the expression has *exactly one* use by a non-leaf node of the expression. This destruction means that the caller MUST either replace 'I' with a new expression or use something like RewriteExprTree to put the values back in if the routine indicates that it made a change by returning 'true'.
In the above example either the right operand of A or the left operand of B will be replaced by undef. If it is B's operand then this gives:
+ | I / \ | + + | A, B - operand of B replaced with undef / \ \ | + * | C, D, E / \ / \ / \ | + * | F, G
Note that such undef operands can only be reached by passing through 'I'. For example, if you visit operands recursively starting from a leaf node then you will never see such an undef operand unless you get back to 'I', which requires passing through a phi node.
Note that this routine may also mutate binary operators of the wrong type that have all uses inside the expression (i.e. only used by non-leaf nodes of the expression) if it can turn them into binary operators of the right type and thus make the expression bigger.
Definition at line 547 of file Reassociate.cpp.
References llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), DEBUG, llvm::SmallVectorBase::empty(), llvm::UndefValue::get(), llvm::ConstantExpr::getBinOpIdentity(), llvm::BinaryOperator::getOpcode(), llvm::User::getOperand(), llvm::Type::getPrimitiveSizeInBits(), llvm::Type::getScalarType(), llvm::Value::getType(), llvm::Value::hasOneUse(), IncorporateWeight(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::Instruction::isAssociative(), llvm::Instruction::isCommutative(), llvm::BinaryOperator::isFNeg(), llvm::APInt::isMinValue(), llvm::BinaryOperator::isNeg(), isReassociableOp(), LowerNegateToMultiply(), P, llvm::SmallVectorTemplateBase< T, isPodLike >::push_back(), llvm::SmallVectorTemplateBase< T, isPodLike< T >::value >::push_back(), llvm::User::setOperand(), llvm::SmallVectorTemplateCommon< T >::size(), and llvm::Value::use_empty().
| static BinaryOperator* LowerNegateToMultiply | ( | Instruction * | Neg | ) | [static] |
LowerNegateToMultiply - Replace 0-X with X*-1.
Definition at line 367 of file Reassociate.cpp.
References CreateMul(), llvm::ConstantFP::get(), llvm::Constant::getAllOnesValue(), llvm::Constant::getNullValue(), llvm::User::getOperand(), llvm::Value::getType(), llvm::Type::isIntegerTy(), llvm::Instruction::setDebugLoc(), llvm::User::setOperand(), and llvm::Value::takeName().
Referenced by LinearizeExprTree().
| static Value* NegateValue | ( | Value * | V, |
| Instruction * | BI | ||
| ) | [static] |
NegateValue - Insert instructions before the instruction pointed to by BI, that computes the negative version of the value specified. The negative version of the value is returned, and BI is left pointing at the instruction that should be processed next by the reassociation pass.
Definition at line 895 of file Reassociate.cpp.
References llvm::BasicBlock::begin(), llvm::CallingConv::C, CreateNeg(), llvm::Function::getEntryBlock(), llvm::ConstantExpr::getFNeg(), llvm::Value::getName(), llvm::ConstantExpr::getNeg(), llvm::User::getOperand(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), I, llvm::BinaryOperator::isFNeg(), llvm::BinaryOperator::isNeg(), isReassociableOp(), llvm::Instruction::moveBefore(), llvm::Value::setName(), llvm::User::setOperand(), and llvm::Value::users().
Referenced by BreakUpSubtract().
| static Value* OptimizeAndOrXor | ( | unsigned | Opcode, |
| SmallVectorImpl< ValueEntry > & | Ops | ||
| ) | [static] |
OptimizeAndOrXor - Optimize a series of operands to an 'and', 'or', or 'xor' instruction. This optimizes based on identities. If it can be reduced to a single Value, it is returned, otherwise the Ops list is mutated as necessary.
Definition at line 1154 of file Reassociate.cpp.
References llvm::APIntOps::And(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::SmallVectorImpl< T >::erase(), FindInOperandList(), llvm::Constant::getAllOnesValue(), llvm::BinaryOperator::getNotArgument(), llvm::Constant::getNullValue(), llvm::Value::getType(), llvm::BinaryOperator::isNot(), llvm::APIntOps::Or(), llvm::SmallVectorTemplateCommon< T >::size(), llvm::X, and llvm::APIntOps::Xor().
| static void PrintOps | ( | Instruction * | I, |
| const SmallVectorImpl< ValueEntry > & | Ops | ||
| ) | [static] |
PrintOps - Print out the expression identified in the Ops list.
Definition at line 64 of file Reassociate.cpp.
References llvm::dbgs(), llvm::Instruction::getOpcode(), llvm::Instruction::getOpcodeName(), llvm::Instruction::getParent(), llvm::BasicBlock::getParent(), llvm::GlobalValue::getParent(), and llvm::SmallVectorTemplateCommon< T >::size().
| static bool ShouldBreakUpSubtract | ( | Instruction * | Sub | ) | [static] |
ShouldBreakUpSubtract - Return true if we should break up this subtract of X-Y into (X + -Y).
Definition at line 965 of file Reassociate.cpp.
References llvm::User::getOperand(), llvm::Value::hasOneUse(), llvm::BinaryOperator::isFNeg(), llvm::BinaryOperator::isNeg(), isReassociableOp(), and llvm::Instruction::user_back().
| STATISTIC | ( | NumChanged | , |
| "Number of insts reassociated" | |||
| ) |
| STATISTIC | ( | NumAnnihil | , |
| "Number of expr tree annihilated" | |||
| ) |
| STATISTIC | ( | NumFactor | , |
| "Number of multiplies factored" | |||
| ) |
1.7.6.1