LLVM: lib/Transforms/Scalar/Reassociate.cpp File Reference (original) (raw)

Go to the source code of this file.

◆ DEBUG_TYPE

#define DEBUG_TYPE "reassociate"

◆ RepeatedValue

◆ BreakUpSubtract()

◆ buildMultiplyTree()

◆ collectMultiplyFactors()

Build up a vector of value/power pairs factoring a product.

Given a series of multiplication operands, build a vector of factors and the powers each is raised to when forming the final product. Sort them in the order of descending power.

(xx) -> [(x, 2)] ((xx)*x) -> [(x, 3)]

((((x*y)*x)*y)*x) -> [(x, 3), (y, 2)]

Returns

Whether any factors have a power greater than one.

Definition at line 1727 of file Reassociate.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, assert(), llvm::Count, LHS, llvm::SmallVectorTemplateBase< T, bool >::push_back(), RHS, Size, and llvm::stable_sort().

◆ convertOrWithNoCommonBitsToAdd()

◆ 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 1024 of file Reassociate.cpp.

References assert(), llvm::BitWidth, llvm::cast(), llvm::ConstantFoldBinaryInstruction(), llvm::PoisonValue::get(), llvm::Instruction::getDebugLoc(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::User::getOperand(), llvm::Type::getScalarSizeInBits(), llvm::Value::getType(), Mul, llvm::Value::replaceAllUsesWith(), and llvm::User::setOperand().

◆ CreateAdd()

◆ createAndInstr()

◆ CreateMul()

◆ CreateNeg()

◆ EmitAddTreeOfValues()

◆ FindInOperandList()

◆ FindSingleUseMultiplyFactors()

◆ getNegatibleInsts()

Recursively analyze an expression to build a list of instructions that have negative floating-point constant operands.

The caller can then transform the list to create positive constants for better reassociation and CSE.

Definition at line 2016 of file Reassociate.cpp.

References llvm::CallingConv::C, llvm::dbgs(), getNegatibleInsts(), I, LLVM_DEBUG, llvm::PatternMatch::m_APFloat(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_Instruction(), llvm::MIPatternMatch::m_OneUse(), llvm::PatternMatch::match(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

Referenced by getNegatibleInsts().

◆ hasFPAssociativeFlags()

◆ INITIALIZE_PASS()

◆ isLoadCombineCandidate()

◆ isReassociableOp() [1/2]

◆ isReassociableOp() [2/2]

◆ 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 382 of file Reassociate.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, assert(), llvm::cast(), Changed, llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), DL, llvm::dyn_cast(), llvm::SmallVectorTemplateCommon< T, typename >::empty(), llvm::ConstantExpr::getBinOpIdentity(), getOpcode(), hasFPAssociativeFlags(), I, llvm::SetVector< T, Vector, Set, N >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::isa(), llvm::isKnownNonNegative(), llvm::isKnownNonZero(), isReassociableOp(), LLVM_DEBUG, LowerNegateToMultiply(), llvm::PatternMatch::m_FNeg(), llvm::PatternMatch::m_Instruction(), llvm::MIPatternMatch::m_Neg(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), Mul, OpIdx, llvm::SmallVectorImpl< T >::pop_back_val(), and llvm::SmallVectorTemplateBase< T, bool >::push_back().

◆ LowerNegateToMultiply()

Replace 0-X with X*-1.

Definition at line 289 of file Reassociate.cpp.

References assert(), CreateMul(), llvm::Constant::getAllOnesValue(), llvm::Instruction::getDebugLoc(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::Constant::getNullValue(), llvm::User::getOperand(), llvm::Value::getType(), llvm::isa(), llvm::Value::replaceAllUsesWith(), llvm::Instruction::setDebugLoc(), llvm::User::setOperand(), and llvm::Value::takeName().

Referenced by LinearizeExprTree().

◆ 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. Also add intermediate instructions to the redo list that are modified while pushing the negates through adds. These will be revisited to see if additional opportunities have been exposed.

Definition at line 767 of file Reassociate.cpp.

References llvm::Instruction::andIRFlags(), llvm::CallingConv::C, llvm::ConstantFoldUnaryOpOperand(), CreateNeg(), DL, llvm::Instruction::dropLocation(), llvm::dyn_cast(), llvm::Instruction::getDataLayout(), llvm::Instruction::getDebugLoc(), llvm::Function::getEntryBlock(), llvm::BasicBlock::getFirstNonPHIOrDbg(), llvm::Instruction::getFunction(), llvm::ilist_node_impl< OptionsT >::getIterator(), llvm::ConstantExpr::getNeg(), llvm::Instruction::getOpcode(), llvm::ilist_detail::node_parent_access< NodeTy, ParentTy >::getParent(), I, llvm::SetVector< T, Vector, Set, N >::insert(), isReassociableOp(), llvm::PatternMatch::m_BinOp(), llvm::PatternMatch::m_Constant(), llvm::PatternMatch::m_FNeg(), llvm::MIPatternMatch::m_Neg(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), llvm::Instruction::moveBefore(), NegateValue(), llvm::Instruction::setDebugLoc(), llvm::Instruction::setHasNoSignedWrap(), llvm::Instruction::setHasNoUnsignedWrap(), and llvm::Value::users().

Referenced by BreakUpSubtract(), and NegateValue().

◆ 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 1188 of file Reassociate.cpp.

References AbstractManglingParser< Derived, Alloc >::Ops, assert(), FindInOperandList(), llvm::Constant::getAllOnesValue(), llvm::Constant::getNullValue(), llvm::MIPatternMatch::m_Not(), llvm::PatternMatch::m_Value(), llvm::PatternMatch::match(), and X.

◆ PrintOps()

◆ ShouldBreakUpSubtract()

◆ shouldConvertOrWithNoCommonBitsToAdd()

◆ STATISTIC() [1/3]

◆ STATISTIC() [2/3]

◆ STATISTIC() [3/3]

◆ UseCSELocalOpt