PNaCl: Add support for GCC/LLVM vector extensions

lib/Transforms/NaCl/ConstantInsertExtractElementIndex.cpp

+//===- ConstantInsertExtractElementIndex.cpp - Insert/Extract element -----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Transform all InsertElement and ExtractElement with non-constant or
+// out-of-bounds indices into stack accesses. This moves all undefined
+// behavior to the stack, making InsertElement and ExtractElement
+// well-defined.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Transforms/NaCl.h"
+
+#include <algorithm>
+
+using namespace llvm;
+
+namespace {
+class ConstantInsertExtractElementIndex : public BasicBlockPass {
+public:
+  static char ID; // Pass identification, replacement for typeid
+  ConstantInsertExtractElementIndex() : BasicBlockPass(ID), M(0), TD(0) {
+    initializeConstantInsertExtractElementIndexPass(
+        *PassRegistry::getPassRegistry());
+  }
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.addRequired<DataLayout>();
+    BasicBlockPass::getAnalysisUsage(AU);
+  }
+  virtual bool doInitialization(Module &Mod) {
+    M = &Mod;
+    return false; // Unchanged.
+  }
+  virtual bool runOnBasicBlock(BasicBlock &BB);
+
+private:
+  typedef SmallVector<Instruction *, 8> Instructions;
+  const Module *M;
+  const DataLayout *TD;

[jvoung (off chromium), 2014/04/04 23:20:21]

I think TargetData was renamed to DataLayout. Some of the old variables were
left as TD.

However, this is new, so might as well call it "DL" instead of "TD". 

[JF, 2014/04/15 01:52:27]

Done, in this and other files.

+
+  /// Get the index of an InsertElement or ExtractElement instruction, or null.
+  static Value *getIdx(const Instruction *I);
+
+  void findInvalidInsertExtractElements(const BasicBlock &BB,

[jvoung (off chromium), 2014/04/04 23:20:21]

nit: It's not actually invalid so "Invalid" should probably be something like
NonConstant?

[JF, 2014/04/15 01:52:27]

Done.

+                                        Instructions &BadVectorIdx) const;
+  void fixInvalidInsertExtractElements(BasicBlock &BB,
+                                       const Instructions &BadVectorIdx) const;
+};
+}
+
+char ConstantInsertExtractElementIndex::ID = 0;
+INITIALIZE_PASS(
+    ConstantInsertExtractElementIndex, "constant-insert-extract-element-index",
+    "Force insert and extract vector elemement to always be in bounds", false,

[jvoung (off chromium), 2014/04/04 23:20:21]

elemement -> element

This doesn't really force things to always be in bounds? It just puts things on
the stack right? The stack doesn't have some canary or anything to detect the
out of bounds accesses.

An alternative would have been to mask any non-constant indices to force things
to be in bounds (the right power of 2)?

[JF, 2014/04/15 01:52:27]

Correct. I don't mind doing what you suggest instead, since it would have better
performance, but I'd rather have us agree on doing this before I go out and code
it.

I talked to Mark and he'd rather have us stay as-is for now, and maybe add the
masking on translator side to non-constant insert/extract later. He was
wondering if code actually triggers this, and what the code looks like on
x86/ARM, and what Jim's opinion is for subzero.

In a separate update I'll change the code to just wrap constant indices that are
out of bounds.

[jvoung (off chromium), 2014/04/16 00:10:27]

Sure, I'm okay with leaving this as is for now, since, yes we're not sure how
much code actually triggers non-constant insert/extract.

I had forgotten that to really trust the masking you would need to do it on the
translator side. Otherwise (if the masking was done in bitcode) the bitcode ABI
checks would not be simple. Maybe we want different semantics from masking too
(like abort) and we can decide that later...

+    false)
+
+Value *ConstantInsertExtractElementIndex::getIdx(const Instruction *I) {

[jvoung (off chromium), 2014/04/04 23:20:21]

Could have just been a static function that's not in the class namespace?

[JF, 2014/04/15 01:52:27]

Done.

+  switch (I->getOpcode()) {
+  default: return 0;

[Jim Stichnoth, 2014/04/04 23:08:17]

I don't know of a style guide reference, but could you "return NULL" instead?

[JF, 2014/04/15 01:52:27]

Done.

+  case Instruction::InsertElement: return I->getOperand(2);
+  case Instruction::ExtractElement: return I->getOperand(1);
+  }
+}
+
+void ConstantInsertExtractElementIndex::findInvalidInsertExtractElements(
+    const BasicBlock &BB, Instructions &BadVectorIdx) const {

[jvoung (off chromium), 2014/04/04 23:20:21]

nit: BadVectorIdx sounds like it's a single index, instead of a collection of
instructions (yes..  the type indicates it's instructions but not the variable
name =))

[JF, 2014/04/15 01:52:27]

Done.

+  for (BasicBlock::const_iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE;
+       ++BBI) {
+    const Instruction *I = &*BBI;
+    Value *Idx = getIdx(I);
+    if (!Idx)
+      // Not and InsertElement or ExtractElement, ignore the instruction.

[Jim Stichnoth, 2014/04/04 23:08:17]

and --> an

[JF, 2014/04/15 01:52:27]

Done.

+      continue;
+    if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
+      unsigned NumElements =
+          cast<VectorType>(I->getOperand(0)->getType())->getNumElements();
+      if (CI->getValue().ult(NumElements))
+        // Index is constant in-range for the vector type, keep as-is.
+        continue;
+    }
+    BadVectorIdx.push_back(const_cast<Instruction *>(I));

[Jim Stichnoth, 2014/04/04 23:08:17]

I trust const_cast is actually necessary :(

[JF, 2014/04/15 01:52:27]

Yeah, I wanted to go all const-correctness, but some const overloads are missing
on basic LLVM functions. Casting away const could go in a few places, but I'd
rather keep it here since it means that the function signatures actually express
my intent (one function just takes note of the edits to perform, and the other
actually does the edits). I think it expresses the high-level intent well :)

+  }
+}
+
+void ConstantInsertExtractElementIndex::fixInvalidInsertExtractElements(
+    BasicBlock &BB, const Instructions &BadVectorIdx) const {
+  for (Instructions::const_iterator IB = BadVectorIdx.begin(),
+                                    IE = BadVectorIdx.end();
+       IB != IE; ++IB) {
+    Instruction *I = *IB;
+    Value *Vec = I->getOperand(0);
+    Value *Idx = getIdx(I);
+    VectorType *VecTy = cast<VectorType>(Vec->getType());
+    Type *ElemTy = VecTy->getElementType();
+    unsigned ElemAlign = TD->getPrefTypeAlignment(ElemTy);
+    unsigned VecAlign = std::max(ElemAlign, TD->getPrefTypeAlignment(VecTy));
+
+    IRBuilder<> IRB(I);
+    AllocaInst *Alloca = IRB.CreateAlloca(
+        ElemTy, ConstantInt::get(Type::getInt32Ty(M->getContext()),

[jvoung (off chromium), 2014/04/04 23:20:21]

Instead of ElemTy, have the alloca be i8, and multiply size appropriately?

Our ABI says the allocas are supposed to be i8:
https://developers.google.com/native-client/dev/reference/pnacl-bitcode-abi#a...

[jvoung (off chromium), 2014/04/07 15:40:11]

n/m about this point -- it'll be handled by the ReplacePtrsWithInts pass...

[JF, 2014/04/15 01:52:27]

Yeah I wanted to do the "right" thing for LLVM, and let the next passes fix
things up.

+                                 VecTy->getNumElements()));
+    Alloca->setAlignment(VecAlign);
+    Value *AllocaAsVec = IRB.CreateBitCast(Alloca, VecTy->getPointerTo());
+    IRB.CreateAlignedStore(Vec, AllocaAsVec, Alloca->getAlignment());
+    Value *GEP = IRB.CreateGEP(Alloca, Idx);
+
+    Value *Res;
+    switch (I->getOpcode()) {
+    default:
+      llvm_unreachable("expected InsertElement or ExtractElement");
+    case Instruction::InsertElement: {
+      IRB.CreateAlignedStore(I->getOperand(1), GEP, ElemAlign);
+      Res = IRB.CreateAlignedLoad(AllocaAsVec, Alloca->getAlignment());
+      break;
+    }
+    case Instruction::ExtractElement: {
+      Res = IRB.CreateAlignedLoad(GEP, ElemAlign);
+      break;
+    }
+    }

[Jim Stichnoth, 2014/04/04 23:08:17]

Sorry, these two perfectly aligned braces really bother me. :)  The extra braces
are unnecessary in this switch statement; can they just be removed?

[JF, 2014/04/15 01:52:27]

Done, though if they *had* been required I'd have sent you to clang-format style
bugs ;-)

+
+    I->replaceAllUsesWith(Res);

[jvoung (off chromium), 2014/04/04 23:20:21]

CopyDebug?

[JF, 2014/04/15 01:52:27]

I was going to fix IRBuilder instead so it copies debug information properly.
I'll do that upstream though (I talked to echristo about it, he thinks it's the
right thing to do).

+    I->eraseFromParent();
+  }
+}
+
+bool ConstantInsertExtractElementIndex::runOnBasicBlock(BasicBlock &BB) {
+  bool Changed = false;
+  if (!TD)
+    TD = &getAnalysis<DataLayout>();
+  Instructions BadVectorIdx;
+  findInvalidInsertExtractElements(BB, BadVectorIdx);
+  if (!BadVectorIdx.empty()) {
+    Changed = true;
+    fixInvalidInsertExtractElements(BB, BadVectorIdx);
+  }
+  return Changed;
+}
+
+BasicBlockPass *llvm::createConstantInsertExtractElementIndexPass() {
+  return new ConstantInsertExtractElementIndex();
+}