src/gallium/auxiliary/gallivm/lp_bld_logic.c

   1 /**************************************************************************
   2  *
   3  * Copyright 2009 VMware, Inc.
   4  * All Rights Reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sub license, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the
  15  * next paragraph) shall be included in all copies or substantial portions
  16  * of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  21  * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
  22  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  **************************************************************************/
  27
  28 /**
  29  * @file
  30  * Helper functions for logical operations.
  31  *
  32  * @author Jose Fonseca <jfonseca@vmware.com>
  33  */
  34
  35
  36 #include "util/u_cpu_detect.h"
  37 #include "util/u_memory.h"
  38 #include "util/u_debug.h"
  39
  40 #include "lp_bld_type.h"
  41 #include "lp_bld_const.h"
  42 #include "lp_bld_intr.h"
  43 #include "lp_bld_logic.h"
  44
  45
  46 /*
  47  * XXX
  48  *
  49  * Selection with vector conditional like
  50  *
  51  *    select <4 x i1> %C, %A, %B
  52  *
  53  * is valid IR (e.g. llvm/test/Assembler/vector-select.ll), but it is not
  54  * supported on any backend.
  55  *
  56  * Expanding the boolean vector to full SIMD register width, as in
  57  *
  58  *    sext <4 x i1> %C to <4 x i32>
  59  *
  60  * is valid and supported (e.g., llvm/test/CodeGen/X86/vec_compare.ll), but
  61  * it causes assertion failures in LLVM 2.6. It appears to work correctly on
  62  * LLVM 2.7.
  63  */
  64
  65
  66 /**
  67  * Build code to compare two values 'a' and 'b' of 'type' using the given func.
  68  * \param func  one of PIPE_FUNC_x
  69  * The result values will be 0 for false or ~0 for true.
  70  */
  71 LLVMValueRef
  72 lp_build_compare(LLVMBuilderRef builder,
  73                  const struct lp_type type,
  74                  unsigned func,
  75                  LLVMValueRef a,
  76                  LLVMValueRef b)
  77 {
  78    LLVMTypeRef int_vec_type = lp_build_int_vec_type(type);
  79    LLVMValueRef zeros = LLVMConstNull(int_vec_type);
  80    LLVMValueRef ones = LLVMConstAllOnes(int_vec_type);
  81    LLVMValueRef cond;
  82    LLVMValueRef res;
  83
  84    assert(func >= PIPE_FUNC_NEVER);
  85    assert(func <= PIPE_FUNC_ALWAYS);
  86
  87    if(func == PIPE_FUNC_NEVER)
  88       return zeros;
  89    if(func == PIPE_FUNC_ALWAYS)
  90       return ones;
  91
  92    /* TODO: optimize the constant case */
  93
  94    /* XXX: It is not clear if we should use the ordered or unordered operators */
  95
  96 #if HAVE_LLVM < 0x0207
  97 #if defined(PIPE_ARCH_X86) || defined(PIPE_ARCH_X86_64)
  98    if(type.width * type.length == 128) {
  99       if(type.floating && util_cpu_caps.has_sse) {
 100          /* float[4] comparison */
 101          LLVMTypeRef vec_type = lp_build_vec_type(type);
 102          LLVMValueRef args[3];
 103          unsigned cc;
 104          boolean swap;
 105
 106          swap = FALSE;
 107          switch(func) {
 108          case PIPE_FUNC_EQUAL:
 109             cc = 0;
 110             break;
 111          case PIPE_FUNC_NOTEQUAL:
 112             cc = 4;
 113             break;
 114          case PIPE_FUNC_LESS:
 115             cc = 1;
 116             break;
 117          case PIPE_FUNC_LEQUAL:
 118             cc = 2;
 119             break;
 120          case PIPE_FUNC_GREATER:
 121             cc = 1;
 122             swap = TRUE;
 123             break;
 124          case PIPE_FUNC_GEQUAL:
 125             cc = 2;
 126             swap = TRUE;
 127             break;
 128          default:
 129             assert(0);
 130             return lp_build_undef(type);
 131          }
 132
 133          if(swap) {
 134             args[0] = b;
 135             args[1] = a;
 136          }
 137          else {
 138             args[0] = a;
 139             args[1] = b;
 140          }
 141
 142          args[2] = LLVMConstInt(LLVMInt8Type(), cc, 0);
 143          res = lp_build_intrinsic(builder,
 144                                   "llvm.x86.sse.cmp.ps",
 145                                   vec_type,
 146                                   args, 3);
 147          res = LLVMBuildBitCast(builder, res, int_vec_type, "");
 148          return res;
 149       }
 150       else if(util_cpu_caps.has_sse2) {
 151          /* int[4] comparison */
 152          static const struct {
 153             unsigned swap:1;
 154             unsigned eq:1;
 155             unsigned gt:1;
 156             unsigned not:1;
 157          } table[] = {
 158             {0, 0, 0, 1}, /* PIPE_FUNC_NEVER */
 159             {1, 0, 1, 0}, /* PIPE_FUNC_LESS */
 160             {0, 1, 0, 0}, /* PIPE_FUNC_EQUAL */
 161             {0, 0, 1, 1}, /* PIPE_FUNC_LEQUAL */
 162             {0, 0, 1, 0}, /* PIPE_FUNC_GREATER */
 163             {0, 1, 0, 1}, /* PIPE_FUNC_NOTEQUAL */
 164             {1, 0, 1, 1}, /* PIPE_FUNC_GEQUAL */
 165             {0, 0, 0, 0}  /* PIPE_FUNC_ALWAYS */
 166          };
 167          const char *pcmpeq;
 168          const char *pcmpgt;
 169          LLVMValueRef args[2];
 170          LLVMValueRef res;
 171          LLVMTypeRef vec_type = lp_build_vec_type(type);
 172
 173          switch (type.width) {
 174          case 8:
 175             pcmpeq = "llvm.x86.sse2.pcmpeq.b";
 176             pcmpgt = "llvm.x86.sse2.pcmpgt.b";
 177             break;
 178          case 16:
 179             pcmpeq = "llvm.x86.sse2.pcmpeq.w";
 180             pcmpgt = "llvm.x86.sse2.pcmpgt.w";
 181             break;
 182          case 32:
 183             pcmpeq = "llvm.x86.sse2.pcmpeq.d";
 184             pcmpgt = "llvm.x86.sse2.pcmpgt.d";
 185             break;
 186          default:
 187             assert(0);
 188             return lp_build_undef(type);
 189          }
 190
 191          /* There are no unsigned comparison instructions. So flip the sign bit
 192           * so that the results match.
 193           */
 194          if (table[func].gt && !type.sign) {
 195             LLVMValueRef msb = lp_build_const_int_vec(type, (unsigned long long)1 << (type.width - 1));
 196             a = LLVMBuildXor(builder, a, msb, "");
 197             b = LLVMBuildXor(builder, b, msb, "");
 198          }
 199
 200          if(table[func].swap) {
 201             args[0] = b;
 202             args[1] = a;
 203          }
 204          else {
 205             args[0] = a;
 206             args[1] = b;
 207          }
 208
 209          if(table[func].eq)
 210             res = lp_build_intrinsic(builder, pcmpeq, vec_type, args, 2);
 211          else if (table[func].gt)
 212             res = lp_build_intrinsic(builder, pcmpgt, vec_type, args, 2);
 213          else
 214             res = LLVMConstNull(vec_type);
 215
 216          if(table[func].not)
 217             res = LLVMBuildNot(builder, res, "");
 218
 219          return res;
 220       }
 221    } /* if (type.width * type.length == 128) */
 222 #endif
 223 #endif /* HAVE_LLVM < 0x0207 */
 224
 225    if(type.floating) {
 226       LLVMRealPredicate op;
 227       switch(func) {
 228       case PIPE_FUNC_NEVER:
 229          op = LLVMRealPredicateFalse;
 230          break;
 231       case PIPE_FUNC_ALWAYS:
 232          op = LLVMRealPredicateTrue;
 233          break;
 234       case PIPE_FUNC_EQUAL:
 235          op = LLVMRealUEQ;
 236          break;
 237       case PIPE_FUNC_NOTEQUAL:
 238          op = LLVMRealUNE;
 239          break;
 240       case PIPE_FUNC_LESS:
 241          op = LLVMRealULT;
 242          break;
 243       case PIPE_FUNC_LEQUAL:
 244          op = LLVMRealULE;
 245          break;
 246       case PIPE_FUNC_GREATER:
 247          op = LLVMRealUGT;
 248          break;
 249       case PIPE_FUNC_GEQUAL:
 250          op = LLVMRealUGE;
 251          break;
 252       default:
 253          assert(0);
 254          return lp_build_undef(type);
 255       }
 256
 257 #if HAVE_LLVM >= 0x0207
 258       cond = LLVMBuildFCmp(builder, op, a, b, "");
 259       res = LLVMBuildSExt(builder, cond, int_vec_type, "");
 260 #else
 261       if (type.length == 1) {
 262          cond = LLVMBuildFCmp(builder, op, a, b, "");
 263          res = LLVMBuildSExt(builder, cond, int_vec_type, "");
 264       }
 265       else {
 266          unsigned i;
 267
 268          res = LLVMGetUndef(int_vec_type);
 269
 270          debug_printf("%s: warning: using slow element-wise float"
 271                       " vector comparison\n", __FUNCTION__);
 272          for (i = 0; i < type.length; ++i) {
 273             LLVMValueRef index = LLVMConstInt(LLVMInt32Type(), i, 0);
 274             cond = LLVMBuildFCmp(builder, op,
 275                                  LLVMBuildExtractElement(builder, a, index, ""),
 276                                  LLVMBuildExtractElement(builder, b, index, ""),
 277                                  "");
 278             cond = LLVMBuildSelect(builder, cond,
 279                                    LLVMConstExtractElement(ones, index),
 280                                    LLVMConstExtractElement(zeros, index),
 281                                    "");
 282             res = LLVMBuildInsertElement(builder, res, cond, index, "");
 283          }
 284       }
 285 #endif
 286    }
 287    else {
 288       LLVMIntPredicate op;
 289       switch(func) {
 290       case PIPE_FUNC_EQUAL:
 291          op = LLVMIntEQ;
 292          break;
 293       case PIPE_FUNC_NOTEQUAL:
 294          op = LLVMIntNE;
 295          break;
 296       case PIPE_FUNC_LESS:
 297          op = type.sign ? LLVMIntSLT : LLVMIntULT;
 298          break;
 299       case PIPE_FUNC_LEQUAL:
 300          op = type.sign ? LLVMIntSLE : LLVMIntULE;
 301          break;
 302       case PIPE_FUNC_GREATER:
 303          op = type.sign ? LLVMIntSGT : LLVMIntUGT;
 304          break;
 305       case PIPE_FUNC_GEQUAL:
 306          op = type.sign ? LLVMIntSGE : LLVMIntUGE;
 307          break;
 308       default:
 309          assert(0);
 310          return lp_build_undef(type);
 311       }
 312
 313 #if HAVE_LLVM >= 0x0207
 314       cond = LLVMBuildICmp(builder, op, a, b, "");
 315       res = LLVMBuildSExt(builder, cond, int_vec_type, "");
 316 #else
 317       if (type.length == 1) {
 318          cond = LLVMBuildICmp(builder, op, a, b, "");
 319          res = LLVMBuildSExt(builder, cond, int_vec_type, "");
 320       }
 321       else {
 322          unsigned i;
 323
 324          res = LLVMGetUndef(int_vec_type);
 325
 326          debug_printf("%s: warning: using slow element-wise int"
 327                       " vector comparison\n", __FUNCTION__);
 328
 329          for(i = 0; i < type.length; ++i) {
 330             LLVMValueRef index = LLVMConstInt(LLVMInt32Type(), i, 0);
 331             cond = LLVMBuildICmp(builder, op,
 332                                  LLVMBuildExtractElement(builder, a, index, ""),
 333                                  LLVMBuildExtractElement(builder, b, index, ""),
 334                                  "");
 335             cond = LLVMBuildSelect(builder, cond,
 336                                    LLVMConstExtractElement(ones, index),
 337                                    LLVMConstExtractElement(zeros, index),
 338                                    "");
 339             res = LLVMBuildInsertElement(builder, res, cond, index, "");
 340          }
 341       }
 342 #endif
 343    }
 344
 345    return res;
 346 }
 347
 348
 349
 350 /**
 351  * Build code to compare two values 'a' and 'b' using the given func.
 352  * \param func  one of PIPE_FUNC_x
 353  * The result values will be 0 for false or ~0 for true.
 354  */
 355 LLVMValueRef
 356 lp_build_cmp(struct lp_build_context *bld,
 357              unsigned func,
 358              LLVMValueRef a,
 359              LLVMValueRef b)
 360 {
 361    return lp_build_compare(bld->builder, bld->type, func, a, b);
 362 }
 363
 364
 365 /**
 366  * Return mask ? a : b;
 367  *
 368  * mask is a bitwise mask, composed of 0 or ~0 for each element.
 369  */
 370 LLVMValueRef
 371 lp_build_select(struct lp_build_context *bld,
 372                 LLVMValueRef mask,
 373                 LLVMValueRef a,
 374                 LLVMValueRef b)
 375 {
 376    struct lp_type type = bld->type;
 377    LLVMValueRef res;
 378
 379    if(a == b)
 380       return a;
 381
 382    if (type.length == 1) {
 383       mask = LLVMBuildTrunc(bld->builder, mask, LLVMInt1Type(), "");
 384       res = LLVMBuildSelect(bld->builder, mask, a, b, "");
 385    }
 386    else if (util_cpu_caps.has_sse4_1 &&
 387             type.width * type.length == 128 &&
 388             !LLVMIsConstant(a) &&
 389             !LLVMIsConstant(b) &&
 390             !LLVMIsConstant(mask)) {
 391       const char *intrinsic;
 392       LLVMTypeRef arg_type;
 393       LLVMValueRef args[3];
 394
 395       if (type.width == 64) {
 396          intrinsic = "llvm.x86.sse41.blendvpd";
 397          arg_type = LLVMVectorType(LLVMDoubleType(), 2);
 398       } else if (type.width == 32) {
 399          intrinsic = "llvm.x86.sse41.blendvps";
 400          arg_type = LLVMVectorType(LLVMFloatType(), 4);
 401       } else {
 402          intrinsic = "llvm.x86.sse41.pblendvb";
 403          arg_type = LLVMVectorType(LLVMInt8Type(), 16);
 404       }
 405
 406       if (arg_type != bld->int_vec_type) {
 407          mask = LLVMBuildBitCast(bld->builder, mask, arg_type, "");
 408       }
 409
 410       if (arg_type != bld->vec_type) {
 411          a = LLVMBuildBitCast(bld->builder, a, arg_type, "");
 412          b = LLVMBuildBitCast(bld->builder, b, arg_type, "");
 413       }
 414
 415       args[0] = b;
 416       args[1] = a;
 417       args[2] = mask;
 418
 419       res = lp_build_intrinsic(bld->builder, intrinsic,
 420                                arg_type, args, Elements(args));
 421
 422       if (arg_type != bld->vec_type) {
 423          res = LLVMBuildBitCast(bld->builder, res, bld->vec_type, "");
 424       }
 425    }
 426    else {
 427       if(type.floating) {
 428          LLVMTypeRef int_vec_type = lp_build_int_vec_type(type);
 429          a = LLVMBuildBitCast(bld->builder, a, int_vec_type, "");
 430          b = LLVMBuildBitCast(bld->builder, b, int_vec_type, "");
 431       }
 432
 433       a = LLVMBuildAnd(bld->builder, a, mask, "");
 434
 435       /* This often gets translated to PANDN, but sometimes the NOT is
 436        * pre-computed and stored in another constant. The best strategy depends
 437        * on available registers, so it is not a big deal -- hopefully LLVM does
 438        * the right decision attending the rest of the program.
 439        */
 440       b = LLVMBuildAnd(bld->builder, b, LLVMBuildNot(bld->builder, mask, ""), "");
 441
 442       res = LLVMBuildOr(bld->builder, a, b, "");
 443
 444       if(type.floating) {
 445          LLVMTypeRef vec_type = lp_build_vec_type(type);
 446          res = LLVMBuildBitCast(bld->builder, res, vec_type, "");
 447       }
 448    }
 449
 450    return res;
 451 }
 452
 453
 454 LLVMValueRef
 455 lp_build_select_aos(struct lp_build_context *bld,
 456                     LLVMValueRef a,
 457                     LLVMValueRef b,
 458                     const boolean cond[4])
 459 {
 460    const struct lp_type type = bld->type;
 461    const unsigned n = type.length;
 462    unsigned i, j;
 463
 464    if(a == b)
 465       return a;
 466    if(cond[0] && cond[1] && cond[2] && cond[3])
 467       return a;
 468    if(!cond[0] && !cond[1] && !cond[2] && !cond[3])
 469       return b;
 470    if(a == bld->undef || b == bld->undef)
 471       return bld->undef;
 472
 473    /*
 474     * There are three major ways of accomplishing this:
 475     * - with a shuffle,
 476     * - with a select,
 477     * - or with a bit mask.
 478     *
 479     * Select isn't supported for vector types yet.
 480     * The flip between these is empirical and might need to be.
 481     */
 482    if (n <= 4) {
 483       /*
 484        * Shuffle.
 485        */
 486       LLVMTypeRef elem_type = LLVMInt32Type();
 487       LLVMValueRef shuffles[LP_MAX_VECTOR_LENGTH];
 488
 489       for(j = 0; j < n; j += 4)
 490          for(i = 0; i < 4; ++i)
 491             shuffles[j + i] = LLVMConstInt(elem_type, (cond[i] ? 0 : n) + j + i, 0);
 492
 493       return LLVMBuildShuffleVector(bld->builder, a, b, LLVMConstVector(shuffles, n), "");
 494    }
 495    else {
 496 #if 0
 497       /* XXX: Unfortunately select of vectors do not work */
 498       /* Use a select */
 499       LLVMTypeRef elem_type = LLVMInt1Type();
 500       LLVMValueRef cond[LP_MAX_VECTOR_LENGTH];
 501
 502       for(j = 0; j < n; j += 4)
 503          for(i = 0; i < 4; ++i)
 504             cond[j + i] = LLVMConstInt(elem_type, cond[i] ? 1 : 0, 0);
 505
 506       return LLVMBuildSelect(bld->builder, LLVMConstVector(cond, n), a, b, "");
 507 #else
 508       LLVMValueRef mask = lp_build_const_mask_aos(type, cond);
 509       return lp_build_select(bld, mask, a, b);
 510 #endif
 511    }
 512 }
 513
 514
 515 /** Return (a & ~b) */
 516 LLVMValueRef
 517 lp_build_andc(struct lp_build_context *bld, LLVMValueRef a, LLVMValueRef b)
 518 {
 519    b = LLVMBuildNot(bld->builder, b, "");
 520    b = LLVMBuildAnd(bld->builder, a, b, "");
 521    return b;
 522 }