Lines Matching refs:And
35 // TODO: We should use these routines and value representations to implement
55 // Using the chains of recurrences algebra for data dependence testing and
477 // so that (a + b) and (b + a) don't end up as different expressions.
507 // For instructions, compare their loop depth, and their operand
624 /// complexity, and group objects of the same complexity together by value.
626 /// consecutive and that complexity is monotonically increasing.
656 // If there are any objects of the same complexity and same value as this
695 // Computes the Quotient and Remainder of the division of Numerator by
909 // be equal to zero and the remainder to be equal to the numerator.
945 // K! (i.e. trailing zeros in the binary representation of K!), and ^ is
952 // K! / 2^T is odd, and exact division by an odd number *is* safe in modular
967 // a division step, whereas this formula only requires multiplies and shifts.
980 // extra arithmetic, so it's not an obvious win, and it gets
990 // Calculate K! / 2^T and T; we divide out the factors of two before
1031 // Truncate the result, and divide by K! / 2^T.
1186 // Used to make code generic over signed and unsigned overflow.
1255 // subtraction is expensive. For this purpose, perform a quick and dirty
1275 // "{S,+,X} is <nsw>/<nuw>" and "the backedge is taken at least once" implies
1293 // or FlagNUW) and that `PreStart` + `Step` is `WrapType` too, then
1327 // motivating example for this rule: if we know `{0,+,4}` is `ult` `-1` and it
1349 // Thus, if (1), (2) and (3) are true for some T, then
1354 // to check for (1) and (2).
1356 // In the current context, S is `Start`, X is `Step`, Ext is `ExtendOpTy` and T
1367 // non-constant `Start` and do a general SCEV subtraction to compute
1421 // computed a SCEV for this Op and Ty.
1442 // If the input value is a chrec scev, and we can prove that the value
1462 // simply not analyzable, and it covers the case where this code is
1466 // cope with a conservative value, and it will take care to purge
1518 // with the start value and the backedge is guarded by a comparison
1603 // computed a SCEV for this Op and Ty.
1655 // If the input value is a chrec scev, and we can prove that the value
1675 // simply not analyzable, and it covers the case where this code is
1679 // cope with a conservative value, and it will take care to purge
1738 // with the start value and the backedge is guarded by a comparison
1755 // If Start and Step are constants, check if we can apply this
1847 /// where A and B are constants, update the map with these values:
1851 /// and add 13 + A*B*29 to AccumulatedConstant.
1861 /// the common case where no interesting opportunities are present, and
1930 // We're trying to construct a SCEV of type `Type' with `Ops' as operands and
1949 // If FlagNSW is true and all the operands are non-negative, infer FlagNUW.
2121 // and they are not necessarily sorted. Recurse to resort and resimplify
2250 // Scan all of the other operands to this add and add them to the vector if
2271 // Build the new addrec. Propagate the NUW and NSW flags if both the
2272 // outer add and the inner addrec are guaranteed to have no overflow.
2351 /// intermediate computation overflows, Overflow will be set and the return will
2356 // At each iteration, we take the n-th term of the numeral and divide by the
2358 // integral result, and helps reduce the chance of overflow in the
2492 // and they are not necessarily sorted. Recurse to resort and resimplify
2506 // Scan all of the other operands to this mul and add them to the vector if
2527 // Build the new addrec. Propagate the NUW and NSW flags if both the
2528 // outer mul and the inner addrec are guaranteed to have no overflow.
2665 // {X,+,N}/C --> {X/C,+,N/C} if safe and N/C can be folded.
2694 // (A*B)/C --> A*(B/C) if safe and B/C can be folded.
2712 // (A+B)/C --> (A/C + B/C) if safe and A/C and B/C can be folded.
2769 /// in SCEV IR, but we can attempt to remove factors from the LHS and RHS.
2862 // It's tempting to want to call getMaxBackedgeTakenCount count here and
2863 // use that information to infer NUW and NSW flags. However, computing a
2865 // meaningful BE count at this point (and if we don't, we'd be stuck
2944 // flow and the no-overflow bits may not be valid for the expression in any
3041 // onto our operand list, and recurse to simplify.
3144 // onto our operand list, and recurse to simplify.
3206 // constant expression and then folding it back into a ConstantInt.
3215 // constant expression and then folding it back into a ConstantInt.
3224 // interesting possibilities, and any other code that calls getUnknown
3244 // Basic SCEV Analysis and PHI Idiom Recognition Code
3248 /// the SCEV framework. This primarily includes integer types, and it
3252 // Integers and pointers are always SCEVable.
3264 /// the given type and which represents how SCEV will treat the given
3314 /// expression and create a new one.
3380 // signed-wraps if and only if RHS is M. That can happen even for
3385 // If LHS is non-negative and we know that LHS - RHS does not
3394 // RHS is NSW and LHS >= 0.
3397 // relative to a loop that is to be found in a recurrence in LHS and
3503 /// the types using zero-extension, and then perform a umax operation
3519 /// the types using zero-extension, and then perform a umin operation
3573 /// instructions that depend on the given instruction and removes them from
3689 // this phi as an addrec if it has a unique entry value and a unique
3774 // We cannot transfer nuw and nsw flags from subtraction
3788 // to be symbolic. We now need to go back and purge all of the
3798 // In this case, j = {1,+,1} and BEValue is j.
3812 // to be symbolic. We now need to go back and purge all of the
3898 // Try to match a control flow sequence that branches out at BI and merges back
3992 // loop pass transforms an inner loop and moves on to process the outer loop.
4086 /// createNodeForGEP - Expand GEP instructions into add and multiply
4291 // If there's no signed wrap, and all the operands have the same sign or
4385 // computeKnownBits and ComputeNumSignBits. This restriction can be lifted
4446 // loop that V is considered in relation to and prove that V is executed for
4479 // reachable. Such instructions don't matter, and they aren't required
4499 // and call getAddExpr with the result. However if we're looking at a
4502 // Instead, gather up all the operands and make a single getAddExpr call.
4577 case Instruction::And:
4620 // form X*(2^n) and the Or constant must be less than 2^n.
4628 // If the LHS of the add was an addrec and it has no-wrap flags,
4651 // Model xor(and(x, C), C) as and(~x, C), if C is a low-bits mask.
4652 // This is a variant of the check for xor with -1, and it handles
4657 if (BO->getOpcode() == Instruction::And &&
4667 // mask off the high bits. Complement the operand and
4674 // using an add, which is equivalent, and re-apply the zext.
4701 // and http://reviews.llvm.org/D8890 .
4770 // It's tempting to handle inttoptr and ptrtoint as no-ops, however this can
4783 // createNodeForSelect only works for a condition that is an `ICmpInst`, and
4885 // for zero to handle the case where the trip count == -1 and the
4938 // succeeds, proceed to actually compute a backedge-taken count and
5150 /// Allocate memory for BackedgeTakenInfo and copy the not-taken count of each
5177 /// clear - Invalidate this result and free the ExitNotTakenInfo array.
5198 // and compute maxBECount.
5214 // LoopMustExits and LoopMayExits.
5247 // at this block and remember the exit block and whether all other targets
5290 // If the predecessor has a successor that isn't BB and isn't
5324 /// were a conditional branch of ExitCond, TBB, and FBB.
5328 /// condition is true and can infer that failing to meet the condition prior to
5336 // Check if the controlling expression for this loop is an And or Or.
5338 if (BO->getOpcode() == Instruction::And) {
5339 and.
5417 // preserve the CFG and is temporarily leaving constant conditions
5576 // initializer, and make sure the first IDX is really 0.
5653 // Return LHS in OutLHS and shift_opt in OutOpCode.
5679 // above) in PNOut and the opcode of the shift operation in OpCodeOut.
5689 // and remember that we did so. Later when we inspect %iv's backedge
5718 // and the kind of shift should be match the kind of shift we peeled
5761 // Both {K,lshr,<positive-constant>} and {K,shl,<positive-constant>}
5835 // Recurse and memoize the results, whether a phi is found or not.
5850 /// getConstantEvolvingPHI - Given an LLVM value and a loop, return a PHI node
5943 /// constant number of times, and the PHI node is just a recurrence
6260 // the arguments into constants, and if so, try to constant propagate the
6271 // If any of the operands is non-constant and if they are
6272 // non-integer and non-pointer, don't even try to analyze them
6378 // ahead and return the folded value.
6434 /// where N = 2^BW and BW is the common bit width of A and B. The signedness of
6435 /// A and B isn't important.
6446 // The gcd of A and N may have only one prime factor: 2. The number of
6453 // B is divisible by D if and only if the multiplicity of prime factor 2 for B
6553 /// effectively V != 0. We know and take advantage of the fact that this
6608 // where BW is the common bit width of Start and Step.
6651 // done by counting and comparing the number of trailing zeros of Step and
6664 // where we're operating on a W bit wide integer domain and k is
6693 // and a zero extend.
6704 // is true) and the addition is no-wrap we can use unsigned divide to
6739 // this, and if they did, they would already be constant folded.
6778 // identical and do not read memory; but compute distinct values.
6795 /// SimplifyICmpOperands - Simplify LHS and RHS in a comparison with
6837 // cases, and canonicalize *-or-equal comparisons to regular comparisons.
7100 // If LHS and RHS are both addrec, both conditions must be true in
7139 // increasing change to a monotonically decreasing one, and vice versa.
7159 // flipping from false to true (for increasing predicates, and the other way
7231 // true as the loop iterates, and the backedge is control dependent on
7246 // replacing true with false and false with true in the above two bullets.
7403 // expensive; and using isKnownNonNegative(RHS) is sufficient for most of the
7412 /// protected by a conditional between LHS and RHS. This is used to
7499 // We're constructively (and conservatively) enumerating edges within the
7514 /// by a conditional between LHS and RHS. This is used to help avoid max
7515 /// expressions in loop trip counts, and to eliminate casts.
7582 /// and RHS is true whenever the given Cond value evaluates to true.
7591 // Recursively handle And and Or conditions.
7593 if (BO->getOpcode() == Instruction::And) {
7871 // (A s< 0, B s< 0), (A s< 0, B s>= 0), (A s>= 0, B s< 0) and
7877 // = (i8 -127) and C = (i8 -100). Then INT_MIN - C = (i8 -28), and FoundRHS
7906 /// LHS, and RHS is true whenever the condition described by Pred, FoundLHS,
7907 /// and FoundRHS is true.
7943 /// Is MaybeMaxExpr an SMax or UMax of Candidate and some other values?
7954 /// Is MaybeMinExpr an SMin or UMin of Candidate and some other values?
7971 // steps, and we know the recurrences don't wrap, then we only
8033 /// Pred, LHS, and RHS is true whenever the condition described by Pred,
8034 /// FoundLHS, and FoundRHS is true.
8126 // stride and the knowledge of NSW/NUW flags on the recurrence.
8155 // the stride and the knowledge of NSW/NUW flags on the recurrence.
8183 // stride and presence of the equality in the comparison.
8381 // This is strange and shouldn't happen.
8390 // Okay at this point we know that all elements of the chrec are constants and
8533 // Collect all SCEVUnknown and SCEVMulExpr expressions.
8914 /// Splits the SCEV into two vectors of SCEVs representing the subscripts and
8918 /// expressions in the stride and base of a SCEV corresponding to the
8919 /// computation of a GCD (greatest common divisor) of base and stride. When
8942 /// and then SCEV->delinearize determines the size of some of the dimensions of
8959 /// DelinearizationPass that walks through all loads and stores of a function
8961 /// loops, calling SCEV->delinearize on that and printing the results.
9077 // Iterate through all the SCEVUnknown instances and call their
9330 // produces the addrec's value is a PHI, and a PHI effectively properly
9450 // false and 0 are semantically equivalent. This can happen in dead loops.
9477 // Now compare whether they're the same with and without caches. This allows
9708 // If we already have an entry and the version matches, return it.