From d7aeefebd6b049f017711cd7c6ef5f217a17b673 Mon Sep 17 00:00:00 2001 From: Duncan Sands Date: Tue, 12 Jun 2012 14:33:56 +0000 Subject: Now that Reassociate's LinearizeExprTree can look through arbitrary expression topologies, it is quite possible for a leaf node to have huge multiplicity, for example: x0 = x*x, x1 = x0*x0, x2 = x1*x1, ... rapidly gives a value which is x raised to a vast power (the multiplicity, or weight, of x). This patch fixes the computation of weights by correctly computing them no matter how big they are, rather than just overflowing and getting a wrong value. It turns out that the weight for a value never needs more bits to represent than the value itself, so it is enough to represent weights as APInts of the same bitwidth and do the right overflow-avoiding dance steps when computing weights. As a side-effect it reduces the number of multiplies needed in some cases of large powers. While there, in view of external uses (eg by the vectorizer) I made LinearizeExprTree static, pushing the rank computation out into users. This is progress towards fixing PR13021. llvm-svn: 158358 --- llvm/lib/VMCore/Instruction.cpp | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) (limited to 'llvm/lib/VMCore/Instruction.cpp') diff --git a/llvm/lib/VMCore/Instruction.cpp b/llvm/lib/VMCore/Instruction.cpp index c1d63877575..faa99db4fcb 100644 --- a/llvm/lib/VMCore/Instruction.cpp +++ b/llvm/lib/VMCore/Instruction.cpp @@ -395,6 +395,29 @@ bool Instruction::isCommutative(unsigned op) { } } +/// isIdempotent - Return true if the instruction is idempotent: +/// +/// Idempotent operators satisfy: x op x === x +/// +/// In LLVM, the And and Or operators are idempotent. +/// +bool Instruction::isIdempotent(unsigned Opcode) { + return Opcode == And || Opcode == Or; +} + +/// isNilpotent - Return true if the instruction is nilpotent: +/// +/// Nilpotent operators satisfy: x op x === Id, +/// +/// where Id is the identity for the operator, i.e. a constant such that +/// x op Id === x and Id op x === x for all x. +/// +/// In LLVM, the Xor operator is nilpotent. +/// +bool Instruction::isNilpotent(unsigned Opcode) { + return Opcode == Xor; +} + Instruction *Instruction::clone() const { Instruction *New = clone_impl(); New->SubclassOptionalData = SubclassOptionalData; -- cgit v1.2.3