← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
 
1
//===- InstCombineSelect.cpp ----------------------------------------------===//
 
2
//
 
3
//                     The LLVM Compiler Infrastructure
 
4
//
 
5
// This file is distributed under the University of Illinois Open Source
 
6
// License. See LICENSE.TXT for details.
 
7
//
 
8
//===----------------------------------------------------------------------===//
 
9
//
 
10
// This file implements the visitSelect function.
 
11
//
 
12
//===----------------------------------------------------------------------===//
 
13
 
 
14
#include "InstCombine.h"
 
15
#include "llvm/Support/PatternMatch.h"
 
16
using namespace llvm;
 
17
using namespace PatternMatch;
 
18
 
 
19
/// MatchSelectPattern - Pattern match integer [SU]MIN, [SU]MAX, and ABS idioms,
 
20
/// returning the kind and providing the out parameter results if we
 
21
/// successfully match.
 
22
static SelectPatternFlavor
 
23
MatchSelectPattern(Value *V, Value *&LHS, Value *&RHS) {
 
24
  SelectInst *SI = dyn_cast<SelectInst>(V);
 
25
  if (SI == 0) return SPF_UNKNOWN;
 
26
  
 
27
  ICmpInst *ICI = dyn_cast<ICmpInst>(SI->getCondition());
 
28
  if (ICI == 0) return SPF_UNKNOWN;
 
29
  
 
30
  LHS = ICI->getOperand(0);
 
31
  RHS = ICI->getOperand(1);
 
32
  
 
33
  // (icmp X, Y) ? X : Y 
 
34
  if (SI->getTrueValue() == ICI->getOperand(0) &&
 
35
      SI->getFalseValue() == ICI->getOperand(1)) {
 
36
    switch (ICI->getPredicate()) {
 
37
    default: return SPF_UNKNOWN; // Equality.
 
38
    case ICmpInst::ICMP_UGT:
 
39
    case ICmpInst::ICMP_UGE: return SPF_UMAX;
 
40
    case ICmpInst::ICMP_SGT:
 
41
    case ICmpInst::ICMP_SGE: return SPF_SMAX;
 
42
    case ICmpInst::ICMP_ULT:
 
43
    case ICmpInst::ICMP_ULE: return SPF_UMIN;
 
44
    case ICmpInst::ICMP_SLT:
 
45
    case ICmpInst::ICMP_SLE: return SPF_SMIN;
 
46
    }
 
47
  }
 
48
  
 
49
  // (icmp X, Y) ? Y : X 
 
50
  if (SI->getTrueValue() == ICI->getOperand(1) &&
 
51
      SI->getFalseValue() == ICI->getOperand(0)) {
 
52
    switch (ICI->getPredicate()) {
 
53
      default: return SPF_UNKNOWN; // Equality.
 
54
      case ICmpInst::ICMP_UGT:
 
55
      case ICmpInst::ICMP_UGE: return SPF_UMIN;
 
56
      case ICmpInst::ICMP_SGT:
 
57
      case ICmpInst::ICMP_SGE: return SPF_SMIN;
 
58
      case ICmpInst::ICMP_ULT:
 
59
      case ICmpInst::ICMP_ULE: return SPF_UMAX;
 
60
      case ICmpInst::ICMP_SLT:
 
61
      case ICmpInst::ICMP_SLE: return SPF_SMAX;
 
62
    }
 
63
  }
 
64
  
 
65
  // TODO: (X > 4) ? X : 5   -->  (X >= 5) ? X : 5  -->  MAX(X, 5)
 
66
  
 
67
  return SPF_UNKNOWN;
 
68
}
 
69
 
 
70
 
 
71
/// GetSelectFoldableOperands - We want to turn code that looks like this:
 
72
///   %C = or %A, %B
 
73
///   %D = select %cond, %C, %A
 
74
/// into:
 
75
///   %C = select %cond, %B, 0
 
76
///   %D = or %A, %C
 
77
///
 
78
/// Assuming that the specified instruction is an operand to the select, return
 
79
/// a bitmask indicating which operands of this instruction are foldable if they
 
80
/// equal the other incoming value of the select.
 
81
///
 
82
static unsigned GetSelectFoldableOperands(Instruction *I) {
 
83
  switch (I->getOpcode()) {
 
84
  case Instruction::Add:
 
85
  case Instruction::Mul:
 
86
  case Instruction::And:
 
87
  case Instruction::Or:
 
88
  case Instruction::Xor:
 
89
    return 3;              // Can fold through either operand.
 
90
  case Instruction::Sub:   // Can only fold on the amount subtracted.
 
91
  case Instruction::Shl:   // Can only fold on the shift amount.
 
92
  case Instruction::LShr:
 
93
  case Instruction::AShr:
 
94
    return 1;
 
95
  default:
 
96
    return 0;              // Cannot fold
 
97
  }
 
98
}
 
99
 
 
100
/// GetSelectFoldableConstant - For the same transformation as the previous
 
101
/// function, return the identity constant that goes into the select.
 
102
static Constant *GetSelectFoldableConstant(Instruction *I) {
 
103
  switch (I->getOpcode()) {
 
104
  default: llvm_unreachable("This cannot happen!");
 
105
  case Instruction::Add:
 
106
  case Instruction::Sub:
 
107
  case Instruction::Or:
 
108
  case Instruction::Xor:
 
109
  case Instruction::Shl:
 
110
  case Instruction::LShr:
 
111
  case Instruction::AShr:
 
112
    return Constant::getNullValue(I->getType());
 
113
  case Instruction::And:
 
114
    return Constant::getAllOnesValue(I->getType());
 
115
  case Instruction::Mul:
 
116
    return ConstantInt::get(I->getType(), 1);
 
117
  }
 
118
}
 
119
 
 
120
/// FoldSelectOpOp - Here we have (select c, TI, FI), and we know that TI and FI
 
121
/// have the same opcode and only one use each.  Try to simplify this.
 
122
Instruction *InstCombiner::FoldSelectOpOp(SelectInst &SI, Instruction *TI,
 
123
                                          Instruction *FI) {
 
124
  if (TI->getNumOperands() == 1) {
 
125
    // If this is a non-volatile load or a cast from the same type,
 
126
    // merge.
 
127
    if (TI->isCast()) {
 
128
      if (TI->getOperand(0)->getType() != FI->getOperand(0)->getType())
 
129
        return 0;
 
130
    } else {
 
131
      return 0;  // unknown unary op.
 
132
    }
 
133
 
 
134
    // Fold this by inserting a select from the input values.
 
135
    SelectInst *NewSI = SelectInst::Create(SI.getCondition(), TI->getOperand(0),
 
136
                                          FI->getOperand(0), SI.getName()+".v");
 
137
    InsertNewInstBefore(NewSI, SI);
 
138
    return CastInst::Create(Instruction::CastOps(TI->getOpcode()), NewSI, 
 
139
                            TI->getType());
 
140
  }
 
141
 
 
142
  // Only handle binary operators here.
 
143
  if (!isa<BinaryOperator>(TI))
 
144
    return 0;
 
145
 
 
146
  // Figure out if the operations have any operands in common.
 
147
  Value *MatchOp, *OtherOpT, *OtherOpF;
 
148
  bool MatchIsOpZero;
 
149
  if (TI->getOperand(0) == FI->getOperand(0)) {
 
150
    MatchOp  = TI->getOperand(0);
 
151
    OtherOpT = TI->getOperand(1);
 
152
    OtherOpF = FI->getOperand(1);
 
153
    MatchIsOpZero = true;
 
154
  } else if (TI->getOperand(1) == FI->getOperand(1)) {
 
155
    MatchOp  = TI->getOperand(1);
 
156
    OtherOpT = TI->getOperand(0);
 
157
    OtherOpF = FI->getOperand(0);
 
158
    MatchIsOpZero = false;
 
159
  } else if (!TI->isCommutative()) {
 
160
    return 0;
 
161
  } else if (TI->getOperand(0) == FI->getOperand(1)) {
 
162
    MatchOp  = TI->getOperand(0);
 
163
    OtherOpT = TI->getOperand(1);
 
164
    OtherOpF = FI->getOperand(0);
 
165
    MatchIsOpZero = true;
 
166
  } else if (TI->getOperand(1) == FI->getOperand(0)) {
 
167
    MatchOp  = TI->getOperand(1);
 
168
    OtherOpT = TI->getOperand(0);
 
169
    OtherOpF = FI->getOperand(1);
 
170
    MatchIsOpZero = true;
 
171
  } else {
 
172
    return 0;
 
173
  }
 
174
 
 
175
  // If we reach here, they do have operations in common.
 
176
  SelectInst *NewSI = SelectInst::Create(SI.getCondition(), OtherOpT,
 
177
                                         OtherOpF, SI.getName()+".v");
 
178
  InsertNewInstBefore(NewSI, SI);
 
179
 
 
180
  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TI)) {
 
181
    if (MatchIsOpZero)
 
182
      return BinaryOperator::Create(BO->getOpcode(), MatchOp, NewSI);
 
183
    else
 
184
      return BinaryOperator::Create(BO->getOpcode(), NewSI, MatchOp);
 
185
  }
 
186
  llvm_unreachable("Shouldn't get here");
 
187
  return 0;
 
188
}
 
189
 
 
190
static bool isSelect01(Constant *C1, Constant *C2) {
 
191
  ConstantInt *C1I = dyn_cast<ConstantInt>(C1);
 
192
  if (!C1I)
 
193
    return false;
 
194
  ConstantInt *C2I = dyn_cast<ConstantInt>(C2);
 
195
  if (!C2I)
 
196
    return false;
 
197
  return (C1I->isZero() || C1I->isOne()) && (C2I->isZero() || C2I->isOne());
 
198
}
 
199
 
 
200
/// FoldSelectIntoOp - Try fold the select into one of the operands to
 
201
/// facilitate further optimization.
 
202
Instruction *InstCombiner::FoldSelectIntoOp(SelectInst &SI, Value *TrueVal,
 
203
                                            Value *FalseVal) {
 
204
  // See the comment above GetSelectFoldableOperands for a description of the
 
205
  // transformation we are doing here.
 
206
  if (Instruction *TVI = dyn_cast<Instruction>(TrueVal)) {
 
207
    if (TVI->hasOneUse() && TVI->getNumOperands() == 2 &&
 
208
        !isa<Constant>(FalseVal)) {
 
209
      if (unsigned SFO = GetSelectFoldableOperands(TVI)) {
 
210
        unsigned OpToFold = 0;
 
211
        if ((SFO & 1) && FalseVal == TVI->getOperand(0)) {
 
212
          OpToFold = 1;
 
213
        } else  if ((SFO & 2) && FalseVal == TVI->getOperand(1)) {
 
214
          OpToFold = 2;
 
215
        }
 
216
 
 
217
        if (OpToFold) {
 
218
          Constant *C = GetSelectFoldableConstant(TVI);
 
219
          Value *OOp = TVI->getOperand(2-OpToFold);
 
220
          // Avoid creating select between 2 constants unless it's selecting
 
221
          // between 0 and 1.
 
222
          if (!isa<Constant>(OOp) || isSelect01(C, cast<Constant>(OOp))) {
 
223
            Instruction *NewSel = SelectInst::Create(SI.getCondition(), OOp, C);
 
224
            InsertNewInstBefore(NewSel, SI);
 
225
            NewSel->takeName(TVI);
 
226
            if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TVI))
 
227
              return BinaryOperator::Create(BO->getOpcode(), FalseVal, NewSel);
 
228
            llvm_unreachable("Unknown instruction!!");
 
229
          }
 
230
        }
 
231
      }
 
232
    }
 
233
  }
 
234
 
 
235
  if (Instruction *FVI = dyn_cast<Instruction>(FalseVal)) {
 
236
    if (FVI->hasOneUse() && FVI->getNumOperands() == 2 &&
 
237
        !isa<Constant>(TrueVal)) {
 
238
      if (unsigned SFO = GetSelectFoldableOperands(FVI)) {
 
239
        unsigned OpToFold = 0;
 
240
        if ((SFO & 1) && TrueVal == FVI->getOperand(0)) {
 
241
          OpToFold = 1;
 
242
        } else  if ((SFO & 2) && TrueVal == FVI->getOperand(1)) {
 
243
          OpToFold = 2;
 
244
        }
 
245
 
 
246
        if (OpToFold) {
 
247
          Constant *C = GetSelectFoldableConstant(FVI);
 
248
          Value *OOp = FVI->getOperand(2-OpToFold);
 
249
          // Avoid creating select between 2 constants unless it's selecting
 
250
          // between 0 and 1.
 
251
          if (!isa<Constant>(OOp) || isSelect01(C, cast<Constant>(OOp))) {
 
252
            Instruction *NewSel = SelectInst::Create(SI.getCondition(), C, OOp);
 
253
            InsertNewInstBefore(NewSel, SI);
 
254
            NewSel->takeName(FVI);
 
255
            if (BinaryOperator *BO = dyn_cast<BinaryOperator>(FVI))
 
256
              return BinaryOperator::Create(BO->getOpcode(), TrueVal, NewSel);
 
257
            llvm_unreachable("Unknown instruction!!");
 
258
          }
 
259
        }
 
260
      }
 
261
    }
 
262
  }
 
263
 
 
264
  return 0;
 
265
}
 
266
 
 
267
/// visitSelectInstWithICmp - Visit a SelectInst that has an
 
268
/// ICmpInst as its first operand.
 
269
///
 
270
Instruction *InstCombiner::visitSelectInstWithICmp(SelectInst &SI,
 
271
                                                   ICmpInst *ICI) {
 
272
  bool Changed = false;
 
273
  ICmpInst::Predicate Pred = ICI->getPredicate();
 
274
  Value *CmpLHS = ICI->getOperand(0);
 
275
  Value *CmpRHS = ICI->getOperand(1);
 
276
  Value *TrueVal = SI.getTrueValue();
 
277
  Value *FalseVal = SI.getFalseValue();
 
278
 
 
279
  // Check cases where the comparison is with a constant that
 
280
  // can be adjusted to fit the min/max idiom. We may edit ICI in
 
281
  // place here, so make sure the select is the only user.
 
282
  if (ICI->hasOneUse())
 
283
    if (ConstantInt *CI = dyn_cast<ConstantInt>(CmpRHS)) {
 
284
      switch (Pred) {
 
285
      default: break;
 
286
      case ICmpInst::ICMP_ULT:
 
287
      case ICmpInst::ICMP_SLT: {
 
288
        // X < MIN ? T : F  -->  F
 
289
        if (CI->isMinValue(Pred == ICmpInst::ICMP_SLT))
 
290
          return ReplaceInstUsesWith(SI, FalseVal);
 
291
        // X < C ? X : C-1  -->  X > C-1 ? C-1 : X
 
292
        Constant *AdjustedRHS =
 
293
          ConstantInt::get(CI->getContext(), CI->getValue()-1);
 
294
        if ((CmpLHS == TrueVal && AdjustedRHS == FalseVal) ||
 
295
            (CmpLHS == FalseVal && AdjustedRHS == TrueVal)) {
 
296
          Pred = ICmpInst::getSwappedPredicate(Pred);
 
297
          CmpRHS = AdjustedRHS;
 
298
          std::swap(FalseVal, TrueVal);
 
299
          ICI->setPredicate(Pred);
 
300
          ICI->setOperand(1, CmpRHS);
 
301
          SI.setOperand(1, TrueVal);
 
302
          SI.setOperand(2, FalseVal);
 
303
          Changed = true;
 
304
        }
 
305
        break;
 
306
      }
 
307
      case ICmpInst::ICMP_UGT:
 
308
      case ICmpInst::ICMP_SGT: {
 
309
        // X > MAX ? T : F  -->  F
 
310
        if (CI->isMaxValue(Pred == ICmpInst::ICMP_SGT))
 
311
          return ReplaceInstUsesWith(SI, FalseVal);
 
312
        // X > C ? X : C+1  -->  X < C+1 ? C+1 : X
 
313
        Constant *AdjustedRHS =
 
314
          ConstantInt::get(CI->getContext(), CI->getValue()+1);
 
315
        if ((CmpLHS == TrueVal && AdjustedRHS == FalseVal) ||
 
316
            (CmpLHS == FalseVal && AdjustedRHS == TrueVal)) {
 
317
          Pred = ICmpInst::getSwappedPredicate(Pred);
 
318
          CmpRHS = AdjustedRHS;
 
319
          std::swap(FalseVal, TrueVal);
 
320
          ICI->setPredicate(Pred);
 
321
          ICI->setOperand(1, CmpRHS);
 
322
          SI.setOperand(1, TrueVal);
 
323
          SI.setOperand(2, FalseVal);
 
324
          Changed = true;
 
325
        }
 
326
        break;
 
327
      }
 
328
      }
 
329
    }
 
330
 
 
331
  if (CmpLHS == TrueVal && CmpRHS == FalseVal) {
 
332
    // Transform (X == Y) ? X : Y  -> Y
 
333
    if (Pred == ICmpInst::ICMP_EQ)
 
334
      return ReplaceInstUsesWith(SI, FalseVal);
 
335
    // Transform (X != Y) ? X : Y  -> X
 
336
    if (Pred == ICmpInst::ICMP_NE)
 
337
      return ReplaceInstUsesWith(SI, TrueVal);
 
338
    /// NOTE: if we wanted to, this is where to detect integer MIN/MAX
 
339
 
 
340
  } else if (CmpLHS == FalseVal && CmpRHS == TrueVal) {
 
341
    // Transform (X == Y) ? Y : X  -> X
 
342
    if (Pred == ICmpInst::ICMP_EQ)
 
343
      return ReplaceInstUsesWith(SI, FalseVal);
 
344
    // Transform (X != Y) ? Y : X  -> Y
 
345
    if (Pred == ICmpInst::ICMP_NE)
 
346
      return ReplaceInstUsesWith(SI, TrueVal);
 
347
    /// NOTE: if we wanted to, this is where to detect integer MIN/MAX
 
348
  }
 
349
  return Changed ? &SI : 0;
 
350
}
 
351
 
 
352
 
 
353
/// CanSelectOperandBeMappingIntoPredBlock - SI is a select whose condition is a
 
354
/// PHI node (but the two may be in different blocks).  See if the true/false
 
355
/// values (V) are live in all of the predecessor blocks of the PHI.  For
 
356
/// example, cases like this cannot be mapped:
 
357
///
 
358
///   X = phi [ C1, BB1], [C2, BB2]
 
359
///   Y = add
 
360
///   Z = select X, Y, 0
 
361
///
 
362
/// because Y is not live in BB1/BB2.
 
363
///
 
364
static bool CanSelectOperandBeMappingIntoPredBlock(const Value *V,
 
365
                                                   const SelectInst &SI) {
 
366
  // If the value is a non-instruction value like a constant or argument, it
 
367
  // can always be mapped.
 
368
  const Instruction *I = dyn_cast<Instruction>(V);
 
369
  if (I == 0) return true;
 
370
  
 
371
  // If V is a PHI node defined in the same block as the condition PHI, we can
 
372
  // map the arguments.
 
373
  const PHINode *CondPHI = cast<PHINode>(SI.getCondition());
 
374
  
 
375
  if (const PHINode *VP = dyn_cast<PHINode>(I))
 
376
    if (VP->getParent() == CondPHI->getParent())
 
377
      return true;
 
378
  
 
379
  // Otherwise, if the PHI and select are defined in the same block and if V is
 
380
  // defined in a different block, then we can transform it.
 
381
  if (SI.getParent() == CondPHI->getParent() &&
 
382
      I->getParent() != CondPHI->getParent())
 
383
    return true;
 
384
  
 
385
  // Otherwise we have a 'hard' case and we can't tell without doing more
 
386
  // detailed dominator based analysis, punt.
 
387
  return false;
 
388
}
 
389
 
 
390
/// FoldSPFofSPF - We have an SPF (e.g. a min or max) of an SPF of the form:
 
391
///   SPF2(SPF1(A, B), C) 
 
392
Instruction *InstCombiner::FoldSPFofSPF(Instruction *Inner,
 
393
                                        SelectPatternFlavor SPF1,
 
394
                                        Value *A, Value *B,
 
395
                                        Instruction &Outer,
 
396
                                        SelectPatternFlavor SPF2, Value *C) {
 
397
  if (C == A || C == B) {
 
398
    // MAX(MAX(A, B), B) -> MAX(A, B)
 
399
    // MIN(MIN(a, b), a) -> MIN(a, b)
 
400
    if (SPF1 == SPF2)
 
401
      return ReplaceInstUsesWith(Outer, Inner);
 
402
    
 
403
    // MAX(MIN(a, b), a) -> a
 
404
    // MIN(MAX(a, b), a) -> a
 
405
    if ((SPF1 == SPF_SMIN && SPF2 == SPF_SMAX) ||
 
406
        (SPF1 == SPF_SMAX && SPF2 == SPF_SMIN) ||
 
407
        (SPF1 == SPF_UMIN && SPF2 == SPF_UMAX) ||
 
408
        (SPF1 == SPF_UMAX && SPF2 == SPF_UMIN))
 
409
      return ReplaceInstUsesWith(Outer, C);
 
410
  }
 
411
  
 
412
  // TODO: MIN(MIN(A, 23), 97)
 
413
  return 0;
 
414
}
 
415
 
 
416
 
 
417
 
 
418
 
 
419
Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
 
420
  Value *CondVal = SI.getCondition();
 
421
  Value *TrueVal = SI.getTrueValue();
 
422
  Value *FalseVal = SI.getFalseValue();
 
423
 
 
424
  // select true, X, Y  -> X
 
425
  // select false, X, Y -> Y
 
426
  if (ConstantInt *C = dyn_cast<ConstantInt>(CondVal))
 
427
    return ReplaceInstUsesWith(SI, C->getZExtValue() ? TrueVal : FalseVal);
 
428
 
 
429
  // select C, X, X -> X
 
430
  if (TrueVal == FalseVal)
 
431
    return ReplaceInstUsesWith(SI, TrueVal);
 
432
 
 
433
  if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
 
434
    return ReplaceInstUsesWith(SI, FalseVal);
 
435
  if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
 
436
    return ReplaceInstUsesWith(SI, TrueVal);
 
437
  if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
 
438
    if (isa<Constant>(TrueVal))
 
439
      return ReplaceInstUsesWith(SI, TrueVal);
 
440
    else
 
441
      return ReplaceInstUsesWith(SI, FalseVal);
 
442
  }
 
443
 
 
444
  if (SI.getType()->isIntegerTy(1)) {
 
445
    if (ConstantInt *C = dyn_cast<ConstantInt>(TrueVal)) {
 
446
      if (C->getZExtValue()) {
 
447
        // Change: A = select B, true, C --> A = or B, C
 
448
        return BinaryOperator::CreateOr(CondVal, FalseVal);
 
449
      } else {
 
450
        // Change: A = select B, false, C --> A = and !B, C
 
451
        Value *NotCond =
 
452
          InsertNewInstBefore(BinaryOperator::CreateNot(CondVal,
 
453
                                             "not."+CondVal->getName()), SI);
 
454
        return BinaryOperator::CreateAnd(NotCond, FalseVal);
 
455
      }
 
456
    } else if (ConstantInt *C = dyn_cast<ConstantInt>(FalseVal)) {
 
457
      if (C->getZExtValue() == false) {
 
458
        // Change: A = select B, C, false --> A = and B, C
 
459
        return BinaryOperator::CreateAnd(CondVal, TrueVal);
 
460
      } else {
 
461
        // Change: A = select B, C, true --> A = or !B, C
 
462
        Value *NotCond =
 
463
          InsertNewInstBefore(BinaryOperator::CreateNot(CondVal,
 
464
                                             "not."+CondVal->getName()), SI);
 
465
        return BinaryOperator::CreateOr(NotCond, TrueVal);
 
466
      }
 
467
    }
 
468
    
 
469
    // select a, b, a  -> a&b
 
470
    // select a, a, b  -> a|b
 
471
    if (CondVal == TrueVal)
 
472
      return BinaryOperator::CreateOr(CondVal, FalseVal);
 
473
    else if (CondVal == FalseVal)
 
474
      return BinaryOperator::CreateAnd(CondVal, TrueVal);
 
475
  }
 
476
 
 
477
  // Selecting between two integer constants?
 
478
  if (ConstantInt *TrueValC = dyn_cast<ConstantInt>(TrueVal))
 
479
    if (ConstantInt *FalseValC = dyn_cast<ConstantInt>(FalseVal)) {
 
480
      // select C, 1, 0 -> zext C to int
 
481
      if (FalseValC->isZero() && TrueValC->getValue() == 1)
 
482
        return new ZExtInst(CondVal, SI.getType());
 
483
 
 
484
      // select C, -1, 0 -> sext C to int
 
485
      if (FalseValC->isZero() && TrueValC->isAllOnesValue())
 
486
        return new SExtInst(CondVal, SI.getType());
 
487
      
 
488
      // select C, 0, 1 -> zext !C to int
 
489
      if (TrueValC->isZero() && FalseValC->getValue() == 1) {
 
490
        Value *NotCond = Builder->CreateNot(CondVal, "not."+CondVal->getName());
 
491
        return new ZExtInst(NotCond, SI.getType());
 
492
      }
 
493
 
 
494
      // select C, 0, -1 -> sext !C to int
 
495
      if (TrueValC->isZero() && FalseValC->isAllOnesValue()) {
 
496
        Value *NotCond = Builder->CreateNot(CondVal, "not."+CondVal->getName());
 
497
        return new SExtInst(NotCond, SI.getType());
 
498
      }
 
499
      
 
500
      if (ICmpInst *IC = dyn_cast<ICmpInst>(SI.getCondition())) {
 
501
        // If one of the constants is zero (we know they can't both be) and we
 
502
        // have an icmp instruction with zero, and we have an 'and' with the
 
503
        // non-constant value, eliminate this whole mess.  This corresponds to
 
504
        // cases like this: ((X & 27) ? 27 : 0)
 
505
        if (TrueValC->isZero() || FalseValC->isZero())
 
506
          if (IC->isEquality() && isa<ConstantInt>(IC->getOperand(1)) &&
 
507
              cast<Constant>(IC->getOperand(1))->isNullValue())
 
508
            if (Instruction *ICA = dyn_cast<Instruction>(IC->getOperand(0)))
 
509
              if (ICA->getOpcode() == Instruction::And &&
 
510
                  isa<ConstantInt>(ICA->getOperand(1)) &&
 
511
                  (ICA->getOperand(1) == TrueValC ||
 
512
                   ICA->getOperand(1) == FalseValC) &&
 
513
               cast<ConstantInt>(ICA->getOperand(1))->getValue().isPowerOf2()) {
 
514
                // Okay, now we know that everything is set up, we just don't
 
515
                // know whether we have a icmp_ne or icmp_eq and whether the 
 
516
                // true or false val is the zero.
 
517
                bool ShouldNotVal = !TrueValC->isZero();
 
518
                ShouldNotVal ^= IC->getPredicate() == ICmpInst::ICMP_NE;
 
519
                Value *V = ICA;
 
520
                if (ShouldNotVal)
 
521
                  V = Builder->CreateXor(V, ICA->getOperand(1));
 
522
                return ReplaceInstUsesWith(SI, V);
 
523
              }
 
524
      }
 
525
    }
 
526
 
 
527
  // See if we are selecting two values based on a comparison of the two values.
 
528
  if (FCmpInst *FCI = dyn_cast<FCmpInst>(CondVal)) {
 
529
    if (FCI->getOperand(0) == TrueVal && FCI->getOperand(1) == FalseVal) {
 
530
      // Transform (X == Y) ? X : Y  -> Y
 
531
      if (FCI->getPredicate() == FCmpInst::FCMP_OEQ) {
 
532
        // This is not safe in general for floating point:  
 
533
        // consider X== -0, Y== +0.
 
534
        // It becomes safe if either operand is a nonzero constant.
 
535
        ConstantFP *CFPt, *CFPf;
 
536
        if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) &&
 
537
              !CFPt->getValueAPF().isZero()) ||
 
538
            ((CFPf = dyn_cast<ConstantFP>(FalseVal)) &&
 
539
             !CFPf->getValueAPF().isZero()))
 
540
        return ReplaceInstUsesWith(SI, FalseVal);
 
541
      }
 
542
      // Transform (X une Y) ? X : Y  -> X
 
543
      if (FCI->getPredicate() == FCmpInst::FCMP_UNE) {
 
544
        // This is not safe in general for floating point:  
 
545
        // consider X== -0, Y== +0.
 
546
        // It becomes safe if either operand is a nonzero constant.
 
547
        ConstantFP *CFPt, *CFPf;
 
548
        if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) &&
 
549
              !CFPt->getValueAPF().isZero()) ||
 
550
            ((CFPf = dyn_cast<ConstantFP>(FalseVal)) &&
 
551
             !CFPf->getValueAPF().isZero()))
 
552
        return ReplaceInstUsesWith(SI, TrueVal);
 
553
      }
 
554
      // NOTE: if we wanted to, this is where to detect MIN/MAX
 
555
 
 
556
    } else if (FCI->getOperand(0) == FalseVal && FCI->getOperand(1) == TrueVal){
 
557
      // Transform (X == Y) ? Y : X  -> X
 
558
      if (FCI->getPredicate() == FCmpInst::FCMP_OEQ) {
 
559
        // This is not safe in general for floating point:  
 
560
        // consider X== -0, Y== +0.
 
561
        // It becomes safe if either operand is a nonzero constant.
 
562
        ConstantFP *CFPt, *CFPf;
 
563
        if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) &&
 
564
              !CFPt->getValueAPF().isZero()) ||
 
565
            ((CFPf = dyn_cast<ConstantFP>(FalseVal)) &&
 
566
             !CFPf->getValueAPF().isZero()))
 
567
          return ReplaceInstUsesWith(SI, FalseVal);
 
568
      }
 
569
      // Transform (X une Y) ? Y : X  -> Y
 
570
      if (FCI->getPredicate() == FCmpInst::FCMP_UNE) {
 
571
        // This is not safe in general for floating point:  
 
572
        // consider X== -0, Y== +0.
 
573
        // It becomes safe if either operand is a nonzero constant.
 
574
        ConstantFP *CFPt, *CFPf;
 
575
        if (((CFPt = dyn_cast<ConstantFP>(TrueVal)) &&
 
576
              !CFPt->getValueAPF().isZero()) ||
 
577
            ((CFPf = dyn_cast<ConstantFP>(FalseVal)) &&
 
578
             !CFPf->getValueAPF().isZero()))
 
579
          return ReplaceInstUsesWith(SI, TrueVal);
 
580
      }
 
581
      // NOTE: if we wanted to, this is where to detect MIN/MAX
 
582
    }
 
583
    // NOTE: if we wanted to, this is where to detect ABS
 
584
  }
 
585
 
 
586
  // See if we are selecting two values based on a comparison of the two values.
 
587
  if (ICmpInst *ICI = dyn_cast<ICmpInst>(CondVal))
 
588
    if (Instruction *Result = visitSelectInstWithICmp(SI, ICI))
 
589
      return Result;
 
590
 
 
591
  if (Instruction *TI = dyn_cast<Instruction>(TrueVal))
 
592
    if (Instruction *FI = dyn_cast<Instruction>(FalseVal))
 
593
      if (TI->hasOneUse() && FI->hasOneUse()) {
 
594
        Instruction *AddOp = 0, *SubOp = 0;
 
595
 
 
596
        // Turn (select C, (op X, Y), (op X, Z)) -> (op X, (select C, Y, Z))
 
597
        if (TI->getOpcode() == FI->getOpcode())
 
598
          if (Instruction *IV = FoldSelectOpOp(SI, TI, FI))
 
599
            return IV;
 
600
 
 
601
        // Turn select C, (X+Y), (X-Y) --> (X+(select C, Y, (-Y))).  This is
 
602
        // even legal for FP.
 
603
        if ((TI->getOpcode() == Instruction::Sub &&
 
604
             FI->getOpcode() == Instruction::Add) ||
 
605
            (TI->getOpcode() == Instruction::FSub &&
 
606
             FI->getOpcode() == Instruction::FAdd)) {
 
607
          AddOp = FI; SubOp = TI;
 
608
        } else if ((FI->getOpcode() == Instruction::Sub &&
 
609
                    TI->getOpcode() == Instruction::Add) ||
 
610
                   (FI->getOpcode() == Instruction::FSub &&
 
611
                    TI->getOpcode() == Instruction::FAdd)) {
 
612
          AddOp = TI; SubOp = FI;
 
613
        }
 
614
 
 
615
        if (AddOp) {
 
616
          Value *OtherAddOp = 0;
 
617
          if (SubOp->getOperand(0) == AddOp->getOperand(0)) {
 
618
            OtherAddOp = AddOp->getOperand(1);
 
619
          } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) {
 
620
            OtherAddOp = AddOp->getOperand(0);
 
621
          }
 
622
 
 
623
          if (OtherAddOp) {
 
624
            // So at this point we know we have (Y -> OtherAddOp):
 
625
            //        select C, (add X, Y), (sub X, Z)
 
626
            Value *NegVal;  // Compute -Z
 
627
            if (Constant *C = dyn_cast<Constant>(SubOp->getOperand(1))) {
 
628
              NegVal = ConstantExpr::getNeg(C);
 
629
            } else {
 
630
              NegVal = InsertNewInstBefore(
 
631
                    BinaryOperator::CreateNeg(SubOp->getOperand(1),
 
632
                                              "tmp"), SI);
 
633
            }
 
634
 
 
635
            Value *NewTrueOp = OtherAddOp;
 
636
            Value *NewFalseOp = NegVal;
 
637
            if (AddOp != TI)
 
638
              std::swap(NewTrueOp, NewFalseOp);
 
639
            Instruction *NewSel =
 
640
              SelectInst::Create(CondVal, NewTrueOp,
 
641
                                 NewFalseOp, SI.getName() + ".p");
 
642
 
 
643
            NewSel = InsertNewInstBefore(NewSel, SI);
 
644
            return BinaryOperator::CreateAdd(SubOp->getOperand(0), NewSel);
 
645
          }
 
646
        }
 
647
      }
 
648
 
 
649
  // See if we can fold the select into one of our operands.
 
650
  if (SI.getType()->isIntegerTy()) {
 
651
    if (Instruction *FoldI = FoldSelectIntoOp(SI, TrueVal, FalseVal))
 
652
      return FoldI;
 
653
    
 
654
    // MAX(MAX(a, b), a) -> MAX(a, b)
 
655
    // MIN(MIN(a, b), a) -> MIN(a, b)
 
656
    // MAX(MIN(a, b), a) -> a
 
657
    // MIN(MAX(a, b), a) -> a
 
658
    Value *LHS, *RHS, *LHS2, *RHS2;
 
659
    if (SelectPatternFlavor SPF = MatchSelectPattern(&SI, LHS, RHS)) {
 
660
      if (SelectPatternFlavor SPF2 = MatchSelectPattern(LHS, LHS2, RHS2))
 
661
        if (Instruction *R = FoldSPFofSPF(cast<Instruction>(LHS),SPF2,LHS2,RHS2, 
 
662
                                          SI, SPF, RHS))
 
663
          return R;
 
664
      if (SelectPatternFlavor SPF2 = MatchSelectPattern(RHS, LHS2, RHS2))
 
665
        if (Instruction *R = FoldSPFofSPF(cast<Instruction>(RHS),SPF2,LHS2,RHS2,
 
666
                                          SI, SPF, LHS))
 
667
          return R;
 
668
    }
 
669
 
 
670
    // TODO.
 
671
    // ABS(-X) -> ABS(X)
 
672
    // ABS(ABS(X)) -> ABS(X)
 
673
  }
 
674
 
 
675
  // See if we can fold the select into a phi node if the condition is a select.
 
676
  if (isa<PHINode>(SI.getCondition())) 
 
677
    // The true/false values have to be live in the PHI predecessor's blocks.
 
678
    if (CanSelectOperandBeMappingIntoPredBlock(TrueVal, SI) &&
 
679
        CanSelectOperandBeMappingIntoPredBlock(FalseVal, SI))
 
680
      if (Instruction *NV = FoldOpIntoPhi(SI))
 
681
        return NV;
 
682
 
 
683
  if (BinaryOperator::isNot(CondVal)) {
 
684
    SI.setOperand(0, BinaryOperator::getNotArgument(CondVal));
 
685
    SI.setOperand(1, FalseVal);
 
686
    SI.setOperand(2, TrueVal);
 
687
    return &SI;
 
688
  }
 
689
 
 
690
  return 0;
 
691
}