← Back to branch summary

~ubuntu-branches/ubuntu/vivid/clamav/vivid

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/utils/TableGen/DAGISelMatcherOpt.cpp

  • Committer: Package Import Robot
  • Author(s): Scott Kitterman, Sebastian Andrzej Siewior, Andreas Cadhalpun, Scott Kitterman, Javier Fernández-Sanguino
  • Date: 2015-01-28 00:25:13 UTC
  • mfrom: (0.48.14 sid)
  • Revision ID: package-import@ubuntu.com-20150128002513-lil2oi74cooy4lzr
Tags: 0.98.6+dfsg-1
http://bugs.debian.org/774686
http://bugs.debian.org/767350
http://bugs.debian.org/775400
http://bugs.debian.org/767353
http://bugs.debian.org/773563
[ Sebastian Andrzej Siewior ]
* update "fix-ssize_t-size_t-off_t-printf-modifier", include of misc.h was
  missing but was pulled in via the systemd patch.
* Don't leak return codes from libmspack to clamav API. (Closes: #774686).

[ Andreas Cadhalpun ]
* Add patch to avoid emitting incremental progress messages when not
  outputting to a terminal. (Closes: #767350)
* Update lintian-overrides for unused-file-paragraph-in-dep5-copyright.
* clamav-base.postinst: always chown /var/log/clamav and /var/lib/clamav
  to clamav:clamav, not only on fresh installations. (Closes: #775400)
* Adapt the clamav-daemon and clamav-freshclam logrotate scripts,
  so that they correctly work under systemd.
* Move the PidFile variable from the clamd/freshclam configuration files
  to the init scripts. This makes the init scripts more robust against
  misconfiguration and avoids error messages with systemd. (Closes: #767353)
* debian/copyright: drop files from Files-Excluded only present in github
  tarballs
* Drop Workaround-a-bug-in-libc-on-Hurd.patch, because hurd got fixed.
  (see #752237)
* debian/rules: Remove useless --with-system-tommath --without-included-ltdl
  configure options.

[ Scott Kitterman ]
* Stop stripping llvm when repacking the tarball as the system llvm on some
  releases is too old to use
* New upstream bugfix release
  - Library shared object revisions.
  - Includes a patch from Sebastian Andrzej Siewior making ClamAV pid files
    compatible with systemd.
  - Fix a heap out of bounds condition with crafted Yoda's crypter files.
    This issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted mew packer files. This
    issue was discovered by Felix Groebert of the Google Security Team.
  - Fix a heap out of bounds condition with crafted upx packer files. This
    issue was discovered by Kevin Szkudlapski of Quarkslab.
  - Fix a heap out of bounds condition with crafted upack packer files. This
    issue was discovered by Sebastian Andrzej Siewior. CVE-2014-9328.
  - Compensate a crash due to incorrect compiler optimization when handling
    crafted petite packer files. This issue was discovered by Sebastian
    Andrzej Siewior.
* Update lintian override for embedded zlib to match new so version

[ Javier Fernández-Sanguino ]
* Updated Spanish Debconf template translation (Closes: #773563)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/utils/TableGen/DAGISelMatcherOpt.cpp
 
1
//===- DAGISelMatcherOpt.cpp - Optimize a DAG Matcher ---------------------===//
 
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 DAG Matcher optimizer.
 
11
//
 
12
//===----------------------------------------------------------------------===//
 
13
 
 
14
#define DEBUG_TYPE "isel-opt"
 
15
#include "DAGISelMatcher.h"
 
16
#include "CodeGenDAGPatterns.h"
 
17
#include "llvm/ADT/DenseSet.h"
 
18
#include "llvm/ADT/StringSet.h"
 
19
#include "llvm/Support/Debug.h"
 
20
#include "llvm/Support/raw_ostream.h"
 
21
#include <vector>
 
22
using namespace llvm;
 
23
 
 
24
/// ContractNodes - Turn multiple matcher node patterns like 'MoveChild+Record'
 
25
/// into single compound nodes like RecordChild.
 
26
static void ContractNodes(OwningPtr<Matcher> &MatcherPtr,
 
27
                          const CodeGenDAGPatterns &CGP) {
 
28
  // If we reached the end of the chain, we're done.
 
29
  Matcher *N = MatcherPtr.get();
 
30
  if (N == 0) return;
 
31
  
 
32
  // If we have a scope node, walk down all of the children.
 
33
  if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) {
 
34
    for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
 
35
      OwningPtr<Matcher> Child(Scope->takeChild(i));
 
36
      ContractNodes(Child, CGP);
 
37
      Scope->resetChild(i, Child.take());
 
38
    }
 
39
    return;
 
40
  }
 
41
  
 
42
  // If we found a movechild node with a node that comes in a 'foochild' form,
 
43
  // transform it.
 
44
  if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) {
 
45
    Matcher *New = 0;
 
46
    if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext()))
 
47
      if (MC->getChildNo() < 8)  // Only have RecordChild0...7
 
48
        New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(),
 
49
                                     RM->getResultNo());
 
50
    
 
51
    if (CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(MC->getNext()))
 
52
      if (MC->getChildNo() < 8 &&  // Only have CheckChildType0...7
 
53
          CT->getResNo() == 0)     // CheckChildType checks res #0
 
54
        New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType());
 
55
    
 
56
    if (New) {
 
57
      // Insert the new node.
 
58
      New->setNext(MatcherPtr.take());
 
59
      MatcherPtr.reset(New);
 
60
      // Remove the old one.
 
61
      MC->setNext(MC->getNext()->takeNext());
 
62
      return ContractNodes(MatcherPtr, CGP);
 
63
    }
 
64
  }
 
65
  
 
66
  // Zap movechild -> moveparent.
 
67
  if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N))
 
68
    if (MoveParentMatcher *MP = 
 
69
          dyn_cast<MoveParentMatcher>(MC->getNext())) {
 
70
      MatcherPtr.reset(MP->takeNext());
 
71
      return ContractNodes(MatcherPtr, CGP);
 
72
    }
 
73
 
 
74
  // Turn EmitNode->MarkFlagResults->CompleteMatch into
 
75
  // MarkFlagResults->EmitNode->CompleteMatch when we can to encourage
 
76
  // MorphNodeTo formation.  This is safe because MarkFlagResults never refers
 
77
  // to the root of the pattern.
 
78
  if (isa<EmitNodeMatcher>(N) && isa<MarkFlagResultsMatcher>(N->getNext()) &&
 
79
      isa<CompleteMatchMatcher>(N->getNext()->getNext())) {
 
80
    // Unlink the two nodes from the list.
 
81
    Matcher *EmitNode = MatcherPtr.take();
 
82
    Matcher *MFR = EmitNode->takeNext();
 
83
    Matcher *Tail = MFR->takeNext();
 
84
        
 
85
    // Relink them.
 
86
    MatcherPtr.reset(MFR);
 
87
    MFR->setNext(EmitNode);
 
88
    EmitNode->setNext(Tail);
 
89
    return ContractNodes(MatcherPtr, CGP);
 
90
  }
 
91
 
 
92
  // Turn EmitNode->CompleteMatch into MorphNodeTo if we can.
 
93
  if (EmitNodeMatcher *EN = dyn_cast<EmitNodeMatcher>(N))
 
94
    if (CompleteMatchMatcher *CM =
 
95
          dyn_cast<CompleteMatchMatcher>(EN->getNext())) {
 
96
      // We can only use MorphNodeTo if the result values match up.
 
97
      unsigned RootResultFirst = EN->getFirstResultSlot();
 
98
      bool ResultsMatch = true;
 
99
      for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i)
 
100
        if (CM->getResult(i) != RootResultFirst+i)
 
101
          ResultsMatch = false;
 
102
      
 
103
      // If the selected node defines a subset of the flag/chain results, we
 
104
      // can't use MorphNodeTo.  For example, we can't use MorphNodeTo if the
 
105
      // matched pattern has a chain but the root node doesn't.
 
106
      const PatternToMatch &Pattern = CM->getPattern();
 
107
      
 
108
      if (!EN->hasChain() &&
 
109
          Pattern.getSrcPattern()->NodeHasProperty(SDNPHasChain, CGP))
 
110
        ResultsMatch = false;
 
111
 
 
112
      // If the matched node has a flag and the output root doesn't, we can't
 
113
      // use MorphNodeTo.
 
114
      //
 
115
      // NOTE: Strictly speaking, we don't have to check for the flag here
 
116
      // because the code in the pattern generator doesn't handle it right.  We
 
117
      // do it anyway for thoroughness.
 
118
      if (!EN->hasOutFlag() &&
 
119
          Pattern.getSrcPattern()->NodeHasProperty(SDNPOutFlag, CGP))
 
120
        ResultsMatch = false;
 
121
      
 
122
      
 
123
      // If the root result node defines more results than the source root node
 
124
      // *and* has a chain or flag input, then we can't match it because it
 
125
      // would end up replacing the extra result with the chain/flag.
 
126
#if 0
 
127
      if ((EN->hasFlag() || EN->hasChain()) &&
 
128
          EN->getNumNonChainFlagVTs() > ... need to get no results reliably ...)
 
129
        ResultMatch = false;
 
130
#endif
 
131
          
 
132
      if (ResultsMatch) {
 
133
        const SmallVectorImpl<MVT::SimpleValueType> &VTs = EN->getVTList();
 
134
        const SmallVectorImpl<unsigned> &Operands = EN->getOperandList();
 
135
        MatcherPtr.reset(new MorphNodeToMatcher(EN->getOpcodeName(),
 
136
                                                VTs.data(), VTs.size(),
 
137
                                                Operands.data(),Operands.size(),
 
138
                                                EN->hasChain(), EN->hasInFlag(),
 
139
                                                EN->hasOutFlag(),
 
140
                                                EN->hasMemRefs(),
 
141
                                                EN->getNumFixedArityOperands(),
 
142
                                                Pattern));
 
143
        return;
 
144
      }
 
145
 
 
146
      // FIXME2: Kill off all the SelectionDAG::SelectNodeTo and getMachineNode
 
147
      // variants.
 
148
    }
 
149
  
 
150
  ContractNodes(N->getNextPtr(), CGP);
 
151
  
 
152
  
 
153
  // If we have a CheckType/CheckChildType/Record node followed by a
 
154
  // CheckOpcode, invert the two nodes.  We prefer to do structural checks
 
155
  // before type checks, as this opens opportunities for factoring on targets
 
156
  // like X86 where many operations are valid on multiple types.
 
157
  if ((isa<CheckTypeMatcher>(N) || isa<CheckChildTypeMatcher>(N) ||
 
158
       isa<RecordMatcher>(N)) &&
 
159
      isa<CheckOpcodeMatcher>(N->getNext())) {
 
160
    // Unlink the two nodes from the list.
 
161
    Matcher *CheckType = MatcherPtr.take();
 
162
    Matcher *CheckOpcode = CheckType->takeNext();
 
163
    Matcher *Tail = CheckOpcode->takeNext();
 
164
    
 
165
    // Relink them.
 
166
    MatcherPtr.reset(CheckOpcode);
 
167
    CheckOpcode->setNext(CheckType);
 
168
    CheckType->setNext(Tail);
 
169
    return ContractNodes(MatcherPtr, CGP);
 
170
  }
 
171
}
 
172
 
 
173
/// SinkPatternPredicates - Pattern predicates can be checked at any level of
 
174
/// the matching tree.  The generator dumps them at the top level of the pattern
 
175
/// though, which prevents factoring from being able to see past them.  This
 
176
/// optimization sinks them as far down into the pattern as possible.
 
177
///
 
178
/// Conceptually, we'd like to sink these predicates all the way to the last
 
179
/// matcher predicate in the series.  However, it turns out that some
 
180
/// ComplexPatterns have side effects on the graph, so we really don't want to
 
181
/// run a the complex pattern if the pattern predicate will fail.  For this
 
182
/// reason, we refuse to sink the pattern predicate past a ComplexPattern.
 
183
///
 
184
static void SinkPatternPredicates(OwningPtr<Matcher> &MatcherPtr) {
 
185
  // Recursively scan for a PatternPredicate.
 
186
  // If we reached the end of the chain, we're done.
 
187
  Matcher *N = MatcherPtr.get();
 
188
  if (N == 0) return;
 
189
  
 
190
  // Walk down all members of a scope node.
 
191
  if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) {
 
192
    for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
 
193
      OwningPtr<Matcher> Child(Scope->takeChild(i));
 
194
      SinkPatternPredicates(Child);
 
195
      Scope->resetChild(i, Child.take());
 
196
    }
 
197
    return;
 
198
  }
 
199
  
 
200
  // If this node isn't a CheckPatternPredicateMatcher we keep scanning until
 
201
  // we find one.
 
202
  CheckPatternPredicateMatcher *CPPM =dyn_cast<CheckPatternPredicateMatcher>(N);
 
203
  if (CPPM == 0)
 
204
    return SinkPatternPredicates(N->getNextPtr());
 
205
  
 
206
  // Ok, we found one, lets try to sink it. Check if we can sink it past the
 
207
  // next node in the chain.  If not, we won't be able to change anything and
 
208
  // might as well bail.
 
209
  if (!CPPM->getNext()->isSafeToReorderWithPatternPredicate())
 
210
    return;
 
211
  
 
212
  // Okay, we know we can sink it past at least one node.  Unlink it from the
 
213
  // chain and scan for the new insertion point.
 
214
  MatcherPtr.take();  // Don't delete CPPM.
 
215
  MatcherPtr.reset(CPPM->takeNext());
 
216
  
 
217
  N = MatcherPtr.get();
 
218
  while (N->getNext()->isSafeToReorderWithPatternPredicate())
 
219
    N = N->getNext();
 
220
  
 
221
  // At this point, we want to insert CPPM after N.
 
222
  CPPM->setNext(N->takeNext());
 
223
  N->setNext(CPPM);
 
224
}
 
225
 
 
226
/// FindNodeWithKind - Scan a series of matchers looking for a matcher with a
 
227
/// specified kind.  Return null if we didn't find one otherwise return the
 
228
/// matcher.
 
229
static Matcher *FindNodeWithKind(Matcher *M, Matcher::KindTy Kind) {
 
230
  for (; M; M = M->getNext())
 
231
    if (M->getKind() == Kind)
 
232
      return M;
 
233
  return 0;
 
234
}
 
235
 
 
236
 
 
237
/// FactorNodes - Turn matches like this:
 
238
///   Scope
 
239
///     OPC_CheckType i32
 
240
///       ABC
 
241
///     OPC_CheckType i32
 
242
///       XYZ
 
243
/// into:
 
244
///   OPC_CheckType i32
 
245
///     Scope
 
246
///       ABC
 
247
///       XYZ
 
248
///
 
249
static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) {
 
250
  // If we reached the end of the chain, we're done.
 
251
  Matcher *N = MatcherPtr.get();
 
252
  if (N == 0) return;
 
253
  
 
254
  // If this is not a push node, just scan for one.
 
255
  ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N);
 
256
  if (Scope == 0)
 
257
    return FactorNodes(N->getNextPtr());
 
258
  
 
259
  // Okay, pull together the children of the scope node into a vector so we can
 
260
  // inspect it more easily.  While we're at it, bucket them up by the hash
 
261
  // code of their first predicate.
 
262
  SmallVector<Matcher*, 32> OptionsToMatch;
 
263
  
 
264
  for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) {
 
265
    // Factor the subexpression.
 
266
    OwningPtr<Matcher> Child(Scope->takeChild(i));
 
267
    FactorNodes(Child);
 
268
    
 
269
    if (Matcher *N = Child.take())
 
270
      OptionsToMatch.push_back(N);
 
271
  }
 
272
  
 
273
  SmallVector<Matcher*, 32> NewOptionsToMatch;
 
274
  
 
275
  // Loop over options to match, merging neighboring patterns with identical
 
276
  // starting nodes into a shared matcher.
 
277
  for (unsigned OptionIdx = 0, e = OptionsToMatch.size(); OptionIdx != e;) {
 
278
    // Find the set of matchers that start with this node.
 
279
    Matcher *Optn = OptionsToMatch[OptionIdx++];
 
280
 
 
281
    if (OptionIdx == e) {
 
282
      NewOptionsToMatch.push_back(Optn);
 
283
      continue;
 
284
    }
 
285
    
 
286
    // See if the next option starts with the same matcher.  If the two
 
287
    // neighbors *do* start with the same matcher, we can factor the matcher out
 
288
    // of at least these two patterns.  See what the maximal set we can merge
 
289
    // together is.
 
290
    SmallVector<Matcher*, 8> EqualMatchers;
 
291
    EqualMatchers.push_back(Optn);
 
292
    
 
293
    // Factor all of the known-equal matchers after this one into the same
 
294
    // group.
 
295
    while (OptionIdx != e && OptionsToMatch[OptionIdx]->isEqual(Optn))
 
296
      EqualMatchers.push_back(OptionsToMatch[OptionIdx++]);
 
297
 
 
298
    // If we found a non-equal matcher, see if it is contradictory with the
 
299
    // current node.  If so, we know that the ordering relation between the
 
300
    // current sets of nodes and this node don't matter.  Look past it to see if
 
301
    // we can merge anything else into this matching group.
 
302
    unsigned Scan = OptionIdx;
 
303
    while (1) {
 
304
      // If we ran out of stuff to scan, we're done.
 
305
      if (Scan == e) break;
 
306
      
 
307
      Matcher *ScanMatcher = OptionsToMatch[Scan];
 
308
      
 
309
      // If we found an entry that matches out matcher, merge it into the set to
 
310
      // handle.
 
311
      if (Optn->isEqual(ScanMatcher)) {
 
312
        // If is equal after all, add the option to EqualMatchers and remove it
 
313
        // from OptionsToMatch.
 
314
        EqualMatchers.push_back(ScanMatcher);
 
315
        OptionsToMatch.erase(OptionsToMatch.begin()+Scan);
 
316
        --e;
 
317
        continue;
 
318
      }
 
319
      
 
320
      // If the option we're checking for contradicts the start of the list,
 
321
      // skip over it.
 
322
      if (Optn->isContradictory(ScanMatcher)) {
 
323
        ++Scan;
 
324
        continue;
 
325
      }
 
326
 
 
327
      // If we're scanning for a simple node, see if it occurs later in the
 
328
      // sequence.  If so, and if we can move it up, it might be contradictory
 
329
      // or the same as what we're looking for.  If so, reorder it.
 
330
      if (Optn->isSimplePredicateOrRecordNode()) {
 
331
        Matcher *M2 = FindNodeWithKind(ScanMatcher, Optn->getKind());
 
332
        if (M2 != 0 && M2 != ScanMatcher &&
 
333
            M2->canMoveBefore(ScanMatcher) &&
 
334
            (M2->isEqual(Optn) || M2->isContradictory(Optn))) {
 
335
          Matcher *MatcherWithoutM2 = ScanMatcher->unlinkNode(M2);
 
336
          M2->setNext(MatcherWithoutM2);
 
337
          OptionsToMatch[Scan] = M2;
 
338
          continue;
 
339
        }
 
340
      }
 
341
      
 
342
      // Otherwise, we don't know how to handle this entry, we have to bail.
 
343
      break;
 
344
    }
 
345
      
 
346
    if (Scan != e &&
 
347
        // Don't print it's obvious nothing extra could be merged anyway.
 
348
        Scan+1 != e) {
 
349
      DEBUG(errs() << "Couldn't merge this:\n";
 
350
            Optn->print(errs(), 4);
 
351
            errs() << "into this:\n";
 
352
            OptionsToMatch[Scan]->print(errs(), 4);
 
353
            if (Scan+1 != e)
 
354
              OptionsToMatch[Scan+1]->printOne(errs());
 
355
            if (Scan+2 < e)
 
356
              OptionsToMatch[Scan+2]->printOne(errs());
 
357
            errs() << "\n");
 
358
    }
 
359
    
 
360
    // If we only found one option starting with this matcher, no factoring is
 
361
    // possible.
 
362
    if (EqualMatchers.size() == 1) {
 
363
      NewOptionsToMatch.push_back(EqualMatchers[0]);
 
364
      continue;
 
365
    }
 
366
    
 
367
    // Factor these checks by pulling the first node off each entry and
 
368
    // discarding it.  Take the first one off the first entry to reuse.
 
369
    Matcher *Shared = Optn;
 
370
    Optn = Optn->takeNext();
 
371
    EqualMatchers[0] = Optn;
 
372
 
 
373
    // Remove and delete the first node from the other matchers we're factoring.
 
374
    for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) {
 
375
      Matcher *Tmp = EqualMatchers[i]->takeNext();
 
376
      delete EqualMatchers[i];
 
377
      EqualMatchers[i] = Tmp;
 
378
    }
 
379
    
 
380
    Shared->setNext(new ScopeMatcher(&EqualMatchers[0], EqualMatchers.size()));
 
381
 
 
382
    // Recursively factor the newly created node.
 
383
    FactorNodes(Shared->getNextPtr());
 
384
    
 
385
    NewOptionsToMatch.push_back(Shared);
 
386
  }
 
387
  
 
388
  // If we're down to a single pattern to match, then we don't need this scope
 
389
  // anymore.
 
390
  if (NewOptionsToMatch.size() == 1) {
 
391
    MatcherPtr.reset(NewOptionsToMatch[0]);
 
392
    return;
 
393
  }
 
394
  
 
395
  if (NewOptionsToMatch.empty()) {
 
396
    MatcherPtr.reset(0);
 
397
    return;
 
398
  }
 
399
  
 
400
  // If our factoring failed (didn't achieve anything) see if we can simplify in
 
401
  // other ways.
 
402
  
 
403
  // Check to see if all of the leading entries are now opcode checks.  If so,
 
404
  // we can convert this Scope to be a OpcodeSwitch instead.
 
405
  bool AllOpcodeChecks = true, AllTypeChecks = true;
 
406
  for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) {
 
407
    // Check to see if this breaks a series of CheckOpcodeMatchers.
 
408
    if (AllOpcodeChecks &&
 
409
        !isa<CheckOpcodeMatcher>(NewOptionsToMatch[i])) {
 
410
#if 0
 
411
      if (i > 3) {
 
412
        errs() << "FAILING OPC #" << i << "\n";
 
413
        NewOptionsToMatch[i]->dump();
 
414
      }
 
415
#endif
 
416
      AllOpcodeChecks = false;
 
417
    }
 
418
 
 
419
    // Check to see if this breaks a series of CheckTypeMatcher's.
 
420
    if (AllTypeChecks) {
 
421
      CheckTypeMatcher *CTM =
 
422
        cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i],
 
423
                                                        Matcher::CheckType));
 
424
      if (CTM == 0 ||
 
425
          // iPTR checks could alias any other case without us knowing, don't
 
426
          // bother with them.
 
427
          CTM->getType() == MVT::iPTR ||
 
428
          // SwitchType only works for result #0.
 
429
          CTM->getResNo() != 0 ||
 
430
          // If the CheckType isn't at the start of the list, see if we can move
 
431
          // it there.
 
432
          !CTM->canMoveBefore(NewOptionsToMatch[i])) {
 
433
#if 0
 
434
        if (i > 3 && AllTypeChecks) {
 
435
          errs() << "FAILING TYPE #" << i << "\n";
 
436
          NewOptionsToMatch[i]->dump();
 
437
        }
 
438
#endif
 
439
        AllTypeChecks = false;
 
440
      }
 
441
    }
 
442
  }
 
443
  
 
444
  // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot.
 
445
  if (AllOpcodeChecks) {
 
446
    StringSet<> Opcodes;
 
447
    SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases;
 
448
    for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) {
 
449
      CheckOpcodeMatcher *COM = cast<CheckOpcodeMatcher>(NewOptionsToMatch[i]);
 
450
      assert(Opcodes.insert(COM->getOpcode().getEnumName()) &&
 
451
             "Duplicate opcodes not factored?");
 
452
      Cases.push_back(std::make_pair(&COM->getOpcode(), COM->getNext()));
 
453
    }
 
454
    
 
455
    MatcherPtr.reset(new SwitchOpcodeMatcher(&Cases[0], Cases.size()));
 
456
    return;
 
457
  }
 
458
  
 
459
  // If all the options are CheckType's, we can form the SwitchType, woot.
 
460
  if (AllTypeChecks) {
 
461
    DenseMap<unsigned, unsigned> TypeEntry;
 
462
    SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases;
 
463
    for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) {
 
464
      CheckTypeMatcher *CTM =
 
465
        cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i],
 
466
                                                        Matcher::CheckType));
 
467
      Matcher *MatcherWithoutCTM = NewOptionsToMatch[i]->unlinkNode(CTM);
 
468
      MVT::SimpleValueType CTMTy = CTM->getType();
 
469
      delete CTM;
 
470
      
 
471
      unsigned &Entry = TypeEntry[CTMTy];
 
472
      if (Entry != 0) {
 
473
        // If we have unfactored duplicate types, then we should factor them.
 
474
        Matcher *PrevMatcher = Cases[Entry-1].second;
 
475
        if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(PrevMatcher)) {
 
476
          SM->setNumChildren(SM->getNumChildren()+1);
 
477
          SM->resetChild(SM->getNumChildren()-1, MatcherWithoutCTM);
 
478
          continue;
 
479
        }
 
480
        
 
481
        Matcher *Entries[2] = { PrevMatcher, MatcherWithoutCTM };
 
482
        Cases[Entry-1].second = new ScopeMatcher(Entries, 2);
 
483
        continue;
 
484
      }
 
485
      
 
486
      Entry = Cases.size()+1;
 
487
      Cases.push_back(std::make_pair(CTMTy, MatcherWithoutCTM));
 
488
    }
 
489
    
 
490
    if (Cases.size() != 1) {
 
491
      MatcherPtr.reset(new SwitchTypeMatcher(&Cases[0], Cases.size()));
 
492
    } else {
 
493
      // If we factored and ended up with one case, create it now.
 
494
      MatcherPtr.reset(new CheckTypeMatcher(Cases[0].first, 0));
 
495
      MatcherPtr->setNext(Cases[0].second);
 
496
    }
 
497
    return;
 
498
  }
 
499
  
 
500
 
 
501
  // Reassemble the Scope node with the adjusted children.
 
502
  Scope->setNumChildren(NewOptionsToMatch.size());
 
503
  for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i)
 
504
    Scope->resetChild(i, NewOptionsToMatch[i]);
 
505
}
 
506
 
 
507
Matcher *llvm::OptimizeMatcher(Matcher *TheMatcher,
 
508
                               const CodeGenDAGPatterns &CGP) {
 
509
  OwningPtr<Matcher> MatcherPtr(TheMatcher);
 
510
  ContractNodes(MatcherPtr, CGP);
 
511
  SinkPatternPredicates(MatcherPtr);
 
512
  FactorNodes(MatcherPtr);
 
513
  return MatcherPtr.take();
 
514
}