1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
//===- llvm/Transforms/DecomposeArrayRefs.cpp - Lower array refs to 1D -----=//
//
// DecomposeArrayRefs -
// Convert multi-dimensional array references into a sequence of
// instructions (using getelementpr and cast) so that each instruction
// has at most one array offset.
//
//===---------------------------------------------------------------------===//
#include "llvm/Transforms/DecomposeArrayRefs.h"
#include "llvm/iMemory.h"
#include "llvm/iOther.h"
#include "llvm/BasicBlock.h"
#include "llvm/Method.h"
#include "llvm/Pass.h"
//
// This function repeats until we have a one-dim. reference: {
// // For an N-dim array ref, where N > 1, insert:
// aptr1 = getElementPtr [N-dim array] * lastPtr, uint firstIndex
// aptr2 = cast [N-dim-arry] * aptr to [<N-1>-dim-array] *
// }
// Then it replaces the original instruction with an equivalent one that
// uses the last aptr2 generated in the loop and a single index.
//
static BasicBlock::reverse_iterator
decomposeArrayRef(BasicBlock::reverse_iterator& BBI)
{
MemAccessInst *memI = cast<MemAccessInst>(*BBI);
BasicBlock* BB = memI->getParent();
Value* lastPtr = memI->getPointerOperand();
vector<Instruction*> newIvec;
MemAccessInst::const_op_iterator OI = memI->idx_begin();
for (MemAccessInst::const_op_iterator OE = memI->idx_end(); OI != OE; ++OI)
{
if (OI+1 == OE) // skip the last operand
break;
assert(isa<PointerType>(lastPtr->getType()));
vector<Value*> idxVec(1, *OI);
// The first index does not change the type of the pointer
// since all pointers are treated as potential arrays (i.e.,
// int *X is either a scalar X[0] or an array at X[i]).
//
const Type* nextPtrType;
// if (OI == memI->idx_begin())
// nextPtrType = lastPtr->getType();
// else
// {
const Type* nextArrayType =
MemAccessInst::getIndexedType(lastPtr->getType(), idxVec,
/*allowCompositeLeaf*/ true);
nextPtrType = PointerType::get(cast<SequentialType>(nextArrayType)
->getElementType());
// }
Instruction* gepInst = new GetElementPtrInst(lastPtr, idxVec, "aptr1");
Instruction* castInst = new CastInst(gepInst, nextPtrType, "aptr2");
lastPtr = castInst;
newIvec.push_back(gepInst);
newIvec.push_back(castInst);
}
// Now create a new instruction to replace the original one
assert(lastPtr != memI->getPointerOperand() && "the above loop did not execute?");
assert(isa<PointerType>(lastPtr->getType()));
vector<Value*> idxVec(1, *OI);
const std::string newInstName = memI->hasName()? memI->getName()
: string("oneDimRef");
Instruction* newInst = NULL;
switch(memI->getOpcode())
{
case Instruction::Load:
newInst = new LoadInst(lastPtr, idxVec /*, newInstName */); break;
case Instruction::Store:
newInst = new StoreInst(memI->getOperand(0),
lastPtr, idxVec /*, newInstName */); break;
break;
case Instruction::GetElementPtr:
newInst = new GetElementPtrInst(lastPtr, idxVec /*, newInstName */); break;
default:
assert(0 && "Unrecognized memory access instruction"); break;
}
newIvec.push_back(newInst);
// Replace all uses of the old instruction with the new
memI->replaceAllUsesWith(newInst);
// Insert the instructions created in reverse order. insert is destructive
// so we always have to use the new pointer returned by insert.
BasicBlock::iterator newI = BBI.base(); // gives ptr to instr. after memI
--newI; // step back to memI
for (int i = newIvec.size()-1; i >= 0; i--)
newI = BB->getInstList().insert(newI, newIvec[i]);
// Now delete the old instruction and return a pointer to the first new one
BB->getInstList().remove(memI);
delete memI;
BasicBlock::reverse_iterator retI(newI); // reverse ptr to instr before newI
return --retI; // reverse pointer to newI
}
//---------------------------------------------------------------------------
// Entry point for decomposing multi-dimensional array references
//---------------------------------------------------------------------------
static bool
doDecomposeArrayRefs(Method *M)
{
bool changed = false;
for (Method::iterator BI = M->begin(), BE = M->end(); BI != BE; ++BI)
for (BasicBlock::reverse_iterator newI, II=(*BI)->rbegin();
II != (*BI)->rend(); II = ++newI)
{
newI = II;
if (MemAccessInst *memI = dyn_cast<MemAccessInst>(*II))
{ // Check for a multi-dimensional array access
const PointerType* ptrType =
cast<PointerType>(memI->getPointerOperand()->getType());
if (isa<ArrayType>(ptrType->getElementType()) &&
memI->getNumOperands() > 1+ memI->getFirstIndexOperandNumber())
{
newI = decomposeArrayRef(II);
changed = true;
}
}
}
return changed;
}
namespace {
struct DecomposeArrayRefsPass : public MethodPass {
virtual bool runOnMethod(Method *M) { return doDecomposeArrayRefs(M); }
};
}
Pass *createDecomposeArrayRefsPass() { return new DecomposeArrayRefsPass(); }
|
