llvm dev - Jan 2010 - [LLVMdev] [PATCH] Fix nondeterministic behaviour in the CodeExtractor

Hello,

The CodeExtractor contains a std::set<BasicBlock*> to keep track of the
blocks to extract. Iterators on this set are not deterministic, and so
the functions that are generated are not (the order of the
inputs/outputs can change).

The attached patch uses a SetVector instead. Ok to apply ?

Thanks,
Julien


-- 
Julien Lerouge
PGP Key Id: 0xB1964A62
PGP Fingerprint: 392D 4BAD DB8B CE7F 4E5F FA3C 62DB 4AA7 B196 4A62
PGP Public Key from: keyserver.pgp.com
-------------- next part --------------
Index: lib/Transforms/Utils/CodeExtractor.cpp
==================================================================---
lib/Transforms/Utils/CodeExtractor.cpp	(revision 93030)
+++ lib/Transforms/Utils/CodeExtractor.cpp	(working copy)
@@ -29,6 +29,7 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include <algorithm>
 #include <set>
@@ -45,7 +46,7 @@
 namespace {
   class CodeExtractor {
     typedef std::vector<Value*> Values;
-    std::set<BasicBlock*> BlocksToExtract;
+    SetVector<BasicBlock*> BlocksToExtract;
     DominatorTree* DT;
     bool AggregateArgs;
     unsigned NumExitBlocks;
@@ -135,7 +136,7 @@
   // We only want to code extract the second block now, and it becomes the new
   // header of the region.
   BasicBlock *OldPred = Header;
-  BlocksToExtract.erase(OldPred);
+  BlocksToExtract.remove(OldPred);
   BlocksToExtract.insert(NewBB);
   Header = NewBB;
 
@@ -180,7 +181,7 @@
 }
 
 void CodeExtractor::splitReturnBlocks() {
-  for (std::set<BasicBlock*>::iterator I = BlocksToExtract.begin(),
+  for (SetVector<BasicBlock*>::iterator I = BlocksToExtract.begin(),
          E = BlocksToExtract.end(); I != E; ++I)
     if (ReturnInst *RI = dyn_cast<ReturnInst>((*I)->getTerminator()))
{
       BasicBlock *New = (*I)->splitBasicBlock(RI,
(*I)->getName()+".ret");
@@ -206,7 +207,7 @@
 //
 void CodeExtractor::findInputsOutputs(Values &inputs, Values &outputs)
{
   std::set<BasicBlock*> ExitBlocks;
-  for (std::set<BasicBlock*>::const_iterator ci =
BlocksToExtract.begin(),
+  for (SetVector<BasicBlock*>::const_iterator ci =
BlocksToExtract.begin(),
        ce = BlocksToExtract.end(); ci != ce; ++ci) {
     BasicBlock *BB = *ci;
 
@@ -482,7 +483,7 @@
   std::map<BasicBlock*, BasicBlock*> ExitBlockMap;
 
   unsigned switchVal = 0;
-  for (std::set<BasicBlock*>::const_iterator i = BlocksToExtract.begin(),
+  for (SetVector<BasicBlock*>::const_iterator i =
BlocksToExtract.begin(),
          e = BlocksToExtract.end(); i != e; ++i) {
     TerminatorInst *TI = (*i)->getTerminator();
     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
@@ -633,7 +634,7 @@
   Function::BasicBlockListType &oldBlocks =
oldFunc->getBasicBlockList();
   Function::BasicBlockListType &newBlocks =
newFunction->getBasicBlockList();
 
-  for (std::set<BasicBlock*>::const_iterator i = BlocksToExtract.begin(),
+  for (SetVector<BasicBlock*>::const_iterator i =
BlocksToExtract.begin(),
          e = BlocksToExtract.end(); i != e; ++i) {
     // Delete the basic block from the old function, and the list of blocks
     oldBlocks.remove(*i);

On Jan 8, 2010, at 5:01 PM, Julien Lerouge wrote:
> Hello,
>
> The CodeExtractor contains a std::set<BasicBlock*> to keep track of  
> the
> blocks to extract. Iterators on this set are not deterministic, and so
> the functions that are generated are not (the order of the
> inputs/outputs can change).
>
> The attached patch uses a SetVector instead. Ok to apply ?
Nice catch, please apply,

-Chris
>
> Thanks,
> Julien
>
>
> -- 
> Julien Lerouge
> PGP Key Id: 0xB1964A62
> PGP Fingerprint: 392D 4BAD DB8B CE7F 4E5F FA3C 62DB 4AA7 B196 4A62
> PGP Public Key from: keyserver.pgp.com
> <codeextractor.diff>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

On Fri, Jan 08, 2010 at 05:04:17PM -0800, Chris Lattner wrote:
> On Jan 8, 2010, at 5:01 PM, Julien Lerouge wrote:
> >Hello,
> >
> >The CodeExtractor contains a std::set<BasicBlock*> to keep track
> >of the
> >blocks to extract. Iterators on this set are not deterministic, and so
> >the functions that are generated are not (the order of the
> >inputs/outputs can change).
> >
> >The attached patch uses a SetVector instead. Ok to apply ?
> Nice catch, please apply,
> -Chris
Thanks for the quick review. There is actually more, is it ok to apply
this one as well (avoid std:vector<Value*> being sorted) ? 

Thanks,
Julien

-- 
Julien Lerouge
PGP Key Id: 0xB1964A62
PGP Fingerprint: 392D 4BAD DB8B CE7F 4E5F FA3C 62DB 4AA7 B196 4A62
PGP Public Key from: keyserver.pgp.com
-------------- next part --------------
Index: lib/Transforms/Utils/CodeExtractor.cpp
==================================================================---
lib/Transforms/Utils/CodeExtractor.cpp	(revision 93080)
+++ lib/Transforms/Utils/CodeExtractor.cpp	(working copy)
@@ -%ld,%ld +%ld,%ld @@
 
 namespace {
   class CodeExtractor {
-    typedef std::vector<Value*> Values;
+    typedef SetVector<Value*> Values;
     SetVector<BasicBlock*> BlocksToExtract;
     DominatorTree* DT;
     bool AggregateArgs;
@@ -%ld,%ld +%ld,%ld @@
       // instruction is used outside the region, it's an output.
       for (User::op_iterator O = I->op_begin(), E = I->op_end(); O != E;
++O)
         if (definedInCaller(*O))
-          inputs.push_back(*O);
+          inputs.insert(*O);
 
       // Consider uses of this instruction (outputs).
       for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
            UI != E; ++UI)
         if (!definedInRegion(*UI)) {
-          outputs.push_back(I);
+          outputs.insert(I);
           break;
         }
     } // for: insts
@@ -%ld,%ld +%ld,%ld @@
   } // for: basic blocks
 
   NumExitBlocks = ExitBlocks.size();
-
-  // Eliminate duplicates.
-  std::sort(inputs.begin(), inputs.end());
-  inputs.erase(std::unique(inputs.begin(), inputs.end()), inputs.end());
-  std::sort(outputs.begin(), outputs.end());
-  outputs.erase(std::unique(outputs.begin(), outputs.end()), outputs.end());
 }
 
 /// constructFunction - make a function based on inputs and outputs, as
follows: