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    assert(lp_check_value(type, a));
  87    assert(lp_check_value(type, b));
  88
  89    if(func == PIPE_FUNC_NEVER)
  90       return zeros;
  91    if(func == PIPE_FUNC_ALWAYS)
  92       return ones;
  93
  94    /* TODO: optimize the constant case */
  95
  96    /* XXX: It is not clear if we should use the ordered or unordered operators */
  97
  98 #if HAVE_LLVM < 0x0207
  99 #if defined(PIPE_ARCH_X86) || defined(PIPE_ARCH_X86_64)
 100    if(type.width * type.length == 128) {
 101       if(type.floating && util_cpu_caps.has_sse) {
 102          /* float[4] comparison */
 103          LLVMTypeRef vec_type = lp_build_vec_type(type);
 104          LLVMValueRef args[3];
 105          unsigned cc;
 106          boolean swap;
 107
 108          swap = FALSE;
 109          switch(func) {
 110          case PIPE_FUNC_EQUAL:
 111             cc = 0;
 112             break;
 113          case PIPE_FUNC_NOTEQUAL:
 114             cc = 4;
 115             break;
 116          case PIPE_FUNC_LESS:
 117             cc = 1;
 118             break;
 119          case PIPE_FUNC_LEQUAL:
 120             cc = 2;
 121             break;
 122          case PIPE_FUNC_GREATER:
 123             cc = 1;
 124             swap = TRUE;
 125             break;
 126          case PIPE_FUNC_GEQUAL:
 127             cc = 2;
 128             swap = TRUE;
 129             break;
 130          default:
 131             assert(0);
 132             return lp_build_undef(type);
 133          }
 134
 135          if(swap) {
 136             args[0] = b;
 137             args[1] = a;
 138          }
 139          else {
 140             args[0] = a;
 141             args[1] = b;
 142          }
 143
 144          args[2] = LLVMConstInt(LLVMInt8Type(), cc, 0);
 145          res = lp_build_intrinsic(builder,
 146                                   "llvm.x86.sse.cmp.ps",
 147                                   vec_type,
 148                                   args, 3);
 149          res = LLVMBuildBitCast(builder, res, int_vec_type, "");
 150          return res;
 151       }
 152       else if(util_cpu_caps.has_sse2) {
 153          /* int[4] comparison */
 154          static const struct {
 155             unsigned swap:1;
 156             unsigned eq:1;
 157             unsigned gt:1;
 158             unsigned not:1;
 159          } table[] = {
 160             {0, 0, 0, 1}, /* PIPE_FUNC_NEVER */
 161             {1, 0, 1, 0}, /* PIPE_FUNC_LESS */
 162             {0, 1, 0, 0}, /* PIPE_FUNC_EQUAL */
 163             {0, 0, 1, 1}, /* PIPE_FUNC_LEQUAL */
 164             {0, 0, 1, 0}, /* PIPE_FUNC_GREATER */
 165             {0, 1, 0, 1}, /* PIPE_FUNC_NOTEQUAL */
 166             {1, 0, 1, 1}, /* PIPE_FUNC_GEQUAL */
 167             {0, 0, 0, 0}  /* PIPE_FUNC_ALWAYS */
 168          };
 169          const char *pcmpeq;
 170          const char *pcmpgt;
 171          LLVMValueRef args[2];
 172          LLVMValueRef res;
 173          LLVMTypeRef vec_type = lp_build_vec_type(type);
 174
 175          switch (type.width) {
 176          case 8:
 177             pcmpeq = "llvm.x86.sse2.pcmpeq.b";
 178             pcmpgt = "llvm.x86.sse2.pcmpgt.b";
 179             break;
 180          case 16:
 181             pcmpeq = "llvm.x86.sse2.pcmpeq.w";
 182             pcmpgt = "llvm.x86.sse2.pcmpgt.w";
 183             break;
 184          case 32:
 185             pcmpeq = "llvm.x86.sse2.pcmpeq.d";
 186             pcmpgt = "llvm.x86.sse2.pcmpgt.d";
 187             break;
 188          default:
 189             assert(0);
 190             return lp_build_undef(type);
 191          }
 192
 193          /* There are no unsigned comparison instructions. So flip the sign bit
 194           * so that the results match.
 195           */
 196          if (table[func].gt && !type.sign) {
 197             LLVMValueRef msb = lp_build_const_int_vec(type, (unsigned long long)1 << (type.width - 1));
 198             a = LLVMBuildXor(builder, a, msb, "");
 199             b = LLVMBuildXor(builder, b, msb, "");
 200          }
 201
 202          if(table[func].swap) {
 203             args[0] = b;
 204             args[1] = a;
 205          }
 206          else {
 207             args[0] = a;
 208             args[1] = b;
 209          }
 210
 211          if(table[func].eq)
 212             res = lp_build_intrinsic(builder, pcmpeq, vec_type, args, 2);
 213          else if (table[func].gt)
 214             res = lp_build_intrinsic(builder, pcmpgt, vec_type, args, 2);
 215          else
 216             res = LLVMConstNull(vec_type);
 217
 218          if(table[func].not)
 219             res = LLVMBuildNot(builder, res, "");
 220
 221          return res;
 222       }
 223    } /* if (type.width * type.length == 128) */
 224 #endif
 225 #endif /* HAVE_LLVM < 0x0207 */
 226
 227    if(type.floating) {
 228       LLVMRealPredicate op;
 229       switch(func) {
 230       case PIPE_FUNC_NEVER:
 231          op = LLVMRealPredicateFalse;
 232          break;
 233       case PIPE_FUNC_ALWAYS:
 234          op = LLVMRealPredicateTrue;
 235          break;
 236       case PIPE_FUNC_EQUAL:
 237          op = LLVMRealUEQ;
 238          break;
 239       case PIPE_FUNC_NOTEQUAL:
 240          op = LLVMRealUNE;
 241          break;
 242       case PIPE_FUNC_LESS:
 243          op = LLVMRealULT;
 244          break;
 245       case PIPE_FUNC_LEQUAL:
 246          op = LLVMRealULE;
 247          break;
 248       case PIPE_FUNC_GREATER:
 249          op = LLVMRealUGT;
 250          break;
 251       case PIPE_FUNC_GEQUAL:
 252          op = LLVMRealUGE;
 253          break;
 254       default:
 255          assert(0);
 256          return lp_build_undef(type);
 257       }
 258
 259 #if HAVE_LLVM >= 0x0207
 260       cond = LLVMBuildFCmp(builder, op, a, b, "");
 261       res = LLVMBuildSExt(builder, cond, int_vec_type, "");
 262 #else
 263       if (type.length == 1) {
 264          cond = LLVMBuildFCmp(builder, op, a, b, "");
 265          res = LLVMBuildSExt(builder, cond, int_vec_type, "");
 266       }
 267       else {
 268          unsigned i;
 269
 270          res = LLVMGetUndef(int_vec_type);
 271
 272          debug_printf("%s: warning: using slow element-wise float"
 273                       " vector comparison\n", __FUNCTION__);
 274          for (i = 0; i < type.length; ++i) {
 275             LLVMValueRef index = LLVMConstInt(LLVMInt32Type(), i, 0);
 276             cond = LLVMBuildFCmp(builder, op,
 277                                  LLVMBuildExtractElement(builder, a, index, ""),
 278                                  LLVMBuildExtractElement(builder, b, index, ""),
 279                                  "");
 280             cond = LLVMBuildSelect(builder, cond,
 281                                    LLVMConstExtractElement(ones, index),
 282                                    LLVMConstExtractElement(zeros, index),
 283                                    "");
 284             res = LLVMBuildInsertElement(builder, res, cond, index, "");
 285          }
 286       }
 287 #endif
 288    }
 289    else {
 290       LLVMIntPredicate op;
 291       switch(func) {
 292       case PIPE_FUNC_EQUAL:
 293          op = LLVMIntEQ;
 294          break;
 295       case PIPE_FUNC_NOTEQUAL:
 296          op = LLVMIntNE;
 297          break;
 298       case PIPE_FUNC_LESS:
 299          op = type.sign ? LLVMIntSLT : LLVMIntULT;
 300          break;
 301       case PIPE_FUNC_LEQUAL:
 302          op = type.sign ? LLVMIntSLE : LLVMIntULE;
 303          break;
 304       case PIPE_FUNC_GREATER:
 305          op = type.sign ? LLVMIntSGT : LLVMIntUGT;
 306          break;
 307       case PIPE_FUNC_GEQUAL:
 308          op = type.sign ? LLVMIntSGE : LLVMIntUGE;
 309          break;
 310       default:
 311          assert(0);
 312          return lp_build_undef(type);
 313       }
 314
 315 #if HAVE_LLVM >= 0x0207
 316       cond = LLVMBuildICmp(builder, op, a, b, "");
 317       res = LLVMBuildSExt(builder, cond, int_vec_type, "");
 318 #else
 319       if (type.length == 1) {
 320          cond = LLVMBuildICmp(builder, op, a, b, "");
 321          res = LLVMBuildSExt(builder, cond, int_vec_type, "");
 322       }
 323       else {
 324          unsigned i;
 325
 326          res = LLVMGetUndef(int_vec_type);
 327
 328          debug_printf("%s: warning: using slow element-wise int"
 329                       " vector comparison\n", __FUNCTION__);
 330
 331          for(i = 0; i < type.length; ++i) {
 332             LLVMValueRef index = LLVMConstInt(LLVMInt32Type(), i, 0);
 333             cond = LLVMBuildICmp(builder, op,
 334                                  LLVMBuildExtractElement(builder, a, index, ""),
 335                                  LLVMBuildExtractElement(builder, b, index, ""),
 336                                  "");
 337             cond = LLVMBuildSelect(builder, cond,
 338                                    LLVMConstExtractElement(ones, index),
 339                                    LLVMConstExtractElement(zeros, index),
 340                                    "");
 341             res = LLVMBuildInsertElement(builder, res, cond, index, "");
 342          }
 343       }
 344 #endif
 345    }
 346
 347    return res;
 348 }
 349
 350
 351
 352 /**
 353  * Build code to compare two values 'a' and 'b' using the given func.
 354  * \param func  one of PIPE_FUNC_x
 355  * The result values will be 0 for false or ~0 for true.
 356  */
 357 LLVMValueRef
 358 lp_build_cmp(struct lp_build_context *bld,
 359              unsigned func,
 360              LLVMValueRef a,
 361              LLVMValueRef b)
 362 {
 363    return lp_build_compare(bld->builder, bld->type, func, a, b);
 364 }
 365
 366
 367 /**
 368  * Return (mask & a) | (~mask & b);
 369  */
 370 LLVMValueRef
 371 lp_build_select_bitwise(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    assert(lp_check_value(type, a));
 380    assert(lp_check_value(type, b));
 381
 382    if (a == b) {
 383       return a;
 384    }
 385
 386    if(type.floating) {
 387       LLVMTypeRef int_vec_type = lp_build_int_vec_type(type);
 388       a = LLVMBuildBitCast(bld->builder, a, int_vec_type, "");
 389       b = LLVMBuildBitCast(bld->builder, b, int_vec_type, "");
 390    }
 391
 392    a = LLVMBuildAnd(bld->builder, a, mask, "");
 393
 394    /* This often gets translated to PANDN, but sometimes the NOT is
 395     * pre-computed and stored in another constant. The best strategy depends
 396     * on available registers, so it is not a big deal -- hopefully LLVM does
 397     * the right decision attending the rest of the program.
 398     */
 399    b = LLVMBuildAnd(bld->builder, b, LLVMBuildNot(bld->builder, mask, ""), "");
 400
 401    res = LLVMBuildOr(bld->builder, a, b, "");
 402
 403    if(type.floating) {
 404       LLVMTypeRef vec_type = lp_build_vec_type(type);
 405       res = LLVMBuildBitCast(bld->builder, res, vec_type, "");
 406    }
 407
 408    return res;
 409 }
 410
 411
 412 /**
 413  * Return mask ? a : b;
 414  *
 415  * mask is a bitwise mask, composed of 0 or ~0 for each element. Any other value
 416  * will yield unpredictable results.
 417  */
 418 LLVMValueRef
 419 lp_build_select(struct lp_build_context *bld,
 420                 LLVMValueRef mask,
 421                 LLVMValueRef a,
 422                 LLVMValueRef b)
 423 {
 424    struct lp_type type = bld->type;
 425    LLVMValueRef res;
 426
 427    assert(lp_check_value(type, a));
 428    assert(lp_check_value(type, b));
 429
 430    if(a == b)
 431       return a;
 432
 433    if (type.length == 1) {
 434       mask = LLVMBuildTrunc(bld->builder, mask, LLVMInt1Type(), "");
 435       res = LLVMBuildSelect(bld->builder, mask, a, b, "");
 436    }
 437    else if (util_cpu_caps.has_sse4_1 &&
 438             type.width * type.length == 128 &&
 439             !LLVMIsConstant(a) &&
 440             !LLVMIsConstant(b) &&
 441             !LLVMIsConstant(mask)) {
 442       const char *intrinsic;
 443       LLVMTypeRef arg_type;
 444       LLVMValueRef args[3];
 445
 446       if (type.width == 64) {
 447          intrinsic = "llvm.x86.sse41.blendvpd";
 448          arg_type = LLVMVectorType(LLVMDoubleType(), 2);
 449       } else if (type.width == 32) {
 450          intrinsic = "llvm.x86.sse41.blendvps";
 451          arg_type = LLVMVectorType(LLVMFloatType(), 4);
 452       } else {
 453          intrinsic = "llvm.x86.sse41.pblendvb";
 454          arg_type = LLVMVectorType(LLVMInt8Type(), 16);
 455       }
 456
 457       if (arg_type != bld->int_vec_type) {
 458          mask = LLVMBuildBitCast(bld->builder, mask, arg_type, "");
 459       }
 460
 461       if (arg_type != bld->vec_type) {
 462          a = LLVMBuildBitCast(bld->builder, a, arg_type, "");
 463          b = LLVMBuildBitCast(bld->builder, b, arg_type, "");
 464       }
 465
 466       args[0] = b;
 467       args[1] = a;
 468       args[2] = mask;
 469
 470       res = lp_build_intrinsic(bld->builder, intrinsic,
 471                                arg_type, args, Elements(args));
 472
 473       if (arg_type != bld->vec_type) {
 474          res = LLVMBuildBitCast(bld->builder, res, bld->vec_type, "");
 475       }
 476    }
 477    else {
 478       res = lp_build_select_bitwise(bld, mask, a, b);
 479    }
 480
 481    return res;
 482 }
 483
 484
 485 LLVMValueRef
 486 lp_build_select_aos(struct lp_build_context *bld,
 487                     LLVMValueRef a,
 488                     LLVMValueRef b,
 489                     const boolean cond[4])
 490 {
 491    const struct lp_type type = bld->type;
 492    const unsigned n = type.length;
 493    unsigned i, j;
 494
 495    assert(lp_check_value(type, a));
 496    assert(lp_check_value(type, b));
 497
 498    if(a == b)
 499       return a;
 500    if(cond[0] && cond[1] && cond[2] && cond[3])
 501       return a;
 502    if(!cond[0] && !cond[1] && !cond[2] && !cond[3])
 503       return b;
 504    if(a == bld->undef || b == bld->undef)
 505       return bld->undef;
 506
 507    /*
 508     * There are three major ways of accomplishing this:
 509     * - with a shuffle,
 510     * - with a select,
 511     * - or with a bit mask.
 512     *
 513     * Select isn't supported for vector types yet.
 514     * The flip between these is empirical and might need to be.
 515     */
 516    if (n <= 4) {
 517       /*
 518        * Shuffle.
 519        */
 520       LLVMTypeRef elem_type = LLVMInt32Type();
 521       LLVMValueRef shuffles[LP_MAX_VECTOR_LENGTH];
 522
 523       for(j = 0; j < n; j += 4)
 524          for(i = 0; i < 4; ++i)
 525             shuffles[j + i] = LLVMConstInt(elem_type, (cond[i] ? 0 : n) + j + i, 0);
 526
 527       return LLVMBuildShuffleVector(bld->builder, a, b, LLVMConstVector(shuffles, n), "");
 528    }
 529    else {
 530 #if 0
 531       /* XXX: Unfortunately select of vectors do not work */
 532       /* Use a select */
 533       LLVMTypeRef elem_type = LLVMInt1Type();
 534       LLVMValueRef cond[LP_MAX_VECTOR_LENGTH];
 535
 536       for(j = 0; j < n; j += 4)
 537          for(i = 0; i < 4; ++i)
 538             cond[j + i] = LLVMConstInt(elem_type, cond[i] ? 1 : 0, 0);
 539
 540       return LLVMBuildSelect(bld->builder, LLVMConstVector(cond, n), a, b, "");
 541 #else
 542       LLVMValueRef mask = lp_build_const_mask_aos(type, cond);
 543       return lp_build_select(bld, mask, a, b);
 544 #endif
 545    }
 546 }
 547
 548
 549 /** Return (a & ~b) */
 550 LLVMValueRef
 551 lp_build_andc(struct lp_build_context *bld, LLVMValueRef a, LLVMValueRef b)
 552 {
 553    const struct lp_type type = bld->type;
 554
 555    assert(lp_check_value(type, a));
 556    assert(lp_check_value(type, b));
 557
 558    /* can't do bitwise ops on floating-point values */
 559    if(type.floating) {
 560       a = LLVMBuildBitCast(bld->builder, a, bld->int_vec_type, "");
 561       b = LLVMBuildBitCast(bld->builder, b, bld->int_vec_type, "");
 562    }
 563
 564    b = LLVMBuildNot(bld->builder, b, "");
 565    b = LLVMBuildAnd(bld->builder, a, b, "");
 566
 567    if(type.floating) {
 568       b = LLVMBuildBitCast(bld->builder, b, bld->vec_type, "");
 569    }
 570    return b;
 571 }