Model zext-extend instructions

Model zext-extend instructions

  A zero-extended value can be interpreted as a piecewise defined signed
  value. If the value was non-negative it stays the same, otherwise it
  is the sum of the original value and 2^n where n is the bit-width of
  the original (or operand) type. Examples:
    zext i8 127 to i32 -> { [127] }
    zext i8  -1 to i32 -> { [256 + (-1)] } = { [255] }
    zext i8  %v to i32 -> [v] -> { [v] | v >= 0; [256 + v] | v < 0 }

  However, LLVM/Scalar Evolution uses zero-extend (potentially lead by a
  truncate) to represent some forms of modulo computation. The left-hand side
  of the condition in the code below would result in the SCEV
  "zext i1 <false, +, true>for.body" which is just another description
  of the C expression "i & 1 != 0" or, equivalently, "i % 2 != 0".

    for (i = 0; i < N; i++)
      if (i & 1 != 0 /* == i % 2 */)
        /* do something */

  If we do not make the modulo explicit but only use the mechanism described
  above we will get the very restrictive assumption "N < 3", because for all
  values of N >= 3 the SCEVAddRecExpr operand of the zero-extend would wrap.
  Alternatively, we can make the modulo in the operand explicit in the
  resulting piecewise function and thereby avoid the assumption on N. For the
  example this would result in the following piecewise affine function:
  { [i0] -> [(1)] : 2*floor((-1 + i0)/2) = -1 + i0;
    [i0] -> [(0)] : 2*floor((i0)/2) = i0 }
  To this end we can first determine if the (immediate) operand of the
  zero-extend can wrap and, in case it might, we will use explicit modulo
  semantic to compute the result instead of emitting non-wrapping assumptions.

  Note that operands with large bit-widths are less likely to be negative
  because it would result in a very large access offset or loop bound after the
  zero-extend. To this end one can optimistically assume the operand to be
  positive and avoid the piecewise definition if the bit-width is bigger than
  some threshold (here MaxZextSmallBitWidth).

  We choose to go with a hybrid solution of all modeling techniques described
  above. For small bit-widths (up to MaxZextSmallBitWidth) we will model the
  wrapping explicitly and use a piecewise defined function. However, if the
  bit-width is bigger than MaxZextSmallBitWidth we will employ overflow
  assumptions and assume the "former negative" piece will not exist.

llvm-svn: 267408